Kurs:Grundkurs Mathematik (Osnabrück 2022-2023)/Teil I/Vorlesung C/Referenzsuche

Wir haben schon für die intuitiv bekannten natürlichen Zahlen ein Axiomensystem eingeführt, das speziell auf die natürlichen Zahlen zugeschnitten war und das sogar die Eigenschaft besitzt, dass es die natürlichen Zahlen in dem Sinne charakterisiert, das je zwei Strukturen (je zwei Modelle), die dieses Axiomensystem erfüllen, zueinander in eine eindeutige Beziehung gebracht werden können, also im Wesentlichen gleich sind (siehe Satz 7.2).

In dieser Vorlesung werden wir eine andere Art von kennenlernen, wie sie in der Mathematik typisch ist. Man fasst verschiedene strukturelle Eigenschaften, die in einem bestimmten Kontext immer wieder auftauchen, in einen neuen Begriff zusammen. Das Ziel ist dabei, weitere Eigenschaften aus einigen wenigen Grundeigenschaften logisch zu erschließen. Man argumentiert dann nicht auf der Ebene vertrauter Beispiele, wie der natürlichen Zahlen, sondern auf der Ebene der Eigenschaften. Der Gewinn ist dabei, dass man mathematische Schlüsse nur einmal auf der abstrakten Ebene der Eigenschaften durchführen muss und diese dann für alle Modelle gelten, die die jeweiligen Grundeigenschaften erfüllen, also unter den Begriff fallen. Zugleich erkennt man logische Abhängigkeiten und Hierarchien zwischen Eigenschaften, die häufig auch im Lernprozess versteckt vorliegen und auch eine gewisse Orientierung für die Didaktik geben, selbst wenn nicht axiomatisch argumentiert wird.

In diesem Sinne werden wir im Laufe der Vorlesung die Begriffe Halbringe, Ringe, Gruppen und Körper kennenlernen (auch der Ordnungsbegriff ist ein axiomatischer Begriff).

Wir fassen die bisher etablierten algebraischen Eigenschaften der natürlichen Zahlen in einem eigenen Begriff zusammen.

Definition

Ein kommutativer Halbring ist eine Menge mit Verknüpfungen

(genannt und) und mit zwei ausgezeichneten Elementen

derart, dass folgende Bedingungen erfüllt sind:

1. Die Addition ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
2. Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
3. Es gilt das also für alle

Korollar

Die natürlichen Zahlen

bilden einen kommutativen Halbring.

Beweis

Dies folgt unmittelbar aus Lemma 8.11 und aus Lemma 9.2.

$\Box$

Neben den natürlichen Zahlen gibt es viele weitere Halbringe, beispielsweise die ganzen Zahlen die rationalen Zahlen oder die reellen Zahlen Wenn man eine Eigenschaft aus den Gesetzen eines Halbringes erschließen kann, so gilt diese Eigenschaft in jedem Halbring. Sobald man also für eine Struktur gezeigt hat, dass ein Halbring vorliegt, so hat man damit auch automatisch gezeigt, dass diese neue Eigenschaft gilt. Dies ist letztlich ein sehr ökonomisches Vorgehen! Der Preis ist, dass man zusätzliche Begriffe einführen muss und dass man sehr abstrakt argumentieren muss.

Wir lassen das Produktzeichen häufig weg, wenn das nicht zu Missverständnissen führen kann und wir benutzen allgemein die dass Punktrechnung stärker bindet als Strichrechnung, d.h. wir schreiben einfach statt An weiteren Notationen verwenden wir für ein Halbringelement

und eine positive natürliche Zahl

die Schreibweisen (tes von und te von)

Hier muss man also richtig die Anzahl der Summanden bzw. die Anzahl der Faktoren zählen. Statt

schreiben wir einfach (bzw. manchmal), d.h. jede natürliche Zahl findet sich in jedem Halbring wieder. Die Schreibweise könnte man dann auch als das Produkt

(mit Einsen) lesen, was aber aufgrund des Distributivgesetzes mit der fachen Summe von mit sich selbst übereinstimmt. Für

ist dies jedenfalls als im Halbring zu lesen, was nicht ohne weiteres gleich sein muss (aber in allen für uns wichtigen Beispielen gleich ist). Weiter setzen wir

Mit dieser Bezeichnung gilt beispielsweise

und

für natürliche Zahlen

(man mache sich klar, was hier jeweils die Multiplikation bezeichnet).

Wie bei den natürlichen Zahlen verwenden wir das Summenzeichen und das Produktzeichen Für indizierte Elemente aus ist also

und

Auch bei einer beliebigen endlichen Indexmenge und Elementen , verwendet man die Schreibweise für die Summe der gegebenen Elemente, die ja wegen der Kommutativität und der Assoziativität nicht von einer Reihenfolge abhängt.

Die beiden folgenden extremen Beispiele zeigen, wie verschieden ein Halbring von dem Halbring der natürlichen Zahlen sein kann. Dennoch gelten alle aus den Halbringaxiomen ableitbaren Eigenschaften auch in diesen beiden Beispielen.

Beispiel

Die einelementige Menge

kann man zu einem kommutativen Halbring machen, indem man sowohl die Addition als auch die Multiplikation auf die einzig mögliche Weise erklärt, nämlich durch

In diesem Fall ist

dies ist also ausdrücklich erlaubt. Die Rechengesetze in einem Halbring sind hier trivialerweise erfüllt, da bei jeder zu erfüllenden Gleichung links und rechts sowieso immer herauskommt. Diesen Halbring nennt man den

Nach dem Nullring ist der folgende Ring der zweitkleinste Halbring.

Beispiel

Wir suchen nach einer Halbringstruktur auf der Menge Wenn das neutrale Element einer Addition und das neutrale Element der Multiplikation sein soll, so ist dadurch schon viel festgelegt. Nach Lemma 11.5 muss

gelten. Ferner legen wir

fest. Die Verknüpfungstabellen (oder Operationstafeln) sehen somit wie folgt aus.

und

Durch etwas aufwändiges Nachrechnen stellt man fest, dass es sich in der Tat um einen kommutativen Halbring handelt.

Eine Interpretation dieses Halbringes gewinnt man, wenn man sich die geraden natürlichen Zahlen durch und die ungeraden natürlichen Zahlen durch repräsentiert denkt. Beispielsweise ist die Summe zweier ungerader Zahlen stets gerade, was der obigen Gleichung

entspricht. Wie oben erwähnt lassen sich in jedem kommutativen Halbring die natürlichen Zahlen eindeutig interpretieren, dabei können aber, wie in den beiden Beispielen, verschiedene Zahlen gleich werden. Im Beispiel wird jede gerade Zahl zu und jede ungerade Zahl zu

Lemma

In einem kommutativen Halbring gilt

Beweis

Dies ergibt sich aus

$\Box$

Das folgende Beispiel zeigt, dass in einem kommutativen Halbring im Allgemeinen nicht die Gleichung

