Hasse-Diagramme
Eine Ordnung < auf einer endlichen Menge A lässt sich wie jede endliche Relation graphentheoretisch visualisieren, indem wir alle Elemente von A in der Ebene geeignet platzieren und für alle a, b ∈ A mit a < b einen Pfeil von a nach b zeichnen. Dabei wirkt sich die Transitivität oft störend aus, da sie zu einer Flut von Verbindungspfeilen führt. Wir lassen deswegen unnötige Verbindungspfeile weg. Zudem vereinbaren wir eine Wachstumsrichtung (z. B. von unten nach oben oder von links nach rechts). Dadurch entstehen sog. Hasse-Diagramme. Um sie genauer zu beschreiben, definieren wir:
Definition (Nachfolger und Vorgänger)
Sei < eine Ordnung auf A. Weiter seien a, b ∈ A. Dann heißt b ein direkter Nachfolger von a und a ein direkter Vorgänger von b, falls a < b und kein c existiert mit a < c und c < b.
Für die Inklusion auf ℘({ 1, 2, 3, 4 }) sind { 1, 2, 3 } und { 1, 3, 4 } die beiden direkten Nachfolger von { 1, 3 }. Die direkten Vorgänger von { 1, 3 } sind { 1 } und { 3 }. Für die übliche Ordnung auf ℤ ist a + 1 der direkte Nachfolger und a − 1 der direkte Vorgänger von a. In ℚ existieren dagegen keine direkten Nachfolger und Vorgänger.
Definition (transitive Reduzierung)
Sei < eine Ordnung auf einer endlichen Menge A. Dann heißt
R< = { (a, b) ∈ A2 | b ist direkter Nachfolger von a bzgl. < }
die transitive Reduzierung von <.
Die transitive Reduzierung der Ordnung < auf den ganzen Zahlen ℤ ist zum Beispiel R< = { (a, a + 1) | a ∈ ℤ }.
Nach diesen Vorbereitungen können wir nun erklären:
Hasse-Diagramme
Sei < eine Ordnung auf einer endlichen Menge A, und sei R< die transitive Reduzierung von <. Wir zeichnen R<, indem wir die Elemente von A so anordnen, dass Nachfolger stets oberhalb von Vorgängern liegen und durch Linien oder Pfeile verbunden sind. Ein derartiges Diagramm heißt ein Hasse-Diagramm der Ordnung <.
In der Sprache der Graphentheorie ist ein Hasse-Diagramm also ein von unten nach oben angeordnetes Ecken-Kanten-Diagramm des gerichteten Graphen (A, R<).
Bemerkung
(1) | Eine gestufte Darstellung, bei der alle Nachfolger eines Elements genau eine Stufe höher erscheinen, ist natürlich, aber nicht zwingend erforderlich. Wir können einen Nachfolger b von a irgendwo oberhalb von a eintragen und zwei verschiedene Nachfolger auf unterschiedlicher Höhe platzieren. Ein Hasse-Diagramm ist damit nicht eindeutig bestimmt. Die Art und Weise der Anordnung der Elemente von A kann zu Diagrammen mit unterschiedlicher Aussagekraft führen. |
(2) | Statt der Wachstumsrichtung „von unten nach oben“ können natürlich auch andere Orientierungen wie „von links nach rechts“ verwendet werden. Da eine Wachstumsrichtung vorgegeben ist, genügen Linien. Es stört aber auch nicht, Pfeile zu verwenden. |
(3) | Für unendliche Mengen ist eine Visualisierung schwieriger. Manchmal lassen sich Hasse-Diagramme „mit Pünktchen“ erstellen, oft sind aber auch ganz andere Ansätze nötig. Bekannte Beispiele sind die Zahlengeraden für ℤ, ℚ oder ℝ. |
Hasse-Diagramme der Inklusion auf ℘({ 1, 2, 3}) (links) und ℘({ 1, 2, 3, 4}) (rechts)
Hasse-Diagramm der Inklusion auf ℘({ 1, 2, 3, 4, 5 })
Hasse-Diagramme der Teilbarkeitsrelation auf { 1, …, 20 } und { 1, …, 32 }
Hasse-Diagramm der Teilbarkeitsrelation auf { 1, …, 127 } (von links nach rechts)