TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 123

Aus VoWi
Zur Navigation springen Zur Suche springen

Seien R_1 und R_2 Halbordnungen auf der Menge M. man beweise, dass dann auch ihr Durchschnitt R = R_1 \cap R_2 Halbordnung auf M ist.

Hilfreiches[Bearbeiten]

Halbordnung
Halbordnung[Bearbeiten]

Eine binäre Relation R auf einer Menge A heißt Halbordnung oder partielle Ordnung, wenn folgende drei Eigenschaften erfüllt sind:

  • Reflexivität: \forall a\, \in A: aRa,
  • Antisymmetrie: \forall a,b\, \in A: (aRb \wedge bRa) \Rightarrow a = b,
  • Transitivität: \forall a,b,c\, \in A: (aRb \wedge bRc) \Rightarrow aRc.

Lösungsvorschlag[Bearbeiten]

Prinzipiell muss man sich nur klar werden, dass nur alle jene Tupel (a,b) \in R sind wenn gilt aRb \Longleftrightarrow (aR_1b) \and (aR_2b)

damit lassen sich die Eigenschaften einer Halbordung relativ leicht zeigen.

Reflexivität[Bearbeiten]

aRa \Longleftrightarrow (aR_1a) \and (aR_2a)

Nachdem die rechte Seite auf jeden Fall gilt (R_1, R_2 sind per Definition Halbordnungen), muss auch die linke Seite gelten

Antisymmetrie[Bearbeiten]

\left( aRb \and bRa \Rightarrow a = b \right) \Longleftrightarrow \left( \left(aR_1b \and bR_1a \Rightarrow a = b \right) \and \left( aR_2b \and bR_2a \Rightarrow a = b \right) \right)

In anderen Worten: Würde aRb \and bRa \Rightarrow a = b nicht gelten, dann würde es auch keine Beziehung der Form aR_1b \and bR_1a \Rightarrow a = b geben. Daher kann aber (a,b) kein Element von R sein.

Transitivität[Bearbeiten]

aRb \and bRc \Rightarrow aRc \Longleftrightarrow \left( \left(aR_1b \and bR_1c \Rightarrow a R_1 c \right) \and \left( aR_2b \and bR_2c \Rightarrow a R_2 c \right) \right)

Nur weil die Transitivität sowohl in R_1 als auch R_2 gilt, sind die Elemente in der Schnittmenge R. Dadurch gilt die Transitivität aber natürlich auch in der Schnittmenge selbst.