Einheit 1 – Sprache und Beweise
Vierte Fassung vom 18. November 2026.
Leitfrage
Man bilde die Zahlen für Die ersten fünf sind
und alle fünf sind Primzahlen. Pierre de Fermat vermutete, dass alle Zahlen prim sind. Die Vermutung ist falsch; Leonhard Euler fand den Teiler:
Die Analysis handelt fast nur von Aussagen über unendlich viele Fälle: über alle natürlichen Zahlen, alle reellen Zahlen, alle noch so kleinen Abstände. Kein Vorrat an Beispielen entscheidet eine solche Aussage. Wie beweist man etwas über unendlich viele Fälle, und wie sagt man überhaupt genau, was man behauptet? Diese Einheit stellt die Sprache und die Beweisformen bereit, die der ganze Kurs benutzt.
Schreibweisen. sind die natürlichen Zahlen, ; , und bezeichnen die ganzen, rationalen und reellen Zahlen. Für heißt ein Teiler von , geschrieben , wenn mit einem gilt. Eine ganze Zahl heißt gerade, wenn , sonst ungerade; die ungeraden Zahlen sind genau die Zahlen mit . Eine Primzahl ist eine natürliche Zahl , deren einzige Teiler in die Zahlen und sind. Für reelle sind und das abgeschlossene und das offene Intervall von bis ; entsprechend und , ferner und . Das Zeichen ist dabei keine Zahl.
Voraussetzungen. Der Kurs setzt keine Hochschulmathematik voraus, verlangt aber, dass jeder Schluss nachvollzogen wird. Was nicht bewiesen wird, ist als Voraussetzung ausgewiesen. In dieser Einheit sind das:
- die Peano-Axiome (Abschnitt 1.6) und, ohne Ausführung, der daraus folgende Aufbau von , und mit Addition, Multiplikation und Anordnung; dazu gehören der Rekursionssatz, die Nullteilerfreiheit von (aus folgt oder ) und die Division mit Rest (insbesondere ist jede ganze Zahl entweder gerade oder ungerade);
- das Rechnen mit Brüchen in ; wie aus entsteht, zeigen Abschnitt 1.9 und Aufgabe B5;
- dass ein angeordneter Körper ist, der enthält; benutzt werden nur die in Abschnitt 1.8 aufgezählten Anordnungsregeln, und jede Stelle nennt die Regel, die eingeht;
- der Mengenbegriff in der Form von Abschnitt 1.4 und die Zählregeln für endliche Mengen aus Abschnitt 1.7.
Einheit 2 löst Punkt 3 ein: Dort wird aus konstruiert, und die Anordnungsregeln werden bewiesen.
1.1 Aussagen und ihre Verknüpfungen
Definition 1.1. Eine Aussage ist ein sprachliches oder formelhaftes Gebilde, das entweder wahr oder falsch ist.
„ ist eine Primzahl“ ist eine Aussage (wahr), „“ ebenfalls (falsch). Keine Aussage ist „“: Der Wahrheitswert hängt von ab. Ein solcher Ausdruck heißt Aussageform; er wird zur Aussage, sobald man für etwas einsetzt oder durch einen Quantor bindet (Abschnitt 1.2).
Aus Aussagen und entstehen neue:
| Zeichen | gelesen | wahr genau dann, wenn |
|---|---|---|
| nicht | falsch ist | |
| und | beide wahr sind | |
| oder | mindestens eine wahr ist | |
| aus folgt | falsch oder wahr ist | |
| genau dann, wenn | beide denselben Wahrheitswert haben |
Zwei Punkte weichen vom Alltagsgebrauch ab. Erstens ist das mathematische „oder“ nicht ausschließend: ist auch wahr, wenn beide gelten. Zweitens ist wahr, sobald falsch ist. Die Implikation behauptet nichts über den Fall, in dem die Voraussetzung nicht eintritt. „Wenn , dann ist “ ist eine wahre Aussage.
Der Grund für diese Festlegung liegt im Gebrauch. Der Satz „Für jedes : Ist durch teilbar, so ist gerade“ soll wahr sein. Er umfasst auch und , bei denen die Voraussetzung nicht erfüllt ist. Wäre die Implikation dort falsch, so wäre jeder Satz dieser Form falsch.
Satz 1.2 (Rechenregeln der Logik). Für Aussagen , gilt:
- und (Regeln von De Morgan),
- (Kontraposition),
- .
Beweis. Jede Seite hängt nur von den Wahrheitswerten von und ab; es gibt vier Fälle. Für (2) und (3):
| w | w | w | w | f |
| w | f | f | f | w |
| f | w | w | w | f |
| f | f | w | w | f |
Die dritte und vierte Spalte stimmen überein, die fünfte ist überall das Gegenteil der dritten. Teil (1) prüft man ebenso.
Regel (3) ist die meistgebrauchte: Eine Implikation widerlegt man, indem man einen Fall angibt, in dem die Voraussetzung gilt und die Behauptung nicht. Die Verneinung von „wenn , dann “ ist nicht „wenn , dann nicht “.
Vorsicht bei der Umkehrung: ist etwas anderes als . Aus „ ist durch teilbar“ folgt „ ist gerade“; die Umkehrung ist falsch, wie zeigt.
1.2 Quantoren
Ist eine Aussageform und eine Menge, so bedeutet
- — für jedes aus gilt ,
- — es gibt mindestens ein aus , für das gilt.
Regel 1.3 (Verneinung).
Regel 1.3 wird nicht aus Satz 1.2 bewiesen; sie gibt wieder, was die Quantoren bedeuten. Für eine endliche Menge ist dasselbe wie , und Regel 1.3 ist dann die wiederholte De-Morgan-Regel. Für die leere Menge ist jede Allaussage wahr und jede Existenzaussage falsch.
Kurzformen wie oder bedeuten beziehungsweise . Beim Verneinen wechselt nur der Quantor, die Einschränkung bleibt stehen: Die Verneinung von ist , nicht .
Beim Verneinen wird also jeder Quantor umgedreht und die Aussage am Ende verneint. Die Leitfrage ist ein Fall davon: „Für alle ist prim“ wird durch ein Gegenbeispiel widerlegt, nämlich .
Die Reihenfolge verschiedener Quantoren ist nicht vertauschbar. Man vergleiche
(a) ist wahr: Zu gegebenem wähle man . Das darf von abhängen. (b) ist falsch: Es müsste eine einzige Zahl geben, die größer ist als jede reelle Zahl, also auch größer als selbst. Bei (a) wird nach gewählt, bei (b) vor .
Dieser Unterschied trägt später ganze Begriffe. Ein Vorgriff auf Einheit 4: Eine Folge reeller Zahlen konvergiert gegen , wenn
Nach Regel 1.3 heißt „ konvergiert nicht gegen “:
Man erhält die Verneinung mechanisch, ohne die Bedeutung schon verstanden zu haben. Genau dafür ist die formale Schreibweise da.
1.3 Beweisformen
Bewiesen werden soll meist eine Implikation . Drei Formen kommen immer wieder vor.
Direkter Beweis. Man setzt voraus und leitet her.
Beispiel. Ist ungerade, so ist ungerade. Denn mit einem , also .
Beweis durch Kontraposition. Statt zeigt man ; nach Satz 1.2 ist das dieselbe Aussage.
Beispiel. Ist gerade, so ist gerade. Direkt kommt man schlecht voran, weil man aus nicht ohne Weiteres auf schließen kann. Die Kontraposition lautet „ist ungerade, so ist ungerade“, und das ist das vorige Beispiel.
Diese kleine Aussage wird in Einheit 2 gebraucht, im Beweis, dass nicht rational ist: Aus einer Darstellung mit ganzen Zahlen , folgt, dass gerade ist, nach dem Beispiel also auch .
Beweis durch Widerspruch. Man nimmt an, die Behauptung sei falsch, und leitet daraus etwas Falsches her. Dann kann die Annahme nicht stimmen.
Beispiel. Es gibt keine kleinste positive rationale Zahl. Angenommen, wäre die kleinste. Dann ist ebenfalls rational und positiv, aber , denn – ein Widerspruch zur Wahl von .
Eine Äquivalenz beweist man in zwei getrennten Teilen, und . Eine Allaussage widerlegt man durch ein Gegenbeispiel; bewiesen ist sie durch noch so viele Beispiele nicht.
1.4 Mengen
Wir verwenden den Mengenbegriff so, wie ihn die gesamte Analysis benutzt: Eine Menge ist eine Zusammenfassung von Objekten, ihren Elementen; heißt, ist Element von . Eine Menge ist durch ihre Elemente bestimmt: gilt genau dann, wenn beide dieselben Elemente haben. Die leere Menge hat kein Element.
Bemerkung (Grenzen des naiven Mengenbegriffs). Nicht jede Eigenschaft definiert eine Menge. Wäre eine Menge, so gälte (Russell). Die axiomatische Mengenlehre (Zermelo-Fraenkel) schließt solche Bildungen aus. Für die Analysis genügt eine Vorsichtsregel: Mengen werden nur als Teilmengen bereits vorhandener Mengen ausgesondert, , oder mit den Operationen der folgenden Definition gebildet.
Definition 1.4. Für Mengen , heißt
- (Teilmenge), wenn jedes Element von auch in liegt; Gleichheit ist zugelassen,
- die Vereinigung,
- der Durchschnitt,
- die Differenz,
- das kartesische Produkt (Menge der geordneten Paare),
- die Potenzmenge.
Von geordneten Paaren wird nur eine Eigenschaft gebraucht: gilt genau dann, wenn und .
Die Gleichheit zweier Mengen beweist man fast immer über zwei Inklusionen: genau dann, wenn und .
Satz 1.5 (De Morgan für Mengen). Für Teilmengen , einer Menge gilt
Beweis. Für gilt: . Der mittlere Schritt ist Satz 1.2 (1), angewandt auf die Aussagen „“ und „“. Die zweite Gleichung folgt ebenso aus der anderen De-Morgan-Regel.
Die Mengenregeln sind also die Regeln der Logik in anderer Schreibweise: entspricht „oder“, entspricht „und“, das Komplement der Verneinung.
Vereinigung und Durchschnitt bildet man auch über beliebig viele Mengen. Eine Familie von Teilmengen einer Menge ordnet jedem aus der Indexmenge eine Teilmenge zu; sie ist eine Abbildung im Sinn von Abschnitt 1.5. Allgemein heißt jede Abbildung mit Definitionsbereich eine Familie; eine Folge ist später eine Familie mit . Man setzt
Beides sind Aussonderungen aus . Für ist die Vereinigung leer und der Durchschnitt gleich . Ohne die Grundmenge wäre der leere Durchschnitt die Gesamtheit aller Dinge, und die ist keine Menge. Die Regeln von De Morgan gelten auch für Familien,
mit demselben Beweis wie Satz 1.5; an die Stelle von Satz 1.2 (1) tritt Regel 1.3.
Beispiel. Für ist , obwohl jede einzelne Menge unendlich viele Elemente hat und gilt. Der Nachweis, dass kein in allen liegt, braucht eine Eigenschaft der reellen Zahlen, die erst Einheit 2 bereitstellt (zu jedem gibt es ein mit ).
1.5 Abbildungen
Definition 1.6. Eine Abbildung ordnet jedem Element genau ein Element zu. heißt Definitionsbereich, Zielmenge. Zwei Abbildungen sind gleich, wenn sie denselben Definitionsbereich, dieselbe Zielmenge und für jedes denselben Wert haben.
Zur Abbildung gehören also drei Angaben, nicht nur die Rechenvorschrift. als Abbildung und als Abbildung sind verschiedene Abbildungen mit verschiedenen Eigenschaften, wie sich gleich zeigt.
Bemerkung (Abbildung als Menge). Präzise ist eine Abbildung durch ihren Graphen zusammen mit und gegeben. Eine Teilmenge ist genau dann Graph einer Abbildung, wenn es zu jedem genau ein mit gibt. Daraus ergeben sich die Randfälle: Für jede Menge gibt es genau eine Abbildung , die leere Abbildung mit dem Graphen . Ist , so gibt es keine Abbildung .
Definition 1.7. Für , und heißt
Das Urbild ist für jede Abbildung erklärt; die Schreibweise setzt nicht voraus, dass es eine Umkehrabbildung gibt.
Zu einer Abbildung und einem gehört die Gleichung . Zwei Fragen stellen sich: Hat sie für jedes eine Lösung? Hat sie für jedes höchstens eine? Die folgenden Begriffe geben diesen Fragen Namen.
Definition 1.8. Eine Abbildung heißt
- injektiv, wenn aus stets folgt,
- surjektiv, wenn es zu jedem ein mit gibt, also ,
- bijektiv, wenn sie injektiv und surjektiv ist.
Surjektiv heißt also: Die Gleichung ist für jedes lösbar. Injektiv heißt: Sie hat für jedes höchstens eine Lösung. Bijektiv heißt: genau eine.
Beispiel. , , ist nicht injektiv () und nicht surjektiv ( wird nicht angenommen). Dieselbe Vorschrift als Abbildung ist injektiv, aber nicht surjektiv. Als Abbildung ist sie injektiv; dass sie auch surjektiv ist, heißt: Jede Zahl hat eine Quadratwurzel. Das ist keine Formalität, sondern ein Satz über die reellen Zahlen (Einheit 2; in ist er falsch).
Definition 1.9. Für und ist die Verkettung durch erklärt. Die identische Abbildung ist .
Die Verkettung ist assoziativ, , aber nicht kommutativ: Für und auf ist und .
Satz 1.10 (Umkehrabbildung). Eine Abbildung ist genau dann bijektiv, wenn es eine Abbildung gibt mit
In diesem Fall ist eindeutig bestimmt; man nennt die Umkehrabbildung und schreibt .
Beweisidee. Injektiv heißt „höchstens ein Urbildpunkt“, surjektiv „mindestens einer“; zusammen gibt es zu jedem genau ein , und dieses ist .
Beweis. „“: Sei bijektiv. Zu gibt es wegen der Surjektivität ein mit und wegen der Injektivität nur eines. Setze . Dann ist nach Konstruktion, und ist das eindeutige Element, das auf abgebildet wird, also .
„“: Sei wie angegeben. Aus folgt ; also ist injektiv. Für ist ; also ist surjektiv.
Eindeutigkeit: Erfüllt auch beide Gleichungen, so ist .
Satz 1.11 (Bild, Urbild und Mengenoperationen). Für , und gilt:
- und ,
- ,
- ,
- ,
- Regel (1) gilt ebenso für Vereinigung und Durchschnitt beliebiger Familien, Regel (2) für die Vereinigung beliebiger Familien.
Beweis. (1) ; mit „oder“ ebenso.
(2) es gibt oder mit .
(3) Ist mit , so liegt in und in .
(4) .
(5) Für eine Familie ist ; mit „“ ebenso, und für das Bild einer Vereinigung wie in (2).
In (3) steht nur eine Inklusion, und mehr gilt nicht; siehe Abschnitt 1.10. Das Urbild verträgt sich mit Vereinigung, Durchschnitt und Komplement, das Bild nur mit der Vereinigung. Deshalb wird Stetigkeit später auch über Urbilder beschrieben: Eine Funktion ist genau dann stetig, wenn die Urbilder offener Mengen offen sind.
Bemerkung (einseitige Inverse). Die beiden Gleichungen in Satz 1.10 lassen sich trennen. Für ist genau dann injektiv, wenn es ein mit gibt (Linksinverse). Gibt es ein mit (Rechtsinverse), so ist surjektiv. Die Umkehrung der zweiten Aussage verlangt, zu jedem gleichzeitig ein Urbild auszuwählen; für unendliches ist das im Allgemeinen nur mit dem Auswahlaxiom möglich (Aufgabe V5).
1.6 Vollständige Induktion
Nun zur ersten Hälfte der Leitfrage. Unendlich viele Fälle einzeln zu prüfen ist unmöglich. Die vollständige Induktion ersetzt diese Prüfung durch zwei endliche Aufgaben: einen ersten Fall nachzuweisen und einmal allgemein zu zeigen, dass jeder Fall den nächsten nach sich zieht. Dass dies genügt, ist keine Eigenschaft der Logik, sondern eine der natürlichen Zahlen.
Die natürlichen Zahlen werden in diesem Kurs nicht konstruiert, sondern durch die Peano-Axiome festgelegt: Es gibt eine Menge , ein Element und eine Abbildung (Nachfolger) mit
- (P1) ist injektiv,
- (P2) ist kein Nachfolger: ,
- (P3) ist mit und , so ist .
Die übliche Beschreibung enthält mit den Pünktchen genau das, was zu klären ist: dass man von aus durch fortgesetztes Weiterzählen jede natürliche Zahl erreicht und nichts sonst. Die drei Axiome sprechen das aus, und keines ist entbehrlich:
- Ohne (P1): mit , erfüllt (P2) und (P3), aber das Zählen bleibt bei stehen.
- Ohne (P2): mit erfüllt (P1) und (P3); das Zählen läuft im Kreis.
- Ohne (P3): mit erfüllt (P1) und (P2), enthält aber Elemente, die man von aus nie erreicht; die Teilmenge zeigt, dass (P3) verletzt ist.
Die Axiomatisierung der natürlichen Zahlen geht auf Richard Dedekind und Giuseppe Peano zurück.
Man schreibt für . Jedes ist ein Nachfolger, hat also einen Vorgänger , der nach (P1) eindeutig ist: Die Menge erfüllt die Voraussetzungen von (P3).
Rekursionssatz (ohne Beweis). Sei eine Menge, , und sei zu jedem eine Abbildung gegeben. Dann gibt es genau eine Abbildung mit und für alle .
Mit dem Rekursionssatz werden Addition, Multiplikation und Anordnung auf erklärt; wir setzen ihre Rechenregeln voraus. Von der Anordnung wird ausdrücklich benutzt: für alle , und zwischen und liegt keine natürliche Zahl, das heißt, aus folgt .
Induktionsprinzip. Sei für jedes eine Aussage. Gilt
- (Induktionsanfang) und
- (Induktionsschritt) für jedes : aus folgt ,
so gilt für alle .
Beweis. Die Menge enthält , und mit enthält sie auch . Nach (P3) ist .
Im Induktionsschritt wird nicht bewiesen, sondern vorausgesetzt; man nennt dort die Induktionsvoraussetzung. Bewiesen wird die Implikation . Das ist kein Zirkel: Niemand behauptet im Schritt, dass gilt.
Anfang an beliebiger Stelle. Sei , und sei für jede ganze Zahl eine Aussage. Gilt und folgt für jedes aus die Aussage , so gilt für alle .
Beweis. Für sei die Aussage . ist . Gilt , so gilt mit , nach Voraussetzung also , und das ist . Nach dem Induktionsprinzip gilt für alle . Jedes ist von der Form mit .
Insbesondere darf eine Induktion bei beginnen; davon machen die Sätze 1.13, 1.19, 1.20 und 1.24 Gebrauch.
Summen, Produkte, Potenzen werden rekursiv erklärt. Für ganze Zahlen und sei
entsprechend mit dem leeren Produkt als Anfang, und , für . Das schließt ein; diese Vereinbarung für ganzzahlige Exponenten bleibt im ganzen Kurs bestehen. Die Schreibweise ist eine Abkürzung für die rekursiv erklärte Summe. Der Name des Laufindex ist frei, und man darf ihn verschieben: . Regeln wie oder das allgemeine Assoziativ- und Kommutativgesetz für endliche Summen sind Induktionsbeweise, die wir nicht einzeln ausführen.
Satz 1.12. Für alle gilt .
Beweis. Induktionsanfang: Für steht links , rechts . Induktionsschritt: Gelte die Formel für ein . Dann ist
Satz 1.13 (geometrische Summe). Für jede reelle Zahl und alle gilt
Beweis. Induktion über , mit Anfang bei : Links steht , rechts . Schritt:
Woher die Formel kommt, sieht man ohne Induktion. Für ist ; in der Differenz heben sich alle Summanden bis auf den ersten und den letzten weg, . In dieser Form, ohne Division, gilt die Gleichung für jedes . Die geometrische Summe wird in Einheit 6 zur geometrischen Reihe, dem Maßstab für fast alle Konvergenzkriterien.
Satz 1.14 (starke Induktion). Sei . Gilt und folgt für jedes aus der Gültigkeit von die von , so gilt für alle .
Beweis. Sei die Aussage „ gilt für alle mit “. ist . Gilt , so nach Voraussetzung auch , also . Nach der Induktion mit Anfang gilt für alle , insbesondere .
Satz 1.15. Jede natürliche Zahl ist ein Produkt von Primzahlen (wobei eine einzelne Primzahl als Produkt mit einem Faktor zählt).
Beweis. Starke Induktion mit Anfang : ist prim. Gelte die Behauptung für alle Zahlen von bis . Ist prim, so ist nichts zu zeigen. Andernfalls hat einen Teiler mit und , also mit einem ; wegen und ist , also . Wegen ist , also . Wegen ist , und würde ergeben; also . Nach Voraussetzung sind und Produkte von Primzahlen, also auch .
Die gewöhnliche Induktion käme hier nicht voran: Über sagt die Aussage für allein nichts.
Satz 1.16 (Wohlordnung). Jede nichtleere Teilmenge besitzt ein kleinstes Element, das heißt ein mit für alle .
Beweis. Angenommen, hat kein kleinstes Element. Sei die Aussage „kein liegt in “. Anfang: Aus folgt , und läge in , so wäre wegen für alle das kleinste Element; also gilt . Schritt: Gelte . Jedes erfüllt dann , also . Läge in , so wäre es das kleinste Element; also , und mit folgt . Nach dem Induktionsprinzip gilt für alle ; wegen liegt kein in , also ist – im Widerspruch dazu, dass nicht leer ist.
Umgekehrt folgt aus der Wohlordnung zusammen mit der Vorgängereigenschaft das Induktionsprinzip (Aufgabe V2). In der Anwendung liefert die Wohlordnung eine eigene Beweisfigur: Man nimmt an, eine Aussage sei nicht für alle richtig, betrachtet das kleinste Gegenbeispiel und zeigt, dass es ein noch kleineres gäbe.
1.7 Fakultät, Binomialkoeffizienten, Binomialsatz
Zwei Fragen führen auf dieselben Zahlen. Welche Koeffizienten entstehen beim Ausmultiplizieren von ? Und wie viele -elementige Teilmengen hat eine -elementige Menge? Für ist , und hat Teilmengen mit Elementen. Wir definieren die Zahlen zunächst durch eine Formel, mit der man rechnen kann, und zeigen dann, dass sie beide Fragen beantwortet.
Definition 1.17. Für ist die Fakultät; insbesondere (leeres Produkt). Für mit ist
der Binomialkoeffizient.
Unmittelbar aus der Definition: und .
Lemma 1.18 (Pascal). Für gilt .
Beweis. Auf den Hauptnenner gebracht:
Mit dem Lemma erkennt man alle Binomialkoeffizienten ohne Rechnung als natürliche Zahlen, durch Induktion über . Für ist . Sind alle mit natürliche Zahlen, so ist für und gleich und für nach Lemma 1.18 die Summe zweier natürlicher Zahlen. Der Bruch in Definition 1.17 geht also stets auf, etwa .
Bemerkung (allgemeiner Binomialkoeffizient). Für reelles und setzt man
Für und ist das Definition 1.17, denn ; für enthält das Produkt den Faktor , also ist . Diese Fassung wird später für die Binomialreihe gebraucht.
Definition (endliche Menge). Sei . Eine Menge hat Elemente, wenn es eine Bijektion gibt; für heißt das . heißt endlich, wenn für ein genau Elemente hat.
Wir benutzen ohne Beweis die folgenden Zählregeln; jede ist eine Induktion über . Die Zahl ist durch eindeutig bestimmt. Hat genau Elemente und ist , so hat genau Elemente. Sind paarweise disjunkt mit Elementen, so hat genau Elemente. Ist bijektiv und hat genau Elemente, so auch . Jede Teilmenge einer Menge mit Elementen ist endlich und hat höchstens Elemente; hat sie genau Elemente, so ist sie die ganze Menge.
Satz 1.19 (Anzahl der Teilmengen). Eine Menge mit Elementen besitzt genau Teilmengen mit Elementen ().
Beweis. Induktion über . Für gibt es genau eine Teilmenge, die leere, und . Sei die Aussage für richtig und eine Menge mit Elementen. Für und gibt es je genau eine Teilmenge. Sei und fest. Die -elementigen Teilmengen von zerfallen in zwei Sorten. Die ohne sind die -elementigen Teilmengen von , also Stück. Die mit entstehen, indem man zu einer -elementigen Teilmenge von das Element hinzunimmt; die Zuordnung ist bijektiv mit der Umkehrung , also sind es Stück. Zusammen sind es nach Lemma 1.18 genau .
Satz 1.20 (Binomialsatz). Für reelle Zahlen , und gilt
Beweisidee. Beim Übergang von zu multipliziert man mit ; jeder Summand zerfällt in zwei, und Pascals Lemma fügt benachbarte Koeffizienten wieder zusammen.
Beweis. Induktion über . Für sind beide Seiten . Gelte die Formel für . Dann ist
In der zweiten Summe verschieben wir den Index ( wird zum neuen ):
Aus der ersten Summe lösen wir den Summanden heraus, aus der zweiten den Summanden , und fassen den Rest zusammen:
zuletzt mit Lemma 1.18 und .
Der Satz lässt sich auch zählend lesen. Beim Ausmultiplizieren von wählt man aus jedem der Faktoren entweder oder . Der Summand entsteht so oft, wie man der Faktoren für auswählen kann, nach Satz 1.19 also -mal.
Bemerkung (Allgemeinheit). Der Beweis benutzt von und nur die Rechengesetze der Addition und Multiplikation einschließlich . Der Binomialsatz gilt deshalb ebenso für komplexe Zahlen; in dieser Form wird er später für die Exponentialfunktion gebraucht. Ohne ist er falsch: Schon zeigt, was fehlt.
Folgerung 1.21. . Eine Menge mit Elementen hat also genau Teilmengen.
Beweis. Binomialsatz mit ; die zweite Aussage folgt mit Satz 1.19 und der Zählregel für disjunkte Vereinigungen.
1.8 Ungleichungen und Betrag
Die Analysis ist zu einem großen Teil die Kunst des Abschätzens: Man berechnet eine Größe nicht, man schließt sie ein. Benutzt werden folgende Anordnungsregeln für reelle Zahlen; Einheit 2 beweist sie. Dabei bedeutet , dass oder gilt.
- (O0) Für je zwei reelle Zahlen , gilt genau eine der Beziehungen , , . Aus und folgt ; aus und folgt , ebenso aus und .
- (O1) Aus folgt .
- (O2) Aus und folgt ; für dreht sich die Ungleichung um.
- (O3) Für jedes ist , und für ; insbesondere ist .
- (O4) Aus und folgt .
- (O5) (O1) und (O2) gelten auch mit statt , in (O2) dann mit beziehungsweise .
- (O6) Aus folgt ; aus folgt .
(O4) ist keine neue Regel: Nach (O1) ist und , nach (O0) also .
Definition 1.22. Der Betrag einer reellen Zahl ist , falls , und , falls .
Es gilt , nur für , und . Für gilt
und ebenso für . Alle diese Regeln beweist man durch die Fallunterscheidung oder nach (O0). Zum Beispiel die erste Äquivalenz: Ist , so ist , und heißt . Ist , so ist , und ist nach (O2) mit gleichwertig mit .
Geometrisch ist der Abstand von und auf der Zahlengeraden. Der Ausdruck aus Abschnitt 1.2 heißt also: liegt näher als bei .
Satz 1.23 (Dreiecksungleichung). Für alle gilt
Beweis. Aus und folgt mit (O4)
und das ist . Für die zweite Ungleichung schreibe man ; die erste liefert , also . Vertauscht man die Rollen, folgt . Beides zusammen ist die Behauptung.
Der Kunstgriff , das Einschieben einer Null, ist der häufigste Handgriff der Analysis. Er kommt in fast jedem Grenzwertbeweis vor.
Ausblick (Abstand). Setzt man , so gilt mit Gleichheit nur für , ferner und, nach Satz 1.23 mit , . Eine Abbildung mit diesen drei Eigenschaften heißt Metrik. Viele Sätze über Konvergenz und Stetigkeit benutzen von nur diese drei Eigenschaften.
Satz 1.24 (Bernoullische Ungleichung). Für jede reelle Zahl und alle gilt
Beweis. Induktion über . Für steht auf beiden Seiten . Gelte die Ungleichung für . Wegen darf man sie nach (O2) mit multiplizieren:
zuletzt wegen ((O2) und (O3)).
Die Voraussetzung geht im Beweis an genau einer Stelle ein: beim Multiplizieren mit . Sie ist eine Bedingung dieses Beweises, nicht die Grenze der Aussage. Für gilt die Ungleichung ebenfalls: Für ist sie eine Gleichung; für ist , also , während ist. Erst für kann sie scheitern, wie (G6) zeigt.
Satz 1.25. Für alle reellen Zahlen , gilt , mit Gleichheit genau für .
Beweis. nach (O3), und der Ausdruck ist genau für null.
Für ist das die Ungleichung zwischen geometrischem und arithmetischem Mittel, ; die Wurzel steht uns erst ab Einheit 2 zur Verfügung.
1.9 Relationen
Die Zeichen , und haben eine gemeinsame Form: Sie setzen je zwei Elemente einer Menge in Beziehung. Zwei Sorten solcher Beziehungen durchziehen die ganze Mathematik.
Definition 1.26. Eine Relation auf einer Menge ist eine Teilmenge ; statt schreibt man , bei Ordnungen meist . Die Relation heißt
- reflexiv, wenn für alle ,
- symmetrisch, wenn aus stets folgt,
- antisymmetrisch, wenn aus und stets folgt,
- transitiv, wenn aus und stets folgt.
Eine reflexive, symmetrische und transitive Relation heißt Äquivalenzrelation. Eine reflexive, antisymmetrische und transitive Relation heißt Ordnung; sie heißt total, wenn je zwei Elemente vergleichbar sind, also stets oder gilt.
Beispiele. (a) auf ist eine totale Ordnung. (b) auf ist eine Ordnung; sie ist nicht total, sobald zwei verschiedene Elemente , hat, denn und sind nicht vergleichbar. (c) Für festes ist „, wenn “ eine Äquivalenzrelation auf . (d) Jede Abbildung liefert eine Äquivalenzrelation auf : , wenn .
Bemerkung (Ordnungen). Zu einer Ordnung gehört die strikte Ordnung , die „ und “ bedeutet. In einer geordneten Menge heißt obere Schranke von , wenn für alle gilt, und Supremum von , wenn obere Schranke ist und für jede obere Schranke von gilt. Wegen der Antisymmetrie gibt es höchstens ein Supremum. Ob jede nichtleere, nach oben beschränkte Teilmenge ein Supremum hat, ist die Frage, die von unterscheidet (Einheit 2).
Äquivalenzrelationen beschreiben „gleich unter einem Gesichtspunkt“. Die Paare und sind verschieden, als Brüche sollen sie gleich sein; die ganzen Zahlen und sind verschieden, haben aber bei Division durch denselben Rest. Man will dann mit den Gesamtheiten gleichwertiger Objekte rechnen wie mit einzelnen Objekten. Dafür muss feststehen, dass diese Gesamtheiten die Menge sauber zerlegen; das leistet Satz 1.28.
Definition 1.27. Sei eine Äquivalenzrelation auf . Die Äquivalenzklasse von ist ; jedes Element einer Klasse heißt Repräsentant. Die Menge aller Klassen heißt Quotientenmenge .
Satz 1.28 (Klasseneinteilung). Sei eine Äquivalenzrelation auf . Dann gilt:
- für jedes ; insbesondere ist keine Klasse leer, und ist die Vereinigung aller Klassen.
- genau dann, wenn .
- Zwei Klassen sind entweder gleich oder disjunkt.
Beweis. (1) ist die Reflexivität.
(2) Ist , so ist , also . Sei umgekehrt und . Dann ist und , wegen der Transitivität also , das heißt . Damit ist . Wegen der Symmetrie gilt auch , und dasselbe Argument liefert .
(3) Ist , so ist und , nach (2) also und , folglich .
Alle drei Eigenschaften gehen ein: die Reflexivität in (1) und in der ersten Richtung von (2), Symmetrie und Transitivität in der zweiten Richtung von (2); (3) folgt aus (2). Dass man auf die Transitivität nicht verzichten kann, zeigt (G8). Umgekehrt definiert jede Zerlegung von in nichtleere, paarweise disjunkte Teilmengen eine Äquivalenzrelation: „, wenn beide in derselben Teilmenge liegen“.
Bemerkung (Wohldefiniertheit). Wer eine Abbildung auf durch eine Vorschrift an Repräsentanten erklärt, muss zeigen, dass das Ergebnis nicht von der Wahl des Repräsentanten abhängt. In Beispiel (c) ist zulässig: Aus und folgt, dass auch teilt. Die Vorschrift „“ ist dagegen keine Abbildung nach .
Auf diese Weise entstehen die Zahlbereiche. Die rationalen Zahlen gewinnt man als Klassen von Paaren unter „, wenn “ (Aufgabe B5); ein Bruch ist eine solche Klasse, und ist die Gleichheit zweier Klassen. Nach demselben Verfahren, mit anderen Objekten, werden später die reellen Zahlen konstruiert: Dort fasst man Folgen rationaler Zahlen, deren Glieder einander beliebig nahe kommen, zu Klassen zusammen.
1.10 Gegenbeispiele: Was geschieht, wenn eine Voraussetzung fehlt
(G1) Induktionsschritt ohne Anfang. Sei die Aussage „“. Der Induktionsschritt gelingt: Aus folgt durch Addition von sofort . Trotzdem ist für jedes falsch. Der Schritt allein beweist nichts.
(G2) Induktionsanfang ohne Schritt. Die Aussage der Leitfrage, „ ist prim“, stimmt für bis und scheitert bei . Ein Induktionsschritt müsste aus der Primalität von die von herleiten; das ist unmöglich, denn ist prim und nicht. Bestätigte Fälle ersetzen keinen Schritt, gleichgültig wie viele es sind.
(G3) Ein Schritt, der nicht für jedes trägt. Behauptung: „In jeder Gruppe von Personen haben alle am selben Tag Geburtstag.“ Scheinbeweis: Für ist das richtig. Gelte es für , und seien Personen gegeben. Die ersten haben nach Voraussetzung denselben Geburtstag, die letzten ebenfalls; weil sich beide Gruppen überschneiden, haben alle denselben.
Der Fehler: Die Gruppen und überschneiden sich nur für . Für sind es und , ohne gemeinsame Person. Der Schritt von auf ist nicht bewiesen, und an ihm hängt alles. Ein Induktionsschritt muss für jedes ab dem Anfang gelten.
(G4) Vertauschte Quantoren. ist wahr, falsch (Abschnitt 1.2).
(G5) Bild eines Durchschnitts. Für , , , ist , aber . In Satz 1.11 (3) gilt Gleichheit für alle , genau dann, wenn injektiv ist (Aufgabe B4).
(G6) Bernoulli ohne Voraussetzung. Für und ist , aber . Die Ungleichung ist verletzt. Im Beweis scheitert der Schritt, in dem mit der negativen Zahl multipliziert wird.
(G7) Einseitige Verkettung. In Satz 1.10 genügt eine der beiden Gleichungen nicht. Für , , und konstant ist , aber ist nicht surjektiv und nicht injektiv.
(G8) Ohne Transitivität keine Klassen. Auf sei , wenn . Die Relation ist reflexiv und symmetrisch, aber nicht transitiv: und , aber nicht . Die Mengen und sind verschieden und nicht disjunkt (beide enthalten ); Satz 1.28 (3) gilt nicht. „Ungefähr gleich“ mit fester Toleranz ist keine Äquivalenzrelation: Kleine Abweichungen addieren sich. Die Analysis arbeitet deshalb nicht mit einer festen Toleranz, sondern mit Aussagen, die für jede vorgegebene Toleranz gelten; das ist die Quantorenform aus Abschnitt 1.2.
1.11 Durchgerechnete Beispiele
Beispiel 1 (Verneinen). Eine Funktion heißt beschränkt, wenn
Unbeschränkt heißt nach Regel 1.3: . Für weist man das so nach: Sei beliebig. Wähle . Dann ist und , nach (O5) also , und ; zusammen . Man beachte die Form: Das wird vorgegeben, das wird in Abhängigkeit von gewählt.
Beispiel 2 (Summe mit zwei Beweisen). Behauptung: für alle .
Erster Beweis (Induktion). Für : . Schritt:
Zweiter Beweis (Teleskopsumme). Wegen heben sich benachbarte Summanden weg:
Die Induktion bestätigt eine Formel, die man schon kennt. Der zweite Beweis zeigt, woher sie kommt; dasselbe Wegheben trug die Herleitung der geometrischen Summe nach Satz 1.13.
Beispiel 3 (Bernoulli als Werkzeug). Sei . Wir zeigen, dass beliebig klein wird, mit einer ausdrücklichen Schranke. Schreibe mit . Nach Bernoulli ist für , mit (O6) also
Für ist , also . Die Schranke ist grob (tatsächlich fällt viel schneller), aber sie genügt für den Schluss, auf den es bei den Folgen ankommt.
Beispiel 4 (Eine Ungleichung ab einer Stelle). Behauptung: für alle . Anfang: . Schritt: Sei und . Nach (O5) ist , und es bleibt zu zeigen, ausmultipliziert . Für ist (Multiplikation von mit , (O2)), also , das Letzte wegen . Mit (O0) folgt .
Was trägt wo? Die Rechnung des Schritts ist für jedes richtig; bei versagt sie, denn . Die Behauptung selbst gilt für (), ist aber für falsch, zuletzt . Der wahre Fall nützt nichts, weil der Schritt von auf nicht trägt; der Schritt ab nützt erst, wenn ein wahrer Fall erreicht ist, und das ist . Beides wird gebraucht.
1.12 Ausblick
- Die Quantorenfolge ist das Gerüst der Einheit über Folgen und kehrt als bei der Stetigkeit wieder. Der Unterschied zwischen Stetigkeit und gleichmäßiger Stetigkeit sowie zwischen punktweiser und gleichmäßiger Konvergenz ist jeweils nur eine vertauschte Quantorenreihenfolge, wie in (G4).
- Die geometrische Summe und die Bernoullische Ungleichung tragen die Konvergenzkriterien für Reihen und die Untersuchung der Folge , aus der die Zahl entsteht (vorbereitet in Aufgabe V4).
- Der Binomialsatz liefert die Funktionalgleichung der Exponentialfunktion.
- Die Dreiecksungleichung steht in jedem Grenzwertbeweis; aus ihr wird der Begriff der Metrik.
- Äquivalenzklassen liefern aus und aus den rationalen Cauchy-Folgen, später jede Quotientenbildung der Algebra und Topologie.
- Die Anordnungsregeln (O0) bis (O6), die hier benutzt wurden, und die Existenz von Wurzeln werden bei der Konstruktion der reellen Zahlen bewiesen. Dort zeigt sich auch, was von unterscheidet.
Zum Vergleich. Der Stoff dieser Einheit gehört zum Anfang jeder Analysis-Vorlesung. Parallel lesen kann man O. Forster, Analysis 1, 12. Auflage (2016), § 1 (vollständige Induktion, Summen- und Produktzeichen, Fakultät, Binomialkoeffizienten, Binomialsatz, geometrische Summe) und § 3 (Peano-Axiome, Betrag und Dreiecksungleichung, Bernoullische Ungleichung). Satz 1.19 wird dort ebenso durch Induktion über die Elementzahl bewiesen (§ 1, Satz 4, mit der Bemerkung über die Ganzzahligkeit), Satz 1.24 mit demselben Induktionsschritt (§ 3, Satz 2); dass für beliebig klein wird, folgt dort ebenfalls aus der Bernoullischen Ungleichung (§ 3, Satz 3). Die Fermat-Zahlen der Leitfrage mit dem Teiler von bespricht Forster in einer Bemerkung zu (1.7). Aufgabe R1 und Beispiel 2 behandeln Aussagen, die bei Forster und in O. Forster und R. Wessoly, Übungsbuch zur Analysis 1, 5. Auflage (2011), Übungsaufgaben sind: die Summenformel in R1 (Forster, Aufgabe 1.3; Übungsbuch, Aufgabe 1 O) und die Summe in Beispiel 2 (Forster, Aufgabe 1.6 und Beispiel (4.9); Übungsbuch, Aufgabe 1 L). Satz 1.25 ist ein Teil der Ungleichungskette in Aufgabe 3 G des Übungsbuchs.
Aufgaben und Lösungen zu dieser Einheit: ../aufgaben/01-aufgaben-und-loesungen.md.