Orders of Infinity

Date: 12/05/2001 at 19:43:22
From: Steve
Subject: Orders of infinity

I recently read a book about infinity that set forth several arguments 
for why there are different sizes or orders of infinity. None of them 
seems convincing to me, and, since my ignorance of math is vast, I was 
wondering if you might fill me in on where my reasoning has gone wrong 
or provide more convincing lines of argument to me.  

The first argument put forward was a geometric one. It was argued that 
since there are an infinite number of points in a two-dimensional as 
well as a three-dimensional figure, one must be talking about 
different orders of infinity in each case, since everyone would agree 
that a three-dimensional figure is bigger than a two-dimensional 
figure. This seems to be a conflation of number with size. I'm willing 
to agree that any two-dimensional or three-dimensional figure is able 
to be subdivided infinitely many times. However, size is not merely 
determined by number. Size is a number _of something_. In the case of 
comparing two-dimensional objects to three-dimensional ones, the 
number of square units and cubic units may well be the same, but 
you're comparing apples and oranges. Of course a cubic unit seems 
bigger than a square unit. It has an extra dimension. Infinity doesn't 
change between the two, the unit of measurement does. 

The second argument was based on the innumerability of irrational 
numbers. It was argued that there is no way to form a one-to-one 
correspondence between the irrational numbers and natural numbers.  
Therefore, a different kind of infinity applies to the irrational 
numbers than applies to countably infinite sets. This argument seems 
to rest on the assumption that if one cannot find a way to generate 
every possible member of a set, you cannot count the members of that 
set. It seems, however, that as long as the members of a set are 
distinct, they could potentially be counted. We just don't know what 
they all are. Why is it necessary to have a whole new kind of number 
to represent their cardinality?  

So, I'm at a loss. Am I misunderstanding these arguments?  Are there 
better ones out there?  I'd appreciate any help. 

Steve

Date: 12/06/2001 at 05:09:02
From: Doctor Luis
Subject: Re: Orders of infinity


Hi Steve,

Thank you for your insightful questions. I've thought about them for a 
bit and I've come up with the following responses to your objections.

> ...Of course a cubic unit seems bigger than a square unit. It has an 
> extra dimension. Infinity doesn't change between the two, the unit 
> of measurement does.

Yes. But you're measuring a completely different thing. In this case,
we were asking about the size of a *set* of points. That is, the 
set of points that comprise a two-dimensional (or three-dimensional) 
figure. The size of a set (called its cardinality) is simply the 
*number* of elements in the set. Period.

What you had in mind was probably something closer to the notion of 
volume, where you pick a basic shape (say, a cube) and define it as 
having unit volume. Then you figure out how many of those shapes fit 
into your original shape. This works out fine but only for nice enough 
shapes. Sometimes you get lots of corners and irregularities (like in 
fractals) where your volume can't even be defined (or it simply 
becomes infinite). Contrast this to the other definition. Even those 
weird irregular sets will have a cardinality, even if their "volume" 
happens to be infinite.

Just as an aside, finding the "volume" of a set is more like 
integrating a function over the set (let f=1 to get the "volume").
How to define this properly without running into problems is a 
delicate matter, and is the subject of a branch of mathematics known 
as Measure Theory.

So, when you wish to know the size of a set you ask "how many 
elements?" When you wish to know the "volume" of a shape, you ask 
"what is the integral of 1 over this set?".


>The second argument was based on the innumerability of irrational 
>numbers... Why is it necessary to have a whole new kind of number 
>to represent their cardinality?  

You don't necessarily have to be able to generate the numbers to 
prove/disprove that a set is countable/uncountable. For example,
Euclid proved that there are infinitely many primes, and we certainly
can't generate them all or don't know how, yet. But we do know that 
the set of all primes is countable anyway. All that is required from 
you to prove that two sets A and B are equinumerable is to show that a 
one-to-one function exists/doesn't exist between those two sets. In 
the case when one of the sets is N, the natural numbers, finding (or 
showing it exists) that one-to-one function that maps to the other set 
is all that is required.

