Le 03-déc.-07, à 16:56, David Nyman a écrit :
>
> 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.
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.domain.name.hidden/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 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 Dec 04 2007 - 09:10:50 PST