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

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

Ist R eine Halbordnung auf $\mathbb{Z}$?

Hilfreiches

Halbordnung

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

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|$