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 01
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 00 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 02 (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.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Wed Sep 16 2009 - 18:12:41 PDT