Re: Cardinality of Set of Computable Numbers?

From: fishfry (BLOCKSPAMfishfry_at_your-mailbox.com)
Date: 12/26/03 

Date: Fri, 26 Dec 2003 02:10:47 GMT

In article <b6adnV6Pvd8vHHai4p2dnA@comcast.com>,
 "Russell Easterly" <logiclab@comcast.net> wrote:

> As often happens, I have managed to confused myself.
> Any enlightenment will be appreciated.
>
> I have read that the set of computable numbers is countable.
>
> Let S be the set of all computable numbers
> and assume S is countable.
>
> Since S is countable there is a function, f(),
> that maps S to the natural numbers.
> Using f() to order S, define a diagonal number, d.

47
12
487384
4738
74858587
343434
387498394838493
...

This is a countable list containing all computable numbers. Exactly
what do you mean by the diagonal number? Do you mean a natural number
whose n-th digit is different from the n-th digit of n-th member of the
list? It seems that the diagonal has a digit in EVERY n-th place, and
is therefore not even a natural number.

Can you clarify your argument to explain what you mean by the diagonal
number defined by the order f?

Even if you are talking about computable reals, say between 0 and 1, you
can then define a diagonal (an infinite decimal) but how do you know
that diagonal number is computable? What rule generates it? You don't
know, because you haven't made f explicit. You can't, because there are
in fact an uncountable number of possible f's.

That's because there are uncountably many bijections from N to N.

Relevant Pages