Die natürlichen Zahlen: Einführung

Eingangstest

Bevor man die Einheit durcharbeitet, empfiehlt es sich, den Ausgangspunkt zu bestimmen. Dieser Test ist eine Selbsteinschätzung: Er wird nicht benotet, und sein einziger Zweck ist es, das Lernen zu lenken. Seine zehn Fragen betreffen einzeln und der Reihe nach die zehn Lektionen der Einheit; die vierte verlangt außerdem, eine in Worten beschriebene Aufgabe als Summe anzusetzen. Dieselben Fertigkeiten werden am Ende, in der Lektion zur Synthese, erneut gemessen; da dies die erste Einheit des Kurses ist, gibt es keine Fragen zu früheren Einheiten. Eine Frage, die man nicht lösen kann, zeigt die Lektion an, bei der es sich lohnt, länger zu verweilen.

Die Inhalte der Einheit

Im Studienplan wurde darauf hingewiesen, dass der Kurs seine Gegenstände konstruiert, statt sie als bekannt vorauszusetzen. Diese erste Einheit ist das Fundament dieser Konstruktion: Sie geht von einigen wenigen Axiomen über die Zahlen aus, mit denen man zählt, und leitet aus ihnen die gesamte Arithmetik der natürlichen Zahlen her. Das Wenige, das sie darüber hinaus annimmt, wird an seiner Stelle ausdrücklich erklärt: die Regeln der naiven Mengenlehre und der Verneinung der Quantoren; die Existenz der rekursiv definierten Funktionen, die der Rekursionssatz von Dedekind garantiert; die Eindeutigkeit der Anzahl der Elemente einer endlichen Menge und die Endlichkeit ihrer Teilmengen, auf denen das Zählen beruht; die verallgemeinerte Kommutativität endlicher Produkte; und die elementaren Regeln der ganzen, der rationalen und der reellen Zahlen, die einige Beispiele und Aufgaben vorwegnehmen und die die nächste Einheit konstruiert. Ihre zehn Lektionen bilden eine Kette, in der jedes Glied auf den vorhergehenden aufbaut.

1. Mengen, Relationen und Funktionen. Sie legt die Sprache fest, in der der ganze Kurs geschrieben ist: die Mengen und ihre Operationen, die Relationen, insbesondere die Äquivalenz- und Ordnungsrelationen, und die Funktionen. Die Äquivalenzrelationen kehren in der nächsten Einheit wieder, wo die ganzen und die rationalen Zahlen als Klassen von Paaren konstruiert werden.
2. Die natürlichen Zahlen und die Peano-Axiome. Sie definiert die natürlichen Zahlen mithilfe der $1$, der Nachfolgeroperation und von fünf Axiomen, deren letztes das Induktionsprinzip ist. Alles Weitere in der Einheit ist eine Folgerung aus diesen Axiomen und dem Wenigen, das ausdrücklich angenommen wird.
3. Grundrechenarten mit natürlichen Zahlen und Ordnungsrelationen. Sie formuliert den Rekursionssatz, definiert mit ihm die Addition, die Multiplikation und die Potenz, beweist deren Eigenschaften durch Induktion und gründet die Ordnung auf die Addition. Sie zeigt, dass Subtraktion und Division zwischen natürlichen Zahlen nicht immer möglich sind, was die nächste Einheit ankündigt.
4. Summen, arithmetische und geometrische Folgen und Induktion. Sie führt das Summenzeichen, die Teleskopsummen und die arithmetischen und geometrischen Folgen ein und beweist, dass die gewöhnliche Induktion die starke Induktion und das Wohlordnungsprinzip impliziert, und in welchem Sinn diese zu ihr äquivalent sind. Das Wohlordnungsprinzip wird das Werkzeug fast aller Existenzbeweise der Einheit sein.
5. Teilbarkeit und Division mit Rest. Sie beweist mit der Wohlordnung, dass jede ganze Zahl einen eindeutigen Quotienten und einen eindeutigen Rest besitzt, teilt damit die ganzen Zahlen nach ihrem Rest ein und begründet die Teilbarkeitsregeln.
6. Primzahlen und der Fundamentalsatz der Arithmetik. Sie beweist, dass es unendlich viele Primzahlen gibt und dass jede natürliche Zahl größer als $1$ auf genau eine Weise in Primzahlen zerfällt, und leitet daraus unter anderem her, dass die Quadratwurzel einer natürlichen Zahl, die keine Quadratzahl ist, irrational ist.
7. Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches. Sie stellt den euklidischen Algorithmus vor, der den größten gemeinsamen Teiler ohne Zerlegung in Primfaktoren berechnet, leitet aus ihm das Lemma von Bézout her und löst die linearen diophantischen Gleichungen vollständig.
8. Kongruenzen und modulare Arithmetik. Sie macht aus der Division mit Rest einen Kalkül: Zwei ganze Zahlen sind kongruent modulo $n$, wenn sie denselben Rest lassen, und die Kongruenz verträgt sich mit Addition und Multiplikation, sodass sich viele Teilbarkeitsprobleme lösen lassen, indem man nur mit den Resten rechnet.
9. Stellenwertsysteme. Sie beweist, dass sich jede natürliche Zahl in jeder Basis auf genau eine Weise schreiben lässt, und erklärt, warum die schulischen Rechenverfahren korrekt sind und warum Computer zur Basis $2$ arbeiten.
10. Elementare Kombinatorik und der binomische Lehrsatz. Sie definiert die Anzahl der Elemente einer endlichen Menge, beweist die Summen- und die Produktregel, lehrt mit ihnen, zu zählen, ohne aufzuzählen, definiert die Binomialkoeffizienten und beweist den binomischen Lehrsatz, der die Induktion, die Summen und das Zählen zusammenführt.

