Ordnungsrelation – Serlo „Mathe für Nicht-Freaks“
Ordnungen sind eine besondere Klasse binärer, homogener Relationen. Sie sind eine Verallgemeinerung der Ordnungsrelationen wie oder , die du bereits für die Zahlbereiche , und 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 oder zu definieren. Die jeweils andere Relation lässt sich dann mit den folgenden Beziehungen darauf zurückführen:
- genau dann, wenn und ,
- genau dann, wenn oder .
Ordnungsrelationen lassen sich umdrehen: so wird aus der Kleiner-Gleich-Relation die Grösser-Gleich-Relation 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
[Bearbeiten]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 auf den Zahlbereichen , und ?
Eigenschaft der Relation | Begründung |
---|---|
reflexiv | Für alle ist . |
antisymmetrisch | Aus und folgt |
transitiv | Aus und folgt |
linear | Für alle reellen Zahlen und ist oder |
nicht irreflexiv | Diese Relation ist reflexiv und die Grundmenge ist nicht leer |
nicht symmetrisch | Gegenbeispiel: Es ist aber 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 auf ist eine binäre und homogene Relation auf der Grundmenge , die folgende Eigenschaften besitzt:
- (Reflexivität)
- (Antisymmetrie)
- (Transitivität)
- (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 Relation auf der Grundmenge ist eine Totalordnung.
- Die Relation auf der Grundmenge ist eine Totalordnung.
- Die Relation auf der Grundmenge ist eine Totalordnung.
- Die alphabetische Ordnung der Wörter in einem Lexikon ist eine Totalordnung
Die Ordnungen auf den Zahlbereichen , und sind zwar alle Totalordnungen, aber sie unterscheiden sich auch! So hat ein kleinstes Element, nämlich die , aber weder noch haben ein kleinstes Element. In gibt es zwischen zwei verschiedenen Elementen mit immer ein weiteres Element mit , und . Das gilt für und nicht.
Satz
Sei eine Totalordnung auf der Menge und eine Teilmenge von . Dann ist die Einschränkung von auf eine Totalordnung auf .
Beweis
Die Einschränkung von auf ist . Die vier Eigenschaften der Totalordnung auf gelten natürlich auch für die Teilmenge . Also ist eine Totalordnung auf .
Wie bereits gesagt, ist auch die Umkehrung einer Totalordnung wieder eine Totalordnung:
Aufgabe: Sei eine Totalordnung. Beweise, dass dann auch die konverse Relation definiert durch eine Totalordnung ist.
Beweisschritt: ist reflexiv
Wir müssen beweisen, dass für alle aus der Grundmenge gilt. Nun gilt nach Definition genau dann, wenn ist. Wir wissen aber bereits, dass reflexiv ist, und damit auch, dass für alle gilt. Es folgt die Reflexivität von .
Beweisschritt: ist antisymmetrisch
Auch dies folgt aus der Antisymmetrie von . Für gilt nämlich . Setzen wir ein, folgt für alle und der Grundmenge. Dies ist die Antisymmetrieeigenschaft von .
Beweisschritt: ist transitiv
Sei und . Nach Definition ist dann und . Es folgt aus der Transitivität von . Damit gilt aber auch nach der Definition von . Ingesamt haben wir so gezeigt und damit die Transitivität von .
Beweisschritt: ist linear
Von wissen wir bereits, dass es linear ist. Also gilt für zwei und : oder . Nach Definition von gilt dann auch für alle und : oder . Dies ist die Linearitätseigenschaft von .
Definition (Weitere Ordnungsrelationen auf Grundlage der Totalordnung)
Sei eine Totalordnung auf der Grundmenge . Dann sind die weiteren Ordnungsrelationen und auf folgendermaßen definiert:
Während ebenfalls eine Totalordnung ist, ist das bei und nicht der Fall. Diese beiden Relationen sind strikte Totalordnungen:
Strikte Totalordnung
[Bearbeiten]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 , und ?
Eigenschaft der Relation | Begründung |
---|---|
irreflexiv | Für alle ist . |
antisymmetrisch | Ist , so folgt automatisch . Damit kann und nie gleichzeitig auftreten. Somit ist die Implikation stets wahr, weil die Prämisse stets falsch ist (siehe Abschnitt zur Implikation). |
asymmetrisch | Die Kleiner-Relation ist antisymmetrisch und irreflexiv. |
transitiv | Aus und folgt . |
konnex | Für zwei verschiedene Zahlen und gilt entweder oder . |
trichotom | Die Kleiner-Relation ist asymmetrisch und konnex. |
nicht linear | Für die Zahlen und gilt weder noch . |
nicht reflexiv | Es ist beispielsweise . |
nicht symmetrisch | Es ist beispielsweise , aber nicht auch . |
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 heißt strikte Totalordnung, wenn folgende Eigenschaften besitzt:
- (Transitivität)
- (Trichotomie)
Das Symbol ist dabei die Kontravalenz, also die Entweder-Oder-Verknüpfung zwischen Aussagen. Wir zeigen nun, dass die mit Hilfe einer Totalordnung definierte Relation eine strikte Totalordnung ist.
Satz
Sei eine Totalordnung auf und die Relation wie folgt definiert: . Dann ist eine strikte Totalordnung auf .
Beweis
Zu zeigen ist, dass transitiv und trichotom ist.
Beweisschritt: ist transitiv
Gelte . Nach Definition von gilt dann: . Mit der Transitivität von folgt . Weiterhin folgt aus mit der Antisymmetrie von . Da gilt, muss gelten. Wäre nun , würde daraus folgen - Widerspruch! Also gilt . Insgesamt haben wir gezeigt, was nach Definition von gerade ist.
Beweisschritt: ist trichotom
Gelte , dann gilt nach Definition von weder noch . Gelte nun . Mit der Linearität von gilt . Wegen der Antisymmetrie von kann aber wegen nicht beides gelten, also: . Daraus folgt . In beiden Fällen gilt also .
Aufgabe: Sei eine Totalordnung. Beweise, dass dann auch die Relation definiert durch eine strikte Totalordnung ist.
Sei eine Totalordnung auf . Wie im vorigen Abschitt gezeigt ist dann auch mit eine Totalordnung auf . Die Definition von lässt sich wie folgt umschreiben: , also gilt . 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 . Dann sind die weiteren Ordnungsrelationen , und auf folgendermaßen definiert:
Aufgabe: Sei eine strikte Totalordnung. Beweise, dass dann auch die Relation definiert durch eine Totalordnung ist.
Zu zeigen ist, dass reflexiv, antisymmetrisch, transitiv und linear ist.
Beweisschritt: ist reflexiv
Es gilt , also auch .
Beweisschritt: ist antisymmetrisch
Gelte . Nach Definition von gilt dann: . Wegen der Trichotomie von können aber nicht und gemeinsam gelten oder eine der beiden Ungleichungen zusammen mit der Gleichung, also folgt .
Beweisschritt: ist transitiv
Gelte . Dann gilt nach Definition von . Ist folgt , also gilt . Ist , folgt ebenfalls und damit . Gelte also und . Dann gelten und und mit der Transitivität von folgt und somit auch .
Beweisschritt: ist linear
Mit der Trichotomie von gilt entweder oder oder . Im ersten Fall gilt , ebenso im zweiten Fall. Im zweiten Fall gilt zusätzlich . Im dritten Fall gilt . Insgesamt gilt .
Die Beweis, dass eine Totalordnung ist verläuft analog.
Aufgabe: Sei eine strikte Totalordnung. Beweise, dass dann auch die Relation definiert durch eine strikte Totalordnung ist.
Zu zeigen ist, dass transitiv und trichotom ist.
Beweisschritt: ist transitiv
Sei . Nach Definition von gilt dann auch: . Mit der Transitivität von folgt daraus , also gilt .
Beweisschritt: ist trichotom
Es gilt . Nach Definition von folgt daraus: , das ist die Trichotomie von .
Aufgabe: Sei eine Totalordnung auf der Menge und wie üblich definiert. Zeige:
Beweis:
Gilt , so gilt nach Definition und . Aus folgt wegen der Antisymmetrie . Da nicht gilt, muss gelten. Gelte nun . Dann folgt mit der Linearität . Gälte , dann folgte mit der Reflexivität ↯. Also gilt und insgesamt folgt .
Aufgabe: Sei eine transitive binäre Relation auf der Menge und wie üblich definiert. Zeige: Gilt , so ist eine Totalordnung auf .
Beweis:
Mit der Definition von lautet die Voraussetzung:
Da transitiv ist, sind nur noch die drei anderen Eigenschaften zu zeigen.
Beweisschritt: Reflexivität
Für den Spezialfall ist die linke Seite von (*) immer falsch. Also ist auch die rechte Seite falsch und es gilt die Reflexivität: .
Beweisschritt: Antisymmetrie
Gelte . Dann ist (*) nur wahr, wenn gilt. Das zeigt die Antisymmetrie.
Beweisschritt: Linearität
Gilt , dann gilt auch , also die Linearität. Gelte nun . Dann liefert (*) , also ebenfalls die Linearität.
Also ist eine Totalordnung. ✔
Zusammenhang von strikter Totalordnung zur Totalordnung
[Bearbeiten]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:
- Sei eine Totalordnung, von der man die strikte Totalordnung über bildet. Wenn man nun wieder die von induzierte Totalordnung über bildet, dann müssen die beiden Relationen und identisch sein. Es muss also gelten .
- Analoges muss gelten, wenn man bei einer strikten Totalordnung beginnt und über den Zwischenschritt der von induzierten Totalordnung die von induzierte strikte Totalordnung bildet: .
Beweis
Sei eine Totalordnung und definiert über , wobei definiert ist über .
Beweisschritt:
Es gilt:
Den letzten Beweisschritt wollen wir näher ausführen: Um die Äquivalenz zu zeigen, müssen wir die beiden Implikationen und beweisen. Die erste Implikation ist klar, weil unabhängig von der Aussage stets wahr ist. Wenn wir in der zweiten Implikation mit der Prämisse starten, dann ist einer der beiden Fälle und wahr. In beiden Fällen gilt , denn im ersten Fall gilt es sowieso und im zweiten Fall folgt es aus der Reflexivität von .
Sei nun eine strikte Totalordnung. Sei die von induzierte Totalordnung mit . Sei wiederum definiert über .
Beweisschritt:
Es gilt:
Halbordnung
[Bearbeiten]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 ist eine binäre und homogene Relation auf der Grundmenge , die folgende Eigenschaften besitzt:
- reflexiv
- antisymmetrisch
- transitiv
Beispiel (Halbordnung)
- Die Ist-Teiler-von-Beziehung auf 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 auf der Potenzmenge ist eine Halbordnung, aber keine Totalordnung. So gilt für die Mengen und weder noch und damit ist keine totale Relation.
Quasiordnung
[Bearbeiten]Noch allgemeiner sind Quasiordnungen, auch Präordnungen genannt. Bei ihnen wird die Antisymmetrie nicht mehr verlangt.
Definition (Quasiordnung)
Eine Quasiordnung ist eine binäre und homogene Relation auf der Grundmenge , die folgende Eigenschaften besitzt:
- reflexiv
- transitiv
Beispiel (Quasiordnung)
- Die Ist-Teiler-von-Beziehung auf ist eine Quasiordnung.
Diese Relation ist nicht antisymmetrisch, denn es gilt beispielsweise und aber nicht . Auf 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
[Bearbeiten]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:
Beispielaufgabe
[Bearbeiten]Aufgabe
Ist die Relation „ ist eine Teilmenge von “ auf der Grundmenge , der Menge aller Teilmengen von , 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 gilt ).
Beweisschritt: Ist die Relation antisymmterisch?
Ja, die Relation ist antisymmetrisch, weil aus und die Gleichheit folgt.
Beweisschritt: Ist die Relation transitiv?
Ja, die Relation ist transitiv, weil aus und die Beziehung folgt.
Beweisschritt: Ist die Relation linear?
Nein, die Relation ist nicht linear. So ist weder noch ist .
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.