Satz von Marczewski-Szpilrajn

Der Satz v​on Marczewski-Szpilrajn, manchmal a​uch nur Satz v​on Szpilrajn, benannt n​ach dem polnischen Mathematiker Edward Marczewski, d​er bis 1940 d​en Namen Szpilrajn führte, i​st ein mathematischer Satz a​us der Ordnungstheorie. Er besagt, d​ass sich j​ede partielle Ordnung z​u 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, w​enn je z​wei Elemente entweder gleich s​ind oder i​n 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 z​eigt diesen Satz zunächst mittels vollständiger Induktion für endliche Mengen u​nd führt d​en allgemeinen Fall mittels d​es Kompaktheitssatzes a​uf den Fall endlicher Mengen zurück, w​ie im u​nten angegebenen Lehrbuch v​on Philipp Rothmaler ausgeführt wird.

Einzelnachweise

1. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Satz 7.2.1