On Nov 20, 4:40 pm, Bruno Marchal <marc....domain.name.hidden> 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.
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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Mon Dec 03 2007 - 10:56:55 PST