Cantor's Solution: Denumerability

A Math Forum Project

Table of Contents:

Famous Problems Home

The Bridges of Konigsberg
· Euler's Solution
· Solution, problem 1
· Solution, problem 2
· Solution, problem 4
· Solution, problem 5

The Value of Pi
· A Chronological Table of Values
· Squaring the Circle

Prime Numbers
· Finding Prime Numbers

Famous Paradoxes
· Zeno's Paradox
· Cantor's Infinities
· Cantor's Infinities, Page 2

The Problem of Points
· Pascal's Generalization
· Summary and Problems
· Solution, Problem 1
· Solution, Problem 2

Proof of the Pythagorean Theorem

Proof that e is Irrational

Book Reviews



In the example on the previous page, student B matched each number with its double, which resulted in the following correspondence:

...-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5...
..-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10..

The integers can be put into correspondence with the natural numbers like this:

1,  2, 3,  4, 5,...
0, -1, 1, -2, 2,...

Now, Cantor made the following definition:

Definition: Two sets are equal in magnitude (i.e. size) if their elements can be put into one-to-one correspondence with each other.

This means that the natural numbers, the integers, and the even integers all have the 'same number' of elements. Cantor denoted the number of natural numbers by the transfinite number (pronounced aleph-nought or aleph-null). For ease of notation, we will call this number d, since the set of all natural numbers (and all sets of equal magnitude) are often called denumerable. A set is denumerable, then, if and only if it can be written as an infinite sequence {a1, a2, a3,...}, where the subscripts correspond to the natural numbers. In this case a1 corresponds to the natural number 1, a2 to 2, and so on.

Numbers that denote the magnitudes of sets are called cardinal numbers. For finite sets, the cardinal numbers are the whole numbers. A cardinal number X is said to be greater than a cardinal number Y if a set of magnitude X has a proper subset (a subset that is not the set itself) of order Y, but a set of order Y does not have a proper subset of order X. Since any infinite set contains a set of the type {a1, a2, a3,...}, d is the smallest transfinite number.

Theorem: The set of rational numbers is denumerable, that is, it has cardinal number d.

At first, one would think that there are 'more' rational numbers than natural numbers, since there is an infinite number of other rational numbers between any two distinct rational numbers. This is not true of the natural numbers. However, Cantor proved the above theorem this way:

Since d is the smallest transfinite number, we just need to prove that a set that contains the rationals is denumerable. That is, the set of rationals is an infinite set, so it has magnitude at d, and it cannot have magnitude greater than a set that it is contained in. Consider this set:

This set contains the rationals (many of them more than once). Now, order this set this way:

This gives a denumerable set {1, 2, 1/2, 1/3, 2/2, 3...}

Now start with zero and include every number's negative, to get the set

    {0, 1, -1, 1/2, -1/2, 1/3, -1/3, 2/2, -2/2, 3, -3...}

Thus a set that includes the rationals has been put into a systematic one-to-one correspondence with the natural numbers:

to Infinite Sets
to the Problem of Points (Probability)

[Privacy Policy] [Terms of Use]

Home || The Math Library || Quick Reference || Search || Help 

© 1994- The Math Forum at NCTM. All rights reserved.

August, 1998