Le 16-nov.-07, à 18:41, meekerdb (Brent Meeker) a écrit :

>
> Bruno Marchal wrote:
>> ...
>> If not, let us just say that your ultrafinitist hypothesis is too
>> strong to make it coherent with the computationalist hypo. It means
>> that you have a theory which is just different from what I propose.
>> And then I will ask you to be "ultra-patient", for I prefer to
>> continue my explanation, and to come back on the discussion on
>> hypotheses after. OK.
>>
>> Actually, my conversation with Tom was interrupted by Norman who fears
>> people leaving the list when matter get too much technical;
> Pay no attention to Norman. :-)
>
> I attend to this list because I learn things from it and I learn a lot
> from your technical presentations.  I'm also doubtful of infinities,  
> but
> they make things simpler; so my attitude is, let's see where the theory
> takes us.



Fair enough, thanks.

I give the solution of the little exercises on the notion of bijection.

1) is there a bijection between N and N?

Of course! The identity function is a bijection from N to N, and  
actually any identity function defined on any set is a bijection from  
that set with itself. Here is a drawing of a bijection from N to N (I  
don't represent the "ropes" ...)

0  1  2  3  4  5  6  7  8  ...
0  1  2  3  4  5  6  7  8 ...

So all sets "have the same number of element" than itself.


2) Q is the set of rational numbers, that is length of segment which
can be measured by the ratio of natural numbers (or integers).

There is a bijection between N and Q.   We have already seen a  
bijection between N and ZXZ, which I called the spiraller (I put only  
the image of the bijection, imagine the rope 0----(0,0),   1-----(0,1),  
   2-----(-1,1), ... :

(0,0) (0,1) (-1,1) (-1,0) (-1,-1) (0,-1) (1,-1) (1,0) (1,1) (1,2) (0,2)  
(-1,2) (-2,2) (-2,-1) ....

We can transform that bijection between N and ZXZ into a bijection  
between N and Q in the following way. We start from the bijection above  
between N and ZXZ, but we interpret (x,y) as the fraction x/y, throwing  
it out in case we already met the corresponding rational number, or  
when we met an indeterminate fraction (like 0/0) or spurious one (like  
1/0, 2/0, ...), this gives first

0/0  0/1  -1/1  -1/0   -1/-1 0/-1  1/-1  1/0  1/1  1/2  0/2   -1/2    
-2/2  -2/1 ...., and after the throwing out of the repeated rationals:

0   -1   1   1/2   -1/2   -2 ...

OK?


3) We have seen a bijection between N and NXN. We can use it to provide  
a bijection between N and NX(NXN). Indeed, you can zigzag on NX(NXN)  
like  we have zigzag on NXN, starting from:

...
5
4
3
2
1
0
    (0,0) (0,1) (1,0) (2,0) (1,1) (0,2) (0,3) (1,2) (2,1) (3,0) (4,0)  
(3,1) ...

All right?

Obviously there is a bijection between NXNXN and NX(NXN)); just send  
(x,y,z) on (x,(y,z)).

In the same manner, you can show the existence of a bijection and any  
of NXNXNXN, NXNXNXNXN, NXNXNXNXNXN, ....

4) (The one important for the sequel). Take any finite alphabet, like  
{0,1}, {a, b},  {a, b, c,  ... z} or all keyboard keys. Then the set of  
all finite words build on any such alphabet is in bijection with N.  
Indeed, to be sure of enumerating all the words, on {a,b,c}, say, just  
enumerate the words having length 1, then length 2, etc. And order just  
alphabetically the words having the same length. On the alphabet  
{a,b,c}, this gives

a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb,  
abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, ...

I hope you see that this gives a bijection between N and A° (the set of  
words on A, which in this example is {a, b, c}. Purist would add the  
empty word in front.
 From this you can give another proof that Q is enumerable (= in  
bijection with N). Indeed all rational numbers, being a (reduced)  
fraction, can be written univocally as a word in the finite alphabet  
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, /}. Example 456765678 / 9898989 (I have  
added blank for reason of readibility, but those are not symbols taken  
from the alphabet).
Another important example, the set of all programs in any programming  
language. For some language, like Python for example, you have to put  
explicitly the "enter", or "carriage return" key symbol in the  
alphabet, of course.


5) Let N be the set {0, 1, 2, 3, 4, 5, 6, ...}, as usual. Let N' be a  
sort of copy or relabeling of N, that is N' = {0', 1', 2', 3', 4', 5',  
6', ...}.
What are really object like 5' is not relevant except that we consider  
that any x is different from any x'. (usually mathematician formalize  
N' by NX{0}, or NX{1}, but that are details).

Is N U N' in bijection with N ?

Sure, NUN' = {0, 0', 1, 1', 2,  2', 3, 3', 4, 4', 5, 5', 6, 6', 7, 7',  
8, 8', ...}, and

0, 0', 1, 1', 2,  2', 3, 3', 4, 4', 5, 5', 6, 6', 7, 7', 8, 8', ... is  
indeed an enumeration of NUN' (bijection from N to the set NUN'). You  
can see it as the result of a zigzagging between

