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 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 Fri Nov 30 2007 - 10:32:27 PST