Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 10

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Die Ordnungsrelation

Wir wollen auf den natürlichen Zahlen die Größer- bzw. genauer die Größergleich-Ordnung einführen.


Definition  

Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge , also .


Definition  

Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

  1. Es ist für alle .
  2. Aus und folgt stets .
  3. Aus und folgt .

Diese Eigenschaften heißen der Reihe nach Reflexivität, Transitivität und Antisymmetrie.


Definition  

Eine Ordnungsrelation auf einer Menge heißt lineare Ordnung (oder totale Ordnung), wenn zu je zwei Elementen die Beziehung oder gilt.



Die Ordnung auf den natürlichen Zahlen

Definition  

Man sagt, dass eine natürliche Zahl größergleich einer natürlichen Zahl ist, geschrieben

wenn man von aus durch endlichfaches Nachfolgernehmen zu gelangt.

Auf dem nach rechts verlaufenden Zahlenstrahl bedeutet , dass sich weiter rechts als befindet. Diese Intepretation gilt für alle reellen Zahlen.

Statt schreibt man auch (gesprochen kleinergleich). Die Schreibweise bedeutet und .



Lemma  

Für natürliche Zahlen gilt

genau dann, wenn es ein mit

gibt.

Beweis  

Die Zahl gibt an, wie oft man von aus den Nachfolger nehmen muss, um zu zu gelangen.




Lemma  

Für die Größergleich-Relation in den natürlichen Zahlen gelten die folgenden Aussagen.

  1. Es ist

    für alle .

  2. Es ist

    oder

  3. Bei

    gilt

    oder

Beweis  

Wir verwenden die Charakterisierung aus Lemma 10.5.

  1. Ist klar wegen .
  2. Wir zeigen die Aussage oder für alle durch Induktion über . Für ist die Aussage klar. Sei also angenommen, dass die Aussage für ein bestimmtes gelte. Dann ist oder . Im ersten Fall ist dann und insbesondere . Im zweiten Fall ist mit einem und damit .
  3. Wird ähnlich wie (2) bewiesen, siehe Aufgabe 10.6.




Satz  

Auf den natürlichen Zahlen

ist durch die Größergleich-Relation eine totale Ordnung definiert.

Beweis  

Wir verwenden die Charakterisierung mit der Addition. Wegen ist . Wenn und ist, so bedeutet dies, dass es natürliche Zahlen mit und gibt. Dann gilt insgesamt

und somit ist auch . Aus und ergibt sich und und somit . Dies ist nach der Abziehregel nur bei möglich, und dies ist wiederum, da kein Nachfolger ist, nur bei möglich. Die Aussage oder beweisen wir durch Induktion über (für jedes feste ), wobei der Induktionsanfang wegen klar ist. Die Aussage gelte also für ein bestimmtes . Wenn die erste Möglichkeit gilt, also , so gilt wegen

erst recht . Wenn die zweite Möglichkeit gilt, also , so gibt es zwei Möglichkeiten. Bei ist und die Gesamtaussage gilt für . Andernfalls ist und somit ist nach Lemma 10.6  (3) und die Gesamtaussage gilt erneut.


Wir begründen nun, dass die Ordnungsrelation mit der Addition und der Multiplikation verträglich ist.



Satz  

Es seien natürliche Zahlen. Dann gelten folgende Aussagen.

  1. Es ist

    genau dann, wenn

    ist.

  2. Aus

    und

    folgt

  3. Aus

    folgt

  4. Aus

    und

    folgt

  5. Aus

    und

    folgt

Beweis  

  1. Wir beweisen die Aussage duch Induktion über . Bei ist die Aussage klar. Für den Induktionsschritt müssen wir lediglich zeigen, dass die Aussage für gilt. Bei ist die Aussage klar, da der Nachfolger wohldefiniert ist. Bei ist nach Lemma 10.6  (3) und somit

    Dies zeigt zugleich, dass aus auch folgt. Da die Ordnung total ist, folgt somit auch aus die Beziehung .

  2. Zweifache Anwendung von Teil (1) liefert

    so dass die Transitivität den Schluss ergibt.

  3. Wir führen Induktion nach , die Fälle sind klar. Sei die Aussage für bewiesen. Dann ist mit dem Distributivgesetz, der Induktionsvoraussetzung und Teil (2)
  4. Aus den Voraussetzungen und Teil (3) ergibt sich
  5. Sei und . Dann ist und somit ist nach Teil (3)

    also .

Die algorithmische Bestimmung der Ordnungsrelation im Dezimalsystem werden wir in Korollar 15.4 beschreiben.



Maxima und Minima

Definition  

Zu einer endlichen nichtleeren Teilmenge heißt das Maximum von , wenn ist und wenn für alle gilt.


