Cantor's first diagonal argument

Cantor's first diagonal argument is a mathematical proof procedure with which one can possibly show that two infinite sets are of equal power.

This process was developed by Georg Cantor .

To understand the problem and the proof, it is necessary to replace the unspecified size of a set with the thickness formally defined in set theory :

Two sets are of equal power if and only if exactly one element of the other set can be assigned to each element of the one set, and vice versa, if there is a bijection between the sets.

While this is clear for sets with a finite number of elements ({1,2,3} and {6,8,10} are equal), the problem becomes obvious for sets with an infinite number of elements.

For example, the set of natural numbers and the set of positive even numbers are equally important, because one can inversely and unambiguously assign each natural number i its double 2 · i , although the positive even numbers are genuinely contained in the natural numbers.

Procedure for Cantor's first diagonal argument

Cantor's method is best illustrated with the simplest infinite set, the set of natural numbers , and the set of positive fractions . The statement is that the set of natural numbers and the set of positive rational numbers are equal. ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Q^{+}} }$

This can be shown by arranging the fractions in a two-dimensional scheme as follows:

${\displaystyle {\begin{array}{cccccccccc}{\tfrac {1}{1}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&&{\tfrac {1}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {2}{1}}&&{\tfrac {2}{2}}&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}&&{\tfrac {2}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}$

This scheme is then counted down diagonally, skipping fractions that are not completely abbreviated :

${\displaystyle {\begin{array}{lclclclclc}{\tfrac {1}{1}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&\\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&\\{\tfrac {3}{1}}\ _{\color {Blue}(4)}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}\ _{\color {Blue}(\cdot )}&&{\tfrac {3}{4}}&&{\tfrac {3}{5}}&\cdots \\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\nearrow }&&&&&&&&\\{\tfrac {5}{1}}\ _{\color {Blue}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}$

In this way one obtains a count of the positive rational numbers:

${\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\end{array}}}$

By skipping fractions that can be shortened, there is exactly one representative (the fraction that can no longer be shortened) in this enumeration for every positive rational number, which produces the desired bijection.

In order to show the equality of all rational numbers and natural numbers, this enumeration is extended. In front of the one you add a zero and behind each number its negative:

${\displaystyle {\begin{array}{cccccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}&-{\tfrac {1}{4}}&{\tfrac {2}{3}}&-{\tfrac {2}{3}}&\cdots \\\end{array}}}$

One obtains a bijection between the set of natural numbers and the set of rational numbers, which means that these two sets are equally powerful.

Sets which are equal to the set of natural numbers are called countable (or countable infinite ). Sets which are equal to any subset of the natural numbers are called at most countable (some also call this countable ). Sets that are equal to a bounded subset of the natural numbers are finite . The set of rational numbers is therefore countable.

Infinite sets often contradict intuition. This is illustrated , for example, by Hilbert's Hotel .

Power of the real numbers

The set of real numbers is not equal to the set of natural numbers, so the set is uncountable . It is also said that the real numbers have the width of the continuum . ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$

The proof of the uncountability of is the content of Cantor's second diagonal proof . ${\displaystyle \mathbb {R} }$

Generalization of Cantor's first diagonal argument

Cantor's first diagonal argument can be generalized in order to make comparable statements about sets of tuples of real numbers.

The following illustration is not the traditional 'first Cantor diagonal argument', but rather a rule for creating a 'fractal' object.

Georg Cantor has shown that there are curves (1 -dimensional objects) that can fill surfaces (2-dimensional objects) as follows:

Take a square area that is spanned by the corner points (0,0) and (3,3). Draw a distance from (0,0) to (3,3).

Visualization of the Cantor diagonalization
In the picture on the right, the course of the curve is made clear by the distance in the contact points, which is visible in sufficient magnification

Change this curve within the square as follows: Divide the square area into a grid of nine squares of equal size. Now change the course of the curve so that the following points form the end points of sections:

(0.0) - (1.1) - (0.2) - (1.3) - (2.2) - (1.1) - (2.0) - (3.1) - (2 , 2) - (3.3)

The modified curve has the property that it also runs through the square and has the same starting point and the same end point.

Repeat this process for each of the small sub-squares, and the resulting sub-squares and so on. The limit of this procedure is a curve that fills the entire square.

This (infinitely long) limit curve is the image of a continuous mapping φ of the interval [0, 1]. To do this, one first sets the end points φ (0) = (0,0), φ (1) = (3,3). The second step is to set the cornerstones of the first refinement:

0	→	(0.0)
1/9	→	(1.1)
2/9	→	(0.2)
3/9	→	(1.3)
4/9	→	(2.2)
5/9	→	(1.1)
6/9	→	(2.0)
7/9	→	(3.1)
8/9	→	(2.2)
1	→	(3.3)

Then in each step you set the additional corner points on values ​​between the previous numbers. The limit curve is then exactly the image of the image φ defined in this way. Note that this is not a bijection from [0, 1] to [0.3] × [0.3] because the mapping is surjective but not injective ; z. B. is φ (1/9) = φ (5/9).

While the number is one-dimensional, the associated coordinates are two-dimensional. Consequently, one can convert one-dimensional numbers into multidimensional numbers and vice versa. Sets of multi-dimensional elements are therefore no more powerful than sets of one-dimensional elements.

See also

• Cantor pairing function