Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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!

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

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/
```
Associated Topics:
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search