Hi, David, are you still there? This is a key post, with respect to the "Church Thesis" thread.

## Advertising

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