Navigation Panel: Graphical Version | PostScript version | SIMMER Home Page | Fields Institute Home | U of T Math Network Home


Society Investigating Mathematical Mind-Expanding Recreations

February 1998 Feature Presentation
Numbers--Finite and Infinite
Prof. A. I. F. Urquhart

University of Toronto

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.

Set Theory and Infinite Numbers

The first consistent theory of infinite numbers was created just over a century ago by the German mathematician Georg Cantor (1845-1918). In this presentation, I shall introduce you to the most basic concepts of Cantor's theory. In spite of their simplicity, Cantor's ideas lead quickly into very difficult questions in the foundations of mathematics.

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.)

Denumerable sets

The sets of positive integers and positive even integers belong to an important class of infinite sets, the denumerable sets. We say that an infinite set is denumerable if it can be put in one-to-one correspondence with the set of positive integers. In other words, we can list the members of the set as an infinite list a_1, a_2, a_3, .... The cardinal number of a denumerable set was written by Cantor as aleph_0, pronounced "aleph nought" or "aleph zero."

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.

Nondenumerable sets

After all these examples of denumerable sets, you might think that all infinite sets are denumerable, so that aleph_0 is the only infinite cardinal number. It was perhaps Cantor's greatest discovery that this is not so.

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."

Arithmetic of infinite numbers

We can add and multiply infinite numbers just like finite numbers. Suppose we have two sets X and Y that are disjoint, that is to say, X and Y have no members in common. Then the sum of the cardinal numbers of the two sets, |X| + |Y|, is defined as the cardinal number of their union X UY, that is, the set whose members are all the members of X together with all the members of Y. In symbols, |X| + |Y| = |X UY|.

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!"

An Unsolvable Problem

Set theory is still an active area of research. The biggest problem that Cantor discovered is still an open question. The smallest infinite number aleph_0 is the cardinal number of the set N of positive integers. The answer to Problem 5 shows that the cardinal number C = |P(N)| is strictly greater than aleph_0. This number is also known as the number of the continuum, because it is the number of all points in the continuum of three-dimensional space.

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