**Society Investigating Mathematical
Mind-Expanding Recreations**

Numbers--Finite and Infinite

Prof. A. I. F. Urquhart

This is a summary of what was presented and discussed
at the February 26th **SIMMER** meeting, along with some problems and
questions to think about.

We start from the basic idea of a *set*, or collection of objects.
For example, the set of all prime numbers, or the set of inhabitants of
Ontario in January 1998. Two sets are the same if
they have exactly the same members;
for example, the set of all even prime numbers greater than 2
is the same set as the set of all unicorns, namely the empty set
with no members. A set A is a *subset* of
a set B if every member of A is a member of B;
A is a *proper* subset of B if it is a subset of B, but
B is not a subset of A.
For example, the set of all prime numbers is a proper subset of
the set of all integers.

Cantor defined two sets to have the same *cardinal number* if
they can be put in one-to-one correspondence with each other.
We write |X| for the cardinal number of a set X;
for example, if X is the set {1,2,3}, then
|X| = 3.
By this definition, the set of positive even integers and the set of
all positive integers have the same cardinal number, because we can set up
the one-to-one correspondence
1 -> 2, 2 -> 4, 3 -> 6, ... .
This may seem surprising since there are infinitely many odd positive
integers, so it seems there should be *more* positive integers
than even positive integers.
But remember we are talking about an *infinite* set.
In fact, we can take it as a *definition* of an infinite set
that there is a one-to-one correspondence between the set and
a proper subset of itself.
So, according to our definition, all we have proved is that the positive
integers form an infinite set, which is as it should be.

**Problem 1:**
Let (0,1) stand for the open unit interval, that is to say, the
set of points on a line strictly between
0 and 1; for example, 0.5 and 0.99999999 belong to the set (0,1),
but 0 and 1 don't. Show that there is a one-to-one correspondence between
the open unit interval (0,1) and the set of *all*
real numbers, that is to say, the set of all points on an infinite straight
line.
(**Hint:** It may help to think in terms of geometrical pictures here.)

**Problem 2:** A *positive rational number* can be written as
a fraction a/b; notice that two different fractions can represent
the same rational number, for example, 2/3 = 4/6.
Show that the set of all positive rational numbers is denumerable.
(**Hint:** Think of a way of listing all fractions systematically,
and then eliminating repetitions.)

Here is a slightly trickier problem along the same lines.
Let's define a *word* to consist of a finite string of lower case
letters from the English alphabet.
For example, `aaa', `abcazfajdksl' and `fehfiskebvkdowjkmd' are all words
according to this definition.

**Problem 3:**
Show that the set of all words is denumerable.

A real number is defined to be *algebraic* if it is
the root of an equation

a_n x^n + a_(n-1) x^(n-1) + ... + a_1 x + a_0 = 0,where a_n not equal to0, and all the a_i's are integers. For example, although sqrt(2) is not a rational number, it is an algebraic number, since it is a root of the equation x^2 = 0. The next problem should not be too hard, if you have figured out how to do the last one.

**Problem 4:**
Show that the set of all algebraic numbers is denumerable.

**Problem 5:**
Show that the set of all sets of positive integers is not
denumerable.
(**Hint:** Assume that you can list all sets of positive integers
as X_1, X_2, ..., and then, to get a contradiction, try to
define a set that is not in the list.
This is not an easy problem if you haven't seen it before!)

We can generalize the result of the last problem.
For any set X, we define the *powerset* of X,
written P(X), to be the set of all subsets of X, including
the empty set. If X is a finite set with 5 members, for
example, then P(X) has 2^5 = 32 members.
If X and Y are two sets, and there is a one-to-one
correspondence between X and a subset of Y, then
we say that the cardinal number of X is less than equal to that
of Y, written |X| <= |Y|.
If |X| <= |Y|, but |X| not equal to |Y|, then we say that
|X| is *strictly less than* |Y|, written |X| < |Y|.

**Problem 6:**
For any set X, show that the cardinal number of X is strictly
less than the cardinal number of P(X), i.e.,
|X| < |P(X)|.

So, from the result of problem 6, we know that not only is there more than one infinite number, there is actually an infinite ascending sequence of them. Cantor's hierarchy of infinite numbers starts

aleph_0, aleph_1, aleph_2, ..., aleph_omega, aleph_(omega+1) ...and on into the mists of the transfinite where only hardened professional set theorists dare to peep!

Here is one more problem about comparing sizes of infinite numbers. It is not quite as easy as it looks.

**Problem 7:**
Let X be an infinite set (defining "infinite" as we did above).
Show that X has a denumerable subset.

The answer to the last problem shows that aleph_0 is the smallest infinite number. The answer to the problem involves a famous axiom of set theory known as "the axiom of choice," since it allows us to define a set by performing infinitely acts of selection or "choice."

**Problem 8:** Show that aleph_0 + 1998 = aleph_0 and
that aleph_0 + aleph_0 = aleph_0.

To multiply two infinite numbers, we proceed as follows. Let X and Y be two sets with cardinal numbers |X| and |Y|. Then the product of |X| and |Y|, which we'll write as |X|·|Y|, is the cardinal number of the Cartesian product X x Y of X and Y, that is to say, the set of all ordered pairs <x, y >, where x is in X and y is in Y.

**Problem 9:**
Show that aleph_0 ·aleph_0 = aleph_0.

**Problem 10:**
Let C be the cardinal of the continuum, that is,
the cardinal of the set of all positive real numbers less than or equal
to 1.
Show that C·C = C.

The answer to Problem 10 is intuitively surprising, because it can be interpreted as saying that there exactly as many points on a line as in a two-dimensional space, thus showing that the notion of dimension cannot be characterized in terms of cardinality. This seemed so surprising to Cantor that when he discovered it in 1878 he wrote in a letter to his friend Richard Dedekind: "I see it, but I don't believe it!"

**Problem 11:** Is there a cardinal number *strictly*
between aleph_0 and the number C of the continuum?

Problem 11 is known as Cantor's Continuum Problem. It is still unsolved, but we also know that in a certain sense it is unsolvable. It has been proved that the problem cannot be solved using only the commonly accepted assumptions of the modern theory of sets. Whether the problem can be solved by inventing new axioms about sets and numbers is a difficult problem in the philosophy of mathematics.

Navigation Panel:

Switch to graphical version (better pictures & formulas)

Access printed version in PostScript format (requires PostScript printer)

Go to SIMMER Home Page

Go to The Fields Institute Home Page

Go to University of Toronto Mathematics Network Home Page