Ordnungsrelation – Serlo „Mathe für Nicht-Freaks“

Ordnungen sind eine besondere Klasse binärer, homogener Relationen. Sie sind eine Verallgemeinerung der Ordnungsrelationen wie $\leq$ oder $<$, die du bereits für die Zahlbereiche $\mathbb {N}$, $\mathbb {Z}$ und $\mathbb {R}$ kennst. Mit Hilfe von Ordnungsrelationen können Elemente einer Grundmenge ihrer Größe nach geordnet und miteinander verglichen werden.

Um eine Ordnung auf einer Menge zu definieren, reicht es, eine der beiden Relationen $\leq$ oder $<$ zu definieren. Die jeweils andere Relation lässt sich dann mit den folgenden Beziehungen darauf zurückführen:

• $x<y$ genau dann, wenn $x\leq y$ und $x\neq y$,
• $x\leq y$ genau dann, wenn $x<y$ oder $x=y$.

Ordnungsrelationen lassen sich umdrehen: so wird aus der Kleiner-Gleich-Relation $\leq$ die Grösser-Gleich-Relation $\geq$ und aus der Echt-Kleiner-Relation $<$ wird die Echt-Größer-Relation $>$. In Listen im Internet kann in der Regel gewählt werden, ob die Ergebnisse aufsteigend oder absteigend sortiert werden sollten.

Ordnungsrelationen gibt es auch außerhalb der Zahlen. So sind beispielsweise die Wörter im Lexikon alphabetisch geordnet.

Totalordnung

Transitivität: Aus $a\leq b$ und $b\leq c$ folgt $a\leq c$

Totalordnungen sind direkte Verallgemeinerungen der Kleiner-Gleich-Relation auf den Zahlen. Genau wie andere binäre homogene Relationen wird die Totalordnung über ihre Eigenschaften bestimmt.

Frage: Welche Eigenschaft besitzt die Relation $\leq$ auf den Zahlbereichen $\mathbb {N}$, $\mathbb {Z}$ und $\mathbb {R}$?

Eigenschaft der Relation $\leq$	Begründung
reflexiv	Für alle $x$ ist $x\leq x$.
antisymmetrisch	Aus $x\leq y$ und $y\leq x$ folgt $x=y$
transitiv	Aus $x\leq y$ und $y\leq z$ folgt $x\leq z$
linear	Für alle reellen Zahlen $x$ und $y$ ist $x\leq y$ oder $y\leq x$
nicht irreflexiv	Diese Relation ist reflexiv und die Grundmenge ist nicht leer
nicht symmetrisch	Gegenbeispiel: Es ist $23\leq 42$ aber $42\not \leq 23$ und damit kann die Relation nicht symmetrisch sein

Eine Relation ist dann eine Totalordnung, wenn sie diejenigen vier Eigenschaften hat, die auch die Kleiner-Gleich-Relation für die Zahlen besitzt:

Definition (Totalordnung)

Eine Totalordnung $\leq$ auf $M$ ist eine binäre und homogene Relation auf der Grundmenge $M$, die folgende Eigenschaften besitzt:

• $\forall x\in M:x\leq x$ (Reflexivität)
• $\forall x,y\in M:x\leq y\land y\leq x\Rightarrow x=y$ (Antisymmetrie)
• $\forall x,y,z\in M:x\leq y\land y\leq z\Rightarrow x\leq z$ (Transitivität)
• $\forall x,y\in M:x\leq y\lor y\leq x$ (Linearität)

Da eine Totalordnung die direkte Verallgemeinerung der Ordnung auf der Zahlengeraden ist, welche eine „Linie“ ist, wird eine Totalordnung auch lineare Ordnung genannt.

Hinweis

In der Mathematik wird das Adjektiv „linear“ mehrfach verwendet. So kennst du „lineare Funktionen“ aus der Schule und in der linearen Algebra gibt es den Begriff der „linearen Abbildung”. Diese Begriffe haben aber nichts mit dem Begriff der „linearen Ordnung“ zu tun!