für alle gilt. Für die natürlichen Zahlen und in jedem kommutativen Ring gilt diese Eigenschaft, siehe Lemma 9.2  (1) und Lemma 19.4  (1). Es ist also keineswegs so, dass man jede Eigenschaft, die im derzeit hauptsächlich interessierenden Zahlenbereich (also derzeit die natürlichen Zahlen) gilt aus dem Begriff eines kommutativen Halbringes ableiten kann.

Beispiel

Wir suchen nach einer Halbringstruktur auf der dreielementigen Menge Wenn das neutrale Element einer Addition und das neutrale Element der Multiplikation sein soll, so ist dadurch schon viel festgelegt. Wir legen die Verknüpfungen durch die Verknüpfungstabellen

und

fest. Durch etwas aufwändiges Nachrechnen stellt man fest, dass es sich in der Tat um einen kommutativen Halbring handelt.

Die folgende Aussage heißt das

Satz

Es sei ein kommutativer Halbring und es seien Elemente aus

Dann gilt das

Beweis

Wir machen eine Doppelinduktion nach und nach D.h. wir beweisen die Aussage für jedes feste durch Induktion nach (innere Induktion) und erhöhen dann in einem eigenen Induktionsdurchgang (äußere Induktion). Bei

ist nichts zu zeigen, da dann die Summen links und rechts leer sind, also gleich Es sei also

sodass der linke Faktor einfach eine fixierte Zahl

ist. Wir wollen die Aussage in dieser Situation für beliebiges zeigen. Bei

ist die Aussage klar. Es sei die Aussage nun für ein

schon bewiesen. Dann ist

nach dem Distributivgesetz und der Induktionsvoraussetzung.

Es sei die Aussage nun für ein festes und jedes bewiesen. Dann ist wieder mit dem Distributivgesetz und der Induktionsvoraussetzung

$\Box$

Wie für die natürlichen Zahlen (siehe Lemma 9.8) gelten in jedem kommutativen Halbring die folgenden Man beachte, dass bei der Potenz die Basis aus dem kommutativen Halbring und der Exponent eine natürliche Zahl ist. Die Schreibweise mit aus dem Halbring hat im Allgemeinen keine Bedeutung.

Lemma

Es sei ein kommutativer Halbring,

und

Dann gelten die folgenden

Beweis

Siehe Aufgabe 11.13.

$\Box$

Die Gültigkeit der ersten binomischen Formel ist keine Besonderheit der natürlichen Zahlen, sondern folgt allein aus den im Begriff eines Halbringes zusammengefassten Eigenschaften.

Korollar

In einem kommutativen Halbring

gilt die erste binomische Formel, also die Beziehung

Beweis

Unter mehrfacher Verwendung des Distributivgesetzes und der Kommutativgesetze ist

$\Box$

Die zweite und die dritte binomische Formel lässt sich nicht in einem beliebigen Halbring formulieren, da in ihnen das Minuszeichen bzw. die Subtraktion vorkommt, die es in einem beliebigen kommutativen Halbring nicht gibt und die innerhalb der natürlichen Zahlen auch nur eingeschränkt ausführbar ist. Stattdessen werden wir uns den höheren Potenzen von Summen zuwenden. Die besagt wie eben formuliert

Für die dritte Potenz einer Summe gilt

und für die vierte Potenz

Worauf beruht dieser Zusammenhang und wo kommen diese Vorfaktoren her? Betrachten wir die dritte Potenz. Es ist (wieder in einem beliebigen kommutativen Halbring)

Für die vierte Potenz siehe Aufgabe 11.32. In dieser Weise kann man jede Potenz einer Summe als Summe von Produkten ausdrücken, wobei die auftretenden Koeffizienten heißen. Um diese einzuführen, müssen wir uns mit elementarer Kombinatorik beschäftigen, was wir in der übernächsten Vorlesung tun werden.

Wir schließen mit einem Objekt ab, das ein eher ungewöhnliches Beispiel für einen kommutativen Halbring und auch ein Beispiel für eine geordnete, aber nicht total geordnete Menge ist, die Potenzmenge. Sie ist auch wichtig im Rahmen der elementaren Kombinatorik.

Definition

Zu einer Menge nennt man die Menge aller Teilmengen von die Potenzmenge von Sie wird mit

bezeichnet.

Wenn die Menge der Leute im Kurs sind, so kann man als die Menge aller Parties auffassen, die diese Leute feiern können, wenn man eine Party mit der Menge der anwesenden Leute identifiziert.

Beispiel

Es sei eine beliebige Menge und

die Potenzmenge davon. Dann sind die Elemente aus

- also die Teilmengen von - durch die Inklusionsbeziehung geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus

und

die Inklusion

folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen sind genau dann gleich, wenn

gilt.

Lemma

Zu einer Menge sei

die Potenzmenge zu

Dann ist mit der Vereinigung

als Addition und der 

leeren Menge als und mit dem Durchschnitt

als Multiplikation und der Gesamtmenge  als  ein

kommutativer Halbring.

Beweis

Die Eigenschaften sind allenfalls bis auf das Distributivgesetz klar. Letzteres besagt die Identität

Wenn ein Element links dazugehört, so gehört es zu und es gehört zu Somit gehört es zu oder zu und damit auch zu oder zu also jedenfalls zur rechten Seite. Wenn es rechts dazu gehört, sagen wir zu was wir wegen der Symmetrie der Situation annehmen können, so gehört es erst recht zu

$\Box$

Im vorstehenden Beispiel kann man die Rollen der Addition und der Multiplikation sogar vertauschen, da das Distributivgesetz auch in der Form

gilt.

Wir besprechen nun die Eigenschaft, dass eine natürliche Zahl eine weitere natürliche Zahl teilt.

Definition

Man sagt, dass die natürliche Zahl

die natürliche Zahl  teilt

(oder dass von geteilt wird, oder dass ein Vielfaches von ist), wenn es eine natürliche Zahl derart gibt, dass

ist. Man schreibt dafür auch

Beispielsweise sind Teiler von und die Teiler von Eine Zerlegung

nennt man auch eine von Wenn ein Teiler von ist und

so ist die Zahl mit

nach der Kürzungsregel eindeutig bestimmt. Man nennt diese Zahl den oder und schreibt dafür Da wir im Moment die rationalen Zahlen noch nicht zur Verfügung haben, ist dies nur dann eine erlaubte Schreibweise, wenn die Teilerbeziehung vorliegt und

ist (so wie die Schreibweise $a-b$ bisher nur erlaubt ist, wenn

ist). Es ist also ein Teiler der der Ausdruck ist aber nicht definiert. Wenn

ein Teiler von ist, so nennt man die Bestimmung des eindeutig bestimmten mit

Teilen. Man sagt, dass man durch teilt mit dem Ergebnis

Lemma

Es sei

eine natürliche Zahl und ein Teiler von

Dann ist

Insbesondere besitzt nur endlich viele Teiler.

Beweis

