F.R. GRANARIA

Zur interaktiven Werkstatt · PDF

Kapiteltext · Aufgaben und Lösungen

Einheit 1 – Sprache und Beweise

Vierte Fassung vom 18. November 2026.

Leitfrage

Man bilde die Zahlen Fn=22n+1F_n=2^{2^n}+1 für n=0,1,2,…n=0,1,2,\dots Die ersten fünf sind

F0=3,F1=5,F2=17,F3=257,F4=65537,F_0=3,\quad F_1=5,\quad F_2=17,\quad F_3=257,\quad F_4=65537,

und alle fünf sind Primzahlen. Pierre de Fermat vermutete, dass alle Zahlen FnF_n prim sind. Die Vermutung ist falsch; Leonhard Euler fand den Teiler:

F5=4294967297=641⋅6700417.F_5=4294967297=641\cdot 6700417 .

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. N={1,2,3,… }\mathbb{N}=\{1,2,3,\dots\} sind die natürlichen Zahlen, N0={0,1,2,… }\mathbb{N}_0=\{0,1,2,\dots\}; Z\mathbb{Z}, Q\mathbb{Q} und R\mathbb{R} bezeichnen die ganzen, rationalen und reellen Zahlen. Für a,b∈Za,b\in\mathbb{Z} heißt aa ein Teiler von bb, geschrieben a∣ba\mid b, wenn b=acb=ac mit einem c∈Zc\in\mathbb{Z} gilt. Eine ganze Zahl nn heißt gerade, wenn 2∣n2\mid n, sonst ungerade; die ungeraden Zahlen sind genau die Zahlen 2k+12k+1 mit k∈Zk\in\mathbb{Z}. Eine Primzahl ist eine natürliche Zahl p≥2p\ge 2, deren einzige Teiler in N\mathbb{N} die Zahlen 11 und pp sind. Für reelle a≤ba\le b sind [a,b]={x∈R: a≤x≤b}[a,b]=\{x\in\mathbb{R}:\ a\le x\le b\} und (a,b)={x∈R: a<x<b}(a,b)=\{x\in\mathbb{R}:\ a<x<b\} das abgeschlossene und das offene Intervall von aa bis bb; entsprechend [a,b)[a,b) und (a,b](a,b], ferner [a,∞)={x∈R: x≥a}[a,\infty)=\{x\in\mathbb{R}:\ x\ge a\} und (a,∞)={x∈R: x>a}(a,\infty)=\{x\in\mathbb{R}:\ x>a\}. Das Zeichen ∞\infty 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:

  1. die Peano-Axiome (Abschnitt 1.6) und, ohne Ausführung, der daraus folgende Aufbau von N\mathbb{N}, N0\mathbb{N}_0 und Z\mathbb{Z} mit Addition, Multiplikation und Anordnung; dazu gehören der Rekursionssatz, die Nullteilerfreiheit von Z\mathbb{Z} (aus ab=0ab=0 folgt a=0a=0 oder b=0b=0) und die Division mit Rest (insbesondere ist jede ganze Zahl entweder gerade oder ungerade);
  2. das Rechnen mit Brüchen in Q\mathbb{Q}; wie Q\mathbb{Q} aus Z\mathbb{Z} entsteht, zeigen Abschnitt 1.9 und Aufgabe B5;
  3. dass R\mathbb{R} ein angeordneter Körper ist, der Q\mathbb{Q} enthält; benutzt werden nur die in Abschnitt 1.8 aufgezählten Anordnungsregeln, und jede Stelle nennt die Regel, die eingeht;
  4. 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 R\mathbb{R} aus Q\mathbb{Q} 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.

„77 ist eine Primzahl“ ist eine Aussage (wahr), „4>94>9“ ebenfalls (falsch). Keine Aussage ist „x>3x>3“: Der Wahrheitswert hängt von xx ab. Ein solcher Ausdruck heißt Aussageform; er wird zur Aussage, sobald man für xx etwas einsetzt oder xx durch einen Quantor bindet (Abschnitt 1.2).

Aus Aussagen AA und BB entstehen neue:

Zeichen gelesen wahr genau dann, wenn
¬A\neg A nicht AA AA falsch ist
A∧BA \wedge B AA und BB beide wahr sind
A∨BA \vee B AA oder BB mindestens eine wahr ist
A⇒BA \Rightarrow B aus AA folgt BB AA falsch oder BB wahr ist
A  ⟺  BA \iff B AA genau dann, wenn BB beide denselben Wahrheitswert haben

Zwei Punkte weichen vom Alltagsgebrauch ab. Erstens ist das mathematische „oder“ nicht ausschließend: A∨BA\vee B ist auch wahr, wenn beide gelten. Zweitens ist A⇒BA\Rightarrow B wahr, sobald AA falsch ist. Die Implikation behauptet nichts über den Fall, in dem die Voraussetzung nicht eintritt. „Wenn 4>94>9, dann ist 1=21=2“ ist eine wahre Aussage.

Der Grund für diese Festlegung liegt im Gebrauch. Der Satz „Für jedes n∈Nn\in\mathbb{N}: Ist nn durch 44 teilbar, so ist nn gerade“ soll wahr sein. Er umfasst auch n=2n=2 und n=3n=3, 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 AA, BB gilt:

  1. ¬(A∧B)  ⟺  (¬A)∨(¬B)\neg(A\wedge B) \iff (\neg A)\vee(\neg B) und ¬(A∨B)  ⟺  (¬A)∧(¬B)\neg(A\vee B) \iff (\neg A)\wedge(\neg B) (Regeln von De Morgan),
  2. (A⇒B)  ⟺  (¬B⇒¬A)(A\Rightarrow B) \iff (\neg B\Rightarrow \neg A) (Kontraposition),
  3. ¬(A⇒B)  ⟺  A∧¬B\neg(A\Rightarrow B) \iff A\wedge \neg B.

Beweis. Jede Seite hängt nur von den Wahrheitswerten von AA und BB ab; es gibt vier Fälle. Für (2) und (3):

AA BB A⇒BA\Rightarrow B ¬B⇒¬A\neg B\Rightarrow\neg A A∧¬BA\wedge\neg B
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. □\square

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 AA, dann BB“ ist nicht „wenn AA, dann nicht BB“.

Vorsicht bei der Umkehrung: B⇒AB\Rightarrow A ist etwas anderes als A⇒BA\Rightarrow B. Aus „nn ist durch 44 teilbar“ folgt „nn ist gerade“; die Umkehrung ist falsch, wie n=6n=6 zeigt.

1.2 Quantoren

Ist A(x)A(x) eine Aussageform und MM eine Menge, so bedeutet

Regel 1.3 (Verneinung).

¬(∀x∈M: A(x))  ⟺  ∃x∈M: ¬A(x),¬(∃x∈M: A(x))  ⟺  ∀x∈M: ¬A(x).\begin{aligned}\neg\bigl(\forall x\in M:\ A(x)\bigr) &\iff \exists x\in M:\ \neg A(x),\\ \neg\bigl(\exists x\in M:\ A(x)\bigr) &\iff \forall x\in M:\ \neg A(x).\end{aligned}

Regel 1.3 wird nicht aus Satz 1.2 bewiesen; sie gibt wieder, was die Quantoren bedeuten. Für eine endliche Menge M={x1,…,xr}M=\{x_1,\dots,x_r\} ist ∀x∈M: A(x)\forall x\in M:\ A(x) dasselbe wie A(x1)∧⋯∧A(xr)A(x_1)\wedge\dots\wedge A(x_r), 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 ∀ε>0\forall\varepsilon>0 oder ∃n≥N\exists n\ge N bedeuten ∀ε∈{x∈R: x>0}\forall\varepsilon\in\{x\in\mathbb{R}:\ x>0\} beziehungsweise ∃n∈{k∈N: k≥N}\exists n\in\{k\in\mathbb{N}:\ k\ge N\}. Beim Verneinen wechselt nur der Quantor, die Einschränkung bleibt stehen: Die Verneinung von ∀ε>0: A(ε)\forall\varepsilon>0:\ A(\varepsilon) ist ∃ε>0: ¬A(ε)\exists\varepsilon>0:\ \neg A(\varepsilon), nicht ∃ε≤0: ¬A(ε)\exists\varepsilon\le 0:\ \neg A(\varepsilon).

Beim Verneinen wird also jeder Quantor umgedreht und die Aussage am Ende verneint. Die Leitfrage ist ein Fall davon: „Für alle nn ist FnF_n prim“ wird durch ein Gegenbeispiel widerlegt, nämlich n=5n=5.

