Cardinality of Set of Computable Numbers?

From: Russell Easterly (logiclab_at_comcast.net)
Date: 12/26/03 

Date: Thu, 25 Dec 2003 16:32:15 -0800

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.
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.
In fact, nearly all members of P(S) are noncomputable.

So, the set of all computable numbers can't exist if
it is countable and if it is uncountable, most of its
powerset is noncomputable.

What am I missing?

Russell
- the universe is one dimensional

Quantcast