Da der Teiler ausgeschlossen ist, sind bei einer Faktorzerlegung

beide Faktoren Wegen Satz 10.8  (3) ist daher

Der Zusatz ist klar, da es unterhalb von überhaupt nur endlich viele natürliche Zahlen gibt.

$\Box$

Wenn man also alle Teiler einer natürlichen Zahl finden möchte, so muss man einfach die Zahlen

der Reihe nach durchgehen und ihre Vielfachen

durchgehen, bis die Zahl auftaucht (in welchem Fall ein Teiler ist) oder eine Zahl auftaucht (dann liegt kein Teiler vor). Übrigens muss man nicht die Zahlen bis durchprobieren, sondern lediglich bis zur ersten Zahl mit

(man muss also nur bis zur Größenordnung der Quadratwurzel aus gehen). Dann muss man aber für jeden Teiler

auch den Gegenteiler mitanführen, siehe Aufgabe 12.13. Für muss man maximal bis gehen. Es ergeben sich die Zerlegungen

und die Teiler sind somit

Eine durch teilbare Zahl, also ein Vielfaches von heißt eine nicht durch teilbare Zahl heißt Für einige Zahlen gibt es einfache Tests, ob sie ein Teiler einer gewissen Zahl sind, die allerdings auf dem Dezimalsystem beruhen. Eine weitere wichtige Möglichkeit ist die Division mit Rest. Auch der dritte Teil des folgenden Lemmas hilft: Wenn kein Teiler von ist, so sind sämtliche Vielfache von ebenfalls kein Teiler von

Lemma

In gelten folgende Teilbarkeitsbeziehungen.

1. Für jede natürliche Zahl gilt
2. Für jede natürliche Zahl gilt
3. Gilt so gilt auch
4. Gilt so gilt auch
5. Gilt so gilt auch für jede natürliche Zahl
6. Gilt so gilt auch für beliebige natürliche Zahlen

Beweis

1. Ist klar wegen
2. Ist klar wegen
3. Die beiden Voraussetzungen bedeuten die Existenz von mit und Somit ist und ist auch ein Teiler von
4. Aus den Voraussetzungen und ergibt sich direkt also ist ein Teiler von
5. Aus der Voraussetzung ergibt sich direkt also ist ein Teiler von
6. Aus den Voraussetzungen und ergibt sich direkt mit dem Distributivgesetz also ist ein Teiler von

$\Box$

Beispiel

Wir betrachten die positiven natürlichen Zahlen zusammen mit der Teilbarkeitsbeziehung. Dies ergibt eine Ordnung auf Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ist, wie

zeigt. Die Transitivität wurde in Lemma 12.3  (3) gezeigt. Die Antisymmetrie folgt so: Aus

folgt

Da wir uns auf positive natürliche Zahlen beschränken, folgt mit der Kürzungsregel

und daraus wegen

auch

Also ist

Einfache Beispiele wie $2$ und $3$ zeigen, dass hier keine totale Ordnung vorliegt, da weder von noch umgekehrt geteilt wird.

Definition

Es seien natürliche Zahlen. Dann heißt eine natürliche Zahl gemeinsamer Teiler der wenn jedes teilt für

Eine natürliche Zahl heißt größter gemeinsamer Teiler der wenn ein gemeinsamer Teiler ist und wenn unter allen gemeinsamen Teilern der der (bezüglich der Ordnungsrelation auf den natürlichen Zahlen) Größte ist.

Beispielsweise haben die Zahlen die gemeinsamen Teiler und ist der größte gemeinsame Teiler.

Definition

Zwei natürliche Zahlen heißen teilerfremd wenn sie keinen gemeinsamen Teiler

besitzen.  

Beispielsweise sind

teilerfremd,

sind nicht teilerfremd, da ein gemeinsamer Teiler ist. Die ist zu jeder natürlichen Zahl (auch zu und) teilerfremd.

Definition

Zu einer Menge von natürlichen Zahlen

heißt eine natürliche Zahl ein gemeinsames Vielfaches wenn ein Vielfaches von jedem ist, also von jedem geteilt wird.

Die Zahl heißt das kleinste gemeinsame Vielfache der wenn ein gemeinsames Vielfaches ist und unter allen gemeinsamen Vielfachen der das Kleinste ist.

Die Existenz eines größten gemeinsamen Teilers ist wegen Lemma 12.2 klar. Die Existenz des kleinsten gemeinsamen Vielfachen ist ebenfalls klar, da das Produkt der Zahlen ein gemeinsames Vielfaches ist. Wir werden später als eine Anwendung der eindeutigen Primfaktorzerlegung (Satz 21.4) sehen, dass jeder gemeinsame Teiler den größten gemeinsamen Teiler teilt und dass jedes gemeinsame Vielfache ein Vielfaches des kleinsten gemeinsamen Vielfachen ist.

Definition

Eine natürliche Zahl

heißt eine Primzahl wenn die einzigen natürlichen Teiler von ihr und sind.

Eine Primzahl ist also eine natürliche Zahl, die genau zwei Teiler hat, nämlich

und die müssen verschieden sein. ist also keine Primzahl. Eine Zahl die keine Primzahl ist, heißt

Die ersten Primzahlen sind Für eine Primzahl und eine natürliche Zahl gilt folgende Alternative: Entweder teilt die Zahl oder aber

sind teilerfremd. Ein gemeinsamer Teiler muss ja ein Teiler von sein, und da kommen nur

in Frage.

Ein wichtiger Satz ist der Satz über die eindeutige Primfaktorzerlegung. Eine einfache Version davon ist der folgende Satz.

Satz

Jede natürliche Zahl , besitzt eine Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

mit Primzahlen

Beweis

Wir beweisen die Existenz durch Induktion über  Für

liegt eine Primzahl vor Bei

ist entweder eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung

mit kleineren Zahlen

Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für zusammen 

$\Box$

Für beispielsweise findet man den Primfaktor und kann daher

schreiben. Für hat man die Zerlegung

und man erhält

Wenn man mit dem Primfaktor startet, so ergibt sich

insgesamt kommen also die gleichen Primfaktoren vor. Gelegentlich betrachten wir die Gleichung

als die Primfaktorzerlegung der hier tritt jeder Primfaktor mit dem Exponenten auf, das leere Produkt ist Wir werden später in Satz 21.4 zeigen, dass die Primfaktorzerlegung bis auf die Reihenfolge eindeutig ist, was keineswegs selbstverständlich ist, einiger Vorbereitungen bedarf und am besten innerhalb der ganzen Zahlen bewiesen wird.

Der folgende Satz wird Euklid zugeschrieben.

Satz

Es gibt unendlich viele Primzahlen.

Beweis

Angenommen die Menge aller Primzahlen sei endlich, sagen wir sei eine vollständige Auflistung aller Primzahlen. Man betrachtet die natürliche Zahl

