Hi,

I recall the proof that N^N is not enumerable.

I recall that N^N is the set of functions from N to N. Such functions 
associate a natural number to each natural number. Example:

factorial = {(0, 1) (1, 1) (2, 2) (3, 6) (4, 24) (5 120) ...}

of course the same information is provided by the sequence:

1, 1, 2, 6, 24, 120, ....      which is an element of the infinite 
cartesian product NXNXNXNXNX ....

So N^N is in bijection with NXNXNXNXNX ...., and giving that we are 
interested in cardinality, for all practical purpose we can identify 
both sets.




Theorem; N^N is not enumerable



Proof 1 (by absurdo):

If a bijection exists between N and N^N, then it will look like (cf the 
identification above):

0   ----------    4  1  2  6  24  57  ...
1   ----------    0  0  5  0  45    7  ...
2   ----------    0  9  7  0    1    0  ...
...

Well, at least in the mind of a God capable of seeing the whole 
infinite table.
Again, for such a God, the diagonal is entirely well defined:

4 1 8 ....

So we can  consider the sequence of the diagonal elements, each added 
to one:

4+1  1+1 8+1 ..., that is

5 2 9 ...

By construction this sequence is not in the list above, because it 
differs:

from the 0th sequence, at the 0th "decimal" let us say,
from the1st sequence, at the 1st "decimal",
from the 2nd sequence, at the 2nd "decimal",
from the 3rd sequence, at the 3nd "decimal"
from the 4th sequence, at the 4th "decimal"
from the 5th sequence, at the 5th "decimal"
from the 6th sequence, at the 6th "decimal"
from the 7th sequence, at the 7th "decimal"
from the 8th sequence, at the 8th "decimal"
...
from the n-th sequence, at the n-th "decimal"
...

All right? This works for any tentative bijection proposed by any Gods.

Now I give you the same proof, but with the traditional functional 
notation. This is for helping those who could have some notation 
problems. Please make you sure that you see I am giving the same proof, 
but with better notations:


proof 2 (by absurdo)

If a bijection exists between N and N^N, then it means there is an 
enumeration of all functions from N to N, it looks like:

f_0  f_1  f_2  f_3  f_4  f_5  f_6 ...

All those f_i are well-defined (in Platonia) functions from N to N. So, 
the following function g is also well defined. By definition:

g(n) = f_n(n) + 1   (this is the diagonal "+1" described above).

Now g cannot be in the list f_0  f_1  f_2  ...
Why?
Because if g is in the list, it means there is a number k such that g = 
f_k  (and thus for all n, g(n) = f_k(n)).

But g(n) = f_k(n) + 1 by definition of g. Now we have, by applying g on 
its code k (cf g = f_k):

g(k) = f_k(k) (by the assumption that g is in the list), and
g(k) = f_k(k) + 1  (by definition of g)

Thus (by Leibniz rule)

  f_k(k) = f_k(k)+1.

But those are well defined numbers   (cf: the f_k are functions from N 
to N), thus we can subtract f_k(k) on both sides, and this gives

0 = 1

Contradiction. Thus g cannot be in the list, and appears as a sheep 
without a rope. N^N has "more element than N", and is thus non 
enumerable. QED (OK?).


NEXT: the key post. It should be even more simple, because, although we 
will be obliged to stay in Platonia, we will not invoke any God 
anymore. Instead we will invoke its quasi antipode, not the devil (!), 
but the humble finite earthly creature. The idea is to concentrate 
ourself on computable functions from N to N, instead of *all* functions 
from N to N.
Computable?
By who? Computability is an epistemic notion, it seems to involve a 
subject.
Well, as you can guess, computable will mean "computable by that humble 
finite earthly creature" ... Now, what does that mean ...

Soon on a screen near you ;) ..., asap ...

Good week-end,

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 [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
-~----------~----~----~----~------~----~------~--~---

Reply via email to