Question

Let $g: N \to N$ be defined as $g(3n+1) = 3n+2, g(3n+2) = 3n+3, g(3n+3) = 3n+1$, for all $n \ge 0$. Then which of the following statements is true ?

• A. $g \circ g \circ g = g$
• B. There exists a one-one function $f: N \to N$ such that $f \circ g = f$.
• C. There exists an onto function $f: N \to N$ such that $f \circ g = f$.
• D. There exists a function $f: N \to N$ such that $g \circ f = f$.

Hint:

If a function \(g\) moves every element (no fixed points), then \(g(y) = y\) is impossible. Consequently, \(g \circ f = f\) is impossible.

Answer 1

The Correct Option is C

Step 1: Understanding the Concept:
The function \(g\) partitions the set of natural numbers \(\mathbb{N}\) into cycles of length 3:
\(\{3n+1, 3n+2, 3n+3\} \rightarrow \{3n+2, 3n+3, 3n+1\}\).
This means \(g(g(g(x))) = x\) for all \(x\).
Step 3: Detailed Explanation:
1. Analysis of $g$:
Since \(g(g(g(x))) = x\), then \(g \circ g \circ g\) is the identity function \(I\). Statement (A) is false.
2. Analysis of $f \circ g = f$:
This equation implies \(f(g(x)) = f(x)\).
This means \(f\) must take the same value for all elements in a cycle: \(f(3n+1) = f(3n+2) = f(3n+3) = c_n\).
If \(f\) takes the same value for different inputs, it cannot be one-one. Statement (B) is false.
3. Analysis of onto function:
Let \(f(x) = \lceil x/3 \rceil\).
Then \(f(3n+1) = f(3n+2) = f(3n+3) = n+1\).
Since \(n\) can be any non-negative integer, the range of \(f\) is \(\{1, 2, 3, .......\}\), which is \(\mathbb{N}\). Thus \(f\) is onto. Statement (C) is true.
4. Analysis of $g \circ f = f$:
This implies \(f(x)\) is a fixed point of \(g\). But according to the definition of \(g\), \(g(k) \neq k\) for any \(k\). So no such \(f\) exists. Statement (D) is false.
Step 4: Final Answer:
Statement (C) is true.