Consider mapping N→N, where is the set of natural numbers
Consider a mapping f: N→N, where N is the set of natural numbers is defined as:
For n ∈ N, which of the following is true
- A.
Surjective but not Bijective
- B.
Injective but not Surjective
- C.
Neither Injective nor Surjective
- D.
Both Injective and Surjective
Attempted by 163 students.
Show answer & explanation
Correct answer: C
Recall the definition: for odd n, f(n) = n^2; for even n, f(n) = 2n + 1.
Not injective:
Example: f(3) = 3^2 = 9 and f(4) = 2·4 + 1 = 9, so two different inputs map to the same output.
Not surjective:
If n is odd, write n = 2k+1. Then n^2 = (2k+1)^2 = 4k(k+1)+1, so n^2 ≡ 1 (mod 4).
If n is even, write n = 2k. Then 2n+1 = 4k+1, so 2n+1 ≡ 1 (mod 4).
Therefore every value of f(n) is congruent to 1 modulo 4, so numbers not congruent to 1 modulo 4 (for example 2, 3, 4, 6, etc.) are never attained. Hence the function is not surjective.
Conclusion: The function is neither injective nor surjective.