Ordnungsrelation – Mathe für Nicht-Freaks

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Eine Ordnung ist wie die Äquivalenzrelation eine besondere Klasse binärer, homogener Relationen. Sie ist eine Verallgemeinerung der Ordnungsrelationen wie oder , die du bereits für die reellen Zahlen kennst. Mit Hilfe von Ordnungsrelationen kannst du also Elemente einer Grundmenge ihrer Größe nach ordnen und miteinander vergleichen.

Um eine Ordnung auf einer Menge zu definieren, reicht es eine der Relationen , , oder anzugeben. Die anderen Ordnungsrelationen können dann auf die bereits definierte Relation zurückgeführt werden. Wenn man beispielsweise die Ordnung schon definiert hat, so ergibt sich automatisch die Ordnung , denn es ist genau dann , wenn und ist.

Totalordnung[Bearbeiten]

Transitivität: Aus und folgt

Totalordnungen sind direkte Verallgemeinerungen der Kleiner-Gleich-Relation auf den reellen Zahlen. Genau wie die Äquivalenzrelation wird die Totalordnung über ihre Eigenschaften definiert.

Frage: Welche Eigenschaft besitzt die Relation „“ auf der Grundmenge ?

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 nun genau dann eine Totalordnung, wenn sie genau diejenigen Eigenschaften hat, die auch die Kleiner-Gleich-Relation für die reellen Zahlen besitzt:

Dialog-information.svg
Definition (Totalordnung)

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

  • (Reflexivität)
  • (Antisymmetrie)
  • (Transitivität)
  • (Linearität)

Ist eine Totalordnung, so schreibt man anstelle von oft oder . Da eine Totalordnung die direkte Verallgemeinerung der Ordnung auf der Zahlengeraden ist, welche eine „Linie“ ist, wird eine Totalordnung auch lineare Ordnung genannt. Wie bereits gesagt, reicht es aus, für eine Menge nur die Totalordnung anzugeben. Alle weiteren Ordnungsrelationen können auf zurückgeführt werden:

Dialog-information.svg
Definition (Weitere Ordnungsrelationen auf Grundlage der Totalordnung)

Sei eine Totalordnung auf der Grundmenge . Dann sind die weiteren Ordnungsrelationen , und auf folgendermaßen definiert:

Das Symbol bedeutet dabei, dass der linke durch den rechten Term definiert wird (für Erklärungen zu den Symbolen und siehe das Kapitel zu den Junktoren).

Accessories-calculator.svg

Beispiel (Totalordnung)

  • Die Relation auf der Grundmenge ist eine Totalordnung.
  • Die Relation auf der Grundmenge ist eine Totalordnung.
  • Die lexikographische Ordnung der Wörter im Duden ist eine Totalordnung

Verständnisfrage: Sei eine Totalordnung. Beweise, dass dann auch 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 entweder oder . Nach Definition von gilt dann auch für alle und entweder oder . Dies ist die Linearitätseigenschaft von .

Emblem-important.svg

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!

Eine Totalordnung heißt nur deswegen auch „lineare Ordnung“, weil dieser Begriff von der Ordnung von abgeleitet ist, welcher die Ordnung einer Linie ist. Eine lineare Ordnung hat aber nichts mit linearen Funktionen oder linearen Abbildungen zu tun.

Strikte Totalordnung[Bearbeiten]

Wie ich im Abschnitt zur Totalordnung dargelegt habe, kann man auf einer Menge mit der Ordnungsrelation beginnen und alle weiteren Ordnungsrelationen auf diese Relation zurückführen. Es ist jedoch auch möglich, mit der Relation zu beginnen und alle weiteren Relationen damit zu definieren. Analog zur Totalordnung, sollte 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 reellen Zahlen?

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 reelle 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 Kleiner-Relation besitzt. Deswegen wählen wir die Trichotomie und die Transitivität als die charakteristischen Eigenschaften einer strikten Totalordnung:

Dialog-information.svg
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. Für strikte Totalordnungen werden oft die Symbole oder verwendet. Sobald eine strikte Totalordnung definiert wurde, können ähnlich wie bei der Totalordnung alle anderen Ordnungsrelationen auf zurückgeführt werden:

Dialog-information.svg
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:

Zusammenhang von strikter Totalordnung zur Totalordnung[Bearbeiten]

In den vorherigen beiden Abschnitten habe ich dargelegt, dass man sowohl die strikte Totalordnung als auch die Totalordnung einer Menge angeben kann, um ihre Ordnung zu definieren. 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 . Analoges muss gelten, wenn man bei einer strikten Totalordnung beginnt und über den Zwischenschritt der von induzierten Totalordnung die von induzierte strikte Totalordnung bildet.
  2. Wenn eine Totalordnung ist, dann muss die davon induzierte Relation eine strikte Totalordnung sein (dies haben wir ja noch nicht im obigen Abschnitt bewiesen). Umgekehrt muss die von einer strikten Totalordnung induzierte -Relation auch die Eigenschaften einer Totalordnung besitzen.

Beweisen wir zunächst den ersten Punkt:

Applications-office.svg

Beweis

Sei eine Totalordnung und definiert über , wobei definiert ist über .

Beweisschritt:

Es gilt:

Den letzten Beweisschritt will ich dabei 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:

Qsicon inArbeit.png
To-Do:

Beweis des zweiten Punktes

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

Dialog-information.svg
Definition (Halbordnung)

Eine Halbordnung ist eine binäre und homogene Relation auf der Grundmenge , die folgende Eigenschaften besitzt:

  • reflexiv
  • antisymmetrisch
  • transitiv
Accessories-calculator.svg

Beispiel (Halbordnung)

  • Die Relation auf der Grundmenge 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 (die Teilmengenbeziehung ist eine Halbordnung, die keine Totalordnung ist).

Quasiordnung[Bearbeiten]

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.

Dialog-information.svg
Definition (Quasiordnung)

Eine Quasiordnung ist eine binäre und homogene Relation auf der Grundmenge , die folgende Eigenschaften besitzt:

  • reflexiv
  • transitiv
Accessories-calculator.svg

Beispiel (Quasiordnung)

  • Die Ist-Teiler-von-Beziehung auf ist eine Quasiordnung.

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:

Entscheidungsbaum zum Nachweis von Ordnungsrelationen

Beispielaufgabe zum Nachweis von Ordnungsrelationen[Bearbeiten]

Accessories-text-editor.svg

Aufgabe

Ist die Relation „ ist eine Teilmenge von “ auf der Grundmenge , der Menge aller Teilmengen von , eine Halbordnung bzw. eine Totalordnung?

Applications-office.svg

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.