Benutzer:Jürgen-Michael Glubrecht/Funktion

Aus Wikibooks

Ordnungsrelation[Bearbeiten]

Totalordnung[Bearbeiten]

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. ✔


Satz

Sei eine Totalordnung auf der Menge . Sei weiterhin die 2-stellige Relation auf wie folgt definiert:

Dann gilt: .

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 .

Wohlordnungen[Bearbeiten]

Was brauchen wir zum Zählen?[Bearbeiten]

Die natürlichen Zahlen benutzen wir zum Zählen. Ist eine beliebige Menge gegeben, so können wir den Elementen von der Reihe nach natürliche Zahlen zuordnen: . Haben wir auf diese Weise alle Elemente von gezählt und sind dabei bei einer Zahl angekommen, hat genau Elemente. Gleichzeitig haben wir die Elemente von in eine Reihenfolge gebracht. Während die Menge ungeordnet ist, ist die abgezählte Menge geordnet. Diese Ordnung ist durch die Ordnungsrelation auf den natürlichen Zahlen gegeben, denn ist auf den natürlichen Zahlen eine strikte Totalordnung. Zur Erinnerung:

Definition (strikte Totalordnung)

Eine binäre und homogene Relation auf einer Menge heißt strikte Totalordnung, wenn für alle die folgenden Eigenschaften besitzt:

  • (irreflexiv)
  • (transitiv)
  • (konnex)

Verständnisfrage: Zeige:

  1. In der letzten Bedingung lässt sich das "oder" () zu "entweder - oder" () verschärfen.
  2. Aus der verschärften Bedingung folgt die Irreflivität.

  1. Wenn oder gälte, folgte , im Widerspruch zur Irreflivität. Gälte , folgte mit der Transitivität ebenfalls . ↯
  2. Gelte nun . Dann gilt wegen auch , also .

Nun ist auch auf den ganzen Zahlen und auf den reellen Zahlen eine strikte Totalordnung. Aber zum Zählen sind diese Ordnungen nicht zu gebrauchen. Warum? Was benötigen wir eigentlich zum Zählen? Wir brauchen dazu zwei Bedingungen:

  • ein eindeutiges Element für den Anfang,
  • einen eindeutiges nächstes Element, um weiterzuzählen, wenn wir schon eine Weile gezählt haben.

Aber und haben keinen eindeutigen Anfang und hat auch keinen eindeutigen Nachfolger. Wenn aber für die strikte Totalordnung gilt:

(*)   jede nichtleere Teilmenge hat ein kleinstes Element,

dann gelten die oben genannten Bedingungen für das Zählen:

  • das kleinste Element der strikten Totalordnung ist der Anfang,
  • mit dem kleinsten Element der Menge der Elemente der Totalordnung, die wir noch nicht zum Zählen genutzt haben, zählen wir weiter.

Eine strikte Totalordnung, die zum Zählen geeignet ist, wird Wohlordnuing genannt.

Definition der Wohlordnung[Bearbeiten]

Definition (Wohlordnung)

Eine strikte Totalordnung auf der Menge ist eine Wohlordnung genau dann, wenn jede nichtleere Teilmenge ein kleinstes Element hat:

Dabei ist definiert als .

Die Bedingung des kleinsten Elements ist in einer strikten Totalordnung gleichwertig zur der Bedingung, dass jede nichtleere Teilmenge von A ein minmales Element hat:

(**)  

Verständnisfrage: Zeige: in einer strikten Totalordnung gilt (*) (**).

Sei und gelte . In einer strikten Totalordnung gilt . Mit (*) gilt , also auch , also (**). Gilt umgekehrt , sind nur noch die beiden anderen Fälle möglich: .

Satz

Die natürlichen Zahlen sind mit der Echt-Kleiner-Relation eine Wohlordnung.

Beweis

ist mit eine strikte Totalordnung, vgl. Kapitel Ordnungsrelation.

Wir zeigen, dass jede nichtleere Teilmenge ein kleinstes Element hat. Annahme: hat kein kleinstes Element. Wir müssen dann zeigen: . Dazu definieren wir und zeigen durch Induktion über :

Induktionsbehauptung:

Induktionsanfang: , denn da kein kleinstes Element hat, gilt .

Induktionsschritt: Gelte . Wäre , so wäre das kleinste Element in , denn alle kleineren Elemente von liegen ja in . Also gilt .

Damit ist die Induktionsbehauptung bewiesen. Daher ist und weil als definiert war, folgt . ✔

Folgerung: Jede Teilmenge von ist eine Wohlordnung.

Sei . Die Einschränkung von auf ist eine strikte Totalordnung. Weiterhin haben wir gerade bewiesen, dass jede Teilmenge von ein kleinstes Element hat, insbesondere also auch jede Teilmenge von .

Die ganzen Zahlen mit der Relation sind keine Wohlordnung, denn hat kein kleinstes Element. Wir können aber eine modifizierte Ordnung auf definieren, so dass eine Wohlordnung ist. Die Idee ist folgende: alle negativen Zahlen sind größer als alle postiven Zahlen, für die positiven Zahlen einschließlich der Null stimmt mit überein, für die negativen Zahlen setzen wir . In aufzählender Schreibweise lässt sich das so darstellen:

Satz (Beispiel)

Auf den ganzen Zahlen sei die 2-stellige Relation wie folgt definiert:

Dann ist eine Wohlordnung auf

Beweis (Beispiel)

ergibt sich aus der Definition indem die einzelnen Fälle betrachtet werden. Wir zeigen die Transitivität: Sei . Sei und . Ist gilt , anderenfalls folgt die Transitivität mit der Transitivität von . Ist und , so muss auch sein, als gilt . Ist schließlich , so sind auch und . Dann ergibt sich die Transitivität aus der Transitivität von .

Sei eine nichtleere Teilmenge von . Hat Elemente aus den positiven Zahlen einschließlich , so ist das kleinste Elelement bezüglich auch das kleinste Element bezüglich . Enthält nur negative Zahlen, so gibt es ein größtes Element bezüglich . Für gilt also . Das heißt aber nach Definition von gerade . ✔