Hi David, Hi John, OK, here is a first try. Let me know if this is too easy, too difficult, or something in between. The path is not so long, so it is useful to take time on the very beginning. I end up with some exercice. I will give the solutions, but please try to be aware if you can or cannot do them, so as not missing the train.
John, if you have never done what has been called "modern math", you could have slight notation problem, please ask any question. I guess for some other the first posts in this thread could look too much simple. Be careful when we will go from this to the computability matter. I recall the plan, where I have added the bijection thread: Plan 0) Bijections 1) Cantor's diagonal 2) Does the universal digital machine exist? And for much later, if people are interested or ask question: 3) Lobian machines, who and/or what are they? 4) The 1-person and the 3- machine. 5) Lobian machines' theology 6) Lobian machines' physics 7) Lobian machines' ethics But my main goal first is to explain that Church thesis is a very strong postulate. I need first to be sure you have no trouble with the notion of bijection. ================ 0) Bijections Suppose you have a flock of sheep. Your neighbor too. You want to know if you have more, less or the same number of sheep, but the trouble is that neither you nor your neighbor can count (nor anyone around). Amazingly enough, perhaps, it is still possible to answer that question, at least if you have enough pieces of rope. The idea consists in attaching one extremity of a rope to one of your sheep and the other extremity to one of the neighbor's sheep, and then to continue. You are not allow to attach two ropes to one sheep, never. In the case you and your neighbor have a different number of sheep, some sheep will lack a corresponding sheep at the extremity of their rope, so that their ropes will not be attached to some other sheep. Exemple (your flock of sheep = {s, r, t, u}, and the sheep of the neighborgh = {a, b, c, d, e, f}. s --------- a r ---------- d u --------- c t ----------- f ------------e ------------b and we see that the neighbor has more sheep than you, because b and e have their ropes unable to be attached to any remaining sheep you have, and this because there are no more sheep left in your flock. You have definitely less sheep. In case all ropes attached in that way have a sheep well attached at both extremities, we can say that your flock and your neighbor's flock have the same number of elements, or same cardinality. In that case, the ropes represent a so called one-one function, or bijection, between the two flocks. If you have less sheep than your neighbor, then there is a bijection between your flock and a subset of your neighbor's flock. If those flocks constitute a finite set, the existence of a bijection between the two flocks means that both flocks have the same number of sheep, and this is the idea that Cantor will generalize to get a notion of "same number of element" or "same cardinality" for couples of infinite sets. Given that it is not clear, indeed, if we can count the number of element of an infinite set, Cantor will have the idea of generalizing the notion of "same number of elements", or "same cardinality" by the existence of such one-one function. The term "bijection" denotes "one-one function". Definition: A and B have same cardinality (size, number of elements) when there is a bijection from A to B. Now, at first sight, we could think that all *infinite* sets have the same cardinality, indeed the "cardinality" of the infinite set N. By N, I mean of course the set {0, 1, 2, 3, 4, ...} By E, I mean the set of even number {0, 2, 4, 6, 8, ...} Galileo is the first, to my knowledge to realize that N and E have the "same number of elements", in Cantor's sense. By this I mean that Galileo realized that there is a bijection between N and E. For example, the function which sends x on 2*x, for each x in N is such a bijection. Now, instead of taking this at face value like Cantor, Galileo will instead take this as a warning against the use of the infinite in math or calculus. Confronted to more complex analytical problems of convergence of Fourier series, Cantor knew that throwing away infinite sets was too pricy, and on the contrary, will consider such problems as a motivation for its "set theory". Dedekind will even define an infinite set by a set which is such that there is a bijection between itself and some proper subset of himself. By Z, I mean the set of integers {..., -3, -2, -1, 0, 1, 2, 3, ...} Again there is a bijection between N and Z. For example, 0 1 2 3 4 5 6 7 8 9 10 .... 0 -1 1 -2 2 -3 3 -4 4 -5 5 ... or perhaps more clearly (especially if the mail does not respect the "blank" uniformely; the bijection, like all function, is better represented as set of couples: bijection from N to Z = {(0,0) (1, -1) (2, 1) (3 -2) (4, 2) (5, -3) (6, 3) ... }. Because everyone know the sequence 0, 1, 2, 3, 4, 5, ... we can also describe a bijection between N and Z (say) just by the sequence of images: 0 -1 1 -2 2 -3 3 -4 4 -5 5 ... That bijection can also be given by a rule: send even number x on x/2, and send odd numbers on x -((x+1)/2). But it is not necessary to get those rules to be convinced, the drawing is enough once you interpret it genuinely. By AXB, I mean the set of couples (x, y) with x in A and y in B. It is natural to put them in a cartesian plane. For exemple, if A = {0, 1} and B = {a, b, c}, then AXB = {(0, a) (1, a) (0, b) (1, b) (0, c) (1, c)}, and is best represented by (0, c) (1, c) (0, b) (1, b) (0, a) (1, a) You see that if A is finite and has n elements and if B is finite and has m elements, then AXB is finite and has m*n elements. Yet, again, NXN "has the same number of elements" that N. NXN is obviously the infinite extension of the following 4X4 approximation: ... (0,3) (1,3) (2,3) (3,3)... (0,2) (1,2) (2,2) (3,2)... (0,1) (1,1) (2,1) (3,1)... (0,0) (1,0) (2,0) (3,0)... Do you see a bijection between N and NXN ? Here is one, which I will call the zigzagger (draw the picture above and draw the link between the couples, a bit like in little children drawing puzzles, so as to see the zigzag clearly). (0,0) (0,1) (1,0) (2,0) (1,1) (0,2) (0,3) (1,2) (2,1) (3,0) (4,0) (3,1) (2,2) (1,3) (0,4) ... Here is another one, due to Cantor, I think. To draw it you will have to raise the pen. (0,0) (0,1) (1,0) (0,2) (1,1) (2,0) (0,3) (1,2) (2,1) (3,0) (0,4) (1,3) (2,2) (3,1) (4,0) ... The inverse of that bijection, which exists and is of course a bijection from NXN to N has a nice quasi polynomial presentation. (x, y) is send on the half of (x+y)^2 + 3x + y. You see that (4,0) is send to 14 (ok ?, it is not 13 because we start from zero), and indeed the half of (4+0)^2 + 3*4 +0 is 14. And ZXZ extends in a similar way : ... ... (-3, 3) (-2, 3) (-1,3) (0,3) (1,3) (2,3) (3,3)... ... (-3, 2) (-2, 2) (-1,2) (0,2) (1,2) (2,2) (3,2)... ... (-3, 1) (-2, 1) (-1,1) (0,1) (1,1) (2,1) (3,1)... ... (-3,0) (-2, 0) (-1,0) (0,0) (1,0) (2,0) (3,0)... ... (-3,-1) (-2,-1)(-1,-1) (0,-1) (1,-1) (2,-1) (3,-1)... ... (-3,-2) (-2,-2)(-1,-2) (0,-2) (1,-2) (2,-1) (3,-2)... ... (-3,-3) (-2,-3)(-1,-3) (0,-3) (1,-3) (2,-1) (3,-3)... ... Do you see a bijection between N and ZXZ ? Here is the spiral-bijection, or spiraler: (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) .... You see: a bijection between N and ZXZ assigns to each natural number one and only one couple of integers, and this in such a way that we are sure that all couples of integers is the image of a natural number by that bijection. Little exercises: 1) is there a bijection between N and N? 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). (equivalently: = the real with repetitive decimals, like 0,99999999...., or 345,78123123123123123...). By the way, could find n and m (in N) such that n/m = 345,78123123123123123... ? (and could you explain why 1,00000000.... = 0, 99999999....?). But this will not been used later. Can you see that there is a bijection between N and Q? Hint: transform the bijection between N and NXN into a bijection between N and Q. 3) The disjoint union of two sets A and B = their formal union together with a relabelling so as to distinguish the elements: exemple: N disjoint-union-with N = {0, 1, 2, 3, ...} U {0', 1', 2', 3', ...}, which I will write N U N' (read: N union N prime). Is there a bijection between N and (with obvious notation) N U N' U N'' U N''' U ...? I will write NXNXN for NX(NXN) can you build a bijection between N and NXNXN ? can you build a bijection between N and NXNXNXN ? can you build a bijection between N and NXNXNXNXN ? 4) Very important for the sequel. Let A be a finite alphabet (for exemple: A = {0,1}). Let us denote by A° the set of all finite words build on A. By a (finite) word a mean any finite sequence of elements taken in the alphabet (like 000, or 10101, or 1101000011010110). Is there a bijection between N and A°, with A = {0,1}. Solutions will be given later, but ask for question if there are any problem. Don't hesitate to tell me the mistakes, which always exist! You can also ask question about motivation, like, "for God sake why are you explaining us all this". Try also to keep those posts for later considerations. ================ 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 -~----------~----~----~----~------~----~------~--~---