[UFO Chicago] Uncountably infinite

[Ian Bicking]

I had forgotten quite how you prove that there are an uncountably
infinite number of real numbers -- that is, by uncountable infinite,
that you cannot make a list of all real numbers (even if it is an
endless list).  So I dug out a text book, for my education (and now
yours if you keep reading...)

So, you can make an endless list of all positive integers.

1
2
3
...

Or for all integers (not just positive), it would look like:

1
-1
2
-2
3
-3
...

and if you keep writing these out forever you'll have all the integers. 
You can do all the rationals between 0 and 1:

1/2
1/3
2/3
1/4
3/4
...

Note that these lists don't necessarily start at 0 and work their way
up.  Still, you can't do all the reals between 0 and 1.  Suppose you did
make a list:

0.124308...
0.458293...
0.981347...
0.349587...
0.429857...
0.126743...
...

Note that each of these real numbers has an infinite number of digits
(since at least some of them are irrational).  Given this (infinite)
list, you can construct a real number that is not on the list.  In this
example, note the parenthetic digits:

0.(1)24308...
0.4(5)8293...
0.98(1)347...
0.349(5)87...
0.4298(5)7...
0.12674(3)...

Using these digits, we get the sequence 151553... going on infinitely. 
Now, create a number from these digits, such that each digit is
different from the equivalent digit in this sequence.  For instance,
0.262664... -- this number cannot be in the list, because when we
constructed it we made sure that it different from every number on the
list by at least one digit.  So we cannot list all the real numbers, and
so the set is "uncountably infinite".  This notion doesn't suppose there
is any infinity that is smaller than countably infinite (infinite as in
an endless list).

As to Neil's question about whether real numbers are important --
without real numbers, many of the axioms of calculus are not true.  For
instance, that a curve has a local maximum, because there are functions
(f(x)) only involving rational numbers that have maximums at sqrt(2),
for instance -- if sqrt(2) is not in your set of numbers, then for any
rational a close to sqrt(2), there will always be another rational b
even closer to sqrt(2) for which f(b) > f(a).  This is a pretty
important axiom for calculus, and it ruins a lot if you get rid of it. 
Once you introduce power series, I believe you can easily get all the
real numbers, not just the simple irrationals like square roots, e, pi,
etc -- I can't remember the term for these numbers.  Again, power series
are quite important to calculus.

I'm unclear on the current theories, but there's a fair amount of recent
mathematics about the computability of real numbers -- I'm not up to
actually reading the papers I found on Google :)  If real numbers are
not computable, then theories of the world that presume computability
will be on shaky ground, though I would not rule out the idea that the
mathematics are not representational of reality.  But giving up calculus
for, say, cellular automata doesn't necessarily seem like a fair trade.

A really good novel that considers some of the implications of
computability is _Permutation City_ I believe by Greg Egan. 

  Ian