Beispiel (Totalordnung)

• Die $x\leq y$ Relation auf der Grundmenge $\mathbb {N}$ ist eine Totalordnung.
• Die $x\leq y$ Relation auf der Grundmenge $\mathbb {Z}$ ist eine Totalordnung.
• Die $x\leq y$ Relation auf der Grundmenge $\mathbb {R}$ ist eine Totalordnung.
• Die alphabetische Ordnung der Wörter in einem Lexikon ist eine Totalordnung

Die Ordnungen $\leq$ auf den Zahlbereichen $\mathbb {N}$, $\mathbb {Z}$ und $\mathbb {R}$ sind zwar alle Totalordnungen, aber sie unterscheiden sich auch! So hat $\mathbb {N}$ ein kleinstes Element, nämlich die $1$, aber weder $\mathbb {Z}$ noch $\mathbb {R}$ haben ein kleinstes Element. In $\mathbb {R}$ gibt es zwischen zwei verschiedenen Elementen $x\neq y$ mit $x\leq y$ immer ein weiteres Element $z$ mit $z\neq x$, $z\neq y$ und $x\leq z\leq y$. Das gilt für $\mathbb {N}$ und $\mathbb {Z}$ nicht.

Satz

Sei $\leq$ eine Totalordnung auf der Menge $M$ und $A\subseteq M$ eine Teilmenge von $M$. Dann ist die Einschränkung von $\leq$ auf $A$ eine Totalordnung auf $A$.

Beweis

Die Einschränkung von $\leq$ auf $A$ ist $\{x,y\in A\,|\,x\leq y\}$. Die vier Eigenschaften der Totalordnung auf $M$ gelten natürlich auch für die Teilmenge $A\subseteq M$. Also ist $\{x,y\in A\,|\,x\leq y\}$ eine Totalordnung auf $A$.

Wie bereits gesagt, ist auch die Umkehrung $\geq$ einer Totalordnung $\leq$ wieder eine Totalordnung:

Aufgabe: Sei $\leq$ eine Totalordnung. Beweise, dass dann auch die konverse Relation $\geq$ definiert durch $x\geq y:\Leftrightarrow y\leq x$ eine Totalordnung ist.

Beweisschritt: $\geq$ ist reflexiv

Wir müssen beweisen, dass für alle $x$ aus der Grundmenge $x\geq x$ gilt. Nun gilt $x\geq x$ nach Definition genau dann, wenn $x\leq x$ ist. Wir wissen aber bereits, dass $\leq$ reflexiv ist, und damit auch, dass $x\leq x$ für alle $x$ gilt. Es folgt die Reflexivität von $\geq$.

Beweisschritt: $\geq$ ist antisymmetrisch

Auch dies folgt aus der Antisymmetrie von $\leq$. Für $\leq$ gilt nämlich $x\leq y\land y\leq x\Rightarrow x=y$. Setzen wir $x\geq y\Leftrightarrow y\leq x$ ein, folgt $y\geq x\land x\geq y\Rightarrow x=y$ für alle $x$ und $y$ der Grundmenge. Dies ist die Antisymmetrieeigenschaft von $\geq$.

Beweisschritt: $\geq$ ist transitiv

Sei $x\geq y$ und $y\geq z$. Nach Definition ist dann $y\leq x$ und $z\leq y$. Es folgt $z\leq x$ aus der Transitivität von $\leq$. Damit gilt aber auch $x\geq z$ nach der Definition von $\geq$. Ingesamt haben wir so $x\geq y\land y\geq z\Rightarrow x\geq z$ gezeigt und damit die Transitivität von $\geq$.

Beweisschritt: $\geq$ ist linear