Da bei Division von durch immer der Rest übrigbleibt  (bzw. nach Aufgabe 12.12) ist diese Zahl durch keine der Primzahlen teilbar. Andererseits besitzt nach Satz 12.9 eine Primfaktorzerlegung. Insbesondere gibt es eine Primzahl die teilt (dabei könnte

sein). Doch damit muss gleich einem der aus der Liste sein, und diese sind keine Teiler von Dies ist ein Widerspruch, da ein nicht gleichzeitig ein Teiler und kein Teiler von sein kann. Also muss die Annahme (nämlich die Endlichkeit der Primzahlmenge) falsch gewesen sein.

$\Box$

In der Vorlesung Grundkurs Mathematik geht es um Sachverhalte, die allesamt seit mindestens Jahren gut verstanden sind und zu einem großen Teil sogar bis in die griechische Antike zurückreichen. Wir unterbrechen die allgemeine Darstellung und gehen kurz auf die Frage ein, was Mathematiker in der Forschung machen. Das ist im Allgemeinen schwierig zu vermitteln, im zahlentheoretischen Kontext gibt es aber einige Beispiele, die sich leicht erläutern lassen.

Die treibende Kraft der Mathematik ist es, Probleme zu lösen. Schwierige Probleme gibt es in allen Bereichen der Mathematik, besonders prägnant sind sie in der Zahlentheorie, da es dort eine Vielzahl von elementar formulierten ungelösten Problemen gibt. Man spricht von oder, wenn man eine bestimmte Erwartung hat, von einer Als Beispiel besprechen wir das Problem der Primzahlzwillinge, zu dem es vor einigen Jahren (2013) einen wichtigen Fortschritt gab.

Definition

Ein Primzahlzwilling ist ein Paar bestehend aus

wobei diese beiden Zahlen Primzahlen sind.

Die ersten Beispiele für Primzahlzwillinge sind

Übrigens ist der einzige Doppel-Primzahlzwilling , siehe Aufgabe 12.43.

Problem

Gibt es unendlich viele Primzahlzwillinge?

Eine Lösung dieses Problems wäre ein mathematischer Satz, der entweder besagt, dass es unendlich viele Primzahlzwillinge gibt, oder dass es nur endlich viele Primzahlzwillinge gibt. D.h. das eine oder das andere müsste bewiesen werden. Bei schwierigen Problemen erwartet man nicht, dass jemand plötzlich einen Beweis hinschreibt, sondern dass eine neue und weit verzweigte Theorie entwickelt wird, mit der man letztlich einen Beweis geben kann.

Bemerkung  

Die Frage, ob es unendlich viele Primzahlzwillinge gibt, besitzt verschiedene schwächere Varianten. Man kann sich zum Beispiel fragen, ob es unendlich oft vorkommt, dass es in einem Zehnerintervall zwei Primzahlen gibt, oder dass es in einem Hunderterintervall zwei Primzahlen gibt, und so weiter. Die ersten Primzahlen vermitteln dabei ein Bild, dass Primzahlen ziemlich häufig sind. Sie werden aber zunehmend seltener, sodass es für hohe Hunderterintervalle, sagen wir für die Zahlen von

ziemlich unwahrscheinlich ist, eine Primzahl zu enthalten, geschweige denn zwei Primzahlen. Bis vor kurzem war es nicht bekannt, ob es überhaupt eine Zahl mit der Eigenschaft gibt, dass es unendlich viele Intervalle der Länge gibt, die zwei Primzahlen enthalten ($m=2$ wäre die positive Lösung des Primzahlzwillingsproblems). Im Jahr 2013 bewies Zhang Yitang, dass man

nehmen kann, dass es also unendlich viele Intervalle der Form gibt, in denen zwei Primzahlen liegen. Dieses Resultat ist ein Durchbruch in der Primzahlzwillingforschung, da es erstmals zeigt, dass sich Primzahlen unendlich oft kommen. Zwischenzeitlich wurde die Schranke von auf gesenkt, siehe [1].

In dieser Vorlesung beschäftigen wir uns mit elementarer Kombinatorik, dabei ist ein wichtiges Ziel, die Binomialkoeffizienten einzuführen, um die allgemeine binomische Formel formulieren und beweisen zu können. Die Kombinatorik beschäftigt sich mit dem systematischen Abzählen (Anzahl bestimmen) von endlichen Mengen. Zwei wichtige Prinzipien haben wir schon kennengelernt, nämlich das Additivitätsprinzip für disjunkte Mengen (Satz 8.14) und das Multiplikativitätsprinzip für Produktmengen (Satz 9.6). In der folgenden Aussage bezeichnen wir zu einer Abbildung

zu

die Menge

als zu

Satz

Es seien

endliche Mengen und es sei

eine Abbildung.

Dann gilt

Beweis

Da jedes Element

auf genau ein Element aus abgebildet wird, liegt eine disjunkte Vereinigung

vor. Nach Satz 8.14 ist daher die Gesamtanzahl der Menge gleich der Summe der Anzahlen der disjunkten Teilmengen.

$\Box$

Bei einem Tanzkurs mit Damen und Herren gilt heute beim Schneewalzer Damenwahl, wobei die Damen in der Reihenfolge ihrer Sitzordnung wählen dürfen. Die erste Dame hat Wahlmöglichkeiten, die zweite Möglichkeiten, die dritte Möglichkeiten, u.s.w., die vorletze Dame hat noch zwei Möglichkeiten und für die letzte Dame verbleibt eine Möglichkeit.

Definition

Zu einer natürlichen Zahl nennt man die Zahl

die Fakultät von (sprich Fakultät).

Es ist

Man setzt

Für kleine erhält man die folgende Wertetabelle.

Lemma

Auf einer endlichen Menge

mit  Elementen   

gibt es bijektive Abbildungen von nach

Beweis

Wir zeigen etwas allgemeiner, dass es zwischen zwei endlichen Mengen

die beide Elemente besitzen, bijektive Abbildungen gibt. Dies zeigen wir durch Induktion nach wobei der Fall

klar ist. Die Aussage sei nun für schon bewiesen und es liegen zwei elementige Mengen

vor. Es sei

ein fixiertes Element. Dann gibt es für die Bilder genau Möglichkeiten, nämlich die Anzahl der Menge Wenn dies festgelegt ist, so entsprechen die bijektiven Abbildungen von nach mit

den bijektiven Abbildungen von nach Nach Induktionsvoraussetzung gibt es solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen

gleich

$\Box$

Gleichbedeutend damit ist, dass es Möglichkeiten gibt, Objekte auf Plätze zu verteilen, oder Möglichkeiten, eine Menge von Objekten abzuzählen (durchzunummerieren).

Beispiel

Wir möchten eine vollständige Liste von allen bijektiven Abbildungen von der Menge in die Menge in der Form von Wertetabellen angeben. Wegen

gibt es sechs solche Abbildungen. Es gibt keine natürliche Reihenfolge dieser Abbildungen, dennoch kann man hier mehr oder weniger systematisch vorgehen. Beispielsweise kann man den Wert an der Stelle zuerst festlegen und dann die möglichen Kombinationen für

