Last post before the key post (was OM = SIGMA_1) 1

```
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

>
> 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/

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