Von $\leq$ wissen wir bereits, dass es linear ist. Also gilt für zwei $x$ und $y$: $x\leq y$ oder $y\leq x$. Nach Definition von $\geq$ gilt dann auch für alle $x$ und $y$: $y\geq x$ oder $x\geq y$. Dies ist die Linearitätseigenschaft von $\geq$.

Definition (Weitere Ordnungsrelationen auf Grundlage der Totalordnung)

Sei $\leq$ eine Totalordnung auf der Grundmenge $M$. Dann sind die weiteren Ordnungsrelationen $<$ und $>$ auf $M$ folgendermaßen definiert:

• $x<y:\Leftrightarrow x\leq y\land x\neq y$
• $x>y:\Leftrightarrow y<x$

Während $\geq$ ebenfalls eine Totalordnung ist, ist das bei $<$ und $>$ nicht der Fall. Diese beiden Relationen sind strikte Totalordnungen:

Strikte Totalordnung

Analog zur Totalordnung, soll auch die Relation $<$ die Kleiner-Relation der reellen Zahlen verallgemeinern. Wenn eine Relation das tut, nennt man sie strikte Totalordnung. Welche Eigenschaften muss nun aber $<$ besitzen, um als strikte Totalordnung zu gelten?

Frage: Welche Eigenschaften besitzt die Relation $<$ auf den Zahlbereichen $\mathbb {N}$, $\mathbb {Z}$ und $\mathbb {R}$ ?

Eigenschaft der Relation $<$	Begründung
irreflexiv	Für alle $x$ ist $x\not <x$.
antisymmetrisch	Ist $x<y$, so folgt automatisch $y\not <x$. Damit kann $x<y$ und $y<x$ nie gleichzeitig auftreten. Somit ist die Implikation $x<y\land y<x\Rightarrow x=y$ stets wahr, weil die Prämisse $x<y\land y<x$ stets falsch ist (siehe Abschnitt zur Implikation).
asymmetrisch	Die Kleiner-Relation ist antisymmetrisch und irreflexiv.
transitiv	Aus $x<y$ und $y<z$ folgt $x<z$.
konnex	Für zwei verschiedene Zahlen $x$ und $y$ gilt entweder $x<y$ oder $y<x$.
trichotom	Die Kleiner-Relation ist asymmetrisch und konnex.
nicht linear	Für die Zahlen $x=1$ und $y=1$ gilt weder $x<y$ noch $y<x$.
nicht reflexiv	Es ist beispielsweise $1\not <1$.
nicht symmetrisch	Es ist beispielsweise $23<42$, aber nicht auch $42<23$.

Aus dem Abschnitt zu den Eigenschaften binärer Relationen wissen wir, dass eine binäre Relation genau dann trichotom ist, wenn sie gleichzeitig irreflexiv, asymmetrisch, konnex und antisymmetrisch ist. Dementsprechend müssen wir von einer binären Relation nur die Trichotomie und die Transitivität fordern und es folgt dann bereits, dass diese Relation genau dieselben Eigenschaften wie die Echt-Kleiner-Relation besitzt. Deswegen wählen wir die Trichotomie und die Transitivität als die charakteristischen Eigenschaften einer strikten Totalordnung:

Definition (strikte Totalordnung)

Eine binäre und homogene Relation $<$ auf der Grundmenge $M$ heißt strikte Totalordnung, wenn $<$ folgende Eigenschaften besitzt:

• $\forall x,y,z\in M:x<y\land y<z\Rightarrow x<z$ (Transitivität)
• $\forall x,y\in M:x<y\ {\dot {\lor }}\ x=y\ {\dot {\lor }}\ y<x$ (Trichotomie)

Das Symbol ${\dot {\lor }}$ ist dabei die Kontravalenz, also die Entweder-Oder-Verknüpfung zwischen Aussagen. Wir zeigen nun, dass die mit Hilfe einer Totalordnung $\leq$ definierte Relation $<$ eine strikte Totalordnung ist.

Satz