Die Reihenfolge verschiedener Quantoren ist nicht vertauschbar. Man vergleiche

(a)∀x∈R ∃y∈R: y>x,(b)∃y∈R ∀x∈R: y>x.\text{(a)}\quad \forall x\in\mathbb{R}\ \exists y\in\mathbb{R}:\ y>x, \qquad\qquad \text{(b)}\quad \exists y\in\mathbb{R}\ \forall x\in\mathbb{R}:\ y>x .

(a) ist wahr: Zu gegebenem xx wähle man y=x+1y=x+1. Das yy darf von xx abhängen. (b) ist falsch: Es müsste eine einzige Zahl yy geben, die größer ist als jede reelle Zahl, also auch größer als yy selbst. Bei (a) wird yy nach xx gewählt, bei (b) vor xx.

Dieser Unterschied trägt später ganze Begriffe. Ein Vorgriff auf Einheit 4: Eine Folge (an)(a_n) reeller Zahlen konvergiert gegen aa, wenn

∀ε>0  ∃N∈N  ∀n≥N: ∣an−a∣<ε.\forall \varepsilon>0\ \ \exists N\in\mathbb{N}\ \ \forall n\ge N:\ |a_n-a|<\varepsilon .

Nach Regel 1.3 heißt „(an)(a_n) konvergiert nicht gegen aa“:

∃ε>0  ∀N∈N  ∃n≥N: ∣an−a∣≥ε.\exists \varepsilon>0\ \ \forall N\in\mathbb{N}\ \ \exists n\ge N:\ |a_n-a|\ge\varepsilon .

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 A⇒BA\Rightarrow B. Drei Formen kommen immer wieder vor.

Direkter Beweis. Man setzt AA voraus und leitet BB her.

Beispiel. Ist n∈Zn\in\mathbb{Z} ungerade, so ist n2n^2 ungerade. Denn n=2k+1n=2k+1 mit einem k∈Zk\in\mathbb{Z}, also n2=4k2+4k+1=2(2k2+2k)+1n^2=4k^2+4k+1=2(2k^2+2k)+1.

Beweis durch Kontraposition. Statt A⇒BA\Rightarrow B zeigt man ¬B⇒¬A\neg B\Rightarrow\neg A; nach Satz 1.2 ist das dieselbe Aussage.

Beispiel. Ist n2n^2 gerade, so ist nn gerade. Direkt kommt man schlecht voran, weil man aus n2=2mn^2=2m nicht ohne Weiteres auf nn schließen kann. Die Kontraposition lautet „ist nn ungerade, so ist n2n^2 ungerade“, und das ist das vorige Beispiel.

Diese kleine Aussage wird in Einheit 2 gebraucht, im Beweis, dass 2\sqrt2 nicht rational ist: Aus einer Darstellung p2=2q2p^2=2q^2 mit ganzen Zahlen pp, qq folgt, dass p2p^2 gerade ist, nach dem Beispiel also auch pp.

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, r>0r>0 wäre die kleinste. Dann ist r/2r/2 ebenfalls rational und positiv, aber r/2<rr/2<r, denn r−r2=r2>0r-\frac r2=\frac r2>0 – ein Widerspruch zur Wahl von rr.

Eine Äquivalenz A  ⟺  BA\iff B beweist man in zwei getrennten Teilen, A⇒BA\Rightarrow B und B⇒AB\Rightarrow A. 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; x∈Mx\in M heißt, xx ist Element von MM. Eine Menge ist durch ihre Elemente bestimmt: M=NM=N gilt genau dann, wenn beide dieselben Elemente haben. Die leere Menge ∅\emptyset hat kein Element.

Bemerkung (Grenzen des naiven Mengenbegriffs). Nicht jede Eigenschaft definiert eine Menge. Wäre R={x: x∉x}R=\{x:\ x\notin x\} eine Menge, so gälte R∈R  ⟺  R∉RR\in R\iff R\notin R (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, {x∈M: A(x)}\{x\in M:\ A(x)\}, oder mit den Operationen der folgenden Definition gebildet.

Definition 1.4. Für Mengen AA, BB heißt

Von geordneten Paaren wird nur eine Eigenschaft gebraucht: (a,b)=(a′,b′)(a,b)=(a',b') gilt genau dann, wenn a=a′a=a' und b=b′b=b'.

Die Gleichheit zweier Mengen beweist man fast immer über zwei Inklusionen: A=BA=B genau dann, wenn A⊆BA\subseteq B und B⊆AB\subseteq A.

Satz 1.5 (De Morgan für Mengen). Für Teilmengen AA, BB einer Menge XX gilt

X∖(A∪B)=(X∖A)∩(X∖B),X∖(A∩B)=(X∖A)∪(X∖B).X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B), \qquad X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B).

Beweis. Für x∈Xx\in X gilt: x∈X∖(A∪B)x\in X\setminus(A\cup B)   ⟺  \iff ¬(x∈A∨x∈B)\neg(x\in A\vee x\in B)   ⟺  \iff x∉A∧x∉Bx\notin A\wedge x\notin B   ⟺  \iff x∈(X∖A)∩(X∖B)x\in(X\setminus A)\cap(X\setminus B). Der mittlere Schritt ist Satz 1.2 (1), angewandt auf die Aussagen „x∈Ax\in A“ und „x∈Bx\in B“. Die zweite Gleichung folgt ebenso aus der anderen De-Morgan-Regel. □\square

Die Mengenregeln sind also die Regeln der Logik in anderer Schreibweise: ∪\cup entspricht „oder“, ∩\cap entspricht „und“, das Komplement der Verneinung.

Vereinigung und Durchschnitt bildet man auch über beliebig viele Mengen. Eine Familie (Ai)i∈I(A_i)_{i\in I} von Teilmengen einer Menge XX ordnet jedem ii aus der Indexmenge II eine Teilmenge Ai⊆XA_i\subseteq X zu; sie ist eine Abbildung I→P(X)I\to\mathcal{P}(X) im Sinn von Abschnitt 1.5. Allgemein heißt jede Abbildung mit Definitionsbereich II eine Familie; eine Folge ist später eine Familie mit I=NI=\mathbb{N}. Man setzt

⋃i∈IAi={x∈X: ∃i∈I: x∈Ai},⋂i∈IAi={x∈X: ∀i∈I: x∈Ai}.\bigcup_{i\in I}A_i=\{x\in X:\ \exists i\in I:\ x\in A_i\},\qquad \bigcap_{i\in I}A_i=\{x\in X:\ \forall i\in I:\ x\in A_i\}.

Beides sind Aussonderungen aus XX. Für I=∅I=\emptyset ist die Vereinigung leer und der Durchschnitt gleich XX. Ohne die Grundmenge XX wäre der leere Durchschnitt die Gesamtheit aller Dinge, und die ist keine Menge. Die Regeln von De Morgan gelten auch für Familien,

X∖⋃i∈IAi=⋂i∈I(X∖Ai),X∖⋂i∈IAi=⋃i∈I(X∖Ai),X\setminus\bigcup_{i\in I}A_i=\bigcap_{i\in I}(X\setminus A_i),\qquad X\setminus\bigcap_{i\in I}A_i=\bigcup_{i\in I}(X\setminus A_i),

mit demselben Beweis wie Satz 1.5; an die Stelle von Satz 1.2 (1) tritt Regel 1.3.

Beispiel. Für An={x∈R: 0<x<1/n}A_n=\{x\in\mathbb{R}:\ 0<x<1/n\} ist ⋂n∈NAn=∅\bigcap_{n\in\mathbb{N}}A_n=\emptyset, obwohl jede einzelne Menge AnA_n unendlich viele Elemente hat und A1⊇A2⊇A3⊇…A_1\supseteq A_2\supseteq A_3\supseteq\dots gilt. Der Nachweis, dass kein x>0x>0 in allen AnA_n liegt, braucht eine Eigenschaft der reellen Zahlen, die erst Einheit 2 bereitstellt (zu jedem x>0x>0 gibt es ein nn mit 1/n<x1/n<x).

1.5 Abbildungen

Definition 1.6. Eine Abbildung f ⁣:X→Yf\colon X\to Y ordnet jedem Element x∈Xx\in X genau ein Element f(x)∈Yf(x)\in Y zu. XX heißt Definitionsbereich, YY Zielmenge. Zwei Abbildungen sind gleich, wenn sie denselben Definitionsbereich, dieselbe Zielmenge und für jedes xx denselben Wert haben.

