Eric Wald eswald at
Fri Jun 3 22:53:44 MDT 2011

On Wed, Jun 1, Shane Hathaway wrote:
> On 06/01/2011 02:27 PM, Aaron Toponce wrote:
>> Similar proofs can be constructed for any countable set:
> Related to this, I've been wondering why irrationals are not considered
> countable.  Is it not true that for any irrational number, a computer
> program can be written that converges to that number as the number of
> iterations reaches infinity?  Any computer program can be represented as
> a large integer, so computer programs are countable, and by extension,
> any number that a computer program can represent (but not necessarily
> produce) ought to be considered countable.

No, it's not true.  For any method of constructing such a program from
an integer, I can construct an infinite number of irrational numbers
that cannot possibly be the output of any resulting program.  For each
program n, take the n'th digit of its output, and substitute a different
digit in its place.  That gives you 9^∞ new irrational numbers.

There does exist a countably infinite set of *computable* numbers for
which programs can be so written.  Fortunately, that set includes almost
every number dealt with in the course of normal math.  Physics brings a
few more interesting irrational numbers that can't really be computed
properly, though: α, c, and e come to mind.

More information about the PLUG mailing list