Le 27-nov.-07, à 17:27, Günther Greindl a écrit :

> Dear Bruno,
> thanks for your posts! I like them very much!
> Looking forward to further stuff,

Thanks for telling.

In this post I recall Cantor's proof of the non enumerability of the 
set of infinite binary sequences. First with a drawing, and then with 
mathematical notation. The goal is to train you with the notations. 
Then I do the same with the almost exactly identical proof that the set 
of functions from N to N is also non enumerable.

I hope you have no more problem with the identification of the set of 
functions from N to 2 (where 2 = {0, 1}), with the set of infinite 
binary sequences. Please ask in case of any trouble with that. A 
function from N to any set A always gives rise to an infinite sequence 
of elements of A.

Note that I will never use Cantor's result. I explain it just to 
illustrate the use of diagonalization, and to contrast it with the use 
in the next post which will illustrate a capital feature of all 
universal machine.


1) 2^N is not enumerable (proof by drawing)

Cantor argument goes like this. It is a reductio ad absurdo:

Suppose that the set of infinite binary sequence is enumerable.
That means that there is a bijection between N and that set. Such
a bijection will have a shape like:

0    --------     000101101111010100111...
1    --------     011111111010100110000...
2    --------    100011001001000100110...
3    --------    101010101001010100100...
4    --------    100000000001001111010...
5    --------    000111111111100000010...

But then I can find an infinite binary sequence which *cannot* be in 
the image of that "bijection". Indeed here is one:

1 0 1 1 1 0 ...

It is the complementary sequence build from the diagonal sequence.  QED.


1bis) 2^N is not enumerable (proof without drawing).

Suppose that the set of binary infinite sequences is enumerable.
That means there is a bijection between N and that set. It means that 
for each natural number i, there is a corresponding sequence s_i, and 
that all infinite binary sequences belongs somewhere in the enumeration

s_0  s_1 s_2 s_3 s_4 s_5 ...

Each s_i is a function from N to 2. For example, if s_0 denote the 
first sequence in the "drawing" above, it means that s_0(0) = 0, s_0(1) 
= 0, s_0(2) = 0, s_0(3) = 1, s_0(4) = 0, s_0(5) = 1, s_0(6) =1, etc. 
That is, s_i(j) the jth number (0 or 1) in the sequence s_i.
s_i(j) gives the matrix drawn above, for i and j natural numbers.

Then the number s_i(i), for i natural numbers gives the diagonal 
sequence, and the sequence 1- s_i(i) gives the complementary of the 
diagonal, and that sequence cannot belongs to the list of the s_i.

We can make explicit the contradiction. If the sequence 1- s_i(i) was 
in the list s_i, there would exist a number k such that s_k(x) = 1 - 
s_x(x). But then for x = k, s_k(k) = 1 - s_k(k). But s_k(k) has to be 
one or zero, and in the first case you get 1 = 1 - 1 = 0, and in the 
other case you get 0 = 1 - 0 = 1. Contradiction.

Damn... I must already go. I suggest you work by yourself the very 
similar proof that N^N is not enumerable. Of course you can derive this 
immediately from what we have just seen, given that a function from N 
to 2, is a particular case of a function from N to N. But it is a good 
training in *diagonalisation* to find the direct proof.

I hope you can see that the set of all functions from N to N can be 
identify with the set NXNXNX... of sequences of natural numbers.

I do quickly the "drawing proof", and let you write the more explicit 
proof (without drawing).

Suppose there is such a bijection. It will look like:

0 -------- 23   456   76    67 ...
1 --------  0    8         23    5   ...
2 -------- 67   10     10    123 ...
3 --------  9    0        0      4   ...

But then the sequence of numbers:

   24   9  11   5 ....

cannot be in that list. All right?

See you tomorrow,


> Bruno Marchal wrote:
>> Hi Mirek, Brent, Barry, David, ... and all those who could be 
>> interested
>> in the INTRO to Church thesis,
>> I have to go, actually. Just to prepare yourself to what will follow,
>> below are recent links in the list . It could be helpful to revise a
>> bit, or to ask last questions.
>> I will ASAP come back on Cantor's Diagonal, (one more post), and then 
>> I
>> will send the key fundamental post where I will present a version of
>> Church thesis, and explain how from just CT you can already derive 
>> what
>> I will call the first fundamental theorem. This one says that ALL
>> universal machine (if that exists) are insecure.
>> It is needed to explain why Lobian machine, which are mainly just
>> Universal machine knowing that they are universal, cannot not be above
>> all "theological" machine. As you can guess, knowing that they are
>> universal, will make them know that they are insecure.
>> All the term here will be defined precisely. In case you find this
>> theorem depressing, I suggest you read "The Wisdom of Insecurity" by
>> Alan Watts (Pantheon Books, Inc. 1951). An amazingly "lobian" informal
>> philosophical text.
>> Here are the last posts I send:
>> 1) Bijections 1
>> http://www.mail-archive.com/everything-lis...m/msg13962.html
>> 2) Bijections 2
>> http://www.mail-archive.com/everything-lis...m/msg13986.html
>> 3) Bijection 3
>> http://www.mail-archive.com/everything-lis...m/msg13991.html
>> 4) Cantor's diagonal
>> http://www.mail-archive.com/everything-lis...m/msg13996.html
>> Don't hesitate to ask any question if something remains unclear,
>> Bruno
>> PS:
>> I recall the combinators thread, which could help later (but please
>> don't consult them now, unless you already love lambda calculus or the
>> combinators).
>> The old (2005) combinators posts:
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05920.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05949.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05953.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05954.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05955.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05956.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05957.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05958.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05959.html
>> http://www.mail-archive.com/everything-list@eskimo.com/msg05961.html
>> 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 [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 

Reply via email to