Proposition - In endlichen Partialordnungen sind zwei Elemente immer durch eine Reihe von Bedeckungen miteinander verbunden

• Involvierte Definitionen:
  • Endliche Partialordnung
  • Bedeckungsrelation
• Veranstaltung: AlMa
• Referenz: } AlgoMathe KE2 - Partialordnungen

⠀

Proposition: In endlichen Partialordnungen sind zwei Elemente immer durch eine Reihe von Bedeckungen miteinander verbunden

Sei eine endliche Partialordnung und beliebige Elemente.

Für gilt:

Mit anderen Worten: in endlichen Partialordnungen passen zwischen und maximal andere Elemente.

Anmerkung

Bedeckungsrelation erzeugt endliche Partialordnung

Wir können daher jede endliche Partialordnung durch die Bedeckungsrelation darstellen.

Ein geeignetes Werkzeug zur Visualisierung ist das Hasse-Diagramm.

Beweis

Es gelte . Dann gilt auch .

Wir müssen nun zwei Fälle unterscheiden:

1. Es gibt keine Zwischenelemente. Wenn es kein Zwischenelement gibt, mit dann ist nach Definition .

2. Es gibt Zwischenelemente. Es gebe jetzt Zwischenelemente mit . Da eine endliche Partialordnung ist, gibt es nur endlich viele Zwischenelemente . Daher gilt