Satz von Marczewski-Szpilrajn

Der Satz von Marczewski-Szpilrajn, manchmal auch nur Satz von Szpilrajn, benannt nach dem polnischen Mathematiker Edward Marczewski, der bis 1940 den Namen Szpilrajn führte, ist ein mathematischer Satz aus der Ordnungstheorie. Er besagt, dass sich jede partielle Ordnung zu einer linearen Ordnung erweitern lässt.

Eine partielle Ordnung ist eine nicht-leere Menge ${\displaystyle X}$ zusammen mit einer 2-stelligen Relation ${\displaystyle \prec }$, so dass

• ${\displaystyle x\nprec x}$ für alle Elemente ${\displaystyle x\in X}$, wobei ${\displaystyle \nprec }$ für das Nichtbestehen der Ordnung ${\displaystyle \prec }$ steht (Irreflexivität),
• Aus ${\displaystyle x\prec y}$ und ${\displaystyle y\prec z}$ folgt ${\displaystyle x\prec z}$ für alle Elemente ${\displaystyle x,y,z\in X}$ (Transitivität).

Die partielle Ordnung heißt linear, wenn je zwei Elemente entweder gleich sind oder in einer Ordnungsrelation stehen.

Die gewöhnliche Anordnung < auf der Menge ${\displaystyle \mathbb {R} }$ der reellen Zahlen ist eine lineare Ordnung. Definiert man auf ${\displaystyle \mathbb {R} ^{2}}$ die Ordnung

${\displaystyle (x_{1},x_{2})\prec (y_{1},y_{2})}$ genau dann, wenn ${\displaystyle x_{1}<y_{1}}$ und ${\displaystyle x_{2}<y_{2}}$,

so ist ${\displaystyle \prec }$ eine partielle Ordnung, die nicht linear ist.

• Satz von Marczewski-Szpilrajn[1]: Jede partielle Ordnung lässt sich zu einer linearen Ordnung erweitern.

Genauer bedeutet dies, dass es auf jeder partiell geordneten Menge ${\displaystyle (X,\prec )}$ eine lineare Ordnung < gibt, so dass aus ${\displaystyle x\prec y}$ stets ${\displaystyle x<y}$ folgt. Im oben angegebenen Beispiel ${\displaystyle (\mathbb {R} ^{2},\prec )}$ ist etwa die lexikographische Ordnung eine lineare Ordnung, die ${\displaystyle \prec }$ fortsetzt.

Man zeigt diesen Satz zunächst mittels vollständiger Induktion für endliche Mengen und führt den allgemeinen Fall mittels des Kompaktheitssatzes auf den Fall endlicher Mengen zurück, wie im unten angegebenen Lehrbuch von Philipp Rothmaler ausgeführt wird.