Well-order theorem

The well-order theorem , sometimes also called the well-order principle , is a statement of set theory and says:

This theorem allows transfinite induction to be applied to any set. The well-order theorem is equivalent to the axiom of choice .

Georg Cantor , the founder of set theory, considered the well-order theorem to be a "fundamental law of thought". Many mathematicians, however, found it difficult to imagine that a well-order should exist on the set of real numbers . So in 1904 Julius König believed that he had refuted this; However, a little later Felix Hausdorff found a mistake in the refutation attempt. Ernst Zermelo introduced the axiom of choice as a “harmless logical principle” in order to prove the well-ordered principle; However, this quickly turned out to be equivalent to the well-order theorem. The axiom of choice and thus the well -ordered theorem are independent of the Zermelo-Fraenkel set theory , i.e. H. Both the proposition and its opposite can be presupposed without contradiction if one presupposes the consistency of all other axioms. In fact, it can be shown that at least the axioms of the Zermelo-Fraenkel set theory alone (including the axiom of choice) do not allow the explicit construction of such a well-order.

Property of natural numbers

Sometimes the well-order theorem or the well-order principle describes the property of the set of natural numbers to be well-ordered :

Every non-empty set of natural numbers contains a smallest number.

This is exploited in the case of proofs by infinite descent or the method of the smallest criminal: in order to show that a set contains all natural numbers, one can first assume that it does not contain every number. Because of the principle of well-being, there is a smallest natural number that is not included (a smallest counterexample ). If you then show that there is an even smaller counterexample, you get a contradiction to the assumption made. Alternatively, you can also show that you can find a smaller one for each counterexample, and thus descend infinitely often, which is not possible in natural numbers. ${\ displaystyle S}$

This proof is a reverse of full induction (as is logically equivalent to ), but is based on the same well-ordering property of natural numbers. ${\ displaystyle \ neg B \ Rightarrow \ neg A}$ ${\ displaystyle A \ Rightarrow B}$

Application example

An example of this method of proof is the following statement:

The subsets of the additive group of integers are exactly the subsets with . ${\ displaystyle (\ mathbb {Z}, +)}$ ${\ displaystyle m \ mathbb {Z}}$ ${\ displaystyle m \ geq 0}$

Proof:

It is easy to verify that these subsets are subgroups. Now be any subgroup of . Does not contain a positive integer, then is . Otherwise, let the smallest positive integer be in . Let any element be off , we have to show that is for an integer . To do this, we divide with remainder by , that is , with integer and . Because in lies, there would be a contradiction in choosing as the smallest positive element of , so is and . ${\ displaystyle U}$ ${\ displaystyle \ mathbb {Z}}$ ${\ displaystyle U}$ ${\ displaystyle U = \ left \ {0 \ right \} = 0 \ mathbb {Z}}$ ${\ displaystyle m}$ ${\ displaystyle U}$ ${\ displaystyle x}$ ${\ displaystyle U}$ ${\ displaystyle x = mq}$ ${\ displaystyle q}$ ${\ displaystyle x}$ ${\ displaystyle m}$ ${\ displaystyle x = mq + r}$ ${\ displaystyle q, r}$ ${\ displaystyle 0 \ leq r <m}$ ${\ displaystyle r = x-mq}$ ${\ displaystyle U}$ ${\ displaystyle 0 <r <m}$ ${\ displaystyle m}$ ${\ displaystyle U}$ ${\ displaystyle r = 0}$ ${\ displaystyle x = mq}$