The innumerability of the set of irrational numbers follows directly
from the innumerability of the set of real numbers. Cantor showed (via 
his famous "diagonalization" proof) that the set of real numbers is 
uncountable. He actually found a much more complicated proof first and 
he didn't convince many people, but years after having found that
solution, he found a much more elegant proof. In fact, it's so simple
that I'll reproduce it here, in case your book didn't. 

First I'll start by noting that there are as many elements in the set 
of real numbers as there are elements in the set (0,1) = {x | 0<x<1 }. 
To see this, you need only find a bijection (one-to-one function) that
takes (0,1) to R. For example: f(x) = Arctan(Pi*(2x-1))

Now assume that we can set up a one-to-one correspondence between the
natural numbers and (0,1). Naturally, I'd expect to see an explicit 
listing of such a correspondence:

  1 -> 0.0011213213111...
  2 -> 0.8199191988110...
  3 -> 0.8878181888108...
  4 -> 0.3996771726507...
   ......

And so on, where each real number in (0,1) appears exactly once to the 
right of a unique natural number on the left. (Here, I'm implicitly 
asking for a single decimal representation for each real number, with 
no repeating 9's so that you dont get any duplicates on the right. 
Example: 0.499999... = 0.500000... This is clearly not much to ask of 
our listing, but you'll see why this point is important later on.) So 
far so good?

It was Cantor's genius to realize that such a listing is impossible. 

"Why?" you ask. Well, we can start by observing that we've required
every number to be on the list. Now, let's define a new real number y
with the following property: The n-th decimal digit of y is not equal to 
the n-th decimal digit of the n-th number in our list.

  y = 0.0176...

Our real number y is clearly well-defined. You provide me with a 
listing of all real numbers in (0,1) and I'll be able to produce a 
number y. (That's why I required a single decimal representation for 
each real number, so that y could be defined properly).

Now, here comes the key step. y is itself in (0,1), so it must have a 
corresponding entry in our listing. We did after all, list all real 
numbers. The problem is, what natural number m corresponds to y?

Well, m can't be 1, since by definition y differs from the first 
number in the first decimal digit. m can't be 2, since by definition y 
differs from the second number in the second decimal digit. In fact, 
if n is a natural number, then m can't be n since by definition y 
differs from the n-th number in our list by precisely the n-th decimal 
digit. (y is defined by the diagonal entries in our list, hence the 
term "diagonalization proof.")

We have produced a number that's not in our list! This is a glaring
contradiction. A one-to-one correspondence between the natural numbers
and (0,1) is impossible. Therefore the set (0,1), and by extension,
the set of real numbers, is innumerable.

As it turns out, the set of rational numbers IS countable 
(denumerable), but the set of real numbers is uncountable 
(innumerable). Since the set of real numbers can be expressed 
(logically) as the union of the set of rational numbers and the set of 
irrational numbers, it follows that the set of irrational numbers has 
to be uncountable. This is a simple consequence of the theorem: the 
union of countably many countable sets is itself countable.  If the 
set of irrational numbers were countable, we'd reach the (wrong) 
conclusion that the set of real numbers was itself countable, contrary 
to what we've already established. We are forced by logic to conclude 
that we have innumerably many irrational numbers, even though we 
haven't produced a single example of what an irrational number looks 
like.

So yes. A different (and "greater") infinity applies to the irrational
numbers. The cardinality of the continuum has historically been
designated by c. So, the result we've just established is that
aleph_0 < c, where aleph_0 is the cardinality of the set of natural
numbers.

I hope these explanations clear up any doubts in your mind. You are, 
of course, free to argue back if any of my points aren't convincing
enough for you.

- Doctor Luis, The Math Forum
  http://mathforum.org/dr.math/