Zur Abbildung gehören also drei Angaben, nicht nur die Rechenvorschrift. x↦x2x\mapsto x^2 als Abbildung R→R\mathbb{R}\to\mathbb{R} und als Abbildung [0,∞)→[0,∞)[0,\infty)\to[0,\infty) sind verschiedene Abbildungen mit verschiedenen Eigenschaften, wie sich gleich zeigt.

Bemerkung (Abbildung als Menge). Präzise ist eine Abbildung f ⁣:X→Yf\colon X\to Y durch ihren Graphen Γf={(x,f(x)): x∈X}⊆X×Y\Gamma_f=\{(x,f(x)):\ x\in X\}\subseteq X\times Y zusammen mit XX und YY gegeben. Eine Teilmenge Γ⊆X×Y\Gamma\subseteq X\times Y ist genau dann Graph einer Abbildung, wenn es zu jedem x∈Xx\in X genau ein y∈Yy\in Y mit (x,y)∈Γ(x,y)\in\Gamma gibt. Daraus ergeben sich die Randfälle: Für jede Menge YY gibt es genau eine Abbildung ∅→Y\emptyset\to Y, die leere Abbildung mit dem Graphen ∅\emptyset. Ist X≠∅X\ne\emptyset, so gibt es keine Abbildung X→∅X\to\emptyset.

Definition 1.7. Für f ⁣:X→Yf\colon X\to Y, A⊆XA\subseteq X und B⊆YB\subseteq Y heißt

f(A)={f(x): x∈A}⊆Ydas Bild von A,f(A)=\{f(x):\ x\in A\}\subseteq Y \quad\text{das \emph{Bild} von } A,

f−1(B)={x∈X: f(x)∈B}⊆Xdas Urbild von B.f^{-1}(B)=\{x\in X:\ f(x)\in B\}\subseteq X \quad\text{das \emph{Urbild} von } B.

Das Urbild ist für jede Abbildung erklärt; die Schreibweise f−1(B)f^{-1}(B) setzt nicht voraus, dass es eine Umkehrabbildung gibt.

Zu einer Abbildung f ⁣:X→Yf\colon X\to Y und einem y∈Yy\in Y gehört die Gleichung f(x)=yf(x)=y. Zwei Fragen stellen sich: Hat sie für jedes yy eine Lösung? Hat sie für jedes yy höchstens eine? Die folgenden Begriffe geben diesen Fragen Namen.

Definition 1.8. Eine Abbildung f ⁣:X→Yf\colon X\to Y heißt

Surjektiv heißt also: Die Gleichung f(x)=yf(x)=y ist für jedes yy lösbar. Injektiv heißt: Sie hat für jedes yy höchstens eine Lösung. Bijektiv heißt: genau eine.

Beispiel. f ⁣:R→Rf\colon\mathbb{R}\to\mathbb{R}, f(x)=x2f(x)=x^2, ist nicht injektiv (f(−1)=f(1)f(-1)=f(1)) und nicht surjektiv (−1-1 wird nicht angenommen). Dieselbe Vorschrift als Abbildung [0,∞)→R[0,\infty)\to\mathbb{R} ist injektiv, aber nicht surjektiv. Als Abbildung [0,∞)→[0,∞)[0,\infty)\to[0,\infty) ist sie injektiv; dass sie auch surjektiv ist, heißt: Jede Zahl y≥0y\ge 0 hat eine Quadratwurzel. Das ist keine Formalität, sondern ein Satz über die reellen Zahlen (Einheit 2; in Q\mathbb{Q} ist er falsch).

Definition 1.9. Für f ⁣:X→Yf\colon X\to Y und g ⁣:Y→Zg\colon Y\to Z ist die Verkettung g∘f ⁣:X→Zg\circ f\colon X\to Z durch (g∘f)(x)=g(f(x))(g\circ f)(x)=g(f(x)) erklärt. Die identische Abbildung id⁡X ⁣:X→X\operatorname{id}_X\colon X\to X ist x↦xx\mapsto x.

Die Verkettung ist assoziativ, h∘(g∘f)=(h∘g)∘fh\circ(g\circ f)=(h\circ g)\circ f, aber nicht kommutativ: Für f(x)=x+1f(x)=x+1 und g(x)=x2g(x)=x^2 auf R\mathbb{R} ist (g∘f)(x)=(x+1)2(g\circ f)(x)=(x+1)^2 und (f∘g)(x)=x2+1(f\circ g)(x)=x^2+1.

Satz 1.10 (Umkehrabbildung). Eine Abbildung f ⁣:X→Yf\colon X\to Y ist genau dann bijektiv, wenn es eine Abbildung g ⁣:Y→Xg\colon Y\to X gibt mit

g∘f=id⁡Xundf∘g=id⁡Y.g\circ f=\operatorname{id}_X \quad\text{und}\quad f\circ g=\operatorname{id}_Y .

In diesem Fall ist gg eindeutig bestimmt; man nennt gg die Umkehrabbildung und schreibt f−1f^{-1}.

Beweisidee. Injektiv heißt „höchstens ein Urbildpunkt“, surjektiv „mindestens einer“; zusammen gibt es zu jedem yy genau ein xx, und dieses xx ist g(y)g(y).

Beweis. „⇒\Rightarrow“: Sei ff bijektiv. Zu y∈Yy\in Y gibt es wegen der Surjektivität ein xx mit f(x)=yf(x)=y und wegen der Injektivität nur eines. Setze g(y)=xg(y)=x. Dann ist f(g(y))=yf(g(y))=y nach Konstruktion, und g(f(x))g(f(x)) ist das eindeutige Element, das auf f(x)f(x) abgebildet wird, also xx.

„⇐\Leftarrow“: Sei gg wie angegeben. Aus f(x)=f(x′)f(x)=f(x') folgt x=g(f(x))=g(f(x′))=x′x=g(f(x))=g(f(x'))=x'; also ist ff injektiv. Für y∈Yy\in Y ist y=f(g(y))y=f(g(y)); also ist ff surjektiv.

Eindeutigkeit: Erfüllt auch hh beide Gleichungen, so ist h=h∘id⁡Y=h∘(f∘g)=(h∘f)∘g=id⁡X∘g=gh=h\circ\operatorname{id}_Y=h\circ(f\circ g)=(h\circ f)\circ g=\operatorname{id}_X\circ g=g. □\square

Satz 1.11 (Bild, Urbild und Mengenoperationen). Für f ⁣:X→Yf\colon X\to Y, A1,A2⊆XA_1,A_2\subseteq X und B,B1,B2⊆YB,B_1,B_2\subseteq Y gilt:

  1. f−1(B1∪B2)=f−1(B1)∪f−1(B2)f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2) und f−1(B1∩B2)=f−1(B1)∩f−1(B2)f^{-1}(B_1\cap B_2)=f^{-1}(B_1)\cap f^{-1}(B_2),
  2. f(A1∪A2)=f(A1)∪f(A2)f(A_1\cup A_2)=f(A_1)\cup f(A_2),
  3. f(A1∩A2)⊆f(A1)∩f(A2)f(A_1\cap A_2)\subseteq f(A_1)\cap f(A_2),
  4. f−1(Y∖B)=X∖f−1(B)f^{-1}(Y\setminus B)=X\setminus f^{-1}(B),
  5. Regel (1) gilt ebenso für Vereinigung und Durchschnitt beliebiger Familien, Regel (2) für die Vereinigung beliebiger Familien.

Beweis. (1) x∈f−1(B1∩B2)x\in f^{-1}(B_1\cap B_2)   ⟺  \iff f(x)∈B1∧f(x)∈B2f(x)\in B_1\wedge f(x)\in B_2   ⟺  \iff x∈f−1(B1)∩f−1(B2)x\in f^{-1}(B_1)\cap f^{-1}(B_2); mit „oder“ ebenso.

(2) y∈f(A1∪A2)y\in f(A_1\cup A_2)   ⟺  \iff es gibt x∈A1x\in A_1 oder x∈A2x\in A_2 mit f(x)=yf(x)=y   ⟺  \iff y∈f(A1)∪f(A2)y\in f(A_1)\cup f(A_2).

(3) Ist y=f(x)y=f(x) mit x∈A1∩A2x\in A_1\cap A_2, so liegt yy in f(A1)f(A_1) und in f(A2)f(A_2).