Sei $\leq$ eine Totalordnung auf $M$ und die Relation $<$ wie folgt definiert: $x<y:\Leftrightarrow x\leq y\land x\neq y$. Dann ist $<$ eine strikte Totalordnung auf $M$.

Beweis

Zu zeigen ist, dass $<$ transitiv und trichotom ist.

Beweisschritt: $<$ ist transitiv

Gelte $x<y\land y<z$. Nach Definition von $<$ gilt dann: $(x\leq y\land x\neq y)\land (y\leq z\land y\neq z)$. Mit der Transitivität von $\leq$ folgt $x\leq z$. Weiterhin folgt aus $x\neq y$ mit der Antisymmetrie von $\neg (x\leq y)\lor \neg (y\leq x)$. Da $x\leq y$ gilt, muss $\neg (y\leq x)$ gelten. Wäre nun $x=z$, würde daraus $\neg (y\leq z)$ folgen - Widerspruch! Also gilt $x\neq z$. Insgesamt haben wir $x\leq z\land x\neq z$ gezeigt, was nach Definition von $<$ gerade $x<z$ ist.

Beweisschritt: $<$ ist trichotom

Gelte $x=y$, dann gilt nach Definition von $<$ weder $x<y$ noch $y<x$. Gelte nun $x\neq y$. Mit der Linearität von $\leq$ gilt $x\leq y\lor y\leq x$. Wegen der Antisymmetrie von $\leq$ kann aber wegen $x\neq y$ nicht beides gelten, also: $x\leq y\,{\dot {\lor }}\,y\leq x$. Daraus folgt $x<y\,{\dot {\lor }}\,y<x$. In beiden Fällen gilt also $x<y\,{\dot {\lor }}\,x=y\,{\dot {\lor }}\,y<x$.

Aufgabe: Sei $\leq$ eine Totalordnung. Beweise, dass dann auch die Relation $>$ definiert durch $x>y:\Leftrightarrow y\leq x\land y\neq x$ eine strikte Totalordnung ist.

Sei $\leq$ eine Totalordnung auf $M$. Wie im vorigen Abschitt gezeigt ist dann auch $\geq$ mit $x\geq y:\Leftrightarrow y\leq x$ eine Totalordnung auf $M$. Die Definition von $>$ lässt sich wie folgt umschreiben: $x>y:\Leftrightarrow y\leq x\land x\neq y$, also gilt $x>y\Leftrightarrow x\geq y\land x\neq y$. Nunmehr folgt der Beweis genauso wie eben für $<$ gezeigt.

Sobald eine strikte Totalordnung $<$ definiert wurde, können ähnlich wie bei der Totalordnung weitere Ordnungsrelationen auf $<$ zurückgeführt werden:

Definition (Weitere Ordnungsrelationen auf Grundlage der strikten Totalordnung)

Sei $<$ eine strikte Totalordnung auf der Grundmenge $M$. Dann sind die weiteren Ordnungsrelationen $\leq$, $\geq$ und $>$ auf $M$ folgendermaßen definiert:

• $x\leq y:\Leftrightarrow x<y\lor x=y$
• $x\geq y:\Leftrightarrow y>x\lor x=y$
• $x>y:\Leftrightarrow y<x$

Aufgabe: Sei $<$ eine strikte Totalordnung. Beweise, dass dann auch die Relation $\leq$ definiert durch $x\leq y:\Leftrightarrow y<x\lor y=x$ eine Totalordnung ist.

Zu zeigen ist, dass $\leq$ reflexiv, antisymmetrisch, transitiv und linear ist.

Beweisschritt: $\leq$ ist reflexiv

Es gilt $x=x$, also auch $x\leq x$.

Beweisschritt: $\leq$ ist antisymmetrisch

