Szpilrajn extension theorem

rdf:langString Satz von Marczewski-Szpilrajn

rdf:langString 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 zusammen mit einer 2-stelligen Relation , so dass * für alle Elemente , wobei für das Nichtbestehen der Ordnung steht (Irreflexivität), * Aus und folgt für alle Elemente (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 der reellen Zahlen ist eine lineare Ordnung. Definiert man auf die Ordnung genau dann, wenn und , so ist eine partielle Ordnung, die nicht linear ist. * Satz von Marczewski-Szpilrajn: Jede partielle Ordnung lässt sich zu einer linearen Ordnung erweitern. Genauer bedeutet dies, dass es auf jeder partiell geordneten Menge eine lineare Ordnung < gibt, so dass aus stets folgt. Im oben angegebenen Beispiel ist etwa die lexikographische Ordnung eine lineare Ordnung, die 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.