Table of Contents:
The Bridges of Konigsberg
The Value of Pi
Prime Numbers
Famous Paradoxes
The Problem of Points Proof of the Pythagorean Theorem

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...
The integers can be put into correspondence with the natural numbers like this:
1, 2, 3, 4, 5,...
Now, Cantor made the following definition: Definition: Two sets are equal in magnitude (i.e. size) if their elements can be put into onetoone 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 alephnought or alephnull). 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 {a_{1}, a_{2}, a_{3},...}, where the subscripts correspond to the natural numbers. In this case a_{1} corresponds to the natural number 1, a_{2} 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
Thus a set that includes the rationals has been put into a systematic onetoone correspondence with the natural numbers:

[Privacy Policy] [Terms of Use]
Home  The Math Library  Quick Reference  Search  Help