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.
CANTOR'S FIRST RESULT
There is NO bijection between N and N^N (N^N is the set of functions
from N to N. N = (0, 1, 2, ...}
Proof
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, ...
etc.
OK?
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
like:
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.
OK?
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
machine'.
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
infinities.
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?
OK?
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.
Best,
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
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
everything-list+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
