Definitionen und Sätze pdf
Teil A: Ordnungstheorie 1
Der zentrale Begriff der Ordnungstheorie ist die Teilgeordnete Menge. Darum soll er an dieser Stelle definiert werden.
Definition A.1 - Teilordnung, Poset
Eine zweistellige Relation ≤ auf einer Menge A heisst Teilordnungsrelation, falls für alle x, y, z ∈ A folgende Bedingungen erfüllt sind:
| Reflexivität | x ≤ x |
| Antisymmetrie | x ≤ y und y ≤ x ⇒ x = y |
| Transitivität | x ≤ y und y ≤ z ⇒ x ≤ z |
In diesem Fall nennt man das Paar A = (A, ≤) eine Teilordnung oder Poset.
Sei P = (P, ≤) ein Poset. Definiere x ≤' y genau dann wenn y ≤ x. Dann ist P' = (P, ≤') auch ein Poset; nämlich das zu (P, ≤) duale Poset.
Definition A.3 - Extreme Elemente, Nachbarn
Sei A = (A, ≤) ein Poset, B ⊆ A eine Teilmenge von A. Ein maximales Element von B ist ein Element b ∈ B mit b < a ⇒ a ∉ B für alle a ∈ A. Das Maximum von B ist ein Element b ∈ B mit b' ≤ b für alle b' ∈ B.
Ein minimales Element von B ist ein Element b ∈ B mit a < b ⇒ a ∉ B für alle a ∈ A. Das Minimum von B ist ein Element b ∈ B mit b ≤ b' für alle b' ∈ B.
Man nennt b einen oberen Nachbarn von a (resp. a einen unteren Nachbarn von b), falls a ≤ b und es gibt kein x ≠ a, b mit a ≤ x ≤ b.
Es ist üblich, Posets A = (A, ≤) mittels sogenannten Hasse-Diagrammen darzustellen. Die Elemente von A werden als Punkte oder Kreislein dargestellt, verbindende Geradenstücke geben die Ordnung wieder: b wird oberhalb von a gezeichnet und mit ihm verbunden, falls b oberer Nachbar von a ist. In einem Hasse-Diagramm sind alle Informationen eines Posets gespeichert. Es versteht sich, dass ein Hasse-Diagramm nicht eindeutig ist (vgl. Abbildung A).
Abbildung A: Zwei Hasse-Diagramme desselben Posets
Bemerkung A.4 - Interpretation der Teilordnungsrelation ≤
In den Definitionen, Sätzen und Beispielen dieser Webseite verwenden wir im folgenden die Standardinterpretation der Ordnungsrelation ≤ und aller verwandten Relationen wie <, ≥, >,...
Eine Teilordnung zeichnet sich schon dem Wort nach dadurch aus, dass unter ihren Elementen nicht zwingend überall Ordnung herrschen muss. Das heisst etwas konkreter, dass es zwei Elemente geben kann, die man nicht miteinander vergleichen kann, die sich nicht ordnen lassen.
Im Folgenden sollen diese Tatsache und einige grundlegende Begriffe für Posets etwas mathematischer dargestellt werden.
Definition A.5 - Vergleichbarkeit
Sei A = (A, ≤) ein Poset. Zwei Elemente a, b ∈ A heissen vergleichbar, falls a ≤ b oder b ≤ a, und sonst unvergleichbar.
Definition A.6 - Kette, Antikette
Eine linear geordnete Menge oder Kette ist ein Poset, in welchem zwei beliebige Elemente vergleichbar sind. Man nennt das Poset Cn := (C, ≤) eine n-Kette, falls C n Elemente besitzt, welche unter ≤ eine Kette bilden.
Eine Teilmange paarweiser unvergleichbarer Elemente heisst Antikette
Definition A.7 - Subposet, Ordnungs-Homomorphismus, Ordnungs-Einbettung, Ordnungs-Isomorphismus
Ein Poset (B, ≤B) heisst Subposet des Posets (A, ≤A), falls B ⊆ A und ≤B ⊆ ≤A, d.h. für alle x, y ∈ B x ≤B y genau dann, wenn x ≤A y.
Sind (A, ≤A) and (B, ≤B) Posets, dann nennt man eine Abbildung f : A → B ordnungserhaltend oder einen Ordnungs-Homomorphismus, falls aus x ≤A y stets f(x) ≤B f(y) folgt für alle x, y ∈ A.
Ist f darüberhinaus injektiv und folgt aus f(x) ≤B f(y) stets x ≤A y für alle x, y ∈ A, dann heisst f Ordnungs-Einbettung.
Surjektive Ordnungs-Einbettungen werden Ordnungs-Isomorphismen genannt.