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 Tue Nov 20 2007 - 11:40:54 PST