Cantor's diagonal argument

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

With its first diagonal argument Cantor showed that the set of rational numbers is countable, he gave a one-to -one mapping ( a bijection ) between the set of natural numbers and the set of rational numbers to. This figure allows vividly to order all rational numbers in a countably infinite sequence.

By contradiction, he showed that there is no such a row for the real numbers, i.e., no bijection to natural numbers.

This evidence is not Cantor's first proof of the uncountable of real numbers. Cantor's first Überabzählbarkeitsbeweis in 1874, published three years before his diagonal argument. The first proof works with other properties of real numbers and completely without a number system.

Proof of uncountable real numbers

Be any infinite sequence of real numbers in the open interval. We will show that there is at least a real number in the interval that does not occur in the sequence. Since this argument applies to any sequence, there can be no sequence containing all real numbers in the interval.

The figures in this presupposed as given sequence seen in its decimal fraction Development as follows:

Here are the real numbers and the decimal places of real numbers. The diagonal elements are highlighted, from these we construct a new number

Each number in the sequence defined in the following way by one decimal place.

In general, we define for each natural number that:

As we go through the entire sequence and obtain a number, which is different from all numbers in the sequence and that is greater than 0 and less than 1. This number is called the diagonal number, which is associated with the sequence.

The result therefore does not contain all real numbers between 0 and 1 If you choose another result, you may receive another diagonal number, but we have proved: For any sequence of numbers between 0 and 1 there is a number between 0 and 1, which is not included in this series. Therefore no consequence all real numbers between 0 and 1 conceived with consequences as pictures, so there is no surjective map. The interval is thus neither equal to powerful, yet finite, hence uncountable.

Since the interval under consideration is a subset of the set of all real numbers is uncountable fortiori: For every surjective map immediately a surjective mapping could win. In fact, even to be equally powerful, as one based on a suitable bijection, for example, recognizes.

Generalization: cardinality of the power set of a set

With a more general form of the above proof showed Cantor that the power set of any set is more powerful than this amount. Specifically, it showed: No onto mapping from on. This statement is also called the set of Cantor.

In earlier evidence from 1891 Cantor showed the greater power of the images from to, which can be bijectively mapped to the subsets of, ie to the power set. The relation to the proof of you can - about - seen when subsets as a result of 0s and 1s writes ( or for ) and interprets them as digits development.

Point of view of constructivists

Met with criticism is Cantor's proof of the uncountable real numbers by the second diagonal process with Leopold Kronecker, Hermann Weyl, Luitzen Brouwer, Henri Poincaré and Ludwig Wittgenstein. Constructivists suggest that Cantor's diagonal method other than Cantor. It is self- understood as a number construction method is selected in the not some sort of order, but a concrete order ( a certain sequence ) of countable output quantity is required. The discovered by the diagonal method property of constructive mathematicians as openness or indefiniteness (Paul Lorenzen, Christian Thiel ) viewed the sets of real numbers rather than the uncountable amount. Just as one can expand about the set of integers to the set of rational numbers, so one could also extend the algebraic numbers by algebraic cases of new diagonal numbers or transcendental numbers and obtains more and more countable sets of reals.