Rado's selection principle

The selection principle of Rado (or Rado selection principle called; English Rado's Principle Selection or Rado's Lemma Selection ) is a mathematical theorem which both the set theory as well as the discrete mathematics is attributable. The selection principle goes back to the German mathematician Richard Rado . It is an important tool to derive significant results of transfinite discrete mathematics such as the transfinite versions of the set of Dilworth or Marriage set of Hall . Likewise, de Bruijn and Erdős' theorem proves to be a direct consequence of Rado's selection principle.

The proof of the principle of selection is based on the axiom of choice or one of the maximum principles of set theory that are equivalent to it . It can be shown that Rado's selection principle results from the application of Tychonoff's theorem .

Formulation of the selection principle

In the following, for two sets and the notation means that is a finite subset of . Rado's selection principle can be formulated as follows: ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X{\subset \subset }Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

A non-empty index set    , a non-empty basic set   and     a set family   consisting of non-empty subsets     (   ) are given. ${\displaystyle I}$   ${\displaystyle M}$ ${\displaystyle M}$   ${\displaystyle {\mathcal {M}}=(M_{i})_{i\in I}}$ ${\displaystyle M_{i}{\subset \subset }M}$ ${\displaystyle i\in I}$

Furthermore,  a selection function is   given for every finite subfamily   (  ) . ${\displaystyle {\mathcal {M}}_{J}=(M_{j})_{j\in J}}$ ${\displaystyle J{\subset \subset }I}$   ${\displaystyle {{\alpha }_{J}}}$

Then there is   a selection function  which is a partial continuation of     (   ) in such a way that for each of these index     sets   there is an identical index set   with     and   ${\displaystyle {\mathcal {M}}}$   ${\displaystyle {\alpha }}$ ${\displaystyle {{\alpha }_{J}}}$ ${\displaystyle J{\subset \subset }I}$ ${\displaystyle J{\subset \subset }I}$ ${\displaystyle K}$ ${\displaystyle J\subseteq K{\subset \subset }I}$ ${\displaystyle {{\alpha }_{K}}{{\upharpoonright }J}={\alpha }{{\upharpoonright }J}}$  .

Some conclusions

Using Rado's selection principle results among other things:

• The set of de Bruijn - Erdős :

A graph is - colorable (   ) if and only if every finite induced subgraph is   - colorable . ${\displaystyle k}$ ${\displaystyle k\in \mathbb {N} }$   ${\displaystyle k}$

• The set of Dilworth (transfinite version) :

An infinite, partially ordered set of width     can always be broken down into     pairs of disjoint chains . ${\displaystyle w\in \mathbb {N} }$ ${\displaystyle w}$

• The marriage sentence (transfinite version) :

An infinite family of finite sets has a choice (system of representatives) if and only if every finite subfamily satisfies the Hall condition .

• The set of BH Neumann :

A group has a total order compatible with the group structure if and only if every finitely generated subgroup has one.

• The set of FW Levi :

An Abelian group has a linear arrangement that is compatible with the group structure if and only if it is torsion-free .

literature

Articles and original works

• WH Gottschalk: Choice functions and Tychonoff's theorem . In: Proc. Amer. Math. Soc. tape 2 , 1951, p. 172 .
• R. Rado : Axiomatic treatment of rank in infinite sets . In: Canad. J. Math. Band 1 , 1949, p. 337-343 .
• R. Rado: A Selection Lemma . In: J. Comb. Theory . tape 10 , 1971, p. 176-177 .

Monographs

• Martin Aigner : Combinatorial Theory . Springer-Verlag , Berlin et al. 1979, ISBN 3-540-90376-3 .
• Egbert Harzheim : Ordered Sets . Springer-Verlag, New York 2005, ISBN 0-387-24219-8 .
• Heinz Lüneburg : Combinatorics . Birkhäuser Verlag , Basel et al. 1971, ISBN 3-7643-0548-7 .
• Leonid Mirsky: Transversal Theory . Academic Press, New York / London 1971, ISBN 0-12-498550-5 .

Individual evidence

1. ^ H. Lüneburg: combinatorics . 1971, p. 61 .
2. ^ L. Mirsky: Transversal Theory . 1971, p. 52 .
3. ^ E. Harzheim: Ordered Sets . 2005, p. 234 .
4. ^ WH Gottschalk: Choice functions and Tychonoff's theorem . 1951, p. 172 .
5. ^ H. Lüneburg: combinatorics . 1971, p. 61-62 .
6. ^ E. Harzheim: Ordered Sets . 2005, p. 234 .
7. ^ L. Mirsky: Transversal Theory . 1971, p. 52 .
8. ↑   stands for the restriction on ${\displaystyle {{\upharpoonright }J}}$ ${\displaystyle J}$
9. ↑ M. Aigner: Combinatorial Theory . 1979, p. 410 .
10. ↑ M. Aigner: Combinatorial Theory . 1979, p. 410 .
11. ^ E. Harzheim: Ordered Sets . 2005, p. 60 .
12. ↑ Dilworth's theorem (general version) can be derived both using Rado's selection principle (Aigner) and de Bruijn / Erdős (Harzheim) theorem.
13. ↑ M. Aigner: Combinatorial Theory . 1979, p. 409 .
14. ^ H. Lüneburg: combinatorics . 1971, p. 65 .
15. ^ H. Lüneburg: combinatorics . 1971, p. 63 .
16. ^ H. Lüneburg: combinatorics . 1971, p. 64 .