On 09 Sep 2009, at 09:21, Bruno Marchal wrote:

> Next post: Cantor theorem(s). There is NO bijection between N and  
> N^N. I will perhaps show that there is no bijection between N and  
> {0, 1}^N. The proof can easily be adapted to show that there is no  
> bijection between N and many sets.
> After Cantor theorem, we will be able to tackle Kleene theorem and  
> the 'mathematical discovery of the mathematical universal machine',  
> needed to grasp the mathematical notion of computation,  
> implementation, etc.


There is NO bijection between N and N^N  (N^N is the set of functions  
from N to N. N = (0, 1, 2,  ...}


1) preliminaries

Like for the irrationality of the square root of 2, we will proceed by  
a reduction to an absurdity.

First note that there are many obvious injection (= one-one function)  
from N to N^N. For example the function which sends the number n on  
the constant function from N to N which send all numbers to n:

0 ======>  {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0) ....}
1 ======>  {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1) ....}
2  ======> {(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2) ....}
3 ...

Such correspondence is one-one: two different numbers are send to two  
different functions from N to N. OK?

With Cantor, inspired by what happens in the case of finite sets,  I  
will say that the cardinal of A is little or equal (≤) than the  
cardinal of B, when A and B are infinite sets, when there is a one-one  
function, also called injection, from A to B.

The injection described in the diagram above shows that the cardinal  
of N is little or equal than the cardinal of N^N.

  I will say that the cardinal of A is equal to the cardinal of B when  
there is a bijection between the two sets.

I will also use the canonical bijection between the set of functions  
from N to N  and the set of infinite sequences of numbers, to write  
any function from N to N, as a sequence of numbers. This will make the  
things more readable.

The diagram above becomes:

0 ======> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
1 ======> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
2 ======> 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...


We can do that because we have all in mind the canonical order of the  
natural numbers: 0, 1, 2, 3, .... so that the sequence of numbers can  
be seen a short way to describe a function from N to N.

2) the proof

Let us do the Cantor's reduction to the absurd.

Suppose there is a bijection from N to N^N.  It will have some shape  

0 =====> 34,  6,  678,  0,  6, 77,  8,  9, 39,  67009, ...
1 =====>   0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ...
2 =====>   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
3 =====>   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
4 =====>  1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ...
5 =====>  0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ...

May be you recognize some functions in the correspondence. The first  
two functions seems arbitrary. The third one seems to be the power of  
two, the fourth one is the constant function sending all numbers on 2,  
the fifth one seems to be the factorial functions, the sixth one seems  
to be an arbitrary function from N to {0, 1}.  From such finite set of  
data we can never be sure, given that the "..." could in this context  
mean practically anything.

BUT, if there is a bijection between N and N^N, the correspondence is  
well defined, at least in Platonia, or in the mind of God. This means  
that each line must be thought as representing *some*, perhaps  
unknown, precise function. In particular, all numbers, including the  
double infinity of numbers that we have not represented, are well  
defined, perhaps unknown by us, numbers.

But then, Cantor reasons, if the whole diagram above makes some sense,  
it is easy to conceive a NEW function, which can be shown not  
belonging to the diagram. That is there will be a function from N to N  
which is not represented at any line of the above diagram.
Indeed the following sequence will play that role:

35,  678, 5, 3, 7, 1, ...

Do you see where it comes from? It comes from the diagonal elements,  
from up-left to down-right, with one added to them:

34+1, 677+1, 4+1, 2+1, 6+1, 0+1, ...

Why does such sequence not belong to the diagram? Because it differs  
from the first sequence for the first output. Indeed the first output  
at the first line is 34, and the new function outputs 35. It differs  
from the second sequence at the second outputs. Indeed the second  
output of the second sequence is 677, and the second output of the new  
sequence is 678, etc. So, by construction, the new function differs  
from all the sequence in the list above. We proceed diagonally to be  
sure that by changing a function, we don't come back on some  
distinction already introduced.

All the function being well defined, in Platonia, or in God's eyes (or  
in the eye of some omniscient being), automatically the new sequence  
is well defined too, and cannot belong to the sequence. Thus we get a  
contradiction. If the correspondence above is a bijection, then if  
fails as being a bijection.

This reasoning did not depend on the choice of the supposed bijection.  
All possible bijections will fail, because for each one, their very  
existence makes them failed to be a bijection, because again their  
very existence entails the existence of the "diagonal sequence", which  
by construction differs from each line of the correspondence. Indeed,  
you should see that they differ at the intersection of the diagonal  
and the line.  End of the proof.


3) Miscellaneous remarks, vocabulary.

When Cantor discovered this, he was in shock. He said the famous  
sentence: "I see it, but I don't believe it". His technic is know as  
the diagonalization (with a "z" or a "s" according to americans or  
english respective common uses).

Is that proof 100% convincing?

I let you judge by yourself. If you say yes, it means you could be  
realist on the notion of set. Torgny Tholerus has already send to the  
list, some month ago, an argument which can throw some doubt about  
such a reasoning. But I want to avoid such premature discussion. Why?

Because I don't want you to redo the whole big set of discoveries, and  
mathematical constructions which have been inspired by Cantor's proof,  
and focus instead on what will become the 'discovery of the universal  

I let you know that this proof, that is Cantor's reasoning showing  
that there is no bijection between N and N^N, *can* be done without  
change in the context of formal axiomatic set theory (like Zermelo  
Fraenkel set theory). Such impossibility theorem is thus well accepted  
by classical mathematicians. Now, the discovery of the universal  
machine will come from a very similar reasoning, in a different  
context, and Torgny Tholerus' remark, for those who remembers it,  
cannot be applied, even without formal set theory.

The biggest objection here would be that Cantor's proof invoke the  
name of God. Cantor will take that objection very seriously and he  
will literally ask the advice of the pope (!) to proceed. The  
formalization of set theory can hide a little bit that invocation, but  
eventually our diagonalization in the comp frame, will not invoke God  
or any omniscient being. We will of course come back on this.

Accepting Cantor's proof, we know that the cardinal of N^N is bigger  
than the cardinal of N. So there are infinities 'bigger' than other  

Definition: we will say that a set S is enumerable if S is finite or  
if there is a bijection between S and N. We will say that an  
*infinite* set S is non enumerable if there is NO bijection between S  
and N. We can sum up Cantor's result by:

    N^N is non enumerable.

Exercise (using 2 for the set {0, 1})
1) Does this prove that 2^N is not enumerable?
2) In case you answer "no" to the first question, can you prove that  
2^N is not enumerable?


I let you think and ask question if necessary.

Next post: I will do again that very proof, but in a way which is  
somehow clearer, by using better notations (yet a bit more abstract,  
so that it is clearer only for those who are not afraid by math  
notations). I don't want to mix the two difficulties (new concept/new  
notations), in a first approach. In some sequel, I will give you the  
proof of what is known as Cantor's theorem: that the cardinal of a  
powerset 2^A is always bigger than the cardinal of the set A. But this  
is not needed for our computationalist purpose, so I will not insist  
on that. From this we get a ladder of bigger and bigger infinities.

A last remark for Mirek, and those who remember what I said about the  
ordinals (which I have illustrated with the growing functions, some  
years ago). Mirek, to ensure that cardinals are ordinals, I would need  
the axiom of choice. But I will never use that, some I will not try to  
put the cardinals among the ordinals.




You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to