Gelte $x\leq y\land y\leq x$. Nach Definition von $\leq$ gilt dann: $(x<y\lor x=y)\land (y<x\lor y=x)$. Wegen der Trichotomie von $<$ können aber nicht $x<y$ und $y<x$ gemeinsam gelten oder eine der beiden Ungleichungen zusammen mit der Gleichung, also folgt $x=y$.

Beweisschritt: $\leq$ ist transitiv

Gelte $x\leq y\land y\leq z$. Dann gilt nach Definition von $\leq$ $(x<y\lor x=y)\land (y<z\lor y=z)$. Ist $x=y$ folgt $x=z$, also gilt $x\leq z$. Ist $y=z$, folgt ebenfalls $x=z$ und damit $x\leq z$. Gelte also $x\neq y$ und $y\neq z$. Dann gelten $x<y$ und $y<z$ und mit der Transitivität von $<$ folgt $x<z$ und somit auch $x\leq z$.

Beweisschritt: $\leq$ ist linear

Mit der Trichotomie von $<$ gilt entweder $x<y$ oder $x=y$ oder $y<x$. Im ersten Fall gilt $x\leq y$, ebenso im zweiten Fall. Im zweiten Fall gilt zusätzlich $y\leq x$. Im dritten Fall gilt $y\leq$. Insgesamt gilt $x\leq y\lor y\leq x$.

Die Beweis, dass $\geq$ eine Totalordnung ist verläuft analog.

Aufgabe: Sei $<$ eine strikte Totalordnung. Beweise, dass dann auch die Relation $>$ definiert durch $x>y:\Leftrightarrow y<x$ eine strikte Totalordnung ist.

Zu zeigen ist, dass $>$ transitiv und trichotom ist.

Beweisschritt: $>$ ist transitiv

Sei $x>y\land y>z$. Nach Definition von $>$ gilt dann auch: $y<x\land z<y$. Mit der Transitivität von $<$ folgt daraus $z<x$, also gilt $x>z$.

Beweisschritt: $>$ ist trichotom

Es gilt $x>y\,{\dot {\lor }}\,x=y\,{\dot {\lor }}\,y>x$. Nach Definition von $>$ folgt daraus: $y>x\,{\dot {\lor }}\,x=y\,{\dot {\lor }}\,x>y$, das ist die Trichotomie von $>$.

Aufgabe: Sei $\leq$ eine Totalordnung auf der Menge $M$ und $<$ wie üblich definiert. Zeige:

$\forall x,y\in M:(x<y\Leftrightarrow y\nleq x)$

Beweis:

Gilt $x<y$, so gilt nach Definition $x\leq y$ und $x\neq y$. Aus $x\neq y$ folgt wegen der Antisymmetrie $x\nleq y\lor y\nleq x$. Da $x\nleq y$ nicht gilt, muss $y\nleq x$ gelten. Gelte nun $y\nleq x$. Dann folgt mit der Linearität $x\leq y$. Gälte $x=y$, dann folgte mit der Reflexivität $y\leq x$ ↯. Also gilt $x\neq y$ und insgesamt folgt $x<y$.

Aufgabe: Sei $\leq$ eine transitive binäre Relation auf der Menge $M$ und $<$ wie üblich definiert. Zeige: Gilt $\forall x,y\in M:(x<y\Leftrightarrow y\nleq x)$, so ist $\leq$ eine Totalordnung auf $M$.

Beweis:

Mit der Definition von $<$ lautet die Voraussetzung:

$(\ast )\quad x\leq y\land x\neq y\Leftrightarrow y\nleq x$

Da $\leq$ transitiv ist, sind nur noch die drei anderen Eigenschaften zu zeigen.

Beweisschritt: Reflexivität

Für den Spezialfall $y=x$ ist die linke Seite von (*) immer falsch. Also ist auch die rechte Seite falsch und es gilt die Reflexivität: $x\leq x$.

Beweisschritt: Antisymmetrie

Gelte $x\leq y\land y\leq x$. Dann ist (*) nur wahr, wenn $x=y$ gilt. Das zeigt die Antisymmetrie.

