Consider the function h : N x N -> N so that h(a, b) = (2a + 1) * 2^b - 1, where N = {0, 1, 2, 3, ...} is the set of natural numbers. a. Prove that the function h is an injection (one-one). b. Prove that it is also a Surjection (onto).

GATE 2001 · Discrete Mathematics · Functions · medium

Answer: h is a bijection from N x N onto N (both injective and surjective).

1. Prove injection: h(a1, b1) = h(a2, b2) => (a1, b1) = (a2, b2): If h(a1,b1) = h(a2,b2), then (2a1+1)*2^b1 = (2a2+1)*2^b2. Both (2a1+1) and (2a2+1) are odd. By unique factorization, the power of 2 in each side must be equal, so 2^b1 = 2^b2, giving b1 = b2. Cancelling 2^b1, we get 2a1+1 = 2a2+1, so a1 = a2. Therefore h is injective.
2. Prove surjection: every n in N has a preimage: Let n be any natural number. Then n+1 >= 1 is a positive integer. By the fundamental theorem of arithmetic, n+1 = 2^b * m where b >= 0 and m is a positive odd integer. Write m = 2a+1 where a = (m-1)/2 >= 0 is a natural number (since m is odd and >= 1). Then h(a, b) = (2a+1)*2^b - 1 = m*2^b - 1 = (n+1) - 1 = n. So every n has a preimage (a, b) in N x N.