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

From VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Revision as of 10:00, 28 September 2019 by Gittenborg (talk | contribs) (use Template:Thema)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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[edit]

Halbordnung
Halbordnung[edit]

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[edit]

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[edit]

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[edit]

\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[edit]

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.