Re: Cardinality of Set of Computable Numbers?

From: Arturo Magidin (magidin_at_math.berkeley.edu)
Date: 12/26/03 

Date: Fri, 26 Dec 2003 02:12:52 +0000 (UTC)

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.

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)?

>d is a computable number not in S.
>Therefore, S can't be the set of computable numbers.
>
>Cantor's powerset argument makes things even weirder.
>
>Let S be the set of all computable numbers (countable or uncountable).
>Let P(S) be the powerset of S. Cantor proves |S| < |P(S)|.
>This means that P(S) contains members that are not in S.
>These members must be noncomputable numbers.

Actually, ALL members of P(S) are not computable numbers, since the
elements of P(S) are not numbers at all: they are sets of numbers. 

-- 
======================================================================
"It's not denial. I'm just very selective about
 what I accept as reality."
    --- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu
Quantcast