# Cantor's first proof of uncountability

Cantor 's first proof of uncountability is Georg Cantor's first proof that the real numbers form an uncountable set. It works without the decimal system or any other number system . The claim and the first proof were discovered by Cantor in December 1873, and published in Crelles Journal in 1874 ( Journal for Pure and Applied Mathematics , Vol. 77, 1874). His second proof of this, found in 1877, Cantor's second diagonal argument , became much better known .

## The sentence

Be a crowd that ${\ displaystyle \ mathbf {R}}$

• contains at least two elements,
• totally ordered is
• is densely ordered , i.e. between every two elements there is always another,
• has no gaps, that is, if it is partitioned into two nonempty subsets and such that every element of is smaller than every element of , then there is an element such that every element that is smaller than in and every element that is larger as is, in lies. It is either off or off (compare Dedekind's cut ).${\ displaystyle \ mathbf {R}}$${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle c}$${\ displaystyle c}$${\ displaystyle A}$${\ displaystyle c}$${\ displaystyle B}$${\ displaystyle c}$${\ displaystyle A}$${\ displaystyle B}$

Then it is uncountable . ${\ displaystyle \ mathbf {R}}$

The properties mentioned apply in particular to as well as to any arbitrarily selected interval (e.g. ), so that in particular these quantities can be counted over . ${\ displaystyle \ mathbb {R}}$${\ displaystyle [0,1]}$

## The proof

First of all, it should be noted that from the property of being dense and totally ordered it already follows that there must be an infinite number of elements of between two elements of with . If there were only a finite number, there would be a largest among them, for example . Between and then have another element lie . But this would contradict the maximality of . ${\ displaystyle a, b}$${\ displaystyle \ mathbf {R}}$${\ displaystyle a ${\ displaystyle \ mathbf {R}}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle b}$${\ displaystyle x ${\ displaystyle x}$

To prove the uncountability we assume that there is a sequence in which has whole as sequential members. We may o. B. d. A. assume that holds (otherwise you swap these two parts of the sequence). Now we define two more sequences and : ${\ displaystyle (x_ {1}, x_ {2}, \ ldots)}$${\ displaystyle \ mathbf {R}}$${\ displaystyle \ mathbf {R}}$${\ displaystyle x_ {1} ${\ displaystyle (a_ {1}, a_ {2}, \ ldots)}$${\ displaystyle (b_ {1}, b_ {2}, \ ldots)}$

${\ displaystyle a_ {1} = x_ {1}}$as well . According prerequisite therefore applies .${\ displaystyle b_ {1} = x_ {2}}$${\ displaystyle a_ {1}
${\ displaystyle a_ {n + 1} = x_ {i}}$, where is the smallest index that is greater than the previously selected index and to which applies. This works because it is tightly ordered. According to the preliminary remark there are infinitely many with and at most a finite number of these candidates are excluded by the comparison with the corresponding index.${\ displaystyle i}$${\ displaystyle b_ {n}}$${\ displaystyle a_ {n} ${\ displaystyle \ mathbf {R}}$${\ displaystyle i}$${\ displaystyle a_ {n} ${\ displaystyle b_ {n}}$
${\ displaystyle b_ {n + 1} = x_ {i}}$, where is the smallest index that is greater than the previously selected index and to which applies. This works again because it is tight.${\ displaystyle i}$${\ displaystyle a_ {n + 1}}$${\ displaystyle a_ {n + 1} ${\ displaystyle \ mathbf {R}}$

The sequence is strictly monotonically growing, the sequence is strictly monotonically falling, and the two sequences limit each other, there is one for each . Let be the set of those elements of that are smaller than all and be the complement. Then contains, among other things, all and all , so the two sets are not empty. In addition, every element of is greater than every element of : If and , then there is an with according to the definition of ; but then follows the definition of . It is therefore a Dedekind pattern, so that there must be an element due to the lack of gaps , for which in particular applies to each . ${\ displaystyle (a_ {n})}$${\ displaystyle (b_ {n})}$${\ displaystyle a_ {n} ${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle \ mathbf {R}}$${\ displaystyle b_ {n}}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle a_ {n}}$${\ displaystyle B}$${\ displaystyle b_ {n}}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle x \ in A}$${\ displaystyle y \ in B}$${\ displaystyle n}$${\ displaystyle b_ {n} \ leq y}$${\ displaystyle B}$${\ displaystyle x ${\ displaystyle A}$${\ displaystyle (A, B)}$${\ displaystyle \ mathbf {R}}$${\ displaystyle c}$${\ displaystyle a_ {n} ${\ displaystyle n}$

Since like every element of occurs in the sequence , there is an index such that is. Here is certain , because is different from and . Let be the smallest natural number with the property that holds for or with . In both cases there is a contradiction to the choice of , since yes or already applies. ${\ displaystyle c}$${\ displaystyle \ mathbf {R}}$${\ displaystyle (x_ {i})}$${\ displaystyle j}$${\ displaystyle c = x_ {j}}$${\ displaystyle j> 2}$${\ displaystyle c}$${\ displaystyle a_ {1}}$${\ displaystyle b_ {1}}$${\ displaystyle n}$${\ displaystyle a_ {n + 1} = x_ {i}}$${\ displaystyle i> j}$${\ displaystyle b_ {n + 1} = x_ {i}}$${\ displaystyle i> j}$${\ displaystyle i}$${\ displaystyle a_ {n} ${\ displaystyle a_ {n + 1}

This contradiction can only be resolved by denying the existence of the sequence , i.e. H. is uncountable. ${\ displaystyle (x_ {1}, x_ {2}, \ ldots)}$${\ displaystyle \ mathbf {R}}$

## Real algebraic and transcendent numbers

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

## Individual evidence

1. Georg Cantor: About a property of the epitome of all real algebraic numbers . Journal for Pure and Applied Mathematics 77: pp. 258–262.