(4) x∈f−1(Y∖B)x\in f^{-1}(Y\setminus B)   ⟺  \iff f(x)∉Bf(x)\notin B   ⟺  \iff x∉f−1(B)x\notin f^{-1}(B).

(5) Für eine Familie (Bi)i∈I(B_i)_{i\in I} ist x∈f−1(⋃iBi)x\in f^{-1}\bigl(\bigcup_i B_i\bigr)   ⟺  \iff ∃i: f(x)∈Bi\exists i:\ f(x)\in B_i   ⟺  \iff x∈⋃if−1(Bi)x\in\bigcup_i f^{-1}(B_i); mit „∀i\forall i“ ebenso, und für das Bild einer Vereinigung wie in (2). □\square

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 f ⁣:R→Rf\colon\mathbb{R}\to\mathbb{R} 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 X≠∅X\ne\emptyset ist ff genau dann injektiv, wenn es ein g ⁣:Y→Xg\colon Y\to X mit g∘f=id⁡Xg\circ f=\operatorname{id}_X gibt (Linksinverse). Gibt es ein h ⁣:Y→Xh\colon Y\to X mit f∘h=id⁡Yf\circ h=\operatorname{id}_Y (Rechtsinverse), so ist ff surjektiv. Die Umkehrung der zweiten Aussage verlangt, zu jedem yy gleichzeitig ein Urbild auszuwählen; für unendliches YY 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 N\mathbb{N}, ein Element 1∈N1\in\mathbb{N} und eine Abbildung ν ⁣:N→N\nu\colon\mathbb{N}\to\mathbb{N} (Nachfolger) mit

Die übliche Beschreibung {1,2,3,… }\{1,2,3,\dots\} enthält mit den Pünktchen genau das, was zu klären ist: dass man von 11 aus durch fortgesetztes Weiterzählen jede natürliche Zahl erreicht und nichts sonst. Die drei Axiome sprechen das aus, und keines ist entbehrlich:

Die Axiomatisierung der natürlichen Zahlen geht auf Richard Dedekind und Giuseppe Peano zurück.

Man schreibt n+1n+1 für ν(n)\nu(n). Jedes n≠1n\ne 1 ist ein Nachfolger, hat also einen Vorgänger n−1∈Nn-1\in\mathbb{N}, der nach (P1) eindeutig ist: Die Menge {1}∪ν(N)\{1\}\cup\nu(\mathbb{N}) erfüllt die Voraussetzungen von (P3).

Rekursionssatz (ohne Beweis). Sei AA eine Menge, a∈Aa\in A, und sei zu jedem n∈Nn\in\mathbb{N} eine Abbildung φn ⁣:A→A\varphi_n\colon A\to A gegeben. Dann gibt es genau eine Abbildung f ⁣:N→Af\colon\mathbb{N}\to A mit f(1)=af(1)=a und f(n+1)=φn(f(n))f(n+1)=\varphi_n\bigl(f(n)\bigr) für alle n∈Nn\in\mathbb{N}.

Mit dem Rekursionssatz werden Addition, Multiplikation und Anordnung auf N\mathbb{N} erklärt; wir setzen ihre Rechenregeln voraus. Von der Anordnung wird ausdrücklich benutzt: 1≤n1\le n für alle nn, und zwischen nn und n+1n+1 liegt keine natürliche Zahl, das heißt, aus k>nk>n folgt k≥n+1k\ge n+1.

Induktionsprinzip. Sei A(n)A(n) für jedes n∈Nn\in\mathbb{N} eine Aussage. Gilt

so gilt A(n)A(n) für alle n∈Nn\in\mathbb{N}.

Beweis. Die Menge M={n∈N: A(n)}M=\{n\in\mathbb{N}:\ A(n)\} enthält 11, und mit nn enthält sie auch ν(n)=n+1\nu(n)=n+1. Nach (P3) ist M=NM=\mathbb{N}. □\square

Im Induktionsschritt wird A(n)A(n) nicht bewiesen, sondern vorausgesetzt; man nennt A(n)A(n) dort die Induktionsvoraussetzung. Bewiesen wird die Implikation A(n)⇒A(n+1)A(n)\Rightarrow A(n+1). Das ist kein Zirkel: Niemand behauptet im Schritt, dass A(n)A(n) gilt.

Anfang an beliebiger Stelle. Sei n0∈N0n_0\in\mathbb{N}_0, und sei A(n)A(n) für jede ganze Zahl n≥n0n\ge n_0 eine Aussage. Gilt A(n0)A(n_0) und folgt für jedes n≥n0n\ge n_0 aus A(n)A(n) die Aussage A(n+1)A(n+1), so gilt A(n)A(n) für alle n≥n0n\ge n_0.

Beweis. Für m∈Nm\in\mathbb{N} sei B(m)B(m) die Aussage A(n0+m−1)A(n_0+m-1). B(1)B(1) ist A(n0)A(n_0). Gilt B(m)B(m), so gilt A(n0+m−1)A(n_0+m-1) mit n0+m−1≥n0n_0+m-1\ge n_0, nach Voraussetzung also A(n0+m)A(n_0+m), und das ist B(m+1)B(m+1). Nach dem Induktionsprinzip gilt B(m)B(m) für alle m∈Nm\in\mathbb{N}. Jedes n≥n0n\ge n_0 ist von der Form n0+m−1n_0+m-1 mit m=n−n0+1∈Nm=n-n_0+1\in\mathbb{N}. □\square

Insbesondere darf eine Induktion bei n0=0n_0=0 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 mm und n≥m−1n\ge m-1 sei

∑k=mm−1ak=0,∑k=mn+1ak=(∑k=mnak)+an+1,\sum_{k=m}^{m-1}a_k=0,\qquad \sum_{k=m}^{n+1}a_k=\Bigl(\sum_{k=m}^{n}a_k\Bigr)+a_{n+1},

entsprechend ∏\prod mit dem leeren Produkt 11 als Anfang, und x0=1x^0=1, xn+1=xn⋅xx^{n+1}=x^n\cdot x für n∈N0n\in\mathbb{N}_0. Das schließt 00=10^0=1 ein; diese Vereinbarung für ganzzahlige Exponenten bleibt im ganzen Kurs bestehen. Die Schreibweise am+am+1+⋯+ana_m+a_{m+1}+\dots+a_n ist eine Abkürzung für die rekursiv erklärte Summe. Der Name des Laufindex ist frei, und man darf ihn verschieben: ∑k=mnak=∑j=m+1n+1aj−1\sum_{k=m}^{n}a_k=\sum_{j=m+1}^{n+1}a_{j-1}. Regeln wie xm+n=xmxnx^{m+n}=x^m x^n oder das allgemeine Assoziativ- und Kommutativgesetz für endliche Summen sind Induktionsbeweise, die wir nicht einzeln ausführen.

Satz 1.12. Für alle n∈Nn\in\mathbb{N} gilt ∑k=1nk=n(n+1)2\displaystyle\sum_{k=1}^{n}k=\frac{n(n+1)}{2}.

Beweis. Induktionsanfang: Für n=1n=1 steht links 11, rechts 1⋅22=1\frac{1\cdot 2}{2}=1. Induktionsschritt: Gelte die Formel für ein nn. Dann ist

∑k=1n+1k=n(n+1)2+(n+1)=(n+1)(n+2)2.□\sum_{k=1}^{n+1}k=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2} .\qquad\square

Satz 1.13 (geometrische Summe). Für jede reelle Zahl q≠1q\ne 1 und alle n∈N0n\in\mathbb{N}_0 gilt

∑k=0nqk=1−qn+11−q.\sum_{k=0}^{n}q^k=\frac{1-q^{n+1}}{1-q}.

Beweis. Induktion über nn, mit Anfang bei n=0n=0: Links steht q0=1q^0=1, rechts (1−q)/(1−q)=1(1-q)/(1-q)=1. Schritt:

∑k=0n+1qk=1−qn+11−q+qn+1=1−qn+1+qn+1−qn+21−q=1−qn+21−q.□\sum_{k=0}^{n+1}q^k=\frac{1-q^{n+1}}{1-q}+q^{n+1}=\frac{1-q^{n+1}+q^{n+1}-q^{n+2}}{1-q}=\frac{1-q^{n+2}}{1-q}.\qquad\square