Die Einheit schließt mit der Lektion Synthese und Herausforderungen, die das Erreichte zusammenfasst, in ihrem Abschlusstest die Fertigkeiten des Eingangstests wiederholt und schwierigere Aufgaben stellt, die mehrere Lektionen verbinden.

Der historische Hintergrund

Das Zählen ist älter als das Schreiben. Knochen mit Reihen von Kerben, wie der von Ishango, der im Kongo gefunden wurde und dessen Alter auf etwa zwanzigtausend Jahre geschätzt wird, werden oft als Aufzeichnungen von Mengen gedeutet. Die ersten städtischen Kulturen mussten Herden zählen, Felder vermessen und Ernten verteilen und entwickelten dabei Zahlensysteme: Vor etwa viertausend Jahren verwendeten die Schreiber Mesopotamiens bereits ein Stellenwertsystem zur Basis $60$, dessen Spur in der Messung der Zeit und der Winkel fortlebt.

In Griechenland untersuchten ab dem 6. Jahrhundert vor unserer Zeitrechnung die Pythagoreer die Zahlen um ihrer selbst willen und nicht nur als Rechenwerkzeuge. Sie ordneten die figurierten Zahlen ein, etwa die Dreieckszahlen $1$, $3$, $6$, $10$, die die Summen $1 + 2 + \cdots + n$ sind, und unterschieden die geraden von den ungeraden Zahlen. Um das Jahr 300 vor unserer Zeitrechnung fasste Euklid in den Büchern VII bis IX der Elemente die Arithmetik seiner Zeit zusammen, deduktiv geordnet: den Algorithmus, der seinen Namen trägt, das Lemma, nach dem eine Primzahl, die ein Produkt teilt, einen seiner Faktoren teilt, den Beweis, dass es unendlich viele Primzahlen gibt, und die Konstruktion der geraden vollkommenen Zahlen. Im 3. Jahrhundert vor unserer Zeitrechnung ersann Eratosthenes von Kyrene sein Sieb der Primzahlen, und wahrscheinlich im 3. Jahrhundert unserer Zeitrechnung untersuchte Diophant von Alexandria in seiner Arithmetika Gleichungen, deren Lösungen ganze oder rationale Zahlen sein mussten.

