Diskrete Mathematik/Natürliche Zahlen/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Wir stellen hier einige Grundtatsachen über die natürlichen Zahlen zusammen, auf die immer wieder Bezug genommen wird. Diese Eigenschaften sind in höchstem Maße vertraut, es ist aber sinnvoll, sich einmal klar zu machen, wie die grundlegenden Strukturen auf den natürlichen Zahlen ausgehend von der Nachfolgerabbildung aufgebaut und ihre Eigenschaften nachgewiesen werden. Der induktive Aufbau der natürlichen Zahlen ist für viele Fragestellungen der diskreten Mathematik auch deshalb instruktiv, weil man diese häufig dadurch zu verstehen versucht, indem man sich überlegt, was passiert, wenn eine gewisse diskrete oder kombinatorische Situation ein bisschen (um ein zusätzliches Element, eine neue Kante, etc.) komplizierter wird.



Der induktive Aufbau der natürlichen Zahlen


Definition  

Eine Menge mit einem ausgezeichneten Element (die Null) und einer (Nachfolger)-Abbildung

heißt natürliche Zahlen (oder Dedekind-Peano-Modell für die natürlichen Zahlen), wenn die folgenden Dedekind-Peano-Axiome erfüllt sind.

  1. Das Element ist kein Nachfolger (die Null liegt also nicht im Bild der Nachfolgerabbildung).
  2. Jedes ist Nachfolger höchstens eines Elementes (d.h. die Nachfolgerabbildung ist injektiv).
  3. Für jede Teilmenge gilt: Wenn die beiden Eigenschaften
      • ,
      • mit jedem Element ist auch ,

    gelten, so ist .



    Satz  

    Es seien und Modelle für die natürlichen Zahlen.

    Dann gibt es genau eine (bijektive) Abbildung

    die das Zählen (also die und die Nachfolgerabbildung) respektiert.

    Beweis  

    Da die Abbildung insbesondere die Null respektieren soll, muss

    sein. Da die Abbildung die Nachfolgerabbildungen respektieren soll, gilt generell

    für alle . Speziell gilt

    Aus dem gleichen Grund muss unter Verwendung des schon Bewiesenen

    Ebenso muss

    u.s.w gelten. Hier hat man keine Wahlmöglichkeiten, alles ist durch die Nachfolgereigenschaft bestimmt. Da jedes Element aus von aus durch die Nachfolgerabbildung schließlich und genau einmal erreicht wird, ist dies eine wohldefinierte Abbildung von nach .

    Zum Nachweis der Surjektivität betrachten wir die Menge

    Wir müssen zeigen, dass

    ist. Dazu wenden wir das Induktionsaxiom für an. Wegen

    gehört . Wenn ist, so ist also

    für ein . Wegen der Verträglichkeit mit der Nachfolgerabbildung ist

    d.h. auch . Daher ist unter dem Nachfolger abgeschlossen und nach dem Induktionsaxiom ist also . Zum Nachweis der Injektivität seien verschieden. und zwar sei ein (direkter oder) höherer Nachfolger von . Dann ist der entsprechende Nachfolger von und insbesondere davon verschieden (siehe Aufgabe), da das Nachfolgernehmen in injektiv ist.


    Eine Visualisierung des Induktionsprinzips. Wenn die Steine nah beieinander stehen und der erste umgestoßen wird, so fallen alle Steine um.

    Die folgende Aussage und ihr Beweis begründen das Beweisprinzip der vollständigen Induktion. Wir schreiben für den Nachfolger.



    Satz  

    Für jede natürliche Zahl sei eine Aussage gegeben. Es gelte

    1. ist wahr.
    2. Für alle gilt: wenn gilt, so ist auch wahr.

    Dann gilt für alle .

    Beweis  

    Es sei

    Wir wollen zeigen, dass ist, denn genau dies bedeutet, dass die Aussage für alle gilt. Nach der ersten Bedingung ist

    Nach der zweiten Voraussetzung gilt für , dass aus stets folgt. Damit erfüllt beide Voraussetzungen im Induktionsprinzip für Mengen, so dass gilt.


    Der Nachweis von (der Gültigkeit von) heißt dabei der Induktionsanfang und der Schluss von auf heißt der Induktionsschluss oder Induktionsschritt. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage erst für für ein gewisses (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage und den Induktionsschritt führt man für alle durch.



    Die Addition

    Die Addition auf den natürlichen Zahlen ist eine vertraute Operation und es gibt viele Möglichkeiten, sie einzuführen. Je nach Kontext und Absicht sind unterschiedliche Ansätze besser geeignet. Zur rechnerischen Definition der Addition ist etwa das schriftliche Addieren im Dezimalsystem besonders effektiv, während zum Nachweis der Assoziativität die inhaltliche Interpretation als disjunkte Vereinigung von Mengen sinnvoll ist. Um ein klares Fundament zu haben, muss man sich bei einem systematisches Aufbau der Mathematik dafür entscheiden, was man als Definition nimmt, und dann beweisen, dass der gewählte Zugang auch andere Charakterisierungen erlaubt und somit mit anderen Zugängen übereinstimmt.

    Wir wollen die Addition auf den natürlichen Zahlen definieren, und zwar allein unter Bezug auf das Nachfolgernehmen, das das Zählen charakterisiert. Das Nachfolgernehmen ist ein Prozess, den man iterieren kann. Sowohl der Startwert des Nachfolgernehmens als auch die Anzahl, wie oft ein Nachfolger genommen werden soll, wird durch natürliche Zahlen beschrieben. Die -fache Durchführung eines Prozesses bedeutet, dass er so oft durchgeführt wird, wie es die Menge vorgibt.

    Additionnachfolger6.png


    Definition  

    Die Summe zweier natürlicher Zahlen und ist diejenige natürliche Zahl, die man erhält, wenn man von ausgehend -fach den Nachfolger nimmt.

    Die Operation heißt die Addition und die beteiligten Zahlen nennt man die Summanden. Nach dieser Definition wird also ausgehend von der Nachfolgerprozess -fach durchgeführt. Bei ist dies als der nullte Nachfolger, also als selbst, zu verstehen. Bei ist dies der erste Nachfolger, ist also die erste Zahl nach . Die Summe ist also mit Nachfolgerstrichen. Wenn umgekehrt

    ist, so ist der -te Nachfolger der gleich . Man beachte, dass hier die Addition in einer Weise definiert wird, in der die Kommutativität keineswegs offensichtlich ist, das wird sich aber gleich ergeben.

    Das kleine Einsundeins. Das Umlegungsprinzip schlägt sich in der Additionstabelle darin nieder, dass in den Linksunten nach Rechtsoben-Diagonalen konstante Werte stehen.



    Lemma  

    Für die Addition der natürlichen Zahlen (mit der in Definition festgelegten Addition) gelten die folgenden Aussagen.

    1. für alle , d.h. ist das neutrale Element der Addition.

    2. für alle (Umlegungsregel).

    3. Die Addition ist kommutativ.
    4. Die Addition ist assoziativ.
    5. Aus einer Gleichung folgt
      (Abziehregel).

    Beweis  

    1. Die Gleichungen links und rechts sind unmittelbar klar, da der -te Nachfolger der gleich ist.
    2. Die Ausdrücke besagen prozesstheoretisch das gleiche: Links geht man von der Zahl aus und nimmt einmal öfters als -mal den Nachfolger. In der Mitte bestimmt man -fach den Nachfolger von und nimmt von diesem Ergebnis den Nachfolger. Rechts nimmt man von den Nachfolger und davon dann -fach den Nachfolger.
    3. Es ist

      für alle zu zeigen. Diese Gleichungen zeigen wir durch Induktion über für alle . Bei steht beidseitig nach Teil (1). Sei die Gleichheit nun für ein (und alle ) schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und Teil (2)

      die Gleichung gilt also auch für .

    4. Wir beweisen die Assoziativität, also die Gleichheit

      durch Induktion über (für alle gleichzeitig). Mit der Regel aus (2) und der Induktionsvoraussetzung ergibt sich direkt

    5. Die Abziehregel beweisen wir ebenfalls durch Induktion über . Der Fall

      ist klar. Sei also die Aussage für ein schon bewiesen und sei eine Gleichung der Form

      gegeben. Dann ist nach der Umlegungsregel auch

      Nach der Induktionsvoraussetzung ist somit

      Da die Nachfolgerabbildung injektiv ist, ergibt sich


    Für einige alternative Begründungen siehe die Aufgaben. Teil (2) kann man auch so verstehen, dass man eine Summe dadurch berechnen kann, dass man sukzessive den ersten Summanden um eins erhöht (also den Nachfolger nimmt) und den zweiten um eins vermindert (also den Vorgänger nimmt), falls ist. Dies macht man so lange, bis der zweite Summand ist. Der dabei entstandene neue erste Summand ist die Summe. Statt Umlegungsregel sagt man auch Umlegungsprinzip oder man spricht von einer „gegensinnigen Veränderung“, was auch oft bei Rechnungen effektiv eingesetzt wird, wenn man etwa rechnet. Die folgende Aussage besagt, dass durch das Umlegungsprinzip die Addition bereits festgelegt ist.



    Satz  

    Auf den natürlichen Zahlen

    gibt es genau eine Verknüpfung

    mit

    Beweis  

    Die Addition erfüllt nach Fakt  (1, 2) diese Eigenschaften.

    Es seien zwei Verknüpfungen und auf gegeben, die beide diese charakteristischen Eigenschaften erfüllen. Es ist zu zeigen, dass dann diese beiden Verknüpfungen überhaupt übereinstimmen. Wir müssen also die Gleichheit

    für alle beweisen. Dies machen wir durch Induktion über (für beliebige ). Bei

    ist wegen

    die Aussage richtig. Sei die Aussage nun für ein bestimmtes schon bewiesen. Dann ist mit der charakteristischen Eigenschaft und der Induktionsvoraussetzung



    Lemma  

    Es seien natürliche Zahlen. Dann ist

    nur bei und möglich.

    Beweis  

    Wenn wäre, so wäre ein Nachfolger einer natürlichen Zahl (nämlich der -te Nachfolger von ), was für die ausgeschlossen ist. Also ist . Wegen

    ist auch der erste Summand gleich .




    Lemma  

    Für die Addition der natürlichen Zahlen (mit der in Definition festgelegten Addition) gelten die folgenden Aussagen.

    1. für alle , d.h. ist das neutrale Element der Addition.

    2. für alle (Umlegungsregel).

    3. Die Addition ist kommutativ.
    4. Die Addition ist assoziativ.
    5. Aus einer Gleichung folgt
      (Abziehregel).

    Beweis  

    1. Die Gleichungen links und rechts sind unmittelbar klar, da der -te Nachfolger der gleich ist.
    2. Die Ausdrücke besagen prozesstheoretisch das gleiche: Links geht man von der Zahl aus und nimmt einmal öfters als -mal den Nachfolger. In der Mitte bestimmt man -fach den Nachfolger von und nimmt von diesem Ergebnis den Nachfolger. Rechts nimmt man von den Nachfolger und davon dann -fach den Nachfolger.
    3. Es ist

      für alle zu zeigen. Diese Gleichungen zeigen wir durch Induktion über für alle . Bei steht beidseitig nach Teil (1). Sei die Gleichheit nun für ein (und alle ) schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und Teil (2)

      die Gleichung gilt also auch für .

    4. Wir beweisen die Assoziativität, also die Gleichheit

      durch Induktion über (für alle gleichzeitig). Mit der Regel aus (2) und der Induktionsvoraussetzung ergibt sich direkt

    5. Die Abziehregel beweisen wir ebenfalls durch Induktion über . Der Fall

      ist klar. Sei also die Aussage für ein schon bewiesen und sei eine Gleichung der Form

      gegeben. Dann ist nach der Umlegungsregel auch

      Nach der Induktionsvoraussetzung ist somit

      Da die Nachfolgerabbildung injektiv ist, ergibt sich




    Lemma  

    Für die Multiplikation der natürlichen Zahlen (mit der in der Definition festgelegten Multiplikation)

    gelten folgende Aussagen.

    1. Es gilt

      für alle .

    2. Es gilt

      für alle , d.h. ist das neutrale Element für die Multiplikation.

    3. Es ist

      und

      für alle .

    4. Die Multiplikation ist kommutativ.
    5. Für beliebige gilt

      (Distributivgesetz).

    6. Die Multiplikation ist assoziativ.

    Beweis  

    1. Die zweite Gleichung ist klar, da unabhängig davon, wie oft die mit sich selbst addiert wird, stets herauskommt. Die erste Gleichung kann man als eine Konvention oder auch als Teil der Definition ansehen: Eine Summe, in der überhaupt keine Zahl vorkommt (die leere Summe), ist als zu interpretieren.
    2. Die erste Gleichung ist klar, der Ausdruck besagt einfach, dass die Zahl einmal dasteht. Die zweite Gleichung bedeutet, dass die -fache Addition der mit sich selbst gleich ist. Dies zeigen wir durch Induktion nach , wobei der Induktionsanfang (für ) klar ist. Sei die Aussage also schon für bewiesen. Der Unterschied zwischen und besteht darin, dass im zweiten Fall einmal mehr dasteht. Somit ist
    3. Die linke Gleichung ergibt sich unmittelbar aus der Definition. Die rechte Gleichung ergibt sich aus
    4. Die Kommutativität beweisen wir durch Induktion nach , und zwar beweisen wir die Behauptung

      für alle . Der Fall ist klar, da dann beidseitig steht. Sei die Gesamtaussage also für ein bestimmtes und beliebiges bereits bewiesen. Dann ist unter Verwendung von (3) und der Induktionsvoraussetzung

    5. Das Distributivgesetz

      beweisen wir durch Induktion nach für beliebige . Der Fall ist klar, da beidseitig rauskommt. Unter Verwendung der Induktionsvoraussetzung und Teil (3) ergibt sich

    6. Das Assoziativitätsgesetz beweisen wir durch Induktion nach dem ersten Faktor (wobei der Induktionsanfang wieder klar ist) unter Verwendung des Distributivgesetzes und Teil (3).



    Lemma

    Für das Potenzieren gelten die folgenden Eigenschaften, wobei und seien.

    Beweis

    Siehe Aufgabe.