Cantor's diagonal argument

concept in set theory

Cantor's diagonal argument is a mathematical method to prove that two infinite sets have the same cardinality.[a] Cantor published articles on it in 1877, 1891 and 1899. His first proof of the diagonal argument was published in 1890 in the journal of the German Mathematical Society (Deutsche Mathematiker-Vereinigung).[2] According to Cantor, two sets have the same cardinality, if it is possible to associate an element from the second set to each element of the first set, and to associate an element of the first set to each element of the second set.

Cantor's first diagonal argument

change

The example below uses two of the simplest infinite sets, that of natural numbers, and that of positive fractions. The idea is to show that both of these sets,   and   have the same cardinality.

First, the fractions are aligned in an array, as follows:

 

Next, the numbers are counted, as shown. Fractions which can be simplified are left out:

 

That way, the fractions are counted:

 

By omitting fractions that can still be simplified, there is a bijection which associates each element of the natural numbers, to one element of the fractions:

To show that all natural numbers and the fractions have the same cardinality, the element 0 needs to be added; after each fraction its negative is added;

 

That way, there is a complete bijection, which associates a fraction to each natural number. In other words: both sets have the same cardinality. Today, sets that have the same number of elements than the set of natural numbers are called countable. Sets which have fewer elements than the natural numbers are called at most countable. With that definition, the set of rational numbers / fractions is countable.

Infinite sets often have properties which go against intuition: David Hilbert showed this in an experiment which is called Hilbert's paradox of the Grand Hotel.

Real numbers

change

The set of real numbers does not have the same cardinality than those of the natural numbers; there are more real numbers than natural numbers. The idea outlined above influenced his proof. In his 1891 article, Cantor considered the set T of all infinite sequences of binary digits (i.e. each digit is zero or one).

He begins with a constructive proof of the following theorem:

If s1, s2, … , sn, … is any enumeration of elements from T, then there is always an element s of T which corresponds to no sn in the enumeration.

To prove this, given an enumeration of elements from T, like e.g.

s1 = (0, 0, 0, 0, 0, 0, 0, ...)
s2 = (1, 1, 1, 1, 1, 1, 1, ...)
s3 = (0, 1, 0, 1, 0, 1, 0, ...)
s4 = (1, 0, 1, 0, 1, 0, 1, ...)
s5 = (1, 1, 0, 1, 0, 1, 1, ...)
s6 = (0, 0, 1, 1, 0, 1, 1, ...)
s7 = (1, 0, 0, 0, 1, 0, 0, ...)
...

The sequence s is constructed by choosing the 1st digit as complementary to the 1st digit of s1 (swapping 0s for 1s and vice versa), the 2nd digit as complementary to the 2nd digit of s2, the 3rd digit as complementary to the 3rd digit of s3, and generally for every n, the nth digit as complementary to the nth digit of sn. In the example, this yields:

s1 = (0, 0, 0, 0, 0, 0, 0, ...)
s2 = (1, 1, 1, 1, 1, 1, 1, ...)
s3 = (0, 1, 0, 1, 0, 1, 0, ...)
s4 = (1, 0, 1, 0, 1, 0, 1, ...)
s5 = (1, 1, 0, 1, 0, 1, 1, ...)
s6 = (0, 0, 1, 1, 0, 1, 1, ...)
s7 = (1, 0, 0, 0, 1, 0, 0, ...)
...
s = (1, 0, 1, 1, 1, 0, 1, ...)

By construction, s differs from each sn, since their nth digits differ (highlighted in the example). Hence, s cannot occur in the enumeration.

Based on this theorem, Cantor then uses a proof by contradiction to show that:

The set T is uncountable.

He assumes for contradiction that T was countable. In that case, all its elements could be written as an enumeration s1, s2, … , sn, … . Applying the previous theorem to this enumeration would produce a sequence s not belonging to the enumeration. However, s was an element of T and should therefore be in the enumeration. This contradicts the original assumption, so T must be uncountable.

  1. The cardinality of a set means the number of its elements.[1]

References

change
  1. "Finite and Infinite Sets". Computer Science. University of Texas at Austin. Archived from the original on 30 August 2016. Retrieved 28 August 2016.
  2. "Uber ein elementare Frage der Mannigfaltigkeitslehre". The Logic Museum. Retrieved 28 August 2016.