durchgehen. Dies führt auf die folgenden Wertetabellen.

Satz

Die Anzahl der elementigen Teilmengen in einer elementigen Menge ist

Beweis

Es sei eine elementige Menge und

eine elementige Teilmenge. Wir betrachten die Menge aller bijektiven Abbildungen

die zusätzlich auf und (deshalb)

auf  abbilden. Nach

Lemma 13.3 und nach Satz 9.6 gibt es solche Abbildungen. Insgesamt gibt es bijektive Abbildungen von nach Daher ist

Insbesondere ist ein Teiler von und es ist

die Anzahl der elementigen Teilmengen von

$\Box$

Der Satz beinhaltet, dass ein Teiler von ist und somit ist der Bruch eine natürliche Zahl. Diese bekommt einen eigenen Namen und ein eigenes Symbol.

Definition

Es seien

natürliche Zahlen mit

Dann nennt man

den Binomialkoeffizienten

Bemerkung  

Für die Binomialkoeffizienten gilt die Regel

wie unmittelbar aus der Definition folgt. Dies kann man sich auch mit Hilfe von Satz 13.5 klar machen. Die Komplementabbildung

auf einer elementigen Menge ist bijektiv und bildet elementige Teilmengen auf elementige Teilmengen ab.

Den Binomialkoeffizienten kann man auch als

schreiben, da die Faktoren aus auch in vorkommen und daher kürzbar sind. In dieser Darstellung stehen im Zähler und im Nenner gleich viele Faktoren. Gelegentlich ist es sinnvoll, auch negative oder

zuzulassen und in diesen Fällen die Binomialkoeffizienten gleich zu setzen. Dies passt zur Interpretation in Satz 13.5.

Beispiel

In der vierelementigen Menge gibt es

zweielementige Teilmengen. Diese sind

Beispiel

In einer elementigen Menge gibt es genau

elementige Teilmengen. Es gibt also so viele mögliche Zahlenkombinationen beim Lotto Der Kehrwert von dieser Zahl ist die Wahrscheinlichkeit, beim Lotto sechs Richtige zu haben. Es werden dabei die Teilmengen gezählt, nicht die möglichen Ziehreihenfolgen. Die Anzahl der möglichen Ziehreihenfolgen ist

zu jeder sechselementigen Teilmenge gibt es mögliche Ziehreihenfolgen die auf diese Teilmenge führen.

Lemma

Die Binomialkoeffizienten

erfüllen die rekursive Beziehung

Beweis

Es ist

$\Box$

Wir geben noch einen zweiten Beweis für diese Aussage, der sich an der inhaltlichen Beschreibung der Binomialkoeffizienten als Teilmengenanzahl orientiert.

Es sei eine elementige Menge und

ein fixiertes Element. Nach Satz 13.5 ist die Anzahl der elementigen Teilmengen von gleich Eine solche Teilmenge enthält entweder oder aber nicht. Im ersten Fall entspricht dann eine solche Teilmenge einer elementigen Teilmenge von das ergibt den Summanden Im zweiten Fall entspricht eine solche Teilmenge einer elementigen Teilmenge von das ergibt den Summanden

Die folgende oder bringt die Addition, die Multiplikation und die Potenzierung in einem kommutativen Halbring und insbesondere für die natürlichen Zahlen miteinander in Beziehung.

Satz

Es sei ein kommutativer Halbring und

Ferner sei eine natürliche Zahl.

Dann gilt

Beweis

Wir führen Induktion nach Für

steht einerseits

und andererseits Es sei die Aussage bereits für bewiesen. Dann ist

$\Box$

Den vorstehenden Satz kann man sich auch folgendermaßen klar machen. Beim Ausmultiplizieren von

muss jeder Summand gemäß dem allgemeinen Distributivgesetz (in jedem Faktor) mit jedem Summanden multipliziert werden. Für jedes Teilprodukt muss man sich bei jedem Faktor entscheiden, ob man den vorderen Summanden oder den hinteren Summanden nimmt. Die einzelnen Produkte haben die Form wobei die Anzahl der Faktoren ist, bei denen gewählt wurde und die Anzahl der Faktoren ist, bei denen gewählt wurde. Wenn man fixiert, so kann man sich fragen, auf wie viele Arten das Produkt zustande kommen kann. Eine solche Möglichkeit ist dadurch gegeben, dass man unter den Faktoren bestimmt, in welchen von ihnen gewählt wird. Die Anzahl der Möglichkeiten ist also die Anzahl der elementigen Teilmengen von also gleich

Jede natürliche Zahl lässt sich bekanntlich als eine Ziffernfolge ausdrücken. Dies beruht auf der (sukzessiven) Division mit Rest. Eine positive natürliche Zahl ist nicht durch jede natürliche Zahl teilbar, die Division mit Rest liefert eine Operation, die stets durchführbar ist.

Satz

Es sei eine fixierte positive natürliche Zahl.

Dann gibt es zu jeder natürlichen Zahl eine eindeutig bestimmte natürliche Zahl und eine eindeutig bestimmte natürliche Zahl , mit

Beweis

Zur Existenz.  Dies wird durch Induktion über bewiesen. Es sei

fixiert. Der Induktionsanfang für

ergibt sich direkt mit

und

Für den Induktionsschluss sei die Aussage für bewiesen, d.h. wir haben eine Darstellung

mit

und müssen eine ebensolche Darstellung für finden. Wenn

ist, so ist

und wegen

ist dies eine gesuchte Darstellung. Ist hingegen

so ist

und dies ist eine gesuchte Darstellung.
Zur Eindeutigkeit. Sei

wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung

Dann gilt

Diese Differenz ist nichtnegativ und kleiner als links steht aber ein Vielfaches von sodass die Differenz sein muss und die beiden Darstellungen übereinstimmen.

$\Box$

Bei der Division mit Rest nennt man auch und Die Zahl nennt man oder und den

Bemerkung  

Zu gegebenen natürlichen Zahlen mit

findet man die Division mit Rest, also die Darstellung

indem man der Reihe nach die Vielfachen von betrachtet. Das größte Vielfache von (gleich oder) unterhalb von ist das gesuchte insbesondere muss das nächste Vielfache

sein. Der Rest ergibt sich dann als

In der Schule verwendet man häufig eine Darstellung für die Division mit Rest wie

Dies ist in Hinblick auf die mathematische Weiterverarbeitung ungünstiger als die im Satz verwendete Gleichungsform.

Mit der Division mit Rest können wir die Existenz und Eindeutigkeit der üblichen Zifferndarstellung einer natürlichen Zahl beweisen. Hinter der Zifferndarstellung verbirgt sich eine Mischung aus Addition, Multiplikation und Potenzierung (). Wir konzentrieren uns hauptsächlich auf die Ziffernentwicklung im (oder).

Satz

Zu jeder natürlichen Zahl

