Cantor's Legacy: Infinity and Diagonalization

Georg Cantor (1845-1918)

The Ideal Computer

The ideal computer has infinite memory. There are two ways to look at this:

• Platonic version: One memory location for each natural number 0, 1, 2, …
• Aristotelian version: Whenever you run out of memory, the computer contacts the factory. A maintenance person is flown in by helicopter and attaches 100 Gigs of RAM and all programs resume their computations, as if they had never been interrupted.

When a program is running on the ideal computer, there is no bound on the amount of memory and no bound on the amount of time. You can run a Java program and never have any overflow, or out of memory errors.

An ideal computer can be programmed to print out:

• : 3.14159265358979323846264…
• : 2.0000000000000000000000…
• : 2.7182818284559045235336…
• : 0.33333333333333333333…
• : 1.6180339887498948482045…

Computable and Describable Numbers

We say that program prints out the infinite sequence if, when is executed on an ideal computer, a sequence of symbols appears on the screen such that

• The th symbol is , and
• For every , eventually prints the th symbol. That is, the delay between symbol and symbol is not infinite.

A real number is computable if there is a program that prints out a decimal representation of from left to right. Thus, each digit of will eventually be printed as part of the output sequence.

Are all real numbers computable?

A real number is describable if it can be unambiguously denoted by a finite piece of English text. For example:

• : "Two."
• : "The area of a circle of radius one."

Is every computable real number also a describable real number? To summarize:

• computable: some program outputs .
• describable: some sentence denotes .

Theorem. Every computable real number is also describable.

Proof. Let be a computable real that is output by a program . The following is an unambiguous description of : "The real number output by the following program: ."

The point is that a computer program can be viewed as a description of its output.

Are all real numbers describable?

Correspondence Principle

If two finite sets can be placed into 1-1, onto correspondence, then they have the same size. That is, two sets are the same size if there is a bijection between their members. This definition was given by Georg Cantor in 1874. Note that the size of a set is called its cardinality.

Examples

Let be the set of natural numbers, and let be the set of even natural numbers. Do and have the same cardinality?

The intuitive answer might be: and do not have the same cardinality! is a proper subset of with plenty left over. The correspondence in mind, does not take onto .

But and do have the same cardinality! Look at the following correspondence:

	0	1	2	3	4	5	…
	0	2	4	6	8	10	…

This is , and it is a bijection between and .

Cantor's definition only requires that some 1-1 correspondence between the two sets be a bijection, not that all 1-1 correspondences be bijections. This distinction never arises when the sets are finite.

Let be the set of integers. Do and have the same cardinality?

Again, the intuitive answer is no. is infinite in two ways: from zero to positive infinity and from zero to negative infinity. Therefore, there are far more integers than naturals. Actually, that's not true. and do have the same cardinality! Here is a bijection:

	0	1	2	3	4	5	6	…
	0	1	-1	2	-2	3	-3	…

Transitivity Lemma

Here is a lemma that's useful when reasoning about cardinalities:

Lemma. If is a bijection, and is a bijection, and , then is a bijection between and .

Using this lemma, we can conclude that , , and all have the same cardinality.

The Rational Numbers

Let be the set of rational numbers. Do and have the same cardinality?

An argument for why not is that the rationals are "dense:" between any two rational numbers, there is another. Therefore, you can't possible list them one by one without leaving out an infinite number of them. But don't jump to conclusions! There is a clever way to list the rationals, one at a time, without missing a single one!

How about the sets (the set of all pairs of natural numbers) and ?

Theorem. and have the same cardinality.

Proof. Here is a bijection between the two sets:

Here's a picture of the function. The point represents the ordered pair . The numbers next to some of the points are , and the line shows the order in which ordered pairs are enumerated:

We can do something similar for the rational numbers. One way to enumerate them is shown in the figure below, where the point represents :

Actually, this enumeration repeats rationals (for example, ), but this is a detail that can be taken care of to produce a bijection.

Countable and Uncountable Sets

We call a set countable if there is a bijection between and the natural numbers. So far we know that , , , and are countable.

What about , the set of real numbers? Do and have the same cardinality? It turns out that unlike the set of rational numbers, the set of real numbers is uncountable. That is, there is no bijection between and . Cantor proved this using a technique called diagonalization.

Theorem. The set of real numbers between 0 and 1 is not countable.

Proof Suppose is countable. Then there exists a bijection between that set and the natural numbers. Let be such a bijection. Make a list as follows:

	decimal expansion of
	decimal expansion of
	decimal expansion of

For example, if , , , and , and column contains the th digit following the decimal point in the expansion, then would start like this:

Now, let be the th digit after the decimal point in the expansion of . Here is where the s appear in :

Consider the real number , where

isn't on the list , because it differs from the th entry in the list at the th position! Therefore, because no natural number is mapped to , but , is not onto. But then is not a bijection. This is a contradiction, so is not countable!

If is not countable, then is not countable either.

Why can't the same argument be used to show that is uncountable? The problem is that is not necessarily rational, so there is no contradiction if it is missing from the list .

Computable and Describable Numbers Again

Let be any finite alphabet. For example, . Then, is the set of all finite strings of symbols from , including the empty string .

Theorem. Every infinite subset of is countable.

Proof. Sort by first by length and then alphabetically. Map the first word to 0, the second to 1, and so on.

If is the set of symbols on a standard keyboard, then the set of all possible Java programs is a subset of as is the set of all possible finite pieces of English text. Therefore, the set of all possible Java programs is countable. The set of all possible finite length pieces of English text is also countable.

There are countably many Java program and uncountably many reals. Therefore, most real numbers are not computable!

There are countably many English descriptions and uncountably many reals. Therefore, most real numbers are not describable!

Power Sets

We know there are at least 2 infinities: the cardinality of and the cardinality of . Are there more?

The power set of is the set of all subsets of . The power set is denoted .

Proposition. If is finite, the power set of has cardinality .

Proof. Recall the bijection between and binary strings of length .

What if is infinite?

Theorem. There is no bijection between and .

Proof. Suppose is a bijection. Let . and is onto, so there exists some such that . Now, is in ?

Suppose so. Then, by the definition of , the answer is no. This is a contradiction. So suppose is not in instead. Then, by definition, . This is again a contradiction. Since there is a contradiction in any case, is not a bijection. Therefore, and do not have the same cardinality. In fact, the cardinality of is strictly greater than the cardinality of , because is an injection from into .

The result is that there are at least a countable number of infinities. The first infinity is the size of countably infinite sets, called . Other infinities are

Cantor wanted to show that the number of reals was . He called this the "Continuum Hypothesis." However, he was unable to prove it. This helped fuel his depression. Much later, it turned out that the the Continuum Hypothesis can't be proved or disproved from the standard axioms of set theory! This has been proved!