Beweisschritt: Linearität

Gilt $y\leq x$, dann gilt auch $x\leq y\lor y\leq x$, also die Linearität. Gelte nun $y\nleq x$. Dann liefert (*) $x\leq y\land x\neq y$, also ebenfalls die Linearität.

Also ist $\leq$ eine Totalordnung. ✔

Zusammenhang von strikter Totalordnung zur Totalordnung

In den vorherigen beiden Abschnitten haben wir dargelegt, wie man aus einer Totalordnung und einer strikten Totalordnung einer Menge die jeweils andere Ordnung definieren kann. Es fehlt aber noch der Beweis, dass beide Wege gleichwertig sind, dass es also egal ist, welchen Weg man geht. Um dies zu zeigen, muss Zweierlei gezeigt werden:

1. Sei $\leq _{1}$ eine Totalordnung, von der man die strikte Totalordnung $<$ über $x<y:\Leftrightarrow x\leq _{1}y\land x\neq y$ bildet. Wenn man nun wieder die von $<$ induzierte Totalordnung $\leq _{2}$ über $x\leq _{2}y:\Leftrightarrow x<y\lor x=y$ bildet, dann müssen die beiden Relationen $\leq _{1}$ und $\leq _{2}$ identisch sein. Es muss also gelten $x\leq _{2}y\Leftrightarrow x\leq _{1}y$.
2. Analoges muss gelten, wenn man bei einer strikten Totalordnung $<_{1}$ beginnt und über den Zwischenschritt der von $<_{1}$ induzierten Totalordnung $\leq$ die von $\leq$ induzierte strikte Totalordnung $<_{2}$ bildet: $x<_{2}y\Leftrightarrow x<_{1}y$.

Beweis

Sei $\leq _{1}$ eine Totalordnung und $\leq _{2}$ definiert über $x\leq _{2}y:\Leftrightarrow x<y\lor x=y$, wobei $<$ definiert ist über $x<y:\Leftrightarrow x\leq _{1}y\land x\neq y$.

Beweisschritt: $x\leq _{2}y\Leftrightarrow x\leq _{1}y$

Es gilt:

${\begin{aligned}&\;x\leq _{2}y\\[0.3em]&\;{\color {Orange}\left\updownarrow \ {\mathsf {Definition\;von\;\leq _{2}}}\right.}\\[0.3em]\Leftrightarrow &\;x<y\lor x=y\\[0.3em]&\;{\color {Orange}\left\updownarrow \ x<y\Leftrightarrow x\leq _{1}y\land x\neq y\right.}\\[0.3em]\Leftrightarrow &\;(x\leq _{1}y\land x\neq y)\lor x=y\\[0.3em]&\;{\color {Orange}\left\updownarrow \ {\mathsf {Distributivgesetz:\;}}(A\land B)\lor C\Leftrightarrow (A\lor C)\land (B\lor C)\right.}\\[0.3em]\Leftrightarrow &\;(x\leq _{1}y\lor x=y)\land (x\neq y\lor x=y)\\[0.3em]&\;{\color {Orange}\left\updownarrow \ A\lor \neg A{\mathsf {\;ist\;eine\;Tautologie\;(immer\;wahr)}}\right.}\\[0.3em]\Leftrightarrow &\;(x\leq _{1}y\lor x=y)\land {\mathsf {W}}\\[0.3em]&\;{\color {Orange}\left\updownarrow \ A\land {\mathsf {W}}\Leftrightarrow A\right.}\\[0.3em]\Leftrightarrow &\;x\leq _{1}y\lor x=y\\[0.3em]&\;{\color {Orange}\left\updownarrow \ \leq _{1}{\mathsf {\;ist\;reflexiv}}\right.}\\[0.3em]\Leftrightarrow &\;x\leq _{1}y\end{aligned}}$

