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

Aus VoWi
Zur Navigation springen Zur Suche springen

Sei m R n \Leftrightarrow |m| \leq |n|, m, n \in \mathbb{Z}.

Ist R eine Halbordnung auf \mathbb{Z}?

Hilfreiches[Bearbeiten]

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.

Damit die Relation R eine Halbordnung ist, muß sie die Eigenschaften Reflexivität, Antisymmetrie und Transitivität erfüllen.

Reflexivität: m R m?

|m| \leq |m| \quad \forall m \in \mathbb{Z} \Longrightarrow reflexiv.

Antisymmetrie: m R n \land n R m \Rightarrow m = n?

Aus |m| \leq |n| \land |n| \leq |m| folgt |m| = |n|. Diese Äquivalenz ist aber nicht nur erfüllt, wenn m = n, sondern aufgrund der Absolutbeträge auch wenn m = -n, daher ist R nicht antisymmetrisch.

Von Axel:

Ich habe die Antisymmetrie ein bisserl anders gemacht, der Grund: Wenn ich das Widerlegen von "Aus |m|<=|n| und |n|<=|m| folgt |m|=|n|" als Beweisgrundlage hernehme, dann wird der Panholzer fragen woher ich wissen will, dass "Aus |m|<=|n| und |n|<=|m| folgt |m|=|n|" und "mRn und nRm impliziert n=m" Äquivalent sind ;-)

Wenn man das gleich "von hinten rum" macht geht es imho einfacher:

Beweise/Wiederlege die Annahme: Aus mRn und nRm folgt m=n fuer alle m,n Element Z.

Sei m Element Z und m groesser 0 und n = -m. Dann ist wegen |m|<=|-m| mRn gegeben, und wegen |-m|<=|m| nRm geben, aber m ungleich n, also die Annahme wiederlegt.

Von Jens: Aus |m| \leq |n| \land |n| \leq |m| folgt aufgrund der Antisymmetrie der Halbordnung \leq, daß |m| = |n|. So ist die Definition der Kleiner-gleich-Relation, das mußt Du nicht extra beweisen.

Transitivität: m R n \land n R o \Rightarrow m R o?


\begin{array}{rrcl}
& |m| & \leq & |n| \\
+ & |n| & \leq & |o| \\
\hline
& |m| + |n| & \leq & |n| + |o| \qquad | - |n| \\
& |m| & \leq & |o|
\end{array}

Daraus folgt, daß R transitiv ist.

Da R nur die Eigenschaften Reflexivität und Transitivität erfüllt, nicht aber die Antisymmetrie, ist R keine Halbordnung auf \mathbb{Z}.

Graphische Ergänzung[Bearbeiten]

TU Wien-Mathematik 1 UE (diverse) - Skizze Bsp 102.png

Orangene Linien zeigen die Reflexivität, da 2 \le 2 und 0 \le 0

Blaue Linien zeigen Transitivität, da 0 \le 1 und 1 \le 2 \to 0 \le 2

Rote Linien widerlegen die Antisymmetrie, da \left|-2\right| \le 2 und 2 \le \left|-2\right|