Question

Let f,g : ℕ → ℕ such that f(n+1) = f(n) + f(1) ∀ n ∈ ℕ and g be any arbitrary function. Which of the following statements is NOT true?

• A. If f is onto, then f(n) = n ∀ n ∈ ℕ
• B. f is one-one
• C. If g is onto, then fog is one-one
• D. If fog is one-one, then g is one-one

Hint:

A linear functional equation $f(x+y) = f(x) + f(y)$ over natural numbers always leads to $f(n) = c \cdot n$.

Answer 1

The Correct Option is C

Step 1: Given $f(n+1) = f(n) + f(1)$. By induction, $f(n) = n \cdot f(1)$. Let $f(1) = k$. So $f(n) = kn$.
Step 2: $f(n) = kn$ is always one-one for $k \in \mathbb{N}$. Thus (B) is true.
Step 3: If $f$ is onto, its range must be $\mathbb{N}$. Since the range is $\{k, 2k, 3k, .......\}$, this is only possible if $k=1$. So $f(n)=n$. Thus (A) is true.
Step 4: For (D), if $f(g(n_1)) = f(g(n_2))$, since $f$ is one-one, $g(n_1) = g(n_2)$. If $f \circ g$ is one-one, then $n_1 = n_2$, so $g$ is one-one. Thus (D) is true.
Step 5: For (C), if $g$ is onto, it doesn't have to be one-one. If $g$ is not one-one, $f \circ g$ cannot be one-one. Therefore, (C) is NOT true.