Das Dezimalsystem mit der Null als Ziffer entstand in Indien, wurde im 9. Jahrhundert von al-Chwarizmi dargestellt und gelangte, unter anderem, durch den Liber Abaci des Fibonacci im Jahr 1202 nach Europa. Das Dreieck der Binomialkoeffizienten war in Indien, in Persien und in China Jahrhunderte bekannt, bevor Pascal ihm Mitte des 17. Jahrhunderts die Abhandlung widmete, die ihm im Abendland seinen Namen gab. Nun ist aber das Schließen durch Induktion als ausdrückliche Beweismethode spät entstanden: Francesco Maurolico verwendete es in einem 1575 veröffentlichten Werk, um zu zeigen, dass die Summe der ersten ungeraden Zahlen eine Quadratzahl ist, und Pascal formulierte es klar in seiner Abhandlung über das arithmetische Dreieck. Im selben Jahrhundert ersann Fermat die Methode des unendlichen Abstiegs, eine Form des Wohlordnungsprinzips, und um 1665 dehnte Newton den binomischen Lehrsatz auf gebrochene und negative Exponenten aus. 1801 veröffentlichte Gauß seine Disquisitiones Arithmeticae, mit denen die Arithmetik zu einer systematischen Theorie wurde, und in ihnen findet sich der erste ausdrückliche Beweis der Eindeutigkeit der Primfaktorzerlegung.

Im 19. Jahrhundert wurde die Analysis auf arithmetischer Grundlage neu aufgebaut: Die reellen Zahlen wurden aus den rationalen definiert, wie es Dedekind 1872 mit seinen Schnitten tat, die rationalen aus den ganzen und die ganzen aus den natürlichen Zahlen. Wenn dem so ist, ruhte das ganze Gebäude auf den natürlichen Zahlen, und es blieb zu beantworten, was diese sind und aus welchen Prinzipien sich ihre Arithmetik herleitet. 1861 hatte Hermann Graßmann gezeigt, dass sich Addition und Multiplikation ausgehend vom Nachfolger rekursiv definieren lassen und dass sich ihre Eigenschaften durch Induktion beweisen lassen. 1888 veröffentlichte Richard Dedekind seine Schrift Was sind und was sollen die Zahlen?, die die natürlichen Zahlen durch den Nachfolger und die Induktion kennzeichnet, und 1889 veröffentlichte Giuseppe Peano auf Lateinisch seine Arithmetices principia, nova methodo exposita mit der Liste von Axiomen, die dieser Kurs übernimmt und die, wie dort, bei der $1$ beginnt.

Das Problem, aus dem die Theorie entstand

Es gibt unendlich viele natürliche Zahlen, und fast alles, was man über sie aussagen möchte, ist eine Aussage über alle zugleich: dass die Addition kommutativ ist, dass jede natürliche Zahl größer als $1$ in Primzahlen zerfällt, dass die Summe der ersten $n$ ungeraden Zahlen gleich $n^2$ ist. Keine Aussage dieser Art lässt sich überprüfen, indem man die Fälle einzeln durchgeht, denn man würde nie fertig; und, was schwerer wiegt, die Überprüfung vieler Fälle, so zahlreich sie auch sein mögen, erlaubt keinen Schluss auf die übrigen. Das Problem lautet also: Mit welchen Prinzipien lässt sich für eine gegebene Eigenschaft $P$ der natürlichen Zahlen beweisen, dass jede natürliche Zahl sie besitzt?

Das folgende Beispiel zeigt, wie sehr Überprüfungen täuschen können.

