Cantor's first uncountability proof

Cantor's first Überabzählbarkeitsbeweis is Georg Cantor's first proof that the real numbers form an uncountable set. It does not need the decimal or any other number system. The claim and the first evidence were discovered by Cantor in December 1873 and 1874 in Crelle's Journal (Journal for Pure and Applied Mathematics, Vol 77, 1874) published. Much was known to be second in 1877 found evidence of Cantor's second diagonal argument.

The set

Let R be a set that

• Contains at least two elements,
• Is totally ordered,
• Is densely ordered, that is between each item always another,
• No gaps has, that is, when R is partitioned into two non-empty subsets A and B, so that each element of A is smaller than each element of B, then there is an element C, so that each element is smaller than C, in A and each element is greater than C, is B. Where c is either from A or from B ( a so-called Dedekind cut ).

Then R is uncountable.

Meet The properties mentioned in particular as well as already on each interval arbitrarily chosen (eg [ 0,1] ), so that these quantities are in particular uncountable.

The proof

It should first be noted that to be sorted dense and totally out of the property already follows that between two elements of R with even need to be an infinite number of elements of R. If there were only finitely many, there would be here under a largest such. Between then and would have to be another element. But this would contradict the maximality of.

To prove the uncountable we assume that there is a sequence in R, the whole R as a sequence terms. We may without loss of generality. presuppose that applies (otherwise permute these two sequence elements ). Now we define two more episodes and:

The sequence is strictly increasing, the sequence is strictly decreasing, and the two sequences restrict each other, there is for each n Let be the set of elements of R that are smaller than all and is the complement. Then inter alia all and all, the two sets are therefore not empty. In addition, each element of each element is greater than of: Is and so there is by definition of a by; but then it follows by definition of. It is therefore in a Dedekind cut, so that there is an element c must be due to the completeness of R, for which in particular is true for every n.

Since c occurs as each element of R in the sequence, there is an index j such that is. This is true because is different from and. Is the smallest positive integer with the property that for a or applies. In both cases, a contradiction to the choice of i, as already or applies.

This contradiction can only be reversed by denies the existence of the sequence, that is, R is uncountable.

Real algebraic and transcendental numbers

In the same work of Cantor proved in 1874 that the set of real algebraic numbers is countable, from which immediately follows the existence of uncountably many transcendental numbers. The existence statement in itself was not new: Joseph Liouville in 1844 had some transcendental numbers explicitly specified.