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.

TotalordnungBearbeiten

 
Transitivität: Aus   und   folgt  

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 TotalordnungBearbeiten

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 >math>M</math>. 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 TotalordnungBearbeiten

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   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  .
  2. 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:

 

HalbordnungBearbeiten

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.

QuasiordnungBearbeiten

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

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:

BeispielaufgabeBearbeiten

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:

Frage: 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  ).

Frage: Ist die Relation antisymmterisch?

Ja, die Relation ist antisymmetrisch, weil aus   und   die Gleichheit   folgt.

Frage: Ist die Relation transitiv?

Ja, die Relation ist transitiv, weil aus   und   die Beziehung   folgt.

Frage: Ist die Relation linear?

Nein, die Relation ist nicht linear. So ist weder   noch ist  .

Frage: 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.