Consider the function f : N -> N (N is the set of natural numbers) so that f(n) = (2n - 1) if n is odd and f(n) = 2n if n is even. a. Prove that the function f is an injection (one-one). b. Prove that it is also a surjection (onto).

GATE 2001 · Discrete Mathematics · Functions · medium

Answer: f is injective (equal outputs imply equal inputs by parity analysis) and surjective (every natural number k has a preimage: (k+1)/2 if k is odd, k/2 if k is even), hence f is a bijection.

1. Prove injection: Case 1 (both odd): f(a)=2a-1=2b-1=f(b) => a=b. Case 2 (both even): f(a)=2a=2b=f(b) => a=b. Case 3 (a odd, b even): f(a)=2a-1 is odd, f(b)=2b is even; odd != even so f(a) != f(b). In all cases f(a)=f(b) implies a=b, so f is injective.
2. Prove surjection: If k is odd: let n = (k+1)/2; since k is odd, k+1 is even, so n is a natural number. Also n is odd iff (k+1)/2 is odd. Check: f(n)=2n-1 = k+1-1 = k. If k is even: let n = k/2; n is a natural number. f(n)=2n=k. Thus every k in N has a preimage, so f is surjective.