gibt es eindeutig bestimmte natürliche Zahlen und mit

und mit

(außer bei) mit der Eigenschaft

Beweis

Wir beweisen die Existenzaussage durch Induktion über Für

wählt man

und Es sei nun

und die Aussage für kleinere Zahlen schon bewiesen. Nach Satz 14.1 mit

gibt es eine Darstellung

mit zwischen und Es ist

deshalb gilt nach Induktionsvoraussetzung die Aussage für D.h. man kann

mit

(bei $q=0$ ist dies als leere Summe zu lesen) und mit

schreiben. Daher ist

eine Darstellung der gesuchten Art. Dabei ist

für

und
Die Eindeutigkeit folgt ebenfalls aus der Eindeutigkeit bei der Division mit Rest, siehe Aufgabe 14.17.

$\Box$

Eine natürliche Zahl wird im Zehnersystem einfach dadurch angegeben, dass die Ziffern nebeneinander hingeschrieben werden, wobei links die höchststellige Ziffer (die vorderste Ziffer) und rechts die niedrigststellige Ziffer, also die Einerziffer, steht. Die Zahl

wird also einfach als

geschrieben (in der gemischten Summen-und Produktdarstellung hätte man den Ausdruck auch weglassen können, nicht aber in der Dezimaldarstellung). Eine beliebige natürliche Zahl im Dezimalsystem mit Ziffern gibt man als

an, was die Zahl

bedeutet. Man beachte, dass wegen der gewünschten Kongruenz die Durchnummerierung der Ziffern bei anfängt, und somit bei insgesamt Ziffern die höchststellige Ziffer die Nummer besitzt. Wenn man von der ten Ziffer spricht, meint man die Ziffer, die sich auf bezieht. Von daher spricht man besser von der Einerziffer (bezieht sich auf), der Zehnerziffer, der Hunderterziffer, der Tausenderziffer u.s.w. Gelegentlich ist es sinnvoll, auch Ziffernentwicklungen zuzulassen, die vorne mit Nullen beginnen, beispielsweise wenn man bei der Addition zweier natürlicher Zahlen gleich viele Ziffern haben möchte. Die Potenzen nennt man auch die Man fasst eine Zahl in Bündel von solchen Einheiten zusammen, wobei von einem Bündel maximal genommen werden, da Bündeleinheiten durch die nächsthöhere Bündelungseinheit ausgedrückt werden kann (und muss, um eine eindeutige Darstellung zu erreichen). Wenn eine große Punktmenge vorliegt, so wird dieses Bündelungsprinzip sichtbar, wenn man zuerst Bündel formt (indem man jeweils Punkte zusammenfasst, umkreist, markiert), dann zehn Zehnerbündel zu einem Hunderterbündel zusammenfasst und so weiter.

Bemerkung  

Aus dem Beweis zu Satz 14.3 kann man ablesen, wie man zu einer irgendwie gegebenen natürlichen Zahl die Entwicklung im Zehnersystem erhält. Man dividiert die Zahl durch und der Rest ergibt die Endziffer. Dann zieht man von diesen Rest ab und weiß, dass diese Zahl ein Vielfaches von ist. Man dividiert sie durch und bestimmt für das Ergebnis erneut den Rest, der die Zehnerziffer gibt, u.s.w. Bei diesem Verfahren berechnet man also die Ziffern von hinten nach vorne.

Ein anderes Verfahren, bei dem man die Ziffern von vorne nach hinten berechnet, geht folgendermaßen: Man bestimmt die maximale Zehnerpotenz die in hineinpasst, es muss also

gelten. Dann findet man das maximale Vielfache von das in hineinpasst, also die Zahl mit

Diese Zahl muss zwischen

liegen. Der Wert

kann nicht sein, da ansonsten

im Widerspruch zur Wahl der Zehnerpotenz wäre, ein Wert

kann nicht sein, da ansonsten

wäre, was wieder der Wahl der Zehnerpotenz widerspricht. Diese Ziffer

ist dann die Anfangsziffer der Dezimalentwicklung. Nun rechnet man

und weiß nach der Wahl von

dass diese neue Zahl echt kleiner als ist. Man bestimmt das maximale Vielfache von unterhalb von der Vorfaktor (der jetzt auch sein kann) ergibt die Ziffer und man zieht das Vielfache von ab und wiederholt das Verfahren.

Bemerkung  

Es sei eine natürliche Zahl in der Form

gegeben, wobei die beliebige natürliche Zahlen sind, also nicht unbedingt kleiner als sein müssen. Die zu gehörige Dezimalentwicklung erhält man sukzessive durch folgende Vorgehensweise. Man führt für die Division mit Rest durch durch und erhält eine Darstellung

mit einem Rest , Damit ist

Somit haben wir eine neue Darstellung von bei der die Einerziffer kleiner als ist. Als nächstes arbeitet man den neuen Vorfaktor (also $c_{1}+q_{0}$) zu ab und bringt ihn auf die erlaubte Zifferngestalt, wobei der davor liegenden Vorfaktor wieder geändert wird. Dies führt letztlich zur Darstellung im Dezimalsystem.

Bemerkung  

Für Rechnungen ist das Dezimalsystem sehr gut geeignet, wie die aus der Schule bekannten und im Laufe der Vorlesung zu entwickelnden Algorithmen zeigen werden, für theoretische Überlegungen und Beweise, auch über das Dezimalsystem selbst, ist die obige gemischte Summen- und Produktdarstellung besser geeignet, da darin die grundlegenden Verknüpfungen auf den natürlichen Zahlen sichtbar werden.

Eine zu Satz 14.3 entsprechende Aussage gilt für jede

statt

Bei

spricht man vom die einzigen Ziffern sind

bei

vom mit den Ziffern u.s.w. Bei

spricht man vom und verwendet die Ziffern

Dass das Dezimalsystem nur eine unter vielen möglichen Darstellungen einer natürlichen Zahl ist, wird besonders deutlich, wenn man Darstellungen in verschiedenen Ziffernsystemen (oder) ineinander umrechnet.

Beispiel

Wir wollen die im Dezimalsystem gegebene Zahl im Dreiersystem ausdrücken. Dazu müssen wir (analog zur zweiten Methode aus Bemerkung 14.4) die größte Dreierpotenz finden, die unterhalb liegt. Das ist

(da

zu groß ist). Für diese Potenz müssen wir schauen, wie oft sie in hineingeht. Wegen

sind das zweimal. Wir wissen daher, dass die Entwicklung der Zahl im Dreiersystem beinhaltet, die Ziffer steht somit als Anfangsziffer fest. Die weitere Ziffernentwicklung hängt jetzt nur von der Differenz

ab. Diese Zahl ist kleiner als

was bedeutet, dass die dritte Dreierpotenz und das heißt hier mit der Ziffer vorkommt. Wir arbeiten dann mit und mit der nächstkleineren Dreierpotenz weiter, also mit

Diese hat wieder zweimal Platz in die Differenz ist