Woher die Formel kommt, sieht man ohne Induktion. Für S=∑k=0nqkS=\sum_{k=0}^{n}q^k ist qS=∑k=1n+1qkqS=\sum_{k=1}^{n+1}q^k; in der Differenz heben sich alle Summanden bis auf den ersten und den letzten weg, S−qS=1−qn+1S-qS=1-q^{n+1}. In dieser Form, ohne Division, gilt die Gleichung für jedes qq. Die geometrische Summe wird in Einheit 6 zur geometrischen Reihe, dem Maßstab für fast alle Konvergenzkriterien.

Satz 1.14 (starke Induktion). Sei n0∈N0n_0\in\mathbb{N}_0. Gilt A(n0)A(n_0) und folgt für jedes n≥n0n\ge n_0 aus der Gültigkeit von A(n0),A(n0+1),…,A(n)A(n_0),A(n_0+1),\dots,A(n) die von A(n+1)A(n+1), so gilt A(n)A(n) für alle n≥n0n\ge n_0.

Beweis. Sei B(n)B(n) die Aussage „A(k)A(k) gilt für alle kk mit n0≤k≤nn_0\le k\le n“. B(n0)B(n_0) ist A(n0)A(n_0). Gilt B(n)B(n), so nach Voraussetzung auch A(n+1)A(n+1), also B(n+1)B(n+1). Nach der Induktion mit Anfang n0n_0 gilt B(n)B(n) für alle n≥n0n\ge n_0, insbesondere A(n)A(n). □\square

Satz 1.15. Jede natürliche Zahl n≥2n\ge 2 ist ein Produkt von Primzahlen (wobei eine einzelne Primzahl als Produkt mit einem Faktor zählt).

Beweis. Starke Induktion mit Anfang n0=2n_0=2: 22 ist prim. Gelte die Behauptung für alle Zahlen von 22 bis nn. Ist n+1n+1 prim, so ist nichts zu zeigen. Andernfalls hat n+1n+1 einen Teiler a∈Na\in\mathbb{N} mit a≠1a\ne 1 und a≠n+1a\ne n+1, also n+1=abn+1=ab mit einem b∈Zb\in\mathbb{Z}; wegen a>0a>0 und ab>0ab>0 ist b>0b>0, also b∈Nb\in\mathbb{N}. Wegen b≥1b\ge 1 ist a≤ab=n+1a\le ab=n+1, also 2≤a≤n2\le a\le n. Wegen a≥2a\ge 2 ist b<2b≤ab=n+1b<2b\le ab=n+1, und b=1b=1 würde a=n+1a=n+1 ergeben; also 2≤b≤n2\le b\le n. Nach Voraussetzung sind aa und bb Produkte von Primzahlen, also auch abab. □\square

Die gewöhnliche Induktion käme hier nicht voran: Über n+1=abn+1=ab sagt die Aussage für nn allein nichts.

Satz 1.16 (Wohlordnung). Jede nichtleere Teilmenge M⊆NM\subseteq\mathbb{N} besitzt ein kleinstes Element, das heißt ein m∈Mm\in M mit m≤km\le k für alle k∈Mk\in M.

Beweis. Angenommen, MM hat kein kleinstes Element. Sei A(n)A(n) die Aussage „kein k≤nk\le n liegt in MM“. Anfang: Aus k≤1k\le 1 folgt k=1k=1, und läge 11 in MM, so wäre 11 wegen 1≤k1\le k für alle kk das kleinste Element; also gilt A(1)A(1). Schritt: Gelte A(n)A(n). Jedes k∈Mk\in M erfüllt dann k>nk>n, also k≥n+1k\ge n+1. Läge n+1n+1 in MM, so wäre es das kleinste Element; also n+1∉Mn+1\notin M, und mit A(n)A(n) folgt A(n+1)A(n+1). Nach dem Induktionsprinzip gilt A(n)A(n) für alle nn; wegen n≤nn\le n liegt kein nn in MM, also ist M=∅M=\emptyset – im Widerspruch dazu, dass MM nicht leer ist. □\square

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 nn 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 (a+b)n(a+b)^n? Und wie viele kk-elementige Teilmengen hat eine nn-elementige Menge? Für n=3n=3 ist (a+b)3=a3+3a2b+3ab2+b3(a+b)^3=a^3+3a^2b+3ab^2+b^3, und {1,2,3}\{1,2,3\} hat 1,3,3,11,3,3,1 Teilmengen mit 0,1,2,30,1,2,3 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 n∈N0n\in\mathbb{N}_0 ist n!=∏k=1nkn!=\prod_{k=1}^{n}k die Fakultät; insbesondere 0!=10!=1 (leeres Produkt). Für n,k∈N0n,k\in\mathbb{N}_0 mit k≤nk\le n ist

(nk)=n!k! (n−k)!\binom{n}{k}=\frac{n!}{k!\,(n-k)!}

der Binomialkoeffizient.

Unmittelbar aus der Definition: (n0)=(nn)=1\binom{n}{0}=\binom{n}{n}=1 und (nk)=(nn−k)\binom{n}{k}=\binom{n}{n-k}.

Lemma 1.18 (Pascal). Für 1≤k≤n1\le k\le n gilt (nk−1)+(nk)=(n+1k)\displaystyle\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}.

Beweis. Auf den Hauptnenner k! (n+1−k)!k!\,(n+1-k)! gebracht:

n!(k−1)! (n−k+1)!+n!k! (n−k)!=n! k+n! (n−k+1)k! (n+1−k)!=n! (n+1)k! (n+1−k)!=(n+1k).□\begin{aligned}\frac{n!}{(k-1)!\,(n-k+1)!}+\frac{n!}{k!\,(n-k)!}&=\frac{n!\,k+n!\,(n-k+1)}{k!\,(n+1-k)!}\\&=\frac{n!\,(n+1)}{k!\,(n+1-k)!}=\binom{n+1}{k}.\qquad\square\end{aligned}

Mit dem Lemma erkennt man alle Binomialkoeffizienten ohne Rechnung als natürliche Zahlen, durch Induktion über nn. Für n=0n=0 ist (00)=1\binom{0}{0}=1. Sind alle (nk)\binom{n}{k} mit 0≤k≤n0\le k\le n natürliche Zahlen, so ist (n+1k)\binom{n+1}{k} für k=0k=0 und k=n+1k=n+1 gleich 11 und für 1≤k≤n1\le k\le n nach Lemma 1.18 die Summe zweier natürlicher Zahlen. Der Bruch in Definition 1.17 geht also stets auf, etwa (73)=50406⋅24=35\binom{7}{3}=\frac{5040}{6\cdot 24}=35.

Bemerkung (allgemeiner Binomialkoeffizient). Für reelles xx und k∈N0k\in\mathbb{N}_0 setzt man

(xk)=1k!∏j=0k−1(x−j).\binom{x}{k}=\frac{1}{k!}\prod_{j=0}^{k-1}(x-j).

Für x=n∈N0x=n\in\mathbb{N}_0 und k≤nk\le n ist das Definition 1.17, denn ∏j=0k−1(n−j)=n!(n−k)!\prod_{j=0}^{k-1}(n-j)=\frac{n!}{(n-k)!}; für k>nk>n enthält das Produkt den Faktor n−n=0n-n=0, also ist (nk)=0\binom{n}{k}=0. Diese Fassung wird später für die Binomialreihe gebraucht.

Definition (endliche Menge). Sei n∈N0n\in\mathbb{N}_0. Eine Menge XX hat nn Elemente, wenn es eine Bijektion {1,…,n}→X\{1,\dots,n\}\to X gibt; für n=0n=0 heißt das X=∅X=\emptyset. XX heißt endlich, wenn XX für ein nn genau nn Elemente hat.

Wir benutzen ohne Beweis die folgenden Zählregeln; jede ist eine Induktion über nn. Die Zahl nn ist durch XX eindeutig bestimmt. Hat XX genau n+1n+1 Elemente und ist x0∈Xx_0\in X, so hat X∖{x0}X\setminus\{x_0\} genau nn Elemente. Sind Y1,…,YrY_1,\dots,Y_r paarweise disjunkt mit p1,…,prp_1,\dots,p_r Elementen, so hat Y1∪⋯∪YrY_1\cup\dots\cup Y_r genau p1+⋯+prp_1+\dots+p_r Elemente. Ist f ⁣:Y→Zf\colon Y\to Z bijektiv und hat YY genau pp Elemente, so auch ZZ. Jede Teilmenge einer Menge mit nn Elementen ist endlich und hat höchstens nn Elemente; hat sie genau nn Elemente, so ist sie die ganze Menge.

