I give the solution. On 15 Sep 2009, at 16:30, Bruno Marchal wrote:

## Advertising

> OK? Take your time to compare with the last post, and to understand > what happens. > > Training exercise: prove, using that notation, that 2^N is non > enumerable. Hint: use a slightly different g. 2^N is non enumerable. 2^N is the set of functions from N to {0, 1}, and I will again note or identify a function from N to {0, 1} with an infinite sequence of 1 and 0. For example, the function {(0, 0), (1, 1), (2, 0), (3, 1), (4, 0), (5, 1), ...} is identified with the sequence 010101010... OK? I reason "by absurdum", ... again with the two notations. Suppose that 2^N *is* enumerable, then there is a bijection from N to 2^N, which is something like 0 ==== 000110100111011010011100 ... 1 ==== 110110010000011110101111... 2 ==== 000000000000000001000000... 3 ==== 101010101010101010101000... 4 ==== 111111111110000000111110... 5 ==== 110011000010100101001100... 6 ==== 000000000000000000000000... 7 ==== 111000111000111000111111... 8 ==== 000000001110000011010000... 9 ==== 111111111111111111110001... ... If the bijection exists, all the "1" and "0" are well defined in the infinite diagram, and the diagonal sequence is well defined too. So the diagonal sequence, made up from the diagonal sequence where all 0 are changed into 1 and vice versa, is well defined too. It is 1011001... (print it, and use a rule to verify!) OK? Suc a sequence cannot appears in the enumeration. Indeed, if it appears in the diagram, it appears at some line, let us say the kth line. But at the intersection of the diagonal and the kth line, there will be a problem. By the construction of the diagonal, the kth element of the kth sequence has to be simultaneously equal to 0 and 1. Contradiction. OK? So 2^N is non enumerable. OK? I do the proof with the "usual" notation: Suppose f_n is an enumeration of the functions from N to {0, 1}. Let g be the function which send n on 1 - f_n(n). g is a function from N to 2 (because both 1 - 1, and 1 - 0 gives 0 or 1). We write g(n) = 1 - f_n(n). g is a function from N to 2, yet cannot belong to the enumeration f_i. Why? Suppose g is in the enumeration f_n. It means there is a number k such that g = f_k. Thus for all n, g(n) = f_k(n). In particular g(k) = f_k(k). But by definition, for all n g(n) = 1 - f_n(n). In particular g(k) = 1 - f_k(k). So we have that g(k) is equal to both f_k(k) and 1 - f_k(k). And f_k is a function from N to {0, 1}, so we get either 0 = 1 (if f_k(k) = 0), and 1 = 0 if f_k(k) = 1. Contradiction. We can say it is the same proof than the proof that N^N is non enumerable. The only change is in the diagonal function g. Yesterday it was g(n) = f_n(n) + 1, and today it is g(n) = 1 - f_n(n). This comes from the fact that we want g to belong to N^N and 2^N respectively. OK? ***************** If it is OK, in the next post we begin to address the computability issue. I give you an anticipative exercise or subject reflection. This is a deep exercise. Its solution leads to the notion of universal function and universal number/machine. More exactly it leads to an evaluation of the price we have to pay if we want to believe in that notion. We have seen that the set N^N is non enumerable. This means it is a *huge* infinite set, compared to N. We could argue that there are too much functions in that set. Most usual functions that we encounter in real life, both in math and physics, seem to share the property that they are computable. This means that we can write some rules or recipe for computing them, or that, may be, we can build some mechanical device capable of computing them. The natural functions we met were the exponential f(n) = 2^n, or the factorial(n), or similars. It seems that we can explain to each other how to compute them, and you already known that we can build machines computing them indeed. So, we could decide, if only to avoid those big infinities, to restrict ourself on the computable functions. Let us define N^N-comp to be the set of computable functions from N to N. The question is: is there a bijection from N to N^N-comp ? 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 -~----------~----~----~----~------~----~------~--~---