Comparability rate

In elementary set theory there are two important theorems of comparability :

1. For any quantity , the following always applies: or . where is an abbreviation for the statement that there is an injective mapping from to . (Note: if both relationships apply, the sets are equal according to the Cantor-Bernstein-Schröder theorem .) ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle |M|\leq |N|}$ ${\displaystyle |N|\leq |M|}$ ${\displaystyle |M|\leq |N|}$ ${\displaystyle M}$ ${\displaystyle N}$
   
2. Whenever and are well-orders , one of these well-orders is isomorphic to an initial section of the other . ${\displaystyle (A,<)}$ ${\displaystyle (B,<)}$

Proof of the theorem for well-ordered sets

For any well-order and we define a relation as follows: ${\displaystyle (A,<)}$ ${\displaystyle (B,<)}$ ${\displaystyle R_{A,B}\subseteq A\times B}$

${\displaystyle R_{A,B}:={\bigg \{}(a,b)\in A\times B:\{x\in A:x<a\}\simeq \{y\in B:y<b\}{\bigg \}}}$

It is easy to show that a partial injective function (quite clearly and unambiguously on the left) that domain and range of the top portions respectively , and that this function is strictly monotonous. ${\displaystyle R_{A,B}}$ ${\displaystyle A}$ ${\displaystyle B}$

The assumption that both the domain of definition and domain of values ​​are genuine initial sections of or leads to a contradiction; because then it would have and give so a Ordnungsisomorphie of to be, that would by definition also in . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a_{0}\in A}$ ${\displaystyle b_{0}\in B}$ ${\displaystyle R_{A,B}}$ ${\displaystyle \{x\in A:x<a_{0}\}}$ ${\displaystyle \{y\in B:y<b_{0}\}}$ ${\displaystyle (a_{0},b_{0})}$ ${\displaystyle R_{A,B}}$

Therefore, either the definition or the range of values ​​is whole or whole . There is then either an isomorphism between and an initial section of , or between an initial section of and . ${\displaystyle R_{A,B}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R_{A,B}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Proof sketch of the theorem for arbitrary sets

Be and arbitrary sets. According to the principle of well-order there are on and well-orders and . According to the comparability law for well-orders, there is an isomorphism between one well-order and an initial section of the other. This mapping is now an injective function from one set to the other. ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle (M,<)}$ ${\displaystyle (N,<)}$ ${\displaystyle f}$

The need for the axiom of choice

The theorem of comparability for well-ordered sets can be proved without using the axiom of choice.

From the comparability theorem for arbitrary sets, on the other hand, follows the well-order theorem, thus also the axiom of choice: According to Hartogs' theorem, for every set one can find an ordinal number that cannot be embedded in an injective. According to the comparability principle, there must be an injective mapping from to ; Such a picture induces a well-order . ${\displaystyle M}$ ${\displaystyle \alpha }$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \alpha }$ ${\displaystyle M}$

The comparability theorem for arbitrary quantities is therefore equivalent to the axiom of choice (via the theory ZF ).

history

The sentence was long suspected by Georg Cantor , but could only be proven in 1904 by Ernst Zermelo .

literature

• Oliver Deiser: Introduction to set theory . Berlin 2004 . ISBN 3-540-20401-6