- #1
Khichdi lover
- 5
- 0
Homework Statement
Prove that the function N = 1/2*((a + b)2 + 3a + b) is an bijective map from the set of natural numbers to the set of pairs of natural numbers (a,b).
Homework Equations
N = 1/2*((a + b)2 + 3a + b)
The Attempt at a Solution
I tried to prove the other way around that this function is an bijective map from the set of pairs of natural numbers (a,b) to set of natural numbers.
Let us say the map is f:X-->N . where X is set of pairs of natural numbers.
(i) to show that the map is surjective :-
We will have to show that for any y [itex]\in[/itex] N there is an x [itex]\in[/itex] X such that f(x) = y.
i.e all the natural numbers can be expressed by a unique 1/2*((a + b)2 + 3a + b) .
I tried to prove this by showing this as a property of set of natural numbers by mathematical induction.
I faced a problem here as the natural number 1 can be obtained as f((0,1)) , and (0,1) doesn't belong to set of pairs of natural numbers.
Further in second part of proof by induction,
Let us say there exists an (a,b) such that N = 1/2*((a + b)2 + 3a + b)
then we have to find an ordered pair (a1,b1) such that
N + 1 = 1/2*((a1 + b1)2 + 3a1 + b1).
This also I was unable to prove.
(ii) to show that the map is injective.
we have to show that if x1≠ x2 then f(x1)≠ f(x2).
I could show this only for cases such as when x1 = (a,b1) ,x2 = (a,b2).
I couldn't prove it for the more general case.
(The map is bijective can be seen by arranging the ordered pairs in a matrix form . Just as we do when we prove that the rationals are countable. But I thought that wouldn't be a proper proof. Just a visualisation aid.)