# function from $\mathbb{N}$ to $\mathbb{N}\times\mathbb{N}\times\mathbb{N}$

I want to prove that the size (cardinality) of $\mathbb{N}$ is the same as the size of the set of all ordered triples of natural numbers ; just to be more clear that $|\mathbb{N}|=|\mathbb{N}\times\mathbb{N}\times\mathbb{N}|$.

-
What's the group operation? –  Qiaochu Yuan Dec 26 '10 at 23:04
Do you really mean group? Or do you just mean size (cardinality) of the two sets? –  TNi Dec 26 '10 at 23:04
I mean size (cardinality) of the two sets. thank u –  Tomer Dec 26 '10 at 23:07
@Tomer: I've edited the question to try to better reflect what I think you are asking. If you disagree, feel free to re-edit or revert my edit. –  Isaac Dec 26 '10 at 23:22
(As monoids under multiplication, by the way, you actually do get an isomorphism.) –  Qiaochu Yuan Dec 26 '10 at 23:39

Here is one way: I assume $0\in{\mathbb N}$. Given a triple $(a,b,c)$, assign to it the number $2^a(2(2^b(2c+1)-1)+1)-1$. The same idea shows that ${\mathbb N}$ has the same size as ${\mathbb N}^k$ for any positive integer $k$.

(This can be easily modified and in fact gives a slightly easier formula if your convention is that the naturals begin with 1.)

There are of course many other ways. The idea I am using above is to first find a bijection between ${\mathbb N}\times{\mathbb N}$ and ${\mathbb N}$, and then use it to create the one you want. The bijection I used is $(a,b)\mapsto 2^a(2b+1)-1$. Another popular choice uses Cantor's pairing function, $\displaystyle (a,b)\mapsto \frac{(a+b)(a+b+1)}2 +b$. As a technical comment, there is actually an advantage to Cantor's choice, in that it is a polynomial, and it is easier to define (in a first-order way) in the usual structure of the natural numbers $({\mathbb N},+,\times,0,1,<)$. The choice I used requires exponentiation, and although this can also be defined in a first-order way, it is significantly less trivial.

That exponentiation is first-order definable is known since Gödel's work on the incompleteness theorem. In fact, there is a way to define any recursive function. For exponentiation, I sketch the details in this answer. The bulk of the argument for Hilbert's 10th problem is that in fact there is a polynomial definition of exponentiation, in the sense mentioned here. This is significantly more involved, and was rather surprising at the time.

-
That's a rather complicated injection of $\mathbb N^3$ into $\mathbb N$. I'm curious why you chose it rather than something simpler like, say, $(a,b,c) \mapsto 2^a 3^b 5^c$? –  Rahul Dec 27 '10 at 0:13
@Raul Narian: Andres' functions are actually bijective, whereas yours is merely injective. Using Cantor-Schroeder-Bernstein it follows that a bijective function exists, but if you try to apply the proof of that to write down an explicit bijection, you'll get something much more complicated than what Andres has given. (OTOH, if you don't care about explicit bijections, then yes, I think your argument is easier.) –  Pete L. Clark Dec 27 '10 at 1:10

Do you know a Pairing function? Do you see how this can help?

-

I will not give you an answer but a geometrical figure in proving what is equivalent to the naturals. You can think that the natural numbers is an elastic rope (infinite from one side ) and the natural numbers are marked points on this rope .If you want to prove that the integers have the same cardinality as $N^2$ you can think that $N^2$ is a lattice in $R^2$ and you have to create an 1-1 and surjective function or start passing the "natural" rope through the lattice such that every natural number fits on every vertex of the lattice .You can see then what is the function i.e. 1 goes to (0,1) 2 goes to (1,1) 3 goes to (1,0) 4 to (2,0) and you create a spiral round the (0,0).It is an 1-1 surjective function that sends n to (exercise).The same goes to 3 or n dimensions. Of course you can have different ways to use the elastic natural rope to create bijective functions (of course you must have a way to pass the rope through every vertex so usually you make a spiral in a way that grows biger and biger) but you can have an image that $N$ have the same cardinality as $N^k$ or $Z^k$ for any k.

-
If someone could give an image of what i am trying to say would be great but i do not know how to post images ,thanks –  minasteris Dec 27 '10 at 11:42