Zum Inhalt springen
Topos Uranos
Deutsch

Grundrechenarten mit natürlichen Zahlen und Ordnungsrelationen

Zusammenfassung

Diese Lektion definiert die Addition, die Multiplikation und die Potenz natürlicher Zahlen ausgehend vom Nachfolger der Peano-Axiome, mit dem Rekursionssatz, der garantiert, dass rekursive Definitionen eine eindeutige Operation bestimmen; sie setzt seinen Existenzteil voraus, beweist seinen Eindeutigkeitsteil durch Induktion und leitet die Eigenschaften der Operationen her: Kommutativität, Assoziativität, Distributivität und Kürzungsregel. Danach definiert sie die Ordnungsrelation mithilfe der Addition, mit ihren Eigenschaften Trichotomie, Transitivität und Monotonie, sowie die Umkehroperationen, die Subtraktion und die Division, zusammen mit den Bedingungen, unter denen sie existieren. Das Induktionsprinzip ist das Werkzeug aller Beweise.

Lernziele

  1. Den Rekursionssatz formulieren und mit ihm die rekursiven Definitionen der Addition, der Multiplikation und der Potenz natürlicher Zahlen aufschreiben.
  2. Eigenschaften der Operationen ausgehend von ihren Definitionen durch Induktion beweisen.
  3. Die Ordnung der natürlichen Zahlen mithilfe der Addition definieren und ihre Eigenschaften Trichotomie, Transitivität und Monotonie anwenden.
  4. Erkennen, wann die Subtraktion und die Division zweier natürlicher Zahlen existieren, und mit ihnen rechnen, ohne die natürlichen Zahlen zu verlassen.

Die Addition

Die Rechenoperationen mit natürlichen Zahlen kennt man aus der Schule; hier geht es darum, sie mit mathematischer Genauigkeit zu begründen. In der Lektion über die Peano-Axiome wurden die natürlichen Zahlen ausgehend von der 11 und von der Nachfolgeroperation definiert, die jeder natürlichen Zahl nn die nächste zuordnet, S(n)S(n). Die Addition wird ausgehend vom Nachfolger durch zwei Regeln definiert: 11 addieren heißt, den Nachfolger nehmen, und den Nachfolger von mm addieren heißt, den Nachfolger der Summe mit mm nehmen.

n+1=S(n),n+S(m)=S(n+m)n + 1 = S(n), \qquad n + S(m) = S(n + m)

Eine Definition dieser Art heißt rekursiv: Die erste Regel legt den Wert für 11 fest, und die zweite führt jeden Fall auf den vorhergehenden zurück. Dass zwei solche Regeln tatsächlich eine Operation definieren, enthält nun zwei verschiedene Aussagen: dass es eine Funktion gibt, die sie für alle natürlichen Zahlen erfüllt (Existenz), und dass es keine zwei verschiedenen Funktionen gibt, die sie erfüllen (Eindeutigkeit). Beide zusammen bilden den Rekursionssatz, der auf Dedekind zurückgeht: Dieser Kurs setzt den Existenzteil voraus, wie nach dem Kasten erläutert wird, und beweist den Eindeutigkeitsteil. Er wird in einer allgemeinen Form formuliert, damit er auch für die Multiplikation, für die Potenz und für die rekursiven Definitionen der folgenden Lektionen dient.

Vorausgesetzte Tatsache (Rekursionssatz). Seien XX eine Menge und cc ein Element von XX, und sei für jede natürliche Zahl nn eine Regel gng_n gegeben, die jedem Element von XX ein Element von XX zuordnet. Dann gibt es eine Funktion ff von N\mathbb{N} nach XX mit f(1)=cf(1) = c und f(S(n))=gn(f(n))f(S(n)) = g_n(f(n)) für jede natürliche Zahl nn, und diese Funktion ist eindeutig.