Den letzten Beweisschritt wollen wir näher ausführen: Um die Äquivalenz $x\leq _{1}y\Leftrightarrow x\leq _{1}y\lor x=y$ zu zeigen, müssen wir die beiden Implikationen $x\leq _{1}y\Rightarrow x\leq _{1}y\lor x=y$ und $x\leq _{1}y\lor x=y\Rightarrow x\leq _{1}y$ beweisen. Die erste Implikation ist klar, weil $A\Rightarrow A\lor B$ unabhängig von der Aussage $B$ stets wahr ist. Wenn wir in der zweiten Implikation mit der Prämisse $x\leq _{1}y\lor x=y$ starten, dann ist einer der beiden Fälle $x\leq _{1}y$ und $x=y$ wahr. In beiden Fällen gilt $x\leq _{1}y$, denn im ersten Fall gilt es sowieso und im zweiten Fall folgt es aus der Reflexivität von $\leq _{1}$.

Sei nun $<_{1}$ eine strikte Totalordnung. Sei $\leq$ die von $<_{1}$ induzierte Totalordnung mit $x\leq y\Leftrightarrow x<_{1}y\lor x=y$. Sei wiederum $<_{2}$ definiert über $x<_{2}y\Leftrightarrow x\leq y\land x\neq y$.

Beweisschritt: $x<_{2}y\Leftrightarrow x<_{1}y$

Es gilt:

${\begin{aligned}&\;x<_{2}y\\[0.3em]&\;{\color {Orange}\left\updownarrow \ {\mathsf {Definition\;von\;<_{2}}}\right.}\\[0.3em]\Leftrightarrow &\;x\leq y\land x\neq y\\[0.3em]&\;{\color {Orange}\left\updownarrow \ x\leq y\Leftrightarrow x<_{1}y\lor x=y\right.}\\[0.3em]\Leftrightarrow &\;(x<_{1}y\lor x=y)\land x\neq y\\[0.3em]&\;{\color {Orange}\left\updownarrow \ {\mathsf {Distributivgesetz:\;}}(A\lor B)\land C\Leftrightarrow (A\land C)\lor (B\land C)\right.}\\[0.3em]\Leftrightarrow &\;(x<_{1}y\land x\neq y)\lor (x=y\land x\neq y)\\[0.3em]&\;{\color {Orange}\left\updownarrow \ A\land \neg A{\mathsf {\;ist\;immer\;falsch\;}}({\mathsf {F}})\right.}\\[0.3em]\Leftrightarrow &\;(x<_{1}y\land x\neq y)\lor {\mathsf {F}}\\[0.3em]&\;{\color {Orange}\left\updownarrow \ A\lor F\Leftrightarrow A{\mathsf {\;ist\;eine\;Tautologie}}\right.}\\[0.3em]\Leftrightarrow &\;(x<_{1}y\land x\neq y)\\[0.3em]&\;{\color {Orange}\left\updownarrow \ <_{1}{\mathsf {\;ist\;irreflexiv}}\right.}\\[0.3em]\Leftrightarrow &\;x<_{1}y\end{aligned}}$

Halbordnung

Es gibt Relationen, die bis auf die Linearität alle Eigenschaften der Totalordnung erfüllen. Damit verhalten sie sich fast wie Totalordnungen. Jedoch können bei diesen Relationen nicht alle Paare von Elemente der Grundmenge miteinander verglichen werden. Diese Relationen werden Halbordnungen oder partielle Ordnungen genannt (eben weil diese Ordnungen nur „zur Hälfte“ Totalordnungen sind):

Definition (Halbordnung)

Eine Halbordnung $R\subseteq M\times M$ ist eine binäre und homogene Relation auf der Grundmenge $M$, die folgende Eigenschaften besitzt:

• reflexiv
• antisymmetrisch
• transitiv

Beispiel (Halbordnung)

