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