Satz 1.19 (Anzahl der Teilmengen). Eine Menge mit nn Elementen besitzt genau (nk)\binom{n}{k} Teilmengen mit kk Elementen (0≤k≤n0\le k\le n).

Beweis. Induktion über nn. Für n=0n=0 gibt es genau eine Teilmenge, die leere, und (00)=1\binom{0}{0}=1. Sei die Aussage für nn richtig und XX eine Menge mit n+1n+1 Elementen. Für k=0k=0 und k=n+1k=n+1 gibt es je genau eine Teilmenge. Sei 1≤k≤n1\le k\le n und x0∈Xx_0\in X fest. Die kk-elementigen Teilmengen von XX zerfallen in zwei Sorten. Die ohne x0x_0 sind die kk-elementigen Teilmengen von X∖{x0}X\setminus\{x_0\}, also (nk)\binom{n}{k} Stück. Die mit x0x_0 entstehen, indem man zu einer (k−1)(k-1)-elementigen Teilmenge TT von X∖{x0}X\setminus\{x_0\} das Element x0x_0 hinzunimmt; die Zuordnung T↦T∪{x0}T\mapsto T\cup\{x_0\} ist bijektiv mit der Umkehrung S↦S∖{x0}S\mapsto S\setminus\{x_0\}, also sind es (nk−1)\binom{n}{k-1} Stück. Zusammen sind es nach Lemma 1.18 genau (n+1k)\binom{n+1}{k}. □\square

Satz 1.20 (Binomialsatz). Für reelle Zahlen aa, bb und n∈N0n\in\mathbb{N}_0 gilt

(a+b)n=∑k=0n(nk)an−kbk.(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k .

Beweisidee. Beim Übergang von nn zu n+1n+1 multipliziert man mit (a+b)(a+b); jeder Summand zerfällt in zwei, und Pascals Lemma fügt benachbarte Koeffizienten wieder zusammen.

Beweis. Induktion über nn. Für n=0n=0 sind beide Seiten 11. Gelte die Formel für nn. Dann ist

(a+b)n+1=(a+b)∑k=0n(nk)an−kbk=∑k=0n(nk)an+1−kbk+∑k=0n(nk)an−kbk+1.(a+b)^{n+1}=(a+b)\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k=\sum_{k=0}^{n}\binom{n}{k}a^{n+1-k}b^k+\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k+1}.

In der zweiten Summe verschieben wir den Index (k+1k+1 wird zum neuen kk):

∑k=0n(nk)an−kbk+1=∑k=1n+1(nk−1)an+1−kbk.\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k+1}=\sum_{k=1}^{n+1}\binom{n}{k-1}a^{n+1-k}b^{k}.

Aus der ersten Summe lösen wir den Summanden k=0k=0 heraus, aus der zweiten den Summanden k=n+1k=n+1, und fassen den Rest zusammen:

(a+b)n+1=an+1+∑k=1n[(nk)+(nk−1)]an+1−kbk+bn+1=∑k=0n+1(n+1k)an+1−kbk,(a+b)^{n+1}=a^{n+1}+\sum_{k=1}^{n}\left[\binom{n}{k}+\binom{n}{k-1}\right]a^{n+1-k}b^k+b^{n+1}=\sum_{k=0}^{n+1}\binom{n+1}{k}a^{n+1-k}b^k,

zuletzt mit Lemma 1.18 und (n+10)=(n+1n+1)=1\binom{n+1}{0}=\binom{n+1}{n+1}=1. □\square

Der Satz lässt sich auch zählend lesen. Beim Ausmultiplizieren von (a+b)n=(a+b)⋯(a+b)(a+b)^n=(a+b)\cdots(a+b) wählt man aus jedem der nn Faktoren entweder aa oder bb. Der Summand an−kbka^{n-k}b^k entsteht so oft, wie man kk der nn Faktoren für bb auswählen kann, nach Satz 1.19 also (nk)\binom{n}{k}-mal.

Bemerkung (Allgemeinheit). Der Beweis benutzt von aa und bb nur die Rechengesetze der Addition und Multiplikation einschließlich ab=baab=ba. Der Binomialsatz gilt deshalb ebenso für komplexe Zahlen; in dieser Form wird er später für die Exponentialfunktion gebraucht. Ohne ab=baab=ba ist er falsch: Schon (a+b)2=a2+ab+ba+b2(a+b)^2=a^2+ab+ba+b^2 zeigt, was fehlt.

Folgerung 1.21. ∑k=0n(nk)=2n\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n. Eine Menge mit nn Elementen hat also genau 2n2^n Teilmengen.

Beweis. Binomialsatz mit a=b=1a=b=1; die zweite Aussage folgt mit Satz 1.19 und der Zählregel für disjunkte Vereinigungen. □\square

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 x≤yx\le y, dass x<yx<y oder x=yx=y gilt.

(O4) ist keine neue Regel: Nach (O1) ist x+u≤y+ux+u\le y+u und y+u≤y+vy+u\le y+v, nach (O0) also x+u≤y+vx+u\le y+v.

Definition 1.22. Der Betrag einer reellen Zahl xx ist ∣x∣=x|x|=x, falls x≥0x\ge 0, und ∣x∣=−x|x|=-x, falls x<0x<0.

Es gilt ∣x∣≥0|x|\ge 0, ∣x∣=0|x|=0 nur für x=0x=0, ∣xy∣=∣x∣ ∣y∣|xy|=|x|\,|y| und −∣x∣≤x≤∣x∣-|x|\le x\le|x|. Für c≥0c\ge 0 gilt

∣x∣≤c  ⟺  −c≤x≤c,|x|\le c \iff -c\le x\le c ,

und ebenso ∣x∣<c  ⟺  −c<x<c|x|<c\iff -c<x<c für c>0c>0. Alle diese Regeln beweist man durch die Fallunterscheidung x≥0x\ge 0 oder x<0x<0 nach (O0). Zum Beispiel die erste Äquivalenz: Ist x≥0x\ge 0, so ist −c≤0≤x-c\le 0\le x, und ∣x∣≤c|x|\le c heißt x≤cx\le c. Ist x<0x<0, so ist x<0≤cx<0\le c, und ∣x∣=−x≤c|x|=-x\le c ist nach (O2) mit z=−1z=-1 gleichwertig mit x≥−cx\ge -c.

Geometrisch ist ∣x−y∣|x-y| der Abstand von xx und yy auf der Zahlengeraden. Der Ausdruck ∣an−a∣<ε|a_n-a|<\varepsilon aus Abschnitt 1.2 heißt also: ana_n liegt näher als ε\varepsilon bei aa.

Satz 1.23 (Dreiecksungleichung). Für alle x,y∈Rx,y\in\mathbb{R} gilt

∣x+y∣≤∣x∣+∣y∣und∣ ∣x∣−∣y∣ ∣≤∣x−y∣.|x+y|\le|x|+|y| \qquad\text{und}\qquad \bigl|\,|x|-|y|\,\bigr|\le|x-y| .

Beweis. Aus −∣x∣≤x≤∣x∣-|x|\le x\le|x| und −∣y∣≤y≤∣y∣-|y|\le y\le|y| folgt mit (O4)

−(∣x∣+∣y∣)≤x+y≤∣x∣+∣y∣,-(|x|+|y|)\le x+y\le|x|+|y|,

und das ist ∣x+y∣≤∣x∣+∣y∣|x+y|\le|x|+|y|. Für die zweite Ungleichung schreibe man x=(x−y)+yx=(x-y)+y; die erste liefert ∣x∣≤∣x−y∣+∣y∣|x|\le|x-y|+|y|, also ∣x∣−∣y∣≤∣x−y∣|x|-|y|\le|x-y|. Vertauscht man die Rollen, folgt ∣y∣−∣x∣≤∣y−x∣=∣x−y∣|y|-|x|\le|y-x|=|x-y|. Beides zusammen ist die Behauptung. □\square

Der Kunstgriff x=(x−y)+yx=(x-y)+y, das Einschieben einer Null, ist der häufigste Handgriff der Analysis. Er kommt in fast jedem Grenzwertbeweis vor.