• Die Ist-Teiler-von-Beziehung auf $\mathbb {N}$ ist eine Halbordnung.
• Die Teilmengenbeziehung auf jeder Menge von Mengen ist eine Halbordnung.

Aus der Definition folgt, dass jede Totalordnung eine Halbordnung ist. Aber nicht jede Halbordnung ist eine Totalordnung.

Aufgabe: Gib ein Beispiel für eine Halbordnung an, die keine Totalordnung ist.

Die Teilmengenbeziehung $\subseteq$ auf der Potenzmenge ${\mathcal {P}}(\{1,2\})=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$ ist eine Halbordnung, aber keine Totalordnung. So gilt für die Mengen $\{1\}$ und $\{2\}$ weder $\{1\}\subseteq \{2\}$ noch $\{2\}\subseteq \{1\}$ und damit ist $\subseteq$ keine totale Relation.

Quasiordnung

Quasiordnungen sind sowohl Verallgemeinerungen der Halbordnung als auch der Äquivalenzrelation

Noch allgemeiner sind Quasiordnungen, auch Präordnungen genannt. Bei ihnen wird die Antisymmetrie nicht mehr verlangt.

Definition (Quasiordnung)

Eine Quasiordnung $R\subseteq M\times M$ ist eine binäre und homogene Relation auf der Grundmenge $M$, die folgende Eigenschaften besitzt:

• reflexiv
• transitiv

Beispiel (Quasiordnung)

• Die Ist-Teiler-von-Beziehung $x\mid y$ auf $\mathbb {Z}$ ist eine Quasiordnung.

Diese Relation ist nicht antisymmetrisch, denn es gilt beispielsweise $3\mid -3$ und $3\mid -3$ aber nicht $3=-3$. Auf $\mathbb {N}$ dagegen ist die Relation $|$ eine Halbordnung.

Der Begriff der Quasiordnung verallgemeinert nicht nur den der Halbordnung, sondern zugleich auch den der Äquivalenzrelation.

Nachweis von Ordnungsrelationen

Wenn du die Aufgabe hast zu entscheiden, ob eine gegebene Relation eine Totalordnung bzw. eine Halbordnung ist, so musst du schauen, ob diese Relation alle notwendigen Eigenschaften für diese Art von Relation erfüllt. Der folgende Entscheidungsbaum demonstriert dir die Vorgehensweise:

Entscheidungsbaum zum Nachweis von Ordnungsrelationen

Beispielaufgabe

Aufgabe

Ist die Relation „$x$ ist eine Teilmenge von $y$“ auf der Grundmenge ${\mathcal {P}}(\mathbb {R} )$, der Menge aller Teilmengen von $\mathbb {R}$, eine Halbordnung bzw. eine Totalordnung?

Lösung

Hier kannst du schrittweise vorgehen:

Beweisschritt: Ist die Relation reflexiv?

Ja, die Relation ist reflexiv, denn jede Menge ist nach Definition eine Teilmenge von sich selbst (Für alle Mengen $M$ gilt $M\subseteq M$).

Beweisschritt: Ist die Relation antisymmterisch?

Ja, die Relation ist antisymmetrisch, weil aus $A\subseteq B$ und $B\subseteq A$ die Gleichheit $A=B$ folgt.

Beweisschritt: Ist die Relation transitiv?

Ja, die Relation ist transitiv, weil aus $A\subseteq B$ und $B\subseteq C$ die Beziehung $A\subseteq C$ folgt.

Beweisschritt: Ist die Relation linear?

Nein, die Relation ist nicht linear. So ist weder $\{1,2,3\}\subseteq \{4,5,6\}$ noch ist $\{4,5,6\}\subseteq \{1,2,3\}$.

Beweisschritt: Ist die Relation eine Halbordnung bzw. eine Totalordnung?

Da die Relation reflexiv, antisymmetrisch und transitiv ist, ist sie eine Halbordnung. Da die Relation aber nicht linear ist, ist sie keine Totalordnung.