On 09 Sep 2009, at 09:21, Bruno Marchal wrote: > Next post: Cantor theorem(s). There is NO bijection between N and > N^N. I will perhaps show that there is no bijection between N and > {0, 1}^N. The proof can easily be adapted to show that there is no > bijection between N and many sets. > > After Cantor theorem, we will be able to tackle Kleene theorem and > the 'mathematical discovery of the mathematical universal machine', > needed to grasp the mathematical notion of computation, > implementation, etc.

CANTOR'S FIRST RESULT There is NO bijection between N and N^N (N^N is the set of functions from N to N. N = (0, 1, 2, ...} Proof 1) preliminaries Like for the irrationality of the square root of 2, we will proceed by a reduction to an absurdity. First note that there are many obvious injection (= one-one function) from N to N^N. For example the function which sends the number n on the constant function from N to N which send all numbers to n: 0 ======> {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0) ....} 1 ======> {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1) ....} 2 ======> {(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2) ....} 3 ... ... Such correspondence is one-one: two different numbers are send to two different functions from N to N. OK? With Cantor, inspired by what happens in the case of finite sets, I will say that the cardinal of A is little or equal (≤) than the cardinal of B, when A and B are infinite sets, when there is a one-one function, also called injection, from A to B. The injection described in the diagram above shows that the cardinal of N is little or equal than the cardinal of N^N. I will say that the cardinal of A is equal to the cardinal of B when there is a bijection between the two sets. I will also use the canonical bijection between the set of functions from N to N and the set of infinite sequences of numbers, to write any function from N to N, as a sequence of numbers. This will make the things more readable. The diagram above becomes: 0 ======> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 1 ======> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 2 ======> 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... etc. OK? We can do that because we have all in mind the canonical order of the natural numbers: 0, 1, 2, 3, .... so that the sequence of numbers can be seen a short way to describe a function from N to N. 2) the proof Let us do the Cantor's reduction to the absurd. Suppose there is a bijection from N to N^N. It will have some shape like: 0 =====> 34, 6, 678, 0, 6, 77, 8, 9, 39, 67009, ... 1 =====> 0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ... 2 =====> 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... 3 =====> 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... 4 =====> 1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ... 5 =====> 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ... ... May be you recognize some functions in the correspondence. The first two functions seems arbitrary. The third one seems to be the power of two, the fourth one is the constant function sending all numbers on 2, the fifth one seems to be the factorial functions, the sixth one seems to be an arbitrary function from N to {0, 1}. From such finite set of data we can never be sure, given that the "..." could in this context mean practically anything. BUT, if there is a bijection between N and N^N, the correspondence is well defined, at least in Platonia, or in the mind of God. This means that each line must be thought as representing *some*, perhaps unknown, precise function. In particular, all numbers, including the double infinity of numbers that we have not represented, are well defined, perhaps unknown by us, numbers. But then, Cantor reasons, if the whole diagram above makes some sense, it is easy to conceive a NEW function, which can be shown not belonging to the diagram. That is there will be a function from N to N which is not represented at any line of the above diagram. Indeed the following sequence will play that role: 35, 678, 5, 3, 7, 1, ... Do you see where it comes from? It comes from the diagonal elements, from up-left to down-right, with one added to them: 34+1, 677+1, 4+1, 2+1, 6+1, 0+1, ... Why does such sequence not belong to the diagram? Because it differs from the first sequence for the first output. Indeed the first output at the first line is 34, and the new function outputs 35. It differs from the second sequence at the second outputs. Indeed the second output of the second sequence is 677, and the second output of the new sequence is 678, etc. So, by construction, the new function differs from all the sequence in the list above. We proceed diagonally to be sure that by changing a function, we don't come back on some distinction already introduced. All the function being well defined, in Platonia, or in God's eyes (or in the eye of some omniscient being), automatically the new sequence is well defined too, and cannot belong to the sequence. Thus we get a contradiction. If the correspondence above is a bijection, then if fails as being a bijection. This reasoning did not depend on the choice of the supposed bijection. All possible bijections will fail, because for each one, their very existence makes them failed to be a bijection, because again their very existence entails the existence of the "diagonal sequence", which by construction differs from each line of the correspondence. Indeed, you should see that they differ at the intersection of the diagonal and the line. End of the proof. OK? 3) Miscellaneous remarks, vocabulary. When Cantor discovered this, he was in shock. He said the famous sentence: "I see it, but I don't believe it". His technic is know as the diagonalization (with a "z" or a "s" according to americans or english respective common uses). Is that proof 100% convincing? I let you judge by yourself. If you say yes, it means you could be realist on the notion of set. Torgny Tholerus has already send to the list, some month ago, an argument which can throw some doubt about such a reasoning. But I want to avoid such premature discussion. Why? Because I don't want you to redo the whole big set of discoveries, and mathematical constructions which have been inspired by Cantor's proof, and focus instead on what will become the 'discovery of the universal machine'. I let you know that this proof, that is Cantor's reasoning showing that there is no bijection between N and N^N, *can* be done without change in the context of formal axiomatic set theory (like Zermelo Fraenkel set theory). Such impossibility theorem is thus well accepted by classical mathematicians. Now, the discovery of the universal machine will come from a very similar reasoning, in a different context, and Torgny Tholerus' remark, for those who remembers it, cannot be applied, even without formal set theory. The biggest objection here would be that Cantor's proof invoke the name of God. Cantor will take that objection very seriously and he will literally ask the advice of the pope (!) to proceed. The formalization of set theory can hide a little bit that invocation, but eventually our diagonalization in the comp frame, will not invoke God or any omniscient being. We will of course come back on this. Accepting Cantor's proof, we know that the cardinal of N^N is bigger than the cardinal of N. So there are infinities 'bigger' than other infinities. Definition: we will say that a set S is enumerable if S is finite or if there is a bijection between S and N. We will say that an *infinite* set S is non enumerable if there is NO bijection between S and N. We can sum up Cantor's result by: N^N is non enumerable. Exercise (using 2 for the set {0, 1}) 1) Does this prove that 2^N is not enumerable? 2) In case you answer "no" to the first question, can you prove that 2^N is not enumerable? OK? I let you think and ask question if necessary. Next post: I will do again that very proof, but in a way which is somehow clearer, by using better notations (yet a bit more abstract, so that it is clearer only for those who are not afraid by math notations). I don't want to mix the two difficulties (new concept/new notations), in a first approach. In some sequel, I will give you the proof of what is known as Cantor's theorem: that the cardinal of a powerset 2^A is always bigger than the cardinal of the set A. But this is not needed for our computationalist purpose, so I will not insist on that. From this we get a ladder of bigger and bigger infinities. A last remark for Mirek, and those who remember what I said about the ordinals (which I have illustrated with the growing functions, some years ago). Mirek, to ensure that cardinals are ordinals, I would need the axiom of choice. But I will never use that, some I will not try to put the cardinals among the ordinals. Best, 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@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---