Marczewski-Szpilrajn's theorem

The Marczewski-Szpilrajn Theorem , sometimes just Szpilrajn's Theorem , named after the Polish mathematician Edward Marczewski , who was called Szpilrajn until 1940, is a mathematical theorem from order theory . It says that every partial order can be expanded to a linear order .

A partial order is a non-empty set together with a 2-place relation such that ${\displaystyle X}$ ${\displaystyle \prec }$

• ${\displaystyle x\nprec x}$for all elements , whereby stands for the non-existence of the order ( irreflectivity ), ${\displaystyle x\in X}$ ${\displaystyle \nprec }$ ${\displaystyle \prec }$
• From and follows for all elements ( transitivity ). ${\displaystyle x\prec y}$ ${\displaystyle y\prec z}$ ${\displaystyle x\prec z}$ ${\displaystyle x,y,z\in X}$

The partial order is called linear if every two elements are either the same or are in an order relation.

The usual order <on the set of real numbers is a linear order. Defined on the order ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} ^{2}}$

${\displaystyle (x_{1},y_{1})\prec (x_{2},y_{2})}$exactly if and , ${\displaystyle x_{1}<y_{1}}$ ${\displaystyle x_{2}<y_{2}}$

so is a partial order that is not linear. ${\displaystyle \prec }$

• Marczewski-Szpilrajn's theorem : Every partial order can be expanded to a linear order.

More precisely this means that on every partially ordered set there is a linear order <, so that it always follows. In the example given above, for example , the lexicographical order is a linear order that continues. ${\displaystyle (X,\prec )}$ ${\displaystyle x\prec y}$ ${\displaystyle x<y}$ ${\displaystyle (\mathbb {R} ^{2},\prec )}$ ${\displaystyle \prec }$

This theorem is shown first by means of complete induction for finite sets and the general case is reduced to the case of finite sets by means of the compactness theorem , as explained in the textbook by Philipp Rothmaler given below.

Individual evidence

1. ↑ Philipp Rothmaler: Introduction to Model Theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , sentence 7.2.1