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.

## Advertising

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