Tutorium Woche 14

schreibt mal auf, was ihr zu Halbordnungen wisst. Was sind Halbordnungen?

Wann ist eine Relation R ⊆ M × M antisymmetrisch?

• Wenn sie nicht symmetrisch ist.

• Wenn sie symmetrisch, aber nicht reflexiv ist.

• Wenn für x, y ∈ M die Bedingung gilt:

  xRy ∧ yRx ⇒ x = y

• Wenn für x, y, z ∈ M die Bedingung gilt:

  xRy ∧ yRz ⇒ x = z

Welche kanonischen Beispiele sind Halbordnungen?

• ≤ ("kleiner gleich" auf ℝ)

• ⊆
  (Teilmengenbeziehung)

• >

  ("echt größer")

• = (Gleichheit)

Man kann Relationen auch als Graphen darstellen: Was bedeutet Antisymmetrie allgemein für Graphen einer Halbordnung? (Mehrfachauswahl, wer weiß?)

• Der Graph darf keine Rückkanten enthalten

• Der Graph darf keine Schleifen enthalten

• Der Graph darf Schleifen, aber keine Zyklen enthalten

• Der Graph muss zusammenhängend sein.

Answer explanation

Wenn der Graph Zyklen enthält, die keine Schleifen sind, kann er nicht gleichzeitig transitiv und antisymmetrisch sein.

Was sind minimale Elemente von M? (in aufsteigender Reihenfolge mit Leerzeichen getrennt)

Was sind maximale Elemente von M? (in aufsteigender Reihenfolge)

Kann es hier eine obere Schranke geben?

• nein

• ja

Answer explanation

gibt es nicht, da es kein y ∈ M mit 7 ⊑ y gibt

Was sind obere Schranken von {1, 2, 3, 4, 5}?

• {5, 7}

• {1, 2, 3, 4, 5}

• {3, 4, 5}

• {5}

Was ist das Supremum bzw. Infimum von {1, 2, 3, 4, 5} ?

• Supremum: 5

  Infimum: gibt es nicht

• Supremum: 7

  Infimum: -1, 0

• Supremum: gibt es nicht

  Infimum: gibt es nicht

• Supremum: 5, 7

  Infimum: -1, 0

Answer explanation

Es gibt kein Infimum, da weder 0 ⊑ −1, noch −1 ⊑ 0 gilt.

Welche Aussage trifft zu? (Mehrfachauswahl)

Eine Ordnung oder totale Ordnung R ⊆ M × M...

• ... ist auch eine Halbordnung

• erfüllt ∀x, y ∈ M : xRy ∨ yRx (Totalität)

• ist nicht reflexiv

• ist keine Relation