Ausblick (Abstand). Setzt man d(x,y)=∣x−y∣d(x,y)=|x-y|, so gilt d(x,y)≥0d(x,y)\ge 0 mit Gleichheit nur für x=yx=y, ferner d(x,y)=d(y,x)d(x,y)=d(y,x) und, nach Satz 1.23 mit x−z=(x−y)+(y−z)x-z=(x-y)+(y-z), d(x,z)≤d(x,y)+d(y,z)d(x,z)\le d(x,y)+d(y,z). Eine Abbildung dd mit diesen drei Eigenschaften heißt Metrik. Viele Sätze über Konvergenz und Stetigkeit benutzen von R\mathbb{R} nur diese drei Eigenschaften.

Satz 1.24 (Bernoullische Ungleichung). Für jede reelle Zahl x≥−1x\ge-1 und alle n∈N0n\in\mathbb{N}_0 gilt

(1+x)n≥1+nx.(1+x)^n\ge 1+nx .

Beweis. Induktion über nn. Für n=0n=0 steht auf beiden Seiten 11. Gelte die Ungleichung für nn. Wegen 1+x≥01+x\ge 0 darf man sie nach (O2) mit 1+x1+x multiplizieren:

(1+x)n+1≥(1+nx)(1+x)=1+(n+1)x+nx2≥1+(n+1)x,(1+x)^{n+1}\ge(1+nx)(1+x)=1+(n+1)x+nx^2\ge 1+(n+1)x,

zuletzt wegen nx2≥0nx^2\ge 0 ((O2) und (O3)). □\square

Die Voraussetzung x≥−1x\ge-1 geht im Beweis an genau einer Stelle ein: beim Multiplizieren mit 1+x1+x. Sie ist eine Bedingung dieses Beweises, nicht die Grenze der Aussage. Für −2≤x<−1-2\le x<-1 gilt die Ungleichung ebenfalls: Für n≤1n\le 1 ist sie eine Gleichung; für n≥2n\ge 2 ist ∣1+x∣≤1|1+x|\le 1, also (1+x)n≥−1(1+x)^n\ge-1, während 1+nx≤1−n≤−11+nx\le 1-n\le-1 ist. Erst für x<−2x<-2 kann sie scheitern, wie (G6) zeigt.

Satz 1.25. Für alle reellen Zahlen aa, bb gilt ab≤(a+b2)2\displaystyle ab\le\left(\frac{a+b}{2}\right)^{2}, mit Gleichheit genau für a=ba=b.

Beweis. (a+b2)2−ab=a2−2ab+b24=(a−b)24≥0\left(\frac{a+b}{2}\right)^2-ab=\frac{a^2-2ab+b^2}{4}=\frac{(a-b)^2}{4}\ge 0 nach (O3), und der Ausdruck ist genau für a=ba=b null. □\square

Für a,b≥0a,b\ge 0 ist das die Ungleichung zwischen geometrischem und arithmetischem Mittel, ab≤a+b2\sqrt{ab}\le\frac{a+b}{2}; die Wurzel steht uns erst ab Einheit 2 zur Verfügung.

1.9 Relationen

Die Zeichen ≤\le, == und ⊆\subseteq 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 XX ist eine Teilmenge R⊆X×XR\subseteq X\times X; statt (x,y)∈R(x,y)\in R schreibt man x∼yx\sim y, bei Ordnungen meist x⪯yx\preceq y. Die Relation heißt

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 x⪯yx\preceq y oder y⪯xy\preceq x gilt.

Beispiele. (a) ≤\le auf R\mathbb{R} ist eine totale Ordnung. (b) ⊆\subseteq auf P(X)\mathcal{P}(X) ist eine Ordnung; sie ist nicht total, sobald XX zwei verschiedene Elemente aa, bb hat, denn {a}\{a\} und {b}\{b\} sind nicht vergleichbar. (c) Für festes m∈Nm\in\mathbb{N} ist „a≡ba\equiv b, wenn m∣a−bm\mid a-b“ eine Äquivalenzrelation auf Z\mathbb{Z}. (d) Jede Abbildung f ⁣:X→Yf\colon X\to Y liefert eine Äquivalenzrelation auf XX: x∼x′x\sim x', wenn f(x)=f(x′)f(x)=f(x').

Bemerkung (Ordnungen). Zu einer Ordnung ⪯\preceq gehört die strikte Ordnung x≺yx\prec y, die „x⪯yx\preceq y und x≠yx\ne y“ bedeutet. In einer geordneten Menge (X,⪯)(X,\preceq) heißt s∈Xs\in X obere Schranke von A⊆XA\subseteq X, wenn a⪯sa\preceq s für alle a∈Aa\in A gilt, und Supremum von AA, wenn ss obere Schranke ist und s⪯ts\preceq t für jede obere Schranke tt von AA 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 R\mathbb{R} von Q\mathbb{Q} unterscheidet (Einheit 2).

Äquivalenzrelationen beschreiben „gleich unter einem Gesichtspunkt“. Die Paare (1,2)(1,2) und (2,4)(2,4) sind verschieden, als Brüche sollen sie gleich sein; die ganzen Zahlen 33 und 1010 sind verschieden, haben aber bei Division durch 77 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 ∼\sim eine Äquivalenzrelation auf XX. Die Äquivalenzklasse von x∈Xx\in X ist [x]={y∈X: y∼x}[x]=\{y\in X:\ y\sim x\}; jedes Element einer Klasse heißt Repräsentant. Die Menge aller Klassen heißt Quotientenmenge X/∼X/{\sim}.

Satz 1.28 (Klasseneinteilung). Sei ∼\sim eine Äquivalenzrelation auf XX. Dann gilt:

  1. x∈[x]x\in[x] für jedes x∈Xx\in X; insbesondere ist keine Klasse leer, und XX ist die Vereinigung aller Klassen.
  2. [x]=[y][x]=[y] genau dann, wenn x∼yx\sim y.
  3. Zwei Klassen sind entweder gleich oder disjunkt.

Beweis. (1) ist die Reflexivität.

(2) Ist [x]=[y][x]=[y], so ist x∈[x]=[y]x\in[x]=[y], also x∼yx\sim y. Sei umgekehrt x∼yx\sim y und z∈[x]z\in[x]. Dann ist z∼xz\sim x und x∼yx\sim y, wegen der Transitivität also z∼yz\sim y, das heißt z∈[y]z\in[y]. Damit ist [x]⊆[y][x]\subseteq[y]. Wegen der Symmetrie gilt auch y∼xy\sim x, und dasselbe Argument liefert [y]⊆[x][y]\subseteq[x].

(3) Ist z∈[x]∩[y]z\in[x]\cap[y], so ist z∼xz\sim x und z∼yz\sim y, nach (2) also [z]=[x][z]=[x] und [z]=[y][z]=[y], folglich [x]=[y][x]=[y]. □\square

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 XX in nichtleere, paarweise disjunkte Teilmengen eine Äquivalenzrelation: „x∼yx\sim y, wenn beide in derselben Teilmenge liegen“.

Bemerkung (Wohldefiniertheit). Wer eine Abbildung auf X/∼X/{\sim} 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 [a]+[b]=[a+b][a]+[b]=[a+b] zulässig: Aus a≡a′a\equiv a' und b≡b′b\equiv b' folgt, dass mm auch (a+b)−(a′+b′)=(a−a′)+(b−b′)(a+b)-(a'+b')=(a-a')+(b-b') teilt. Die Vorschrift „[a]↦a[a]\mapsto a“ ist dagegen keine Abbildung nach Z\mathbb{Z}.

Auf diese Weise entstehen die Zahlbereiche. Die rationalen Zahlen gewinnt man als Klassen von Paaren (a,b)∈Z×N(a,b)\in\mathbb{Z}\times\mathbb{N} unter „(a,b)∼(c,d)(a,b)\sim(c,d), wenn ad=bcad=bc“ (Aufgabe B5); ein Bruch ab\frac{a}{b} ist eine solche Klasse, und 12=24\frac{1}{2}=\frac{2}{4} 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 A(n)A(n) die Aussage „n=n+1n=n+1“. Der Induktionsschritt gelingt: Aus n=n+1n=n+1 folgt durch Addition von 11 sofort n+1=n+2n+1=n+2. Trotzdem ist A(n)A(n) für jedes nn falsch. Der Schritt allein beweist nichts.

(G2) Induktionsanfang ohne Schritt. Die Aussage der Leitfrage, „FnF_n ist prim“, stimmt für n=0n=0 bis n=4n=4 und scheitert bei n=5n=5. Ein Induktionsschritt müsste aus der Primalität von FnF_n die von Fn+1=(Fn−1)2+1F_{n+1}=(F_n-1)^2+1 herleiten; das ist unmöglich, denn F4F_4 ist prim und F5F_5 nicht. Bestätigte Fälle ersetzen keinen Schritt, gleichgültig wie viele es sind.