Die

passt wieder zweimal rein, übrig bleibt Im Dreiersystem lautet also die Ziffernentwicklung

Diese Ziffernfolge kann man sukzessive notieren (Nullen nicht vergessen) oder aber in der Rechnung stets deutlich machen, auf welche Potenz sich der jeweilige Rechenschritt bezieht und dann zum Schluss daraus die Ziffernfolge ablesen.

In dieser Vorlesung besprechen wir, wie sich im Dezimalsystem der Nachfolger, die Größergleichrelation und die Addition darstellen.

Zuerst bemerken wir, dass das übliche Zählen (Einerstelle um erhöhen und eventuell mit den höheren Ziffern verarbeiten), das wir auch in der fünften Vorlesung als eine Zählmöglichkeit erwähnt hatten, korrekt ist. Dies ist eine zwar einfache, aber dennoch durchzuführende Überlegung, da für uns eine Ziffernfolge nicht durch die Reihenfolge im Zählprozess festgelegt ist, sondern über die Interpretation als gemischte Darstellung mit Summen, Produkten und Potenzen.

Bemerkung  

Das Dezimalsystem im Sinne eines Zählsystems, das die Dedekind-Peano-Axiome erfüllt, hat erstmal nichts mit Summe, Produkt, Potenzen zu tun, sondern ist allein durch die folgende Struktur (Menge mit Zählvorschrift) gegeben. Die Elemente sind von der Form

also einfach endliche geordnete Tupel von Ziffern (Ziffernfolgen) aus der Menge Dabei ist das Startelement. Der Zählvorgang wird durch den folgenden dezimalen beschrieben.

1. Für einstellige Ziffern ist der Nachfolger gemäß der Reihenfolge festgelegt (dies ist das).
2. Für beliebige Zahlen im Zehnersystem mit einer letzten Ziffer ist der Nachfolger diejenige Ziffernfolge, bei der die letzte Ziffer durch den Nachfolger ersetzt wird und alle anderen Ziffern unverändert übernommen werden.
3. Für beliebige Zahlen im Zehnersystem mit einer Neun als letzter Ziffer sind sämtliche zusammenhängenden Neunen von hinten durch Nullen zu ersetzen und die von hinten erste von verschiedene Ziffer durch ihren Nachfolger zu ersetzen, die übrigen Ziffern bleiben gleich (wenn die Zahl ausschließlich aus Neunen besteht, ist dies so zu verstehen, dass man sich davor eine dazudenkt).

Lemma

Das Nachfolgernehmen im Dezimalsystem (gemischtes Dezimaldarstellungssystem)

stimmt mit dem Zählvorgang im Sinne von Bemerkung 15.1 (Dezimalzählsystem) überein.

Beweis

Wir gehen vom Dezimalsystem im Sinne einer gemischten Darstellung (Stellenwertsystem) aus und müssen zeigen, dass dort das Nachfolgernehmen, also die Addition mit die gleiche Wirkungsweise besitzt wie der Zählalgorithmus. Der Nachfolger einer im Dezimalsystem gegebenen natürlichen Zahl

ist einfach

Aus diesem Ausdruck lässt sich aber noch nicht unmittelbar die Dezimaldarstellung dieser Zahl ablesen, da der Einerkoeffizient nicht unbedingt sein muss. Wenn

ist, so ist

und die Dezimalentwicklung des Nachfolgers liegt unmittelbar vor. Wenn hingegen

ist, so geht es um die Zahl

Erneut gilt, dass bei

die Dezimalentwicklung vorliegt, bei

muss man wie zuvor weitermachen. Wenn die hintersten (niedrigststelligen)

Ziffern  gleich  sind und

(was den Fall einschließt, dass genau Ziffern hat, in welchem Fall als zu interpretieren ist), so erhält man den Nachfolger, indem man diese Neunen durch Nullen ersetzt und um erhöht. Es liegt also die Wirkungsweise des Zählalgorithmus vor.

$\Box$

Korollar

Es sei Eine natürliche Zahl ist genau dann

wenn sie im Zehnersystem aus maximal Ziffern besteht.

Beweis

Dies folgt aus Lemma 15.2, da es für den Zählprozess klar ist, dass längere Ziffernfolgen größer sind (im Zählprozess später dran kommen).

$\Box$

Korollar

Es seien

und

zwei natürliche Zahlen im Zehnersystem (also mit).

Dann ist

genau dann, wenn

oder wenn

ist und wenn es ein , derart gibt, dass

ist.

Beweis

Dies folgt aus Lemma 15.2. Vom Zählprozess her ist es klar, dass längere Ziffernfolgen größer sind. Bei gleichlangen Ziffernfolgen und übereinstimmender Anfangssequenz entscheidet die nächste Ziffer, welche Zahl im Zählprozess später dran kommt.

$\Box$

Da sich die Addition zweier natürlicher Zahlen aus den Dedekind-Peano-Axiomen ergibt, gibt es in jeder Beschreibung der natürlichen Zahlen genau eine Möglichkeit, zu addieren. Ob diese algorithmisch geschickt oder kompliziert ist, hängt wesentlich von der gewählten Beschreibung ab. Wenn man durch Strichfolgen gegebene Zahlen miteinander addiert, so hängt man einfach die beiden Strichfolgen aneinander. Dies ist auf den ersten Blick ein sehr einfacher Vorgang. Wenn man es aber ernsthaft schriftlich durchführen möchte, so sieht man, dass es extrem mühsam ist, da man jeden Strich der einen Strichfolge einzeln an die andere anhängen muss.

Das schriftliche Addieren zweier natürlicher Zahlen im Zehnersystem ist aus der Schule bekannt. Man schreibt die beiden Zahlen untereinander so, dass die Einerpositionen übereinander stehen und addiert dann die beiden passenden Ziffern (im Sinne des kleinen Einundeins) von hinten nach vorne. Wenn das Ergebnis kleiner als ist, schreibt man diese Zahl hin und rückt nach links. Wenn das Ergebnis größer oder gleich ist, so schreibt man die Einerziffer dieser Summe an der Stelle hin und hat in der links liegenden Stelle einen zusätzlichen Übertrag von mitzuberücksichtigen. Dies ist insgesamt ein rekursives Verfahren, das wir kurz festhalten.

Verfahren  

Das schriftliche Addieren zweier natürlicher Zahlen, die im Dezimalsystem als

gegeben sind (wobei auch vordere Nullen erlaubt sind), funktioniert folgendermaßen. Man berechnet die Dezimalziffern

des Ergebnisses und die    

(mit dem Startwert) sukzessive durch

und

Die Dezimaldarstellung der Summe ist (wobei

sein kann). Es gilt stets

Warum ist dieser Algorithmus richtig, warum liefert er das korrekte Ergebnis? Die Gewöhnung an dieses Verfahren verleitet dazu, diese Frage nicht ernst zu nehmen bzw. nicht zu verstehen. Das eben beschriebene schriftliche Addieren ist nicht die Definition der Addition, sondern eine algorithmische Ausführung der Addition in einem bestimmten Beschreibungssystem (nämlich dem Dezimalsystem) für die natürlichen Zahlen.