Die Existenz wird in diesem Kurs ohne Beweis vorausgesetzt. Ihr Beweis erfordert, die Funktion ff als Menge von Paaren zu konstruieren: als die kleinste Menge von Paaren, die (1,c)(1, c) enthält und die mit jedem Paar (n,x)(n, x) auch (S(n),gn(x))(S(n), g_n(x)) enthält; und danach durch Induktion nachzuweisen, dass jeder natürlichen Zahl darin genau ein zweites Element entspricht. Diese Konstruktion gehört zur Mengenlehre und trägt nichts zur folgenden Arithmetik bei. Die Eindeutigkeit dagegen ist eine unmittelbare Folge des fünften Peano-Axioms.

LemmaEindeutigkeit der durch Rekursion definierten Funktion

Erfüllen zwei Funktionen ff und hh von N\mathbb{N} nach XX die beiden Bedingungen des Rekursionssatzes, so sind sie gleich. Die Abbildung stellt die Werte beider auf den ersten natürlichen Zahlen dar.

Beweis

  1. A={n∈N:f(n)=h(n)}\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}

    Sei AA die Menge der natürlichen Zahlen, an denen die beiden Funktionen übereinstimmen. Es genügt zu beweisen, dass AA die Menge aller natürlichen Zahlen ist.

  2. f(1)=c=h(1)f(1) = \resaltar{c} = h(1)

    Die 11 gehört zu AA, weil beide Funktionen den Wert cc an der Stelle 11 haben.

  3. f(S(k))=gk(f(k))=gk(h(k))=h(S(k))f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))

    Gehört kk zu AA, so auch S(k)S(k): Beide Funktionen wenden dieselbe Regel gkg_k auf denselben Wert an.

  4. A=N,(∀n∈N) (f(n)=h(n))A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))

    Nach dem fünften Peano-Axiom ist AA die Menge aller natürlichen Zahlen: Die beiden Funktionen sind gleich.

Die Addition erhält man aus dem Satz, indem man den ersten Summanden nn festhält und X=NX = \mathbb{N}, c=S(n)c = S(n) und für jedes mm die Regel gmg_m wählt, die jeder natürlichen Zahl ihren Nachfolger zuordnet: Die Funktion ff, die der Satz liefert, ist diejenige, die jedem mm die Zahl n+mn + m zuordnet, und die beiden Regeln der Addition sind die beiden Bedingungen des Satzes. Ebenso erhält man mit c=nc = n und der Regel, die nn addiert, die Multiplikation, und mit c=bc = b und der Regel, die mit bb multipliziert, die Potenz. mm addieren heißt also letztlich, mm-mal den Nachfolger anwenden.

BeispielZwei plus zwei ist vier

Die bekannteste Aussage der Arithmetik ist ein Satz, der sich mit den beiden Regeln der Addition und den Namen 2=S(1)2 = S(1), 3=S(2)3 = S(2) und 4=S(3)4 = S(3) beweisen lässt.

Beweis

  1. 2+2=2+S(1)2 + 2 = 2 + S(1)

    Wir schreiben den zweiten Summanden als Nachfolger von 11.

  2. 2+S(1)=S(2+1)2 + S(1) = S(2 + 1)

    Nach der zweiten Regel heißt einen Nachfolger addieren, den Nachfolger der Summe nehmen.

  3. S(2+1)=S(S(2))S(2 + 1) = S(S(2))

    Nach der ersten Regel heißt 11 addieren, den Nachfolger nehmen.

  4. S(S(2))=S(3)=4S(S(2)) = S(3) = 4

    Da S(2)=3S(2) = 3 und S(3)=4S(3) = 4, ergibt sich das Resultat.

Aus den Regeln der Addition werden durch Induktion ihre Eigenschaften hergeleitet. Für alle natürlichen Zahlen aa, bb und cc gilt:

  1. Kommutativität: a+b=b+aa + b = b + a.
  2. Assoziativität: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c). Deshalb kann man a+b+ca + b + c ohne Klammern schreiben.
  3. Kürzungsregel: Aus a+c=b+ca + c = b + c folgt a=ba = b.

Die Kommutativität wurde in der gelösten Aufgabe 5 der Lektion über die Peano-Axiome bewiesen, und die Assoziativität ist dort eine der Übungsaufgaben. Die Kürzungsregel wird in der gelösten Aufgabe 1 dieser Lektion bewiesen.