function from N\mathbb{N} to N×N×N\mathbb{N}\times\mathbb{N}\times\mathbb{N}

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


Here is one way: I assume 0N. Given a triple (a,b,c), assign to it the number 2a(2(2b(2c+1)1)+1)1. The same idea shows that N has the same size as Nk 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 N×N and N, and then use it to create the one you want. The bijection I used is (a,b)2a(2b+1)1. Another popular choice uses Cantor’s pairing function, (a,b)(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 (N,+,×,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.

Source : Link , Question Author : Community , Answer Author : Community

Leave a Comment