Halbordnungsrelation?
Hey!
Ich möchte beweisen, dass "a < c ∨ (a = c ∧ b ≤ d " eine Halbordnungsrelation ist.
Für reflexiv habe ich: R ist reflexiv, da a < a ∨ (a = a ∧ a ≤ a)
Aber bei transitiv und antisymmetrisch bin ich mir nicht sicher, wie.
Vielen Dank im Voraus!
"a < c ∨ (a = c ∧ b ≤ d "
Kannst du bitte genauer klar machen, wie die Ordnung definiert ist?
Wie lautet die Menge über die die Relation definiert ist?
(a, b) ≤lex (c, d ) ⇔ a < c ∨ (a = c ∧ b ≤ d )
es ist die lexikographische Ordnung
2 Antworten
Transitivität:
Für transitiv, haben wir zu beweisen, dass aRb und bRc ⇒ aRc.
Wenn a < b ∨ (a = b ∧ a ≤ b), und b < c ∨ (b = c ∧ b ≤ c), dann ist
a < c ∨ (a = c ∧ a ≤ c).
Dies ist eine Folgerung der Definition einer Halbordnungsrelation.
Aus diesem Grund R ist transitiv.
Antisymmetrisch:
Für antisymmetrisch, haben wir zu beweisen, dass falls aRa und bRb gelten, dann muss a=b gelten.
Wenn aber a < a oder (a = a und a ≤ a) und b < b oder (b = b und b ≤ b) gelten, folgt daraus natürlich nicht notwendigerweise, dass a=b gilt.
Aus diesem Grund R ist nicht antisymmetrisch.
Für antisymmetrisch, haben wir zu beweisen, dass falls aRa und bRb gelten, dann muss a=b gelten.
Nein, so ist Antisymmetrie nicht definiert.
Außerdem ist die Zu betrachtende Definition anders definiert, der Fragestellers hat es nicht vollständig hingeschrieben.
(a, b) ≤lex (c, d ) ⇔ a < c ∨ (a = c ∧ b ≤ d )
Es ist immer wichtig, dass du die vollständige Aufgabenstellung hinschreibst, da man sonst nicht weiß, was genau gemeint ist.
Für reflexiv habe ich: R ist reflexiv, da a < a ∨ (a = a ∧ a ≤ a)
Nein, du sollst für reflexivität zeigen, dass (a,b) <= (a,b) für alle a,b gilt.
Aber bei transitiv und antisymmetrisch bin ich mir nicht sicher, wie.
Antisymmetrie:
Nimm an, dass (a,b)<=(c,d) und (c,d)<=(a,b) gilt. Du kannst zunächst folgern, dass a=c gelten muss (da die Bedingung "a<c" nicht wahr sein kann). Du kannst dann folgern, dass b=d gilt.
Transitivität:
nimm an, dass (a,b) <= (c,d) und (c,d)<=(e,f) gilt. Du musst nun zeigen, dass (a,b)<=(e,f) gilt.