Le 20-nov.-07, à 17:47, David Nyman a écrit :

## Advertising

> > On 20/11/2007, Bruno Marchal <[EMAIL PROTECTED]> wrote: > >> David, are you still there? This is a key post, with respect to the >> "Church Thesis" thread. > > Sorry Bruno, do forgive me - we seem destined to be out of synch at > the moment. I'm afraid I'm too distracted this week to respond > adequately - back on-line next week at the latest. Take it easy. It is the main advantage of electronical conversation, unlike the phone, we can answer at the best moment. But I appreciate you tell me. "See" you next week. Bruno PS I'm afraid I have not the time to comment the last posts today, except for elementary question perhaps, but I will have more time soon (probably or hopefully tomorrow). > > David > >> Hi, >> >> David, are you still there? This is a key post, with respect to the >> "Church Thesis" thread. >> >> So let us see that indeed there is no bijection between N and 2^N = >> 2X2X2X2X2X2X... = {0,1}X{0,1}X{0,1}X{0,1}X... = the set of infinite >> binary sequences. >> >> Suppose that there is a bijection between N and the set of infinite >> binary sequences. Well, it will look like that, where again "----" >> represents the "ropes": >> >> 0 -------------- (1, 0, 0, 1, 1, 1, 0 ... >> 1 -------------- (0, 0, 0, 1, 1, 0, 1 ... >> 2 --------------- (0, 1, 0, 1, 0, 1, 1, ... >> 3 --------------- (1, 1, 1, 1, 1, 1, 1, ... >> 4 --------------- (0, 0, 1, 0, 0, 1, 1, ... >> 5 ----------------(0, 0, 0, 1, 1, 0, 1, ... >> ... >> >> My "sheep" are the natural numbers, and my neighbor's sheep are the >> infinite binary sequences (the function from N to 2, the elements of >> the infinite cartesian product 2X2X2X2X2X2X... ). >> My flock of sheep is the *set* of natural numbers, and my neighbor's >> flock of sheep is the *set* of all infinite binary sequences. >> >> Now, if this: >> >> 0 -------------- (1, 0, 0, 1, 1, 1, 0 ... >> 1 -------------- (0, 0, 0, 1, 1, 0, 1 ... >> 2 --------------- (0, 1, 0, 1, 0, 1, 1, ... >> 3 --------------- (1, 1, 1, 1, 1, 1, 1, ... >> 4 --------------- (0, 0, 1, 0, 0, 1, 1, ... >> 5 ----------------(0, 0, 0, 1, 1, 0, 1, ... >> ... >> >> is really a bijection, it means that all the numbers 1 and 0 appearing >> on the right are well determined (perhaps in Platonia, or in God's >> mind, ...). >> >> But then the diagonal sequence, going from the left up to right down, >> and build from the list of binary sequences above: >> >> 1 0 0 1 0 0 ... >> >> is also completely well determined (in Platonia or in the mind of a >> God). >> >> But then the complementary sequence (with the 0 and 1 permuted) is >> also >> well defined, in Platonia or in the mind of God(s) >> >> 0 1 1 0 1 1 ... >> >> But this infinite sequence cannot be in the list, above. The "God" in >> question has to ackonwledge that. >> The complementary sequence is clearly different >> -from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at >> the first (better the 0th) entry. >> -from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at >> the second (better the 1th) entry. >> -from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at >> the third (better the 2th) entry. >> and so one. >> So, we see that as far as we consider the bijection above well >> determined (by God, for example), then we can say to that God that the >> bijection misses one of the neighbor sheep, indeed the "sheep" >> constituted by the infinite binary sequence complementary to the >> diagonal sequence cannot be in the list, and that sequence is also >> well >> determined (given that the whole table is). >> >> But this means that this bijection fails. Now the reasoning did not >> depend at all on the choice of any particular bijection-candidate. >> Any >> conceivable bijection will lead to a well determined infinite table of >> binary numbers. And this will determine the diagonal sequence and then >> the complementary diagonal sequence, and this one cannot be in the >> list, because it contradicts all sequences in the list when they cross >> the diagonal (do the drawing on paper). >> >> Conclusion: 2^N, the set of infinite binary sequences, is not >> enumerable. >> >> All right? >> >> Next I will do again that proof, but with notations instead of >> drawing, and I will show more explicitly how the contradiction arise. >> >> >> Exercice-training: show similarly that N^N, the set of functions from >> N >> to N, is not enumerable. >> >> Bruno >> >> 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 http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---