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 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 Nov 19 2007 - 10:04:07 PST