Cantor's second diagonal argument

Cantor's second diagonal argument is a mathematical proof that the set of real numbers is uncountable , and more generally that the mappings of a set to {0,1} and the power set of a set are more powerful than this set. The mathematician Georg Cantor found this proof in 1877 and gave the two generalizations in 1891 and 1899.

With his first diagonal argument , Cantor showed that the set of rational numbers can be counted ; he gave a reversibly unique mapping (a bijection ) between the set of natural numbers and the set of rational numbers. This illustration clearly allows all rational numbers to be arranged in a countably infinite sequence .

By contradiction he showed that there is no such sequence for the real numbers ; H. no bijection to the natural numbers.

This proof is not Cantor's first proof of the uncountability of real numbers. Cantor's first proof of uncountability was published in 1874, three years before his diagonal argument. The first proof works with other properties of the real numbers and gets by without a number system .

Proof of the uncountability of real numbers

Let be any sequence of real numbers in the open interval . We will show that there is at least one real number in this interval that does not appear in the sequence . Since this reasoning holds for any sequence , there can be no sequence that contains all real numbers in the interval . ${\displaystyle (z_{i})}$ ${\displaystyle (0,1)}$ ${\displaystyle (z_{i})}$ ${\displaystyle (z_{i})}$ ${\displaystyle (0,1)}$

The numbers in this given sequence look like this in their decimal fraction development :

${\displaystyle z_{1}=0,{\underline {a_{11}}}\ a_{12}\ a_{13}\ldots }$

${\displaystyle z_{2}=0,a_{21}\ {\underline {a_{22}}}\ a_{23}\ldots }$

${\displaystyle z_{3}=0,a_{31}\ a_{32}\ {\underline {a_{33}}}\ldots }$

${\displaystyle z_{4}=\ldots }$

${\displaystyle \vdots }$

Here are the real numbers and the decimal places of those real numbers. The diagonal elements are highlighted, from which we construct a new number ${\displaystyle z_{i}}$ ${\displaystyle a_{ij}}$

${\displaystyle x=0,x_{1}x_{2}x_{3}\ldots ;\qquad }$

Each number in the sequence defines a decimal of in the following way . ${\displaystyle z_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x}$

If it is, we bet , otherwise . This definition ensures that is a different number than . ${\displaystyle a_{11}=5}$ ${\displaystyle x_{1}=4}$ ${\displaystyle x_{1}=5}$ ${\displaystyle x}$ ${\displaystyle z_{1}}$

If it is, we bet , otherwise . This applies . ${\displaystyle a_{22}=5}$ ${\displaystyle x_{2}=4}$ ${\displaystyle x_{2}=5}$ ${\displaystyle x\neq z_{2}}$

In general we define for every natural number : ${\displaystyle i}$

If it is, we bet , otherwise . This applies . ${\displaystyle a_{ii}=5}$ ${\displaystyle x_{i}=4}$ ${\displaystyle x_{i}=5}$ ${\displaystyle x\neq z_{i}}$

So we go through the whole sequence and get a number that differs from all numbers in the sequence in at least one decimal place and which is greater than 0 and less than 1. This number is called the diagonal number that is assigned to the sequence . ${\displaystyle x}$ ${\displaystyle (z_{i})}$

So the sequence does not contain all real numbers between 0 and 1. If you choose a different sequence, you may get a different diagonal number, but we have proven that for every sequence of numbers between 0 and 1 there is a number between 0 and 1 that is not included in this episode. Therefore, no sequence contains all real numbers between 0 and 1. If sequences are understood as mappings , there is no surjective map . The interval is therefore neither equal to nor finite, and therefore uncountable . ${\displaystyle (z_{i})}$ ${\displaystyle \mathbb {N} \to (0,1)}$ ${\displaystyle \mathbb {N} \to (0,1)}$ ${\displaystyle (0,1)}$ ${\displaystyle \mathbb {N} }$

Since the observed interval is a subset of the set of all real numbers, it is even more uncountable: From every surjective mapping a surjective mapping can be obtained immediately . In fact, it is even irrelevant , as one recognizes by means of a suitable bijection, for example . ${\displaystyle (0,1)}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {N} \to \mathbb {R} }$ ${\displaystyle \mathbb {N} \to (0,1)}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle (0,1)}$ ${\displaystyle x\mapsto {\tfrac {1}{1-x}}-{\tfrac {1}{x}}}$

Generalization: cardinality of the power set of a set

→ Main article : Cantor's theorem

Using a more general form of the above proof, Cantor showed that the power set of any set is more powerful than that set. More precisely he showed: There is no surjective mapping of on . This statement is also called Cantor's theorem . ${\displaystyle A}$ ${\displaystyle {\mathcal {P}}(A)}$

In the older proof from 1891, Cantor showed the greater power of the mappings from after , which can be mapped bijectively to the subsets of , i.e. to the power set. The connection to the proof of can be seen - roughly - if one writes subsets as a sequence of 0s and 1s (for or ) and interprets them as digit expansion. ${\displaystyle A}$ ${\displaystyle \{0,1\}}$ ${\displaystyle A}$ ${\displaystyle |\mathbb {N} |<|\mathbb {R} |}$ ${\displaystyle X\subset \mathbb {N} }$ ${\displaystyle n\not \in X}$ ${\displaystyle n\in X}$

Constructivist point of view

Cantor's proof of the uncountability of real numbers using the second diagonal method has met with criticism from Leopold Kronecker , Hermann Weyl , Luitzen Brouwer , Henri Poincaré and Ludwig Wittgenstein . Constructivists interpret Cantor's diagonal method differently than Cantor. It is itself understood as a number construction method in which not any order is chosen, but a concrete order (a certain sequence) of the countable initial set is assumed. The property discovered by the diagonal method is viewed by constructive mathematicians as openness or as indefiniteness ( Paul Lorenzen , Christian Thiel ) of the sets of real numbers and not as the uncountability of a set. Just as one can extend the set of whole numbers to the set of rational numbers, so one can also extend the algebraic numbers by algebraic envelopes over new diagonal numbers or transcendent numbers and thus get ever larger countable sets of real numbers.

Individual evidence

1. ^ Herbert Meschkowski : Georg Cantor. Life, work and effect. 2nd, expanded edition. Bibliographical Institute. Mannheim u. a. 1983, ISBN 3-411-01653-1 , pp. 85 f.
2. ↑ Georg Cantor: On an elementary question of the theory of manifolds . In: German Mathematicians Association (ed.): Annual report of the German Mathematicians Association . tape 1 . Reimer, 1892, ISSN  0012-0456 , p. 75-78 ( uni-goettingen.de ).