```Holy Thursday (or is it Maundy Thursday?) 2001

I was going to put this up on livejournal (what is liverjournal, asks the
unsuspecting reader?  Go over to meep.livejournal.com (if it's working.  Be
patient.) and you'll find out (oh Lord!  she writes =more=?  Lord help
us.)), but I've decided it would be too long, and as you've shown patience
before in me explaining math/physics/whatever concepts, I'm going to put
this here.

Unlike most tirades, this one gets a title:

Infinity is NOT a Number  (and you may quote me on that)
------------------------

Long long ago, when people decided it would be a "good thing" to keep track
of how many wapiti they killed during the season, people, ingenious
problem-solvers that they are, put marks on a stone or cut notches in a
stick.  And it was good.

Someone noticed that if it was an extremely productive year, the stick or
stone could be saturated, and if the hunting party came back with 40
carcasses (after figuring out how to stampede a herd over a cliff), one
does not want to actually sit there notching a stick 40 times.  One might
screw up.  So some people thought, hey, let's make a =new= kind of mark to
indicate groups of 5.  And it was even better.

(Where is she going with this?)

...and eons later, the decimal system was born.  In all these systems of
keeping track of amount, people noticed you could always add one more
notch, one more alpha, one more digit.  Thus the concept of infinity was
born -- not the "number" one would reach by repeatedly adding 1, but the
idea of the process that one could make numbers bigger and bigger without
end.  And so matters stood for some time.

One day (in the late 1800s or so), there came a guy named Georg Cantor
(Jo-jo to friends) who wondered whether one could count up the real numbers
the same way you could count up, well, counting numbers.  He noticed that
there is a reasonable way to tell if infinite sets have the "same size" -
the way one splits poker pots for example.

Say we're playing a hi-lo poker game, and you and I win the game.  Rather
than count out the amount of the chips in the middle and then dividing the
amount by two to divvy up the kitty, I pair off the chips and give one to
you and then one to me.  If for every chip I get, you get a chip, though at
the end we might not know how much we won, we know that we both have the
same amount (unless I know some good sleight of hand, but we'll ignore
that).

Similarly, even though infinite sets, like all the counting numbers (1, 2,
3, 4...) or all prime numbers (2, 3, 5, 7, ...) don't have a certain number
of elements, but an "infinite" number of elements, we can tell if they have
the "same number" of elements if we can pair them up.  Here's an easy
example - there are the same number of even counting numbers as counting
numbers -- just pair each counting number with its double:

counting number	even number
1		     2
2		     4
3		     6
4		     8
.		     .
.		     .
.		     .

Actually, it's easy to see that any infinite subset of the counting numbers
has the same number of elements as the counting numbers, mainly because you
can put them in order.  Consider the prime numbers, numbers which have only
two number that can divide into them.  There's are several proofs that
there are an infinite number of primes, but how can we pair them off with
the counting numbers?  Easy, for there must be a smallest prime, then a
next smallest prime, and so on.  Just put the primes in increasing order
and label them 1, 2, 3, etc.  You know that every prime will come up
=somewhere= in the ordering, so you will miss no primes by listing them
this way.

Sets of numbers that can be put in an exhaustive list like this are said to
be "countable".  If you cannot put the elements in this kind of list, say
even after making an infinite list there are numbers left over and you can
never put =all= of them in a list, the set is called "uncountable".

Let's consider the integers - they're countable because you can start at 0
and alternate the counting numbers and their negatives as you go out: 0, 1,
-1, 2, -2, 3, -3, 4, -4.  Let's think of something harder - what about the
rational numbers?  The rational numbers are any number that can be
represented as the ratio of two integers: -54/76, 4564567/3, etc.  How can
we make sure that we can put =all= of them in a list?  There's a
"matrix" trick that's been used for a long time:

numer:	1	-1	2	-2	3	-3	4  	...
denom
|
V
1	1/1	-1/1	2/1	-2/1	3/1	-3/1	4/1	...

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

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

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

.
.
.

Now it's obvious that each rational number (except for 0) shows up
=somewhere= in that matrix, but this really doesn't look like a list.  If
we decided to list it out by listing the first row first, we'd never get to
the second row!  The idea is to start one's list off in the upper left-hand
corner, and wiggle around the diagonals.  So let's start off with the
missing 0, then 1/1, then 1/2 right below, then -1/1 on that diagonal, then
2/1, then -1/2, then 1/3....  As you can see, by making this path we can be
sure of hitting everybody in the matrix.  However, there are lots of
repeats -- what to do with them?  Simply skip over them.  In the next
diagonal, we will hit 1/4, -1/3, then 2/2 = 1 = 1/1.  Since it's already in
our list, we jump over it.

There are all sorts of countably infinite sets.  Where the fun comes in is
when one tries to "count" an uncountably infinite set.  For example, take
the real numbers.  Any real number can be expressed in decimal form, with a
countably infinite decimal expansion (one can always add one more digit to
the end....); because the representation of every real number is countable,
it's tempting to think that the set of real numbers must also be
countable.  There have even been people who have tried to think of ways of
making a list of all real numbers.  To make it simple, we will only
consider real numbers between 0 and 1 -- so their decimal expansion will
simply be something like 0.2347213468354....  If the number is rational,
the decimal expansion will either terminate (0.25 = 1/4), or eventually
repeat (0.17171717... = 17/99).  Numbers whose decimal expansions do not
terminate or repeat are =irrational= (because they can't be expressed as
p/q).

One way to "list" the real numbers has been tried -- take the counting
numbers, reverse their digits, and put a decimal in front of the
result: .1, .2, .3, .4, .5, .6, .7, .8, .9, .01, .11, .21, .31, etc.

Can you see a problem with this?  I will tell you now that there are lots
of numbers missed by this technique - do you see why this is?

Anyway, Cantor showed that the set of real numbers is an =uncountable=
set.  And he did it thusly - first he supposed that you =could= list all
the real numbers between 0 and 1.  One should expand terminated decimals
with an infinite number of 0s so that every number has an infinite decimal
expansion.  So the list would look something like this:

#	list item #
1	.3623542238478553452....
2	.17171717171717171717....
3	.50000000000000000000....
4	.278652765403757402835....
5	.12345678910111213141516....
.		.
.		.
.		.

Now this is supposed to be the whole enchilada.  There are supposed to be
=all= real numbers between 0 and 1 on this list (and to take care of that
repeating 9 problem (.9999999.... = 1), we will disallow any decimal
expansion ending in repeating 9s as they can be simplified to a decimal
ending in repeating 0s).  If you can find one real number that's not on
that list, you've contradicted your supposition, meaning it couldn't have
been true to begin with (the infinitude of primes is proved in a similar
way.  You assume there's a largest prime, and then you use it to make a
number that shows you there's an even =bigger= prime.  So your original
supposition cannot have been true.)  This is called proof by contradiction.

So let's see, I want to make a new number.  Let's look at the first digit
of the first number in the list.  It's 3.  Well, I want my new number to be
different, so I'm going to pick 7 as the first digit of my new
number.  Let's look at the second digit of the second number in our list -
it's 7.  Well, I can't have that.  The second digit of my new number will
be 3.  (We have .73 so far).  For the nth digit of my new number, I'm going
to look at the nth digit of the nth number on our list.  If that digit is
7, I'm going to pick 3 for the digit of my new number.  If that digit is
anything other than 7, I'm going to pick 7 as my new digit.  So with the
list that I've started above, I have a number starting 0.73777...

This new number is =nowhere= in my list.  Why?  Because it differs from
each number in the list by at least one digit - meaning they cannot be the
same.  So if I can make a number that's not on my "exhaustive list", that
means I can't have come up with an exhaustive list to begin with.

This is a very famous proof, called the Cantor diagonal argument.  The
"diagonal" comes from the fact that we used the nth digit from the nth
number in the list to create a new number, thus going down a diagonal line
in the list.  This kind of diagonal argument has been used in other famous
proofs - Godel used it for his incompleteness theorem (he used a
combination of a diagonal argument and the liar's paradox "this statement
is false"), and Turing used it to prove there are noncomputable
problems.  You can really impress people with this argument... as long as
the people you're trying to impress aren't mathematicians.

When I presented this argument to a bunch of middle school students, the
response I got was "but infinity is infinity" -- making me realize that I
should never have used the word infinity to begin with.  People have
connotations tied up with words like infinity and chaos that have nothing
to do with the precise mathematical definitions of the words - often people
use words as humpty dumpty does - making them mean what they want them to
mean, so that they can use them to express their ideas.  However,
mathematical ideas are much more limited that the ideas the human mind can
hold and words are restricted to very particular uses.  "Continuous" means
something extremely precise (though not what you think it means.  Most
people equate continuous with smooth), and "infinity", though it can take
on different meanings in mathematical context, has only one meaning in any
given mathematical context.

In any case, the "infinity" of the real numbers is "bigger than" the
"infinity" of the counting numbers.  More to the point, these infinite sets
are not the same size - the real numbers are "uncountable".  Cantor, before
he went irreversibly insane, came up with ways to make infinities larger
than the real numbers, but you really don't want to hear about it.

In any case, this is one of the results you should think about when you
want to bandy infinity about as a number.  When you've got two infinities
to choose from, countable and uncountable (with an uncountable number of
infinities in that second category), how can infinity really be a
number?  Then one is tempted to think of it as a size of a set.  Then
calculus sticks its ugly nose in and all hell breaks loose.

But something on infinity in calculus later.  Infinity is fun, but as long
as you don't bring any preconceptions on the matter to the table, you can
have a lot more fun with it.

```
 Prev Year Next