Set Theory and Orders of infinity

Date: 04/08/97 at 21:06:07
From: Sergio
Subject: sizes or orders of infinity

Hello,

I am an Algebra II student, and I have been assigned a project 
concerning infinity.  I really need help with this.

I have been given the following sets and I am supposed to compare 
their size and explain what rationale I have used in doing so.
  
   A. (1,2,3,4)
   B. (a,b,c,d)
   C. (1,2,3,4,5)
   D. (1,2,3....)
   E. (2,4,6....)
   F  (-5,-4,-3,...)
   G  (1000,2000,3000,....)
   H. (all real numbers between 0 and 1)
   I  (all real numbers between -1 and 1)
   J. (all real numbers between 0 and 1000)
   K. (all rational numbers between 0 and 1)
   L. (the grains of sand in the sahara desert to a depth of 10 feet)
  
I have done some research, especially on Cantor's set theory, but it 
doesn't really make sense to me.  Could you please tell me how to 
label one set as being larger than another?  What criteria are used?

Thanks.

Date: 04/10/97 at 17:50:45
From: Doctor Daniel
Subject: Re: sizes or orders of infinity

Hi Sergio,

You asked about orders of infinity; specifically, you listed a bunch 
of sets, all of which were pretty well-specified, and wanted to know 
how to order them by size.

That's not terribly easy!  It's worth realizing that the rigorous 
mathematical definitions of things like "the real numbers between 0 
and 1" weren't well-developed until roughly 1900, and so it was very 
hard to also talk about things like "this infinite set is bigger than 
that one" until about that same time.  (As a side note, it may be for 
the best that they're hard to identify; Georg Cantor, who's 
responsible for much of the formal set theory that underlies these 
questions, went mad late in life and died in an asylum, as have some 
other people who have looked at them!)

Anyhow, here goes:

Basically, we say that two sets A and B have "equal cardinality" (or, 
more informally, are the same size), if we can map from one to the 
other so that every element of A has exactly one mapping in B, and 
every element of B is the mapping of exactly one element of A.  That's 
called a "bijection," or a "one-to-one" mapping.

Here's an easy example: The sets A = {1,2,3,4} and B = {A,B,C,D} have 
the same cardinality.  That's true because if we take 1 -> A, 2 -> B, 
3 -> C, and 4 -> D, each element of A has a companion in B, and each 
element of B is the companion of an element of A.  So A and B are the 
same size.

Here's a harder example: The sets A = {1,2,3,4,...} and 
B = {2,4,6,8,...} have the same cardinality.  Huh?  But doesn't A have 
all of those extra elements, like 1,3,5, etc.?  YES.  However, that 
doesn't matter.  Remember, we said that all we needed was the 
bijection, which is easy; map 1 -> 2, 2 -> 4, 3 -> 6, and so on.  
Every element a of A has a mapping in B, 2a, and every element b of B 
is the mapping of b/2.  So these two sets have the same size.  

I'll repeat the argument: B and A have the same size, because we can 
map every element of A to an element of B so that every element of B 
is taken exactly once as well. 

Here's another one: {1,2,3,4,5,...} has the same cardinality as 
{100000, 100001, 100002, 100003, ...}, even though the first set has 
100,000 more elements!  Just map 1 -> 100001, 2 -> 100002, etc., and 
the bijection is obvious.

This will take care of sets A through G and L on the list you gave; 
L is obviously an enormous finite set, so it's not able to be put in 
bijection with {1,2,3,4,...}; you'd have to leave elements of 
{1,2,3,4,...} that weren't the mapping of a grain of sand.  
So L has less cardinality than the infinite sets.

Now, there's two more types of sets you gave: Sets of all real numbers 
in an interval (like [0,1] or [1,10], and sets of rationals in [0,1].  
It should be clear that the cardinality of A = {all real numbers in 
[0,1]} is the same as the cardinality of B = {all real numbers in 
[1,10]).  Huh?  Well, let a be an element of A.  Map a to 9a + 1.  
This is clearly in [1,10].  Now, consider each b in B.  It is, 
clearly, the mapping of exactly one point, 1/9 * (b-1). 

That is, 1/9 * (b-1) was mapped by the mapping onto b. Moreover, it's
obvious that ONLY that value was mapped onto b. So every b in [1,10] 
is the mapping of exactly one element of A, and every element of A has 
exactly one mapping in B.  Hence [0,1] and [1,10] have the same 
cardinality!

That should help you compare between H, I, and J.  But what about the
difference between I and, say, D?  Are there more real numbers between 
0 and 1 than there are integers?  Eek!  Let's wait on that one.  (But 
the answer is yes.)

We've still got one type of set left; K = {the rationals between 0 and 
1.} Now, if we can come up with a way of mapping K onto D by a 
bijection, then there's as many integers as there are rationals 
between 0 and 1.  And, actually, that's true!  Here goes:

   Map 1 -> 0/1
   Map 2 -> 1/1
   Map 3 -> 1/2
   Map 4 -> 1/3
   Map 5 -> 2/3
   Map 6 -> 1/4
   Map 7 -> 3/4
   ...

