- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Fri, 30 Nov 2007 16:32:04 +0100

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

Date: Fri, 30 Nov 2007 16:32:04 +0100

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:14 PST
*