I give the solution.

On 15 Sep 2009, at 16:30, Bruno Marchal wrote:

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

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!)


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.  


So 2^N is non enumerable.


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

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  



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  

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  

The question is: is there a bijection from N to N^N-comp ?



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 
For more options, visit this group at 

Reply via email to