Definition  

Zu einer nichtleeren Teilmenge heißt das Minimum von , wenn ist und wenn für alle gilt.

Die leere Menge besitzt weder ein Maximum noch ein Minimum. Die Gesamtmenge besitzt das Minimum und kein Maximum.

Aus dem Induktionsprinzip folgt die nächste wichtige Eigenschaft, die besagt, dass die natürlichen Zahlen wohlgeordnet sind. Vom intuitiven Standpunkt her ist sie selbstverständlich, wir führen sie aber trotzdem auf das Induktionsprinzip zurück. Es geht in diesem Beweis weniger dadrum, sich über die Satzaussage zu vergewissern, sondern vielmehr Einblicke in mathematisches Argumentieren zu gewinnen. Es ist auch ein Beispiel dafür, wie man eine Aussage über Teilmengen zu einer Aussage über natürliche Zahlen macht, um das Induktionsprinzip anwenden zu können.



Lemma  

Jede nichtleere Teilmenge

besitzt ein Minimum.

Beweis  

Wir betrachten die Aussage

= Alle Teilmengen von , die enthalten, besitzen ein Minimum.

Da jede nichtleere Teilmenge mindestens ein besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von für alle . Diese Aussage können wir durch Induktion beweisen. Die Aussage besagt, dass jede Teilmenge , die die enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben das Minimum ist. Sei die Aussage nun für alle schon bewiesen. Wir müssen beweisen. Sei also eine Teilmenge, die enthält. Wenn auch eine Zahl besitzt, so besitzt nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt keine Zahl, die kleiner als ist. Dann ist aber das Minimum von .




Die Differenz von natürlichen Zahlen
Aus einer Menge mit Elementen wird eine Teilmenge mit Elementen () herausgenommen. Zurück bleibt eine Menge mit Elementen.

Definition  

Für natürliche Zahlen

ist diejenige natürliche Zahl für die

gilt. Sie heißt die Differenz zwischen und .

Man mache sich hier die Logik dieser Definition klar: Die Voraussetzung

bedeutet nach Lemma 10.5 die Existenz einer natürlichen Zahl mit

Dieses ist aufgrund der Abziehregel durch diese Eigenschaft eindeutig bestimmt. Die Differenz gibt an, wie oft man von aus den Nachfolger nehmen muss, um zu zu gelangen. Die charakteristische Eigenschaft ist die Gleichheit

Dabei ist die einzige Lösung für die Gleichung[1]

Ferner ist . Wenn eine Gleichung gegeben ist, so sagt man beim Übergang zu

auch, dass (beidseitig) abgezogen wird.

Für ist der Ausdruck innerhalb der natürlichen Zahlen nicht definiert. Da zu stets

oder

gilt, ist einer der beiden Ausdrücke oder eine wohldefinierte natürliche Zahl. Oft nennt man auch diese Zahl, die sich ergibt, wenn man die beiden Zahlen richtig geordnet hat, die Differenz der beiden Zahlen.

Für die Differenz können wir einfach eine mengentheoretische Interpretation angeben.



Satz  

Es sei eine endliche Menge mit Elementen und es sei

eine Teilmenge, die Elemente besitze.

Dann besitzt

genau Elemente.

Beweis  

Es ist

eine disjunkte Zerlegung. Daher gilt nach Satz 8.14

Somit erfüllt die charakteristische Eigenschaft der Differenz und ist daher gleich .




Lemma  

  1. Für natürliche Zahlen mit

    ist

    Insbesondere ist .

  2. Für natürliche Zahlen mit

    und

    ist

    Insbesondere ist bei stets und .

  3. Bei

    ist und es ist

Beweis  

  1. Aus

    ergibt sich direkt

    Der Zusatz ergibt sich aus der Eindeutigkeit der Differenz.

  2. Wegen Satz 10.8  (2) ist

    so dass der Ausdruck links einen Sinn ergibt. Die Rechnung

    unter Verwendung der ersten Teils zeigt, dass die charakteristische Eigenschaft von erfüllt, also wegen der Eindeutigkeit damit übereinstimmt.

  3. Nach Teil (2) folgt aus und die Beziehung

    und insbesondere . Beidseitiges Abziehen von ergibt


Die folgende Aussage ist das Distributivgesetz für die Differenz.



Lemma  

Es seien natürliche Zahlen mit .

Dann ist

Beweis  

Nach Satz 10.8 ist mit auch , so dass wohldefiniert ist. Es ist

und daher ist nach dem Distributivgesetz für die Addition und die Multiplikation

Also ist



Fußnoten
  1. Das Gleichungskonzept werden wir später genauer besprechen.


<< | Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)