Hi,
I will introduce notation for functions, and prove again Cantor
theorem, without making any diagram.
I will lazily write the diagram
>
> 00 =====> 34, 6, 678, 0, 6, 77, 8, 9, 39, 67009, ...
> 01 =====> 0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ...
> 02 =====> 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
> 03 =====> 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
> 04 =====> 1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ...
> 05 =====> 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ...
> ...
in the following way
0 =====> f_0
1 =====> f_1
2 =====> f_2
3 =====> f_3
4 =====> f_4
5 =====> f_5
....
Here the label "f_1" plays the role of a name for the function {(0,
34), (1, 6), (2, 678), (3, 0), ...}. Indeed it plays the role of the
name of the function which is the image by the bijection, which we
were supposing the existence.
To say that f_1 send 0 to 34, or 1 to 6, ... is usually written by
either
f_0: 0 --> 34, f_0 : 1 --> 6, ...
or by f_0(0) = 34, f_0(1) = 6, ...
More generally if f is a name for a function, to say that (x, y)
belongs to f, we write very often f(x) = y, or y = f(x).
For example we say that factorial(5) = 120.
Now, because I am even more lazy, instead of writing
> 0 =====> f_0
> 1 =====> f_1
> 2 =====> f_2
> 3 =====> f_3
> 4 =====> f_4
> 5 =====> f_5
> ....
I will write:
i =====> f_i
which is much shorter. I could even write just f_i. the index i is
supposed to vary from 0 to infinity (excluded). I mean that i belongs
to {0, 1, 2, ...}, or just that it is natural number.
So with that notation, I could begin the proof by saying this: Let us
assume that there is a bijection B: i ==> f_i between N and N^N. OK?
This is the "absurd hypothesis", that is the one we want to show
leading to a contradiction. I call that bijection B to fix the idea.
Now the proof continues. Let us consider the function from N to N
which is defined by g(n) = f_n(n) + 1.
Do you recognize g? if n varies from 0 to infinity, with the f_i given
by the diagram above, f_n(n) describes the diagonal
34 677 4, 2, 6, 0, ...
And f_n(n) + 1, which is g(n), describes
35 678, 5, 3, 7, 1, ...
It is the function which is supposed not be in the range of the
supposed bijection.
Not only this can satisfy my lazy mood, but more importantly, it is
easier to show now more clearly the contradiction.
Indeed, suppose that g is in the range of the bijection. This means
there is some number k which is send on g by the bijection. This means
that there is some k such that g is equal to f_k. OK?
But if g = f_k, it follows that g(n) = f_k(n) for any n. Right? But
then if g is applied to k, its own image under the bijection, we have
that g(k) = f_k(k).
But by definition of g, g(n) = f_n(n) + 1. So g(k) = f_k(k) + 1.
It follows that f_k(k) = f_(k) + 1. OK? This follows by the Leibniz
rule (two quantities equal to a third one are equal with each other),
applied on the two preceding line.
Now, each f_i is a function from N to N, so each f_i(n) are well
defined number (if the bijection exists), so we can substract f_(k) on
both side of the equality f_k(k) = f_(k) + 1, so we get 0 = 1.
Contradiction. Such a bijection cannot exist.
Again, this makes N^N non enumerable. If you consider an enumeration
(bijection from N to a set) f_i, it will means its corresponding
diagonal g function.
OK? Take your time to compare with the last post, and to understand
what happens.
Training exercise: prove, using that notation, that 2^N is non
enumerable. Hint: use a slightly different g.
Bruno
-----------------
On 14 Sep 2009, at 16:40, Bruno Marchal wrote:
>
> 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, ...
<snip>
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.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Tue Sep 15 2009 - 16:30:50 PDT