Le 20-nov.-07, à 17:47, David Nyman a écrit :
>
> On 20/11/2007, Bruno Marchal <marchal.domain.name.hidden> wrote:
>
>> David, are you still there? This is a key post, with respect to the
>> "Church Thesis" thread.
>
> Sorry Bruno, do forgive me - we seem destined to be out of synch at
> the moment. I'm afraid I'm too distracted this week to respond
> adequately - back on-line next week at the latest.
Take it easy. It is the main advantage of electronical conversation,
unlike the phone, we can answer at the best moment. But I appreciate
you tell me.
"See" you next week.
Bruno
PS I'm afraid I have not the time to comment the last posts today,
except for elementary question perhaps, but I will have more time soon
(probably or hopefully tomorrow).
>
> 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/
>>
>>>
>>
>
> >
>
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 Wed Nov 21 2007 - 10:56:04 PST