Le 03-déc.-07, à 16:56, David Nyman a écrit :
> > On Nov 20, 4:40 pm, Bruno Marchal <[EMAIL PROTECTED]> wrote: > >> Conclusion: 2^N, the set of infinite binary sequences, is not >> enumerable. >> >> All right? > > OK. I have to try to catch up now, because I've had to be away longer > than I expected, but I'm clear on this diagonal argument. OK. I hope you have done the exercise below, which consists to show that N^N is also not enumerable. It is the same reasoning, of course. (Of course it is also a consequence of the non enumerability of 2^N, because 2^N is included in N^N, but in the exercise I was asking for a direct diagonal argument). You can look at the solution: http://www.mail-archive.com/everything-list@eskimo.com/msg14063.html I will send the "key post" asap. It is written, but I am currently hesitating to add more explanations, but sometimes when I do that, I introduce just more confusion. I guess I will send some part so that you have something to think about (of 'course I don't doubt you have many things to think about ...). Bruno =================================================================== >> 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 -~----------~----~----~----~------~----~------~--~---