(G3) Ein Schritt, der nicht für jedes nn trägt. Behauptung: „In jeder Gruppe von nn Personen haben alle am selben Tag Geburtstag.“ Scheinbeweis: Für n=1n=1 ist das richtig. Gelte es für nn, und seien n+1n+1 Personen P1,…,Pn+1P_1,\dots,P_{n+1} gegeben. Die ersten nn haben nach Voraussetzung denselben Geburtstag, die letzten nn ebenfalls; weil sich beide Gruppen überschneiden, haben alle n+1n+1 denselben.

Der Fehler: Die Gruppen {P1,…,Pn}\{P_1,\dots,P_n\} und {P2,…,Pn+1}\{P_2,\dots,P_{n+1}\} überschneiden sich nur für n≥2n\ge 2. Für n=1n=1 sind es {P1}\{P_1\} und {P2}\{P_2\}, ohne gemeinsame Person. Der Schritt von 11 auf 22 ist nicht bewiesen, und an ihm hängt alles. Ein Induktionsschritt muss für jedes nn ab dem Anfang gelten.

(G4) Vertauschte Quantoren. ∀x ∃y: y>x\forall x\,\exists y:\ y>x ist wahr, ∃y ∀x: y>x\exists y\,\forall x:\ y>x falsch (Abschnitt 1.2).

(G5) Bild eines Durchschnitts. Für f ⁣:R→Rf\colon\mathbb{R}\to\mathbb{R}, f(x)=x2f(x)=x^2, A1={−1}A_1=\{-1\}, A2={1}A_2=\{1\} ist f(A1∩A2)=f(∅)=∅f(A_1\cap A_2)=f(\emptyset)=\emptyset, aber f(A1)∩f(A2)={1}f(A_1)\cap f(A_2)=\{1\}. In Satz 1.11 (3) gilt Gleichheit für alle A1A_1, A2A_2 genau dann, wenn ff injektiv ist (Aufgabe B4).

(G6) Bernoulli ohne Voraussetzung. Für x=−4x=-4 und n=3n=3 ist (1+x)n=(−3)3=−27(1+x)^n=(-3)^3=-27, aber 1+nx=−111+nx=-11. Die Ungleichung ist verletzt. Im Beweis scheitert der Schritt, in dem mit der negativen Zahl 1+x1+x multipliziert wird.

(G7) Einseitige Verkettung. In Satz 1.10 genügt eine der beiden Gleichungen nicht. Für X={1}X=\{1\}, Y={1,2}Y=\{1,2\}, f(1)=1f(1)=1 und g ⁣:Y→Xg\colon Y\to X konstant ist g∘f=id⁡Xg\circ f=\operatorname{id}_X, aber ff ist nicht surjektiv und gg nicht injektiv.

(G8) Ohne Transitivität keine Klassen. Auf R\mathbb{R} sei x∼yx\sim y, wenn ∣x−y∣≤1|x-y|\le 1. Die Relation ist reflexiv und symmetrisch, aber nicht transitiv: 0∼10\sim 1 und 1∼21\sim 2, aber nicht 0∼20\sim 2. Die Mengen {y: y∼0}\{y:\ y\sim 0\} und {y: y∼1}\{y:\ y\sim 1\} sind verschieden und nicht disjunkt (beide enthalten 12\frac12); 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 ε>0\varepsilon>0 gelten; das ist die Quantorenform aus Abschnitt 1.2.

1.11 Durchgerechnete Beispiele

Beispiel 1 (Verneinen). Eine Funktion f ⁣:R→Rf\colon\mathbb{R}\to\mathbb{R} heißt beschränkt, wenn

∃C>0  ∀x∈R: ∣f(x)∣≤C.\exists C>0\ \ \forall x\in\mathbb{R}:\ |f(x)|\le C .

Unbeschränkt heißt nach Regel 1.3: ∀C>0 ∃x∈R: ∣f(x)∣>C\forall C>0\ \exists x\in\mathbb{R}:\ |f(x)|>C. Für f(x)=x2f(x)=x^2 weist man das so nach: Sei C>0C>0 beliebig. Wähle x=C+1x=C+1. Dann ist x>1x>1 und x>0x>0, nach (O5) also x2>xx^2>x, und x>Cx>C; zusammen ∣f(x)∣=x2>C|f(x)|=x^2>C. Man beachte die Form: Das CC wird vorgegeben, das xx wird in Abhängigkeit von CC gewählt.

Beispiel 2 (Summe mit zwei Beweisen). Behauptung: ∑k=1n1k(k+1)=nn+1\displaystyle\sum_{k=1}^{n}\frac{1}{k(k+1)}=\frac{n}{n+1} für alle n∈Nn\in\mathbb{N}.

Erster Beweis (Induktion). Für n=1n=1: 12=12\frac{1}{2}=\frac{1}{2}. Schritt:

nn+1+1(n+1)(n+2)=n(n+2)+1(n+1)(n+2)=(n+1)2(n+1)(n+2)=n+1n+2.\frac{n}{n+1}+\frac{1}{(n+1)(n+2)}=\frac{n(n+2)+1}{(n+1)(n+2)}=\frac{(n+1)^2}{(n+1)(n+2)}=\frac{n+1}{n+2}.

Zweiter Beweis (Teleskopsumme). Wegen 1k(k+1)=1k−1k+1\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1} heben sich benachbarte Summanden weg:

∑k=1n(1k−1k+1)=1−1n+1=nn+1.\sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right)=1-\frac{1}{n+1}=\frac{n}{n+1}.

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 0<q<10<q<1. Wir zeigen, dass qnq^n beliebig klein wird, mit einer ausdrücklichen Schranke. Schreibe q=11+xq=\frac{1}{1+x} mit x=1q−1>0x=\frac{1}{q}-1>0. Nach Bernoulli ist (1+x)n≥1+nx>nx>0(1+x)^n\ge 1+nx>nx>0 für n∈Nn\in\mathbb{N}, mit (O6) also

qn=1(1+x)n≤11+nx<1nx.q^n=\frac{1}{(1+x)^n}\le\frac{1}{1+nx}<\frac{1}{nx}.

Für q=910q=\frac{9}{10} ist x=19x=\frac{1}{9}, also qn<9nq^n<\frac{9}{n}. Die Schranke ist grob (tatsächlich fällt qnq^n 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: 2n>n32^n>n^3 für alle n≥10n\ge 10. Anfang: 210=1024>1000=1032^{10}=1024>1000=10^3. Schritt: Sei n≥10n\ge 10 und 2n>n32^n>n^3. Nach (O5) ist 2n+1=2⋅2n>2n32^{n+1}=2\cdot 2^n>2n^3, und es bleibt 2n3≥(n+1)32n^3\ge(n+1)^3 zu zeigen, ausmultipliziert n3≥3n2+3n+1n^3\ge 3n^2+3n+1. Für n≥4n\ge 4 ist n2≥4nn^2\ge 4n (Multiplikation von n≥4n\ge 4 mit n>0n>0, (O2)), also n3=n⋅n2≥4n2=3n2+n2≥3n2+4n>3n2+3n+1n^3=n\cdot n^2\ge 4n^2=3n^2+n^2\ge 3n^2+4n>3n^2+3n+1, das Letzte wegen n>1n>1. Mit (O0) folgt 2n+1>(n+1)32^{n+1}>(n+1)^3.

Was trägt wo? Die Rechnung des Schritts ist für jedes n≥4n\ge 4 richtig; bei n=3n=3 versagt sie, denn 2⋅27=54<64=432\cdot 27=54<64=4^3. Die Behauptung selbst gilt für n=1n=1 (2>12>1), ist aber für n=2,…,9n=2,\dots,9 falsch, zuletzt 29=512<729=932^9=512<729=9^3. Der wahre Fall n=1n=1 nützt nichts, weil der Schritt von 11 auf 22 nicht trägt; der Schritt ab n=4n=4 nützt erst, wenn ein wahrer Fall erreicht ist, und das ist n=10n=10. Beides wird gebraucht.

1.12 Ausblick

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 qnq^n für 0<q<10<q<1 beliebig klein wird, folgt dort ebenfalls aus der Bernoullischen Ungleichung (§ 3, Satz 3). Die Fermat-Zahlen der Leitfrage mit dem Teiler 641641 von F5F_5 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.