In general, then, reduce all fractions to least terms.  List all the
fractions with 1 as their denominator, then the fractions with 2 as 
their denominator, then those with 3 as their denominator, and so on.  
(For example, we don't list 2/4, since it's already taken as 1/2.) 

Now, it's clear that this list is infinite; that is, each integer can 
be mapped to something.  Why?  Because just the list 1/1, 1/2, 1/3, 
etc. is infinite, and it's in least terms.  Also, we've made sure that 
we only take each fraction once; not more often.  And, since each 
fraction in [0,1] is taken exactly once, we do, in fact, wind up with 
a bijection.  If that's hard to understand, look at it a couple more 
times.  Basically, I've just shown that there's exactly as many 
fractions between [0,1] as there are positive integers.  That's 
counterintuitive, so it's not surprising if it's not immediately 
obvious!

Okay, so now here we are:  We know that all the finite sets are easily
ordered, that all the infinite subsets of the integers are of the same 
size, which is also the size of the rationals between [0,1], and that 
all the intervals on the real line like [0,1] or [1,10] all have the 
same cardinality.  

All that's left is that we need to find out how A = {the positive 
integers} and B = {the reals in [0,1]} compare.  It should be clear, 
now, that that's the same question as the question of how the 
rationals and the reals between [0,1] compare!

Now comes the biggie.  This is actually a hard proof, so read it a 
couple times if it's not clear the first time.  It's also a proof by 
indirection, which you probably aren't too familiar with.

I'm going to take advantage of this fact: The set of reals between 
0 and 1 is EXACTLY the same as the set of all infinite-length decimal 
numbers. 

Suppose that A and B have the same cardinality.  Then we know that 
there must be a bijection from A -> B.   That basically means there's 
a list of all the reals between 0 and 1, where all of them are listed 
exactly once; the mapping of 1, then the mapping of 2, and so on.  

So we have something like this:

   1 -> .043293084...
   2 -> .2359852423...
   3 -> .224390823...
   etc.

I show that there's at least one element of B which isn't on the 
list.  Look at the first decimal digit of 1's mapping.  It's 0.  
Hence, any number whose decimal doesn't have first digit 0 is not 
1's image.  Look at the second decimal digit of 2's mapping.  
It's 3.  Hence, any number whose decimal doesn't have second 
digit 3 is not 2's image.  So any number which starts .146... 
will not be the image of 1, 2, or 3.  

In general, if the k'th decimal digit of k's mapping is, say, t, 
then any number whose kth decimal digit isn't t (or 0 or 9, to 
avoid the possible .09999... = .10000 problem) will also not be the 
mapping of k!  So we can easily construct a number which is not the 
image of ANY integer; it differs in the first digit from the image 
of 1, in the second digit from the image of 2, and so on.  So it's 
not the image of ANY integer.  But it IS an infinite decimal, and 
hence a real number between 0 and 1.  So we have an element of B 
which is NOT the image of any element of A.  Hence, A has different 
cardinality (smaller) than B.  

That's almost certainly hard on the first (second, ...) reading, so 
give it a bit of a go.  This argument dates to Cantor and is called 
the "diagonalization" argument, since we kind of go down the diagonal 
of the decimals; we look at the first digit of 1's image, the 2nd of 
2's image, and so on.  It's absolutely the most common proof that 
there are more real numbers than there are integers (and hence 
rationals); while there are others, none are nearly as clean.  It 
might be obvious by looking at this, in fact, that there are LOTS 
more reals than integers; there are formalizable ways of looking at 
that which are much more complicated than I want to go here.

So let's recap:

To compare two sets, we know that they're equal in size (cardinality) 
if we can find a bijection between them, which is a mapping from one 
to the other, where every element of the first is mapped to exactly 
one element of the other set, and every element of the second set is 
the mapping of exactly one element of the first set.

It's very easy to find if two finite sets have the same cardinality, 
and all finite sets have smaller cardinality than all infinite sets.  

The integers are infinite, and all infinite subsets of the integers 
are of the same cardinality as is Z = {the integers}.  Even though 
we'd expect that there'd be more integers, say, than odd integers, 
this is actually false; there's exactly the same number.

The rational numbers between [0,1] and, actually, all rational 
numbers, have equal cardinality to the integers; there's the same 
number of rational numbers as there are integers.

Any interval of the real line has the same cardinality.  This is also 
true of the entire real line (We can map [0,1] to [1,infinity) easily 
by taking a and mapping it to 1/a; then, mapping onto the entire real 
line is fairly easy).  So [0,1] has the same cardinality as [1,1000], 
etc.

And, lastly, I showed that any interval of the real line has higher
cardinality than the integers, or the rationals, or, certainly, any 
finite set!

One last bit of terminology, before I let you go!  We say that any set 
which has equal cardinality with the integers is "countably infinite" 
or "denumerable."  A set which is finite or denumerable is 
"countable," and a set which is not countable is "uncountable" or 
"uncountably infinite."  So the rationals are countably infinite, 
while the reals are uncountable.  This is the first lesson in 
Cantorian Set Theory.  And if this seemed hard for starters, rest 
assured; they get worse!

Good luck.  If you have troubles with this answer, or any other 
problems, please don't hesitate to use us again!

-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/