The Cantor bus tour

This is post # 5 of the series on the Euclidean topology of the real line. See the links at the bottom for other posts in the series.

Steven Strogatz is a professor of applied math at Cornell University. He also writes a column in New York Times on math. The latest column and the last in 2010 (May 9, 2010) is titled The Hilbert Hotel. We admire anyone who can write math for popular audience and can make it seem so natural and interesting. In this latest column, professor Strogatz ventures into the world of infinity that is the legacy of Georg Cantor (introduced in the late 1800s). His illustration of infinity is through the telling of the parable of a grand hotel that is now called Hilbert Hotel (in honor of David Hilbert).

The Hilbert Hotel has infinitely many rooms (labeled by the positive integers). Even when it is full, the hotel manager can always accommodate another guest. In fact, when the hotel is full, it can even accommodate infinitely many guests (e.g. guests are labeld by the positive integers). Even stranger still, when the infinitely many guests are labeled by fractions $\frac{p}{q}$ where $p$ and $q$ are positive integers, the Hilbert Hotel, if the manager knows some set theorey, can still find rooms for these guests (in the parable, the fractions $\frac{p}{q}$ are in the form of infinitely many buses and each bus has infinitely many guests). However, the Hilbert Hotel cannot accommodate the guests if the infinitely many guests are labeled by the real numbers within the unit interval $[0,1]$.

So the Hilbert Hotel parable illustrates better than numbers and points that the rational numbers can be put in a one-to-one correspondance with the positive integers while the real numbers between zero and one cannot be put in a one-to-one correspondance with the positive integers. In other words, the cardinality of the set of all real numbers is greater than the cardinality of the set of integers.

The column by Professor Strogatz illustrates that we can make an exhaustive list of the positive rational numbers (fractions of two integers) and the listing is indexed by the positive integers. On the other hand, the real numbers between zero and one cannot be listed out exhaustively in an integer indexed listing. When the elements of a set can be listed by a listing indexed by the integers, we say the set is a countable set. Otherwise, the set is said to be an uncountable set. Right off the bat, the handy examples of countable sets are the set of all positive integers, the set of all integers and the set of all positive rational numbers. With just a little more care, the set of all rational numbers is a countable set too. The set of all real numbers is an uncountable set.

In preparation for a subsequent post, we would like to demonstrate that the set of sequences of 0’s and 1’s is an uncountable set. Our device is not a hotel but rather the tossing of infinitely many coins (the number of coins is infinite as in the positive integers and not the real numbers). Suppose we toss infinitely many coins. Record a tail as 0 and record a tail as 1. The following is one example of an outcome where the first toss results in a tail, the second toss results in a head and so on:

$\displaystyle (0,1,0,1,1,0,0,0,1, \cdots)$

How many such outcomes are possible? Can the set of all such sequences be listed exhaustively by the integers? The answer is no. Suppose we can do so and the following is the exhaustive listing:

$\displaystyle x_1=(x_{1,1}, \ x_{1,2}, \ x_{1,3}, \ x_{1,4}, \ x_{1,5}, \cdots)$
$\displaystyle x_2=(x_{2,1}, \ x_{2,2}, \ x_{2,3}, \ x_{2,4}, \ x_{2,5}, \cdots)$
$\displaystyle x_3=(x_{3,1}, \ x_{3,2}, \ x_{3,3}, \ x_{3,4}, \ x_{3,5}, \cdots)$
$\displaystyle x_4=(x_{4,1}, \ x_{4,2}, \ x_{4,3}, \ x_{4,4}, \ x_{4,5}, \cdots)$
$\displaystyle x_5=(x_{5,1}, \ x_{5,2}, \ x_{5,3}, \ x_{5,4}, \ x_{5,5}, \cdots)$
$\displaystyle \cdot$
$\displaystyle \cdot$
$\displaystyle \cdot$

Each $x_{i,j}$ is either 0 or 1 and is the result of the $j^{th}$ toss in the $i^{th}$ sequence in the list. We consider the terms in the diagonal $x_{1,1}, x_{2,2},x_{3,3}$ and so on. Then for each $i=1,2,3, \cdots$, define $y_i$ as the following:

$\displaystyle y_i=\left\{\begin{matrix}0&\thinspace x_{i,i}=1 \\{1}&\thinspace x_{i,i}=0 \end{matrix}\right.$

Then $y=(y_1,y_2,y_3, \cdots)$ is an outcome of tossing infinitely many coins that is not on the listing. Thus, in attempting to make an exhaustive listing, we can always come up with another outcome that is not on the listing. This means the set of all possible sequences of 0’s and 1’s is an uncountable set. In the next post, we will show that it is the same size as the real numbers. These sequences of 0’s and 1’s are important in the construction of the Cantor set.

Links to previous posts on the topology of the real line:
The Euclidean topology of the real line (1)
The Euclidean topology of the real line (2)
The Euclidean topology of the real line (3) – Completeness
The Euclidean topology of the real line (4) – Compactness