0,  1,  2,  3,   4,  5,  6, ...
0', 1', 2',  3',  4', 5',  6', ...  (do the drawing if you want to see  
the zigzag).


Is the infinite union NUN'UN''UN'''UN''''U ... still enumerable?
Yes, just zigzag on

0,     1,     2,     3,     4,     5,       6, ...
0',     1',    2',    3',     4',    5',      6', ..
0'',    1'',   2'',    3'',    4'',    5'',     6'', ...
0''',   1''',  2''',    3''',   4''',    5''',    6''', ...
0'''',  1'''',  2'''',   3'''',   4'''',   5'''',   6'''', ...
0''''', 1''''',  2''''',  3''''',   4''''',  5''''',  6''''',
...

this gives, starting from up left:

0, 1, 0', 0'', 1', 2, 3, 2', 1'', 0''', 0'''', 1''', 2'', 3', 4, 5, 4',  
3'', 2''', 1'''',  0''''', 0'''''', ...

and gives an enumeration (bijection with N) of the infinite union  
NUN'UN''UN'''UN''''U ...


Remark: for those who recall the transfinite ordinal we have met when  
we have try to give a good answer to the first fairy, you can realize  
that if we put on each set N', N'', N''', etc. the usual order (so that  
3''' < 5''') for example, and if we extend those orders on the all  
infinite union by deciding that x^{n strokes} < y^{m strokes} in case m  
is bigger than n (whatever are x and y),  we get transfinite ordinal  
number.

Example
omega is just N
omega+omega is the ordinal of the order:
   0,     1,     2,     3,     4,     5,       6, ...   0',     1',      
2',     3',     4',     5',       6', ...

omega* omega = omega+omega+omega+omega+omega+omega+omega+ ... = the  
ordinal of the order

0,1,2,3,...0',1',2',3',...0'',1'',2'',3'',...0''',1''',2''',3''',...0''' 
',1'''',2'''',3'''',...0''''',1''''',2''''',3''''',...0'''''',1'''''',2' 
''''',3'''''',...0''''''',1''''''',2''''''',3''''''', ....

Obviously (ask if this is not clear), the zigzagging showing that  
NUN'UN''UN'''UN''''U ...  is in bijection with N, shows that the  
ordinal
omega* omega is in bijection with N.

Note that all the "..." in

0,1,2,3,...0',1',2',3',...0'',1'',2'',3'',...0''',1''',2''',3''',...0''' 
',1'''',2'''',3'''',...0''''',1''''',2''''',3''''',...0'''''',1'''''',2' 
''''',3'''''',...0''''''',1''''''',2''''''',3''''''', ....

have the usual interpretation, except the last one, which supposes you  
have grasped the process for generating that ordinal. (Compare may be  
with Thorgny's ultrafinitist rebuilding of the ordinals, but only if  
you grasp well the non-ultrafinitist one before).

All transfinite ordinal we have used with the first fairy (to give her  
a big finite number) were enumerable (= in bijection with N).

This ends the little introduction to the notion of bijection, and of  
(infinite) enumeration (= bijection with N).

Next, I will show the existence of bigger infinities, that is, of  
infinite set which cannot be put in a bijective correspondence with N.  
You can prepare yourself with the set

NXNXNXNXNXNXNXNX ...  (the infinite cartesian product of N with itself)

This is the set of omega-uples of natural number. It is the set of (x,  
y, z, r, s, t, u, ...) with x, z, ... all belonging to N. So it is also  
the set of sequences of natural numbers, and so it is also the set of  
functions from N to N.

or you can take even just, putting 2 for the set {0,1} the infinite  
product of 2 with itself

2X2X2X2X2X2X2X2X2X2X2X ...  (the infinite cartesian product of {0, 1}  
with itself),

This is the set of infinite binary sequences, or the set of functions  
from N to 2, where 2 is put for {0,1}.

I guess many of you knows that such sets are NOT enumerable, and that  
this can be proved by one application of Cantor's diagonal. But I will  
explain this in detail. The reason is not that we will have some use of  
that result, but just because it is the simplest use of a diagonal.

Only after that, I will be able to explain, by a similar but a bit  
subtle diagonal, why Church thesis, and even more generally the  
hypothesis asserting there exist a universal computing machine, is a  
quite strong postulate whose impact on the everything theories, the  
measure problem, etc. is incalculable ...
This is needed to have a thorough understanding of the seventh and  
eighth steps of the UDA. But my main goal long term is to answer  
precisely a question by David about the origin and importance of the  
first person in the comp frame.

So the sequel is:

1) Cantor's diagonal
2) are there universal computing machine? (Kleene's diagonal, and  
Church thesis)

3) A fundamental theorem about universal computing machines. (All such  
machine are imperfect, or insecure)

Please ask questions. To miss math due to notation problem is like to  
miss travels due to mishandling of the use of maps, or to miss love by  
mishandling of the use of clothes ... It is missing a lot, for  
mishandling a few I wanna say.


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 [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
-~----------~----~----~----~------~----~------~--~---

Reply via email to