Proving Bijectivity of N=1/2((a+b)^2 + 3a + b)

[Khichdi lover]

Homework Statement

Prove that the function N = 1/2*((a + b)² + 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)² + 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 \in N there is an x \in X such that f(x) = y.

i.e all the natural numbers can be expressed by a unique 1/2*((a + b)² + 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)² + 3a + b)
then we have to find an ordered pair (a1,b1) such that
N + 1 = 1/2*((a1 + b1)² + 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.)

 

[HallsofIvy]

I assume you mean that N(a, b) is a mapping that takes a pair of natural numbers, (a, b), to a single natural number, not the other way around!

If N is a natural number, can you find unique natural numbers, a and b, such that
N= 1/2*((a + b)^2 + 3a + b)? The fact that there exist such a number would prove that this is surjective, the fact that it is unique would prove injective.

As you say, with the "natural numbers" defined as "all positive integers" the "smallest" (a, b) can be is (1, 1) and so the smallest N could be is (1/2)((2)^2+ 3+ 1)= 4, not 1. If that is what is meant by "natural numbers" this 'theorem' is simply wrong and cannot be proved.

Now, while today we typically use "natural numbers" to mean "positive integers", back when Peano developed his axioms for the natural numbers, he included 0 (in other words, his "natural numbers" were our "whole numbers"). Check to see if that is intended.

 

[Khichdi lover]

I assume you mean that N(a, b) is a mapping that takes a pair of natural numbers, (a, b), to a single natural number, not the other way around!

yes N(a,b) takes a pair of natural numbers (a,b) to a single natural number N. But why should the other way around be a problem. Since the map is injective (as the problem asks us to prove) , there would also be an inverse map N^-1 such that N^-1(N) = (a,b).
of course proving it that way would be tedious. I hope I am not wrong here.

If N is a natural number, can you find unique natural numbers, a and b, such that
N= 1/2*((a + b)^2 + 3a + b)? The fact that there exist such a number would prove that this is surjective, the fact that it is unique would prove injective.

I was having great trouble in trying to decompose N into the 'a' and 'b' from which it was obtained.
hence i tried to show that all natural numbers from 1 onwards are covered. For this I was trying to use mathematical induction.

As you say, with the "natural numbers" defined as "all positive integers" the "smallest" (a, b) can be is (1, 1) and so the smallest N could be is (1/2)((2)^2+ 3+ 1)= 4, not 1. If that is what is meant by "natural numbers" this 'theorem' is simply wrong and cannot be proved.

Now, while today we typically use "natural numbers" to mean "positive integers", back when Peano developed his axioms for the natural numbers, he included 0 (in other words, his "natural numbers" were our "whole numbers"). Check to see if that is intended.

The problem statement says "natural numbers" , but I am also inclined to think that it includes 0 , else smallest N(a,b) would be 4.
I am currently practising analysis from Rudin PoMa. I am at the topic of enumerable sets etc. But I recalled having read this problem from Roger Penrose's Road to Reality a few years back. Since it was pertinent to what I was studying I tried it. Penrose poses this exercise (16.8) in the section where set of rationals is shown to be countable. So perhaps we should include (0,0) and (0,1) , etc.(and also (1,0) , (2,0) ...and so on, as these give us N = 2 , N= 5 etc)If this is the case is my approach okay in trying to show that all natural numbers from 1 onwards are covered by using mathematical induction.

Cause I am simply unable to decompose N into the (a,b) from which it was got.