Re: Cardinality of Set of Computable Numbers?

• Previous message: Rajsekar Manokaran: "Re: 1-SAT, 2-SAT, and 3-SAT"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Thu, 08 Jan 2004 04:28:59 GMT

In article <bsg5f4$1rf8$1@agate.berkeley.edu>, Arturo Magidin wrote:
> 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)?

I don't see that this is necessary for a proper diaganolization argument (in
general, not just here). If the j-th number has less than j digits, then it
is sufficient to pick "1" for the j-th digit of the constructed number. It
won't match the j-th number, and that is all that is necessary.

The problem with the original argument is that diaganolization constructs
a number with an infinite number of digits. That's fine when you are using
it to product a real number, but not fine when trying to product a
"computable" number, at least for most reasonable definitions of computable.

Cantor's diaganol argument is one of those proofs that is very beautiful.
It is also one of those proofs that seems a lot less subtle than it really
is, so it is easy to misapply it. It also seems to be a big sticking point
for mathematical crackpots. I sometimes wonder if it would be better in
math courses to put it off, and establish the uncountability of the reals
some other way, and give diaganolization later.

The uncountability of the reals is pretty easy to do with elementary
arguments, without diaganolization:

1. Show that there is no one-to-one corresponce between a set and the set of
its subsets. This is doable on the first day of set theory class.

2. Apply #1 to the set of positive integers, showing that the set of subsets
of positive integers is uncountable.

3. Exhibit a one-to-one correspondence between the set of subsets of
positive integers and the reals. Here is such a one-to-one corresponce:

    For non-negative real r, take the continued fraction for r,

        r = [a0, a1, a2, ... ]

    The corresponding subset of positive integers is

        { 2+a0, 3+a0+a1, 4+a0+a1+a2, ... }

    For negative real r, take the continued fraction for |r|,

        |r| = [a0, a1, a2, ...]

    The corresponding subset of positive integers is

        { 1, 2+a0, 3+a0+a1, 4+a0+a1+a2, ... }

-- 
--Tim Smith

• Previous message: Rajsekar Manokaran: "Re: 1-SAT, 2-SAT, and 3-SAT"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]