Die Antwort von Dedekind und Peano besteht darin, das Prinzip, das den Übergang vom Endlichen zum Unendlichen erlaubt, als Axiom festzusetzen: Gilt eine Eigenschaft für $1$ und überträgt sie sich von jeder natürlichen Zahl auf ihren Nachfolger, so gilt sie für alle. Daraus ergibt sich ein genaues Programm, das dieser Einheit: die Operationen so zu definieren, dass sich jeder Fall auf den vorhergehenden zurückführen lässt, und jede ihrer Eigenschaften durch Induktion oder durch eines der äquivalenten Prinzipien zu beweisen. Nun hat das Problem aber eine zweite Seite, die sich durch die ganze Einheit zieht: die der Umkehroperationen. Subtraktion und Division sind zwischen natürlichen Zahlen nicht immer möglich, und die Frage, wann sie es sind, führt zur Teilbarkeit, zu den Primzahlen und zum größten gemeinsamen Teiler; die Frage, wie dem abzuhelfen ist, führt zur nächsten Einheit, die die natürlichen Zahlen bis zu den komplexen Zahlen erweitert.

Die Bedeutung der natürlichen Zahlen

Innerhalb dieses Kurses tauchen die Resultate der Einheit immer wieder auf. Die Lektion über die ganzen Zahlen konstruiert diese als Paare natürlicher Zahlen, und die über die rationalen Zahlen diese als Paare ganzer Zahlen; die Polynomdivision in der Lektion über die Nullstellen höhergradiger Polynome ahmt die Division mit Rest nach, und das Horner-Schema geht auf die Stellenwertschreibweise zurück. Die Abschätzung aus dem binomischen Lehrsatz für $\left(1 + \frac{1}{n}\right)^n$ bereitet die Lektion über die Zahl $e$ vor. Die Fortsetzung dieses Kurses, Algebra und Geometrie II, verwendet sie weiter: In ihrer Einheit über die komplexen Zahlen in Polarform wird die Formel von de Moivre durch Induktion bewiesen, und in ihrer Einheit über Matrizen und algebraische Strukturen macht die Lektion über algebraische Strukturen die Reste bei der Division durch $n$ zu einem Ring, der genau dann ein Körper ist, wenn $n$ eine Primzahl ist.

Außerhalb dieses Kurses werden die Folgen und Summen in Analysis I mit dem Summenzeichen und mit der Induktion untersucht, und die Ableitung einer Potenz ergibt sich mit dem binomischen Lehrsatz. In Grundlagen der Mechanik wird das Gesetz, das Galilei 1638 veröffentlichte und nach dem ein aus der Ruhe fallender Körper in gleichen Zeitintervallen Strecken zurücklegt, die sich wie die aufeinanderfolgenden ungeraden Zahlen $1, 3, 5, 7, \ldots$ verhalten, durch die Summe der ersten ungeraden Zahlen zur Proportionalität zwischen der zurückgelegten Strecke und dem Quadrat der Zeit. Die einfache Verzinsung und die Zinseszinsen in Finanzmathematik sind arithmetische und geometrische Folgen; die Programme in Programmieren in C++ I stellen die Zahlen zur Basis $2$ dar, berechnen Reste und wenden den euklidischen Algorithmus an, und ihre Rekursion ist dieselbe Idee wie die rekursiven Definitionen der Addition und der Multiplikation. Der Kurs Mathematische Logik I: Aussagenlogik untersucht die Schlussregeln, die die Beweise der Einheit verwenden.

In Wissenschaft und Technik ist die Basis $2$ die Sprache jedes Computers, und die Arithmetik der Reste trägt die Prüfziffern, mit denen man Fehler beim Abschreiben der Nummern von Dokumenten, Konten oder Büchern erkennt. Das 1977 von Rivest, Shamir und Adleman veröffentlichte Verschlüsselungsverfahren, auf dem ein großer Teil der Sicherheit der Kommunikation beruht, gründet sich auf einen Gegensatz, den diese Einheit verständlich macht: Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler von Zahlen mit Hunderten von Ziffern schnell, während man kein schnelles Verfahren kennt, um sie in Primfaktoren zu zerlegen. Die Kombinatorik schließlich ist die Grundlage der Wahrscheinlichkeitsrechnung und mit ihr der Statistik und eines großen Teils der Physik und der Biologie.