Re: Cardinality of Set of Computable Numbers?

From: Ahto Truu (ahto.truu_at_mail.ee)
Date: 12/26/03 

Date: Fri, 26 Dec 2003 13:24:26 +0200

> >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.
>
> I don't really see how to do this. Do you know that every computable
> number has an infinite number of digits? If not, how do you know that
> f^{-1}(j) (i.e., the j-th computable number) has at least j digits, so
> that you can define a new number whose j-th digit is different from
> the j-th digit of f^{-1}(j)?

This is really not a problem. Any integer (representation in any base)
can be zero-padded from left to ensure it really has at least j digits.
Of course, the mere existance of d does not make it computable, still.

Ahto