Der Ausgangspunkt der Addition der natürlichen Zahlen liegt in der disjunkten Vereinigung von endlichen Mengen, wir haben die Addition über die Nachfolgerabbildung eingeführt und bereits in Satz 8.14 gezeigt, dass sie mit dem Vereinigungskonzept übereinstimmt. Warum stimmt auch das schriftliche Addieren damit überein? Konkret: Man hat zwei Mengen

an Äpfeln und bestimmt für beide Mengen ihre Anzahl im Zehnersystem: diese seien

Dann schüttet man die Mengen zusammen, erhält die Menge

und bestimmt für diese Menge die Anzahl im Zehnersystem: diese sei Warum kommt, wenn man die Zahlen

im Zehnersystem schriftlich addiert, ausgerechnet heraus?

Die beiden Zahlen seien als

gegeben, wobei die Ziffern alle zwischen

seien. Es sei

und wir können sogar annehmen, dass

ist, indem wir fehlende Ziffern in der zweiten Dezimalentwicklung durch Nullen auffüllen. Dann ist

Dies beruht auf dem Assoziativgesetz der Addition und dem Distributivgesetz. Achtung! Dieses Ergebnis ist nicht in der Dezimaldarstellung, da die vor den Zehnerpotenzen stehenden Zahlen nicht unbedingt kleiner als sein müssen. Man kann an dieser Stelle Bemerkung 14.5 anwenden und zu den Ziffern nach oben schaufeln. Dies ist aber nicht das Verfahren des schriftlichen Addierens.

Satz

Das schriftliche Addieren im Zehnersystem ist korrekt.

Beweis

Die beiden Zahlen seien

wobei wir eventuell auch vordere Nullen erlauben. Aufgrund des Distributivgesetzes ist die Summe gleich

Wir ersetzen gemäß Verfahren 15.5

und erhalten

Jetzt ersetzen wir

und erhalten

Jetzt ersetzen wir

und erhalten

So fortfahrend bringt man die Summe sukzessive auf die Form, in der vor allein steht. Wegen

erhält man so die Darstellung im Dezimalsystem.

$\Box$

Die Korrektheit des schriftlichen Addierens überträgt sich auf die Addition mehrerer Summanden in der Dezimaldarstellung. Man summiert wieder ziffernweise und schreibt die letzte Ziffer der Summe an der entsprechenden Stelle hin, ebenso den Übertrag. Dieser kann jetzt allerdings (ab zwölf Summanden) sogar größergleich sein, in diesem Fall muss man die Zehnerziffer wie zuvor um eins nach links schreiben und die Hunderterstelle um zwei nach links. Grundsätzlich kann man auch eine Summe mit beliebig vielen Summanden dadurch errechnen, dass man je zwei Summanden zusammenaddiert und somit die Anzahl der Summanden sukzessive verringert, doch ist das viel komplizierter.

Bemerkung  

Unter einem versteht man ein durch bestimmte Regeln festgelegtes (deterministisches) Verfahren, mit dem man in endlich vielen Schritten zu einem Ergebnis kommt. Ein Algorithmus bezieht sich auf eine Menge von möglichen Eingaben (Input) und liefert eine Ausgabe, das Ergebnis (Output). Ein Algorithmus berechnet den Wert einer Abbildung (einschließlich einer Verknüpfung), überprüft, ob eine Relation zwischen Elementen vorliegt oder nicht, findet die Lösung zu einer Gleichung. Die Regeln sind präzise Handlungsanweisungen und müssen alle möglichen Fälle abdecken. Ein Algorithmus kann prinzipiell durch eine Maschine durchgeführt werden.

Im Grundkurs werden wir die folgenden Algorithmen behandelt: Schriftliches Zählen (Nachfolgernehmen), schriftliches Vergleichen, schriftliches Addieren, schriftliches Multiplizieren, schriftliches Subtrahieren, schriftliches Dividieren (in einem Stellenwertsystem), der euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers, das Gaußsche Eliminationsverfahren zur Lösung linearer Gleichungssysteme, das Invertierungsverfahren für Matrizen, das Heron-Verfahren.

Folgende Punkte sind charakteristisch für einen Algorithmus.

1. Es gibt eine relativ kleine Zahl von Einzelschritten, auf die im Durchlauf des Algorithmus immer wieder Bezug genommen wird.
2. Die Einzelschritte verwenden eine endliche Liste von gespeicherten elementaren Teilergebnissen (Datenbank).
3. Es muss irgendwie verbucht werden, auf welche Stelle sich der Einzelschritt bzw. dessen Ergebnis bezieht (Nummerierung, Indizierung, Anordnung).
4. Die Einzelschritte verwenden Fallunterscheidung, entlang welcher sich das Verfahren verzweigt.
5. Es werden Hilfszahlen zwischengespeichert und verwendet.

Beispielsweise werden im Additionsalgorithmus immer wieder zwei einstellige Zahlen miteinander addiert, dabei wird auf das kleine Einsundeins Bezug genommen und die Endziffer dieser Teilrechnung wird an der richtigen Stelle notiert. Die Weiterverarbeitung hängt davon ab, ob diese Einzelsummen kleiner als oder darüber sind, es werden Überträge notiert.

Bemerkung  

Von der Beschreibung eines Algorithmus, d.h. der präzisen Festlegung der einzelnen auszuführenden Rechenschritte, ist die Begründung für die Korrektheit des Algorithmus zu unterscheiden. Mit Korrektheit meint man, dass der Algorithmus wirklich das leistet, was er verspricht, also dass beispielsweise das schriftliche Additionsverfahren wirklich die beiden Zahlen addiert. Für diesen Nachweis braucht man einen mathematischen Beweis, der sowohl auf die zu berechnende mathematische Struktur (die Addition) als auch auf die Festlegungen des Algorithmus Bezug nimmt.

Ein wichtiger Aspekt bei vielen Algorithmen, der bei einem solchen Beweis hilft, ist ein Bei einem Algorithmus werden typischerweise mehrere Zwischenergebnisse berechnet und weiterverarbeitet. Insbesondere bei rekursiven Definitionen und bei der maschinellen Durchführung werden Zwischenergebnisse auch überschrieben. Dennoch ist zu jedem Zeitpunkt des Ablaufes die volle Information in einer bestimmten Weise in den Zwischenergebnissen repräsentiert. Wenn man beipielsweise zwei zehnstellige Zahlen schriftlich addiert, und die hinteren fünf Endziffern der Summe und den letzten Übertrag schon berechnet hat, so kann man die hinteren Endziffern der Summanden vergessen. Die Information, was berechnet werden soll, steckt vollständig (invariant) in den vorderen Ziffern der Summanden, den hinteren Ziffern der Summe und dem einen Übertrag drin.