F.R. GRANARIA

Zur interaktiven Werkstatt · PDF

Kapiteltext · Aufgaben und Lösungen

Einheit 1 – Aufgaben und Lösungen

Vierte Fassung vom 18. November 2026. Verweise beziehen sich auf ../kapitel/01-sprache-und-beweise.md.

Aufgaben

Stufe R – Rechnen

R1. Beweisen Sie durch Induktion: ∑k=1nk2=n(n+1)(2n+1)6\displaystyle\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6} für alle n∈Nn\in\mathbb{N}.

R2. Verneinen Sie, ohne das Zeichen ¬\neg vor einem Quantor stehen zu lassen:

Welche der Aussagen (a) und (b) sind wahr? (Bei (a) genügt eine Begründung, warum die Aussage wahr sein sollte; der Beweis folgt in Einheit 2.)

R3. Bestimmen Sie den Koeffizienten von x3x^3 in (2x−1)5(2x-1)^5.

R4. Bestimmen Sie alle x∈Rx\in\mathbb{R} mit ∣2x−3∣<5|2x-3|<5.

R5. Für n∈Nn\in\mathbb{N} sei

An={x∈R: 1n≤x≤2−1n},Bn={x∈R: −1n<x<1+1n}.A_n=\Bigl\{x\in\mathbb{R}:\ \tfrac1n\le x\le 2-\tfrac1n\Bigr\},\qquad B_n=\Bigl\{x\in\mathbb{R}:\ -\tfrac1n<x<1+\tfrac1n\Bigr\}.

Bestimmen Sie ⋃n∈NAn\bigcup_{n\in\mathbb{N}}A_n und ⋂n∈NBn\bigcap_{n\in\mathbb{N}}B_n und beweisen Sie Ihr Ergebnis über zwei Inklusionen. Sie dürfen dabei die archimedische Eigenschaft benutzen, die in Einheit 2 bewiesen wird:

(A) Zu jedem t>0t>0 gibt es ein n∈Nn\in\mathbb{N} mit 1n<t\frac1n<t.

An welcher Stelle wird (A) gebraucht, an welcher nicht?

R6. (a) Bestimmen Sie alle x∈Rx\in\mathbb{R} mit ∣x−1∣+∣x+2∣≤5|x-1|+|x+2|\le 5.

(b) Zeigen Sie mit der Dreiecksungleichung, ohne Fallunterscheidung, dass ∣x−1∣+∣x+2∣≥3|x-1|+|x+2|\ge 3 für alle x∈Rx\in\mathbb{R} gilt. Für welche xx gilt Gleichheit?

Stufe B – Beweisen

B1. Zeigen Sie ∑k=1nk⋅k!=(n+1)!−1\displaystyle\sum_{k=1}^{n}k\cdot k!=(n+1)!-1 für alle n∈Nn\in\mathbb{N} auf zwei Wegen: durch Induktion und, indem Sie jeden Summanden als Differenz zweier Fakultäten schreiben, wie im zweiten Beweis von Beispiel 2 (Abschnitt 1.11).

B2. Seien f ⁣:X→Yf\colon X\to Y und g ⁣:Y→Zg\colon Y\to Z Abbildungen. Zeigen Sie:

B3. (a) Zeigen Sie für n∈N0n\in\mathbb{N}_0: ∑k=0n(nk)2k=3n\displaystyle\sum_{k=0}^{n}\binom{n}{k}2^k=3^n.

(b) Sei XX eine Menge mit nn Elementen. Zeigen Sie mit (a): Es gibt genau 3n3^n Paare (S,T)(S,T) von Teilmengen von XX mit S⊆TS\subseteq T.

B4. Sei f ⁣:X→Yf\colon X\to Y. Zeigen Sie: Genau dann gilt f(A1∩A2)=f(A1)∩f(A2)f(A_1\cap A_2)=f(A_1)\cap f(A_2) für alle A1,A2⊆XA_1,A_2\subseteq X, wenn ff injektiv ist.

B5. Auf X=Z×NX=\mathbb{Z}\times\mathbb{N} sei (a,b)∼(c,d)(a,b)\sim(c,d), wenn ad=bcad=bc. Zeigen Sie, dass ∼\sim eine Äquivalenzrelation ist. An welcher Stelle wird benutzt, dass die zweite Komponente nicht null ist? Zeigen Sie außerdem, dass [(a,b)]+[(c,d)]=[(ad+bc, bd)][(a,b)]+[(c,d)]=[(ad+bc,\,bd)] wohldefiniert ist.

B6. (a) Zeigen Sie, dass ((A⇒B)∧(B⇒C))⇒(A⇒C)\bigl((A\Rightarrow B)\wedge(B\Rightarrow C)\bigr)\Rightarrow(A\Rightarrow C) für alle Wahrheitswerte von AA, BB, CC wahr ist. Es genügt, die Belegungen zu untersuchen, in denen A⇒CA\Rightarrow C falsch ist – warum?

(b) Zeigen Sie, dass (A⇒B)⇒C(A\Rightarrow B)\Rightarrow C und A⇒(B⇒C)A\Rightarrow(B\Rightarrow C) nicht gleichwertig sind.

(c) Beweisen Sie durch Kontraposition: Sind m,n∈Zm,n\in\mathbb{Z} und ist mnmn gerade, so ist mm gerade oder nn gerade.

(d) Beweisen Sie durch Widerspruch: Sind a,b∈Ra,b\in\mathbb{R} und gilt ∣a−b∣≤ε|a-b|\le\varepsilon für jedes ε>0\varepsilon>0, so ist a=ba=b.

B7. Sei (Ai)i∈I(A_i)_{i\in I} eine Familie von Teilmengen einer Menge XX.

B8. (a) Zeigen Sie durch Induktion für reelle Zahlen x1,…,xnx_1,\dots,x_n:

∣∑k=1nxk∣≤∑k=1n∣xk∣.\Bigl|\sum_{k=1}^{n}x_k\Bigr|\le\sum_{k=1}^{n}|x_k|.

(b) Zeigen Sie für alle a,b,x,y∈Ra,b,x,y\in\mathbb{R}:

∣xy−ab∣≤∣x∣ ∣y−b∣+∣b∣ ∣x−a∣,|xy-ab|\le|x|\,|y-b|+|b|\,|x-a|,

und folgern Sie: Ist ∣x−a∣≤1|x-a|\le1, so gilt ∣xy−ab∣≤(∣a∣+1)∣y−b∣+∣b∣ ∣x−a∣|xy-ab|\le(|a|+1)|y-b|+|b|\,|x-a|.

(c) Zeigen Sie: ∣x+y∣=∣x∣+∣y∣|x+y|=|x|+|y| gilt genau dann, wenn xy≥0xy\ge0 ist.

Stufe V – Vertiefen

V1. Die Fibonacci-Zahlen sind durch f1=f2=1f_1=f_2=1 und fn+1=fn+fn−1f_{n+1}=f_n+f_{n-1} für n≥2n\ge 2 erklärt. Zeigen Sie fn<2nf_n<2^n für alle n∈Nn\in\mathbb{N}. Erklären Sie, warum im Induktionsschritt zwei Vorgänger gebraucht werden und warum deshalb f2f_2 gesondert geprüft werden muss.

V2. Setzen Sie voraus: N\mathbb{N} mit der üblichen Anordnung erfüllt die Wohlordnung (jede nichtleere Teilmenge hat ein kleinstes Element), und jedes n∈Nn\in\mathbb{N} mit n≠1n\ne 1 hat einen Vorgänger n−1∈Nn-1\in\mathbb{N} mit n−1<nn-1<n und (n−1)+1=n(n-1)+1=n.

V3. Zeigen Sie für n∈Nn\in\mathbb{N}: ∑k=0nk(nk)=n 2n−1\displaystyle\sum_{k=0}^{n}k\binom{n}{k}=n\,2^{n-1}.

V4. Sei an=(1+1n)na_n=\left(1+\frac{1}{n}\right)^{n} für n∈Nn\in\mathbb{N}. Zeigen Sie mit der Bernoullischen Ungleichung:

V5. Sei f ⁣:X→Yf\colon X\to Y eine Abbildung und X≠∅X\ne\emptyset. Zeigen Sie:

V6. Für a,b∈Na,b\in\mathbb{N} schreibe man a∣ba\mid b („aa teilt bb“), wenn es ein k∈Nk\in\mathbb{N} mit b=kab=ka gibt.

(a) Zeigen Sie, dass ∣\mid eine Ordnung auf N\mathbb{N} ist, aber keine totale.

(b) Auf Z\mathbb{Z} sei a∣ba\mid b entsprechend mit k∈Zk\in\mathbb{Z} erklärt. Welche der drei Eigenschaften einer Ordnung gehen verloren, und an welcher Stelle Ihres Beweises aus (a)?

(c) Zeigen Sie: Aus a∣ba\mid b folgt a≤ba\le b (für a,b∈Na,b\in\mathbb{N}).

(d) Sei ⪯\preceq eine Ordnung auf einer Menge MM. Ein m∈Mm\in M heißt kleinstes Element, wenn m⪯xm\preceq x für alle x∈Mx\in M gilt, und minimal, wenn aus x∈Mx\in M und x⪯mx\preceq m stets x=mx=m folgt. Zeigen Sie: Ein kleinstes Element ist minimal, und es ist dann das einzige minimale Element. Ist ⪯\preceq total, so ist jedes minimale Element ein kleinstes.

(e) Bestimmen Sie für M={2,3,4,… }M=\{2,3,4,\dots\} mit der Ordnung ∣\mid alle minimalen Elemente und zeigen Sie, dass MM kein kleinstes Element hat. Vergleichen Sie mit Satz 1.16.

Lösungen

R1

Anfang n=1n=1: 1=1⋅2⋅361=\frac{1\cdot 2\cdot 3}{6}. Schritt:

n(n+1)(2n+1)6+(n+1)2=(n+1)(2n2+n+6n+6)6=(n+1)(2n2+7n+6)6=(n+1)(n+2)(2n+3)6,\begin{aligned}\frac{n(n+1)(2n+1)}{6}+(n+1)^2&=\frac{(n+1)\bigl(2n^2+n+6n+6\bigr)}{6}\\&=\frac{(n+1)(2n^2+7n+6)}{6}=\frac{(n+1)(n+2)(2n+3)}{6},\end{aligned}

denn (n+2)(2n+3)=2n2+7n+6(n+2)(2n+3)=2n^2+7n+6. Das ist die Formel für n+1n+1.

R2

R3

Nach dem Binomialsatz mit a=2xa=2x, b=−1b=-1 ist der Summand mit x3x^3 der zu k=2k=2:

(52)(2x)3(−1)2=10⋅8 x3=80 x3.\binom{5}{2}(2x)^3(-1)^2=10\cdot 8\,x^3=80\,x^3 .

Der Koeffizient ist 8080.

R4

Nach Abschnitt 1.8 gilt ∣y∣<c  ⟺  −c<y<c|y|<c\iff-c<y<c für c>0c>0. Mit den strengen Regeln (O5) folgt

∣2x−3∣<5  ⟺  −5<2x−3<5  ⟺  −2<2x<8  ⟺  −1<x<4|2x-3|<5\iff-5<2x-3<5\iff-2<2x<8\iff-1<x<4

(zweiter Schritt: 33 addieren; dritter: mit 12>0\frac12>0 multiplizieren). Die Lösungsmenge ist das offene Intervall (−1,4)(-1,4): alle Punkte, deren Abstand von 32\frac32 kleiner als 52\frac52 ist, denn ∣2x−3∣<5  ⟺  ∣x−32∣<52|2x-3|<5\iff|x-\frac32|<\frac52.

R5

Vorbemerkung. Für n≥mn\ge m gilt 1n≤1m\frac1n\le\frac1m, und stets 1n>0\frac1n>0 ((O6) und (O3)).

Vereinigung. Behauptung: ⋃nAn={x∈R: 0<x<2}\bigcup_{n}A_n=\{x\in\mathbb{R}:\ 0<x<2\}.

„⊆\subseteq“: Liegt xx in einem AnA_n, so ist 0<1n≤x0<\frac1n\le x und x≤2−1n<2x\le2-\frac1n<2. Hier wird (A) nicht gebraucht.

„⊇\supseteq“: Sei 0<x<20<x<2. Dann sind x>0x>0 und 2−x>02-x>0. Nach (A) gibt es n1n_1 mit 1n1<x\frac1{n_1}<x und n2n_2 mit 1n2<2−x\frac1{n_2}<2-x. Für n=max⁡{n1,n2}n=\max\{n_1,n_2\} ist 1n≤1n1<x\frac1n\le\frac1{n_1}<x und 1n≤1n2<2−x\frac1n\le\frac1{n_2}<2-x, also 1n≤x≤2−1n\frac1n\le x\le 2-\frac1n, das heißt x∈Anx\in A_n.

Durchschnitt. Behauptung: ⋂nBn={x∈R: 0≤x≤1}\bigcap_{n}B_n=\{x\in\mathbb{R}:\ 0\le x\le1\}.

„⊇\supseteq“: Aus 0≤x≤10\le x\le1 folgt −1n<0≤x≤1<1+1n-\frac1n<0\le x\le1<1+\frac1n für jedes nn. Hier wird (A) nicht gebraucht.

„⊆\subseteq“: Sei xx in allen BnB_n. Angenommen, x<0x<0. Dann ist −x>0-x>0, und nach (A) gibt es nn mit 1n<−x\frac1n<-x, also x<−1nx<-\frac1n; dann liegt xx nicht in BnB_n – Widerspruch. Angenommen, x>1x>1. Dann gibt es nach (A) ein nn mit 1n<x−1\frac1n<x-1, also x>1+1nx>1+\frac1n, und x∉Bnx\notin B_n – Widerspruch. Also ist 0≤x≤10\le x\le1.

Deutung. Jedes AnA_n enthält seine Randpunkte, die Vereinigung keinen; jedes BnB_n enthält seine Randpunkte nicht, der Durchschnitt beide. Später heißt das: Eine Vereinigung abgeschlossener Intervalle braucht nicht abgeschlossen, ein Durchschnitt offener Intervalle nicht offen zu sein. (A) wird jeweils nur für die schwierigere Inklusion gebraucht, wie im Beispiel ⋂n{0<x<1n}=∅\bigcap_n\{0<x<\frac1n\}=\emptyset des Abschnitts 1.4.

R6

(a) Nach Definition 1.22 ist ∣x−1∣=x−1|x-1|=x-1 für x≥1x\ge1 und =1−x=1-x für x<1x<1, ebenso ∣x+2∣=x+2|x+2|=x+2 für x≥−2x\ge-2 und =−x−2=-x-2 für x<−2x<-2. Drei Fälle:

Zusammen: {x∈R: −3≤x≤2}\{x\in\mathbb{R}:\ -3\le x\le2\}. Geometrisch: alle Punkte, deren Abstände zu 11 und zu −2-2 zusammen höchstens 55 betragen.

(b) Mit ∣−u∣=∣u∣|-u|=|u| und der Dreiecksungleichung:

3=∣(x+2)+(1−x)∣≤∣x+2∣+∣1−x∣=∣x+2∣+∣x−1∣.3=\bigl|(x+2)+(1-x)\bigr|\le|x+2|+|1-x|=|x+2|+|x-1|.

Gleichheit: Nach der Fallunterscheidung aus (a) ist die Summe im mittleren Fall gleich 33, im ersten Fall 2x+1=32x+1=3 nur für x=1x=1, im dritten Fall −2x−1=3-2x-1=3 nur für x=−2x=-2, das nicht zum dritten Fall gehört. Also gilt Gleichheit genau für −2≤x≤1-2\le x\le1, das heißt für die Punkte zwischen −2-2 und 11 einschließlich der Endpunkte. (Vergleich mit B8 (c): Gleichheit genau, wenn (x+2)(1−x)≥0(x+2)(1-x)\ge0, und das ist dieselbe Bedingung.)

B1

Induktion. Anfang n=1n=1: links 1⋅1!=11\cdot 1!=1, rechts 2!−1=12!-1=1. Schritt: Gilt die Formel für nn, so ist

∑k=1n+1k⋅k!=(n+1)!−1+(n+1)⋅(n+1)!=(n+1)! (1+(n+1))−1=(n+2)!−1.\sum_{k=1}^{n+1}k\cdot k!=(n+1)!-1+(n+1)\cdot(n+1)!=(n+1)!\,\bigl(1+(n+1)\bigr)-1=(n+2)!-1 .

Differenzen. Für jedes k∈Nk\in\mathbb{N} ist (k+1)!=(k+1)⋅k!=k⋅k!+k!(k+1)!=(k+1)\cdot k!=k\cdot k!+k!, also k⋅k!=(k+1)!−k!k\cdot k!=(k+1)!-k!. Damit ist

∑k=1nk⋅k!=(2!−1!)+(3!−2!)+⋯+((n+1)!−n!)=(n+1)!−1!,\sum_{k=1}^{n}k\cdot k!=\bigl(2!-1!\bigr)+\bigl(3!-2!\bigr)+\dots+\bigl((n+1)!-n!\bigr)=(n+1)!-1!,

denn jede Fakultät von 2!2! bis n!n! tritt einmal mit Plus und einmal mit Minus auf. Wegen 1!=11!=1 ist das die Behauptung. Der zweite Weg erklärt, warum gerade (n+1)!−1(n+1)!-1 herauskommt; der erste setzt die Formel als bekannt voraus.

B2

(a) Sei f(x)=f(x′)f(x)=f(x'). Dann ist g(f(x))=g(f(x′))g(f(x))=g(f(x')), und weil g∘fg\circ f injektiv ist, folgt x=x′x=x'.

(b) Sei z∈Zz\in Z. Weil g∘fg\circ f surjektiv ist, gibt es x∈Xx\in X mit g(f(x))=zg(f(x))=z. Dann ist y=f(x)∈Yy=f(x)\in Y ein Element mit g(y)=zg(y)=z.

(c) f(n)=n+1f(n)=n+1 und g(1)=1g(1)=1, g(n)=n−1g(n)=n-1 für n≥2n\ge 2 (Vorgänger, Abschnitt 1.6). Dann ist g(f(n))=g(n+1)=ng(f(n))=g(n+1)=n, also g∘f=id⁡Ng\circ f=\operatorname{id}_{\mathbb{N}}. ff nimmt den Wert 11 nicht an (P2), und g(1)=g(2)=1g(1)=g(2)=1.

Für eine endliche Menge XX mit nn Elementen ist eine injektive Abbildung f ⁣:X→Xf\colon X\to X auch surjektiv: ff ist eine Bijektion von XX auf f(X)f(X), also hat die Teilmenge f(X)⊆Xf(X)\subseteq X genau nn Elemente und ist nach den Zählregeln des Abschnitts 1.7 ganz XX. Nach (a) wäre ff injektiv, also bijektiv, und dann wäre g=g∘f∘f−1=f−1g=g\circ f\circ f^{-1}=f^{-1} ebenfalls bijektiv. Das Beispiel zeigt, dass sich unendliche Mengen anders verhalten: N\mathbb{N} lässt sich injektiv auf eine echte Teilmenge von sich abbilden. Ein Beispiel mit verschiedenen endlichen Mengen ist (G7).

B3

(a) Satz 1.20 mit a=1a=1 und b=2b=2 gibt 3n=(1+2)n=∑k=0n(nk)1n−k2k=∑k=0n(nk)2k3^n=(1+2)^n=\sum_{k=0}^{n}\binom{n}{k}1^{n-k}2^k=\sum_{k=0}^{n}\binom{n}{k}2^k.

(b) Für 0≤k≤n0\le k\le n sei PkP_k die Menge der gesuchten Paare (S,T)(S,T), bei denen TT genau kk Elemente hat. Jedes Paar liegt in genau einem PkP_k, denn T⊆XT\subseteq X hat nach den Zählregeln eine eindeutig bestimmte Elementzahl k≤nk\le n. Halten wir eine kk-elementige Teilmenge TT fest. Die Paare (S,T)(S,T) mit diesem TT entsprechen umkehrbar eindeutig den Teilmengen SS von TT, vermöge (S,T)↦S(S,T)\mapsto S und S↦(S,T)S\mapsto(S,T); nach Folgerung 1.21 sind es 2k2^k. Nach Satz 1.19 gibt es (nk)\binom{n}{k} solche TT, und Paare mit verschiedenem TT sind verschieden. Also zerfällt PkP_k in (nk)\binom{n}{k} disjunkte Teile mit je 2k2^k Elementen und hat nach der Zählregel für disjunkte Vereinigungen (nk)2k\binom{n}{k}2^k Elemente. Dieselbe Regel, auf P0,…,PnP_0,\dots,P_n angewandt, ergibt mit (a) insgesamt ∑k=0n(nk)2k=3n\sum_{k=0}^{n}\binom{n}{k}2^k=3^n Paare.

Deutung. Ein Paar (S,T)(S,T) legt für jedes x∈Xx\in X eine von drei Möglichkeiten fest: x∈Sx\in S, oder x∈T∖Sx\in T\setminus S, oder x∉Tx\notin T. Das macht die Zahl 3n3^n plausibel; ein Beweis auf diesem Weg bräuchte eine Zählregel für Auswahlen, die Abschnitt 1.7 nicht bereitstellt. Für n=1n=1, X={x}X=\{x\}, sind es die drei Paare (∅,∅)(\emptyset,\emptyset), (∅,X)(\emptyset,X) und (X,X)(X,X).

B4

„⇐\Leftarrow“: Sei ff injektiv. Die Inklusion „⊆\subseteq“ gilt immer (Satz 1.11 (3)). Sei y∈f(A1)∩f(A2)y\in f(A_1)\cap f(A_2). Dann gibt es a1∈A1a_1\in A_1 und a2∈A2a_2\in A_2 mit f(a1)=y=f(a2)f(a_1)=y=f(a_2). Aus der Injektivität folgt a1=a2a_1=a_2; dieses Element liegt in A1∩A2A_1\cap A_2, also y∈f(A1∩A2)y\in f(A_1\cap A_2).

„⇒\Rightarrow“: Kontraposition. Sei ff nicht injektiv; dann gibt es x≠x′x\ne x' mit f(x)=f(x′)f(x)=f(x'). Für A1={x}A_1=\{x\}, A2={x′}A_2=\{x'\} ist A1∩A2=∅A_1\cap A_2=\emptyset, also f(A1∩A2)=∅f(A_1\cap A_2)=\emptyset, aber f(A1)∩f(A2)={f(x)}≠∅f(A_1)\cap f(A_2)=\{f(x)\}\ne\emptyset.

B5

Reflexiv: ab=baab=ba. Symmetrisch: Aus ad=bcad=bc folgt cb=dacb=da. Transitiv: Sei (a,b)∼(c,d)(a,b)\sim(c,d) und (c,d)∼(e,f)(c,d)\sim(e,f), also ad=bcad=bc und cf=decf=de. Dann ist

(af)d=(ad)f=(bc)f=b(cf)=b(de)=(be)d,(af)d=(ad)f=(bc)f=b(cf)=b(de)=(be)d,

also d (af−be)=0d\,(af-be)=0. Wegen d≠0d\ne 0 folgt af=beaf=be, das heißt (a,b)∼(e,f)(a,b)\sim(e,f). Genau hier geht d≠0d\ne 0 ein, zusammen mit der Nullteilerfreiheit von Z\mathbb{Z}. Ließe man die zweite Komponente 00 zu, wäre (1,1)∼(0,0)(1,1)\sim(0,0) und (0,0)∼(2,1)(0,0)\sim(2,1), aber nicht (1,1)∼(2,1)(1,1)\sim(2,1).

Wohldefiniertheit: Sei (a,b)∼(a′,b′)(a,b)\sim(a',b') und (c,d)∼(c′,d′)(c,d)\sim(c',d'), also ab′=a′bab'=a'b und cd′=c′dcd'=c'd. Zu zeigen ist (ad+bc) b′d′=(a′d′+b′c′) bd(ad+bc)\,b'd'=(a'd'+b'c')\,bd. Es ist

(ad+bc) b′d′=(ab′) dd′+(cd′) bb′=(a′b) dd′+(c′d) bb′=(a′d′+b′c′) bd.(ad+bc)\,b'd'=(ab')\,dd'+(cd')\,bb'=(a'b)\,dd'+(c'd)\,bb'=(a'd'+b'c')\,bd .

Außerdem liegt bdbd wieder in N\mathbb{N}, das Ergebnis also in XX.

B6

(a) Eine Implikation P⇒QP\Rightarrow Q ist nur dann falsch, wenn QQ falsch und PP wahr ist. Es genügt also, die Belegungen zu betrachten, in denen Q=(A⇒C)Q=(A\Rightarrow C) falsch ist, und dort zu zeigen, dass PP falsch ist. A⇒CA\Rightarrow C ist genau dann falsch, wenn AA wahr und CC falsch ist. Ist dann BB wahr, so ist B⇒CB\Rightarrow C falsch; ist BB falsch, so ist A⇒BA\Rightarrow B falsch. In beiden Fällen ist (A⇒B)∧(B⇒C)(A\Rightarrow B)\wedge(B\Rightarrow C) falsch, die Gesamtaussage also wahr. In allen übrigen Belegungen ist sie wahr, weil ihre Behauptung wahr ist. Diese Regel (Kettenschluss) erlaubt, Beweise in Zwischenschritte zu zerlegen.

(b) Belegung AA falsch, BB beliebig, CC falsch: A⇒BA\Rightarrow B ist wahr, also ist (A⇒B)⇒C(A\Rightarrow B)\Rightarrow C falsch. Dagegen ist A⇒(B⇒C)A\Rightarrow(B\Rightarrow C) wahr, weil AA falsch ist. Die Klammerung bei mehrfachen Implikationen ist also nicht gleichgültig.

(c) Die Verneinung der Behauptung „mm gerade oder nn gerade“ ist nach Satz 1.2 (1) „mm ungerade und nn ungerade“ (jede ganze Zahl ist entweder gerade oder ungerade). Zu zeigen ist also: Sind mm und nn ungerade, so ist mnmn ungerade. Mit m=2k+1m=2k+1, n=2l+1n=2l+1, k,l∈Zk,l\in\mathbb{Z}, ist

mn=4kl+2k+2l+1=2(2kl+k+l)+1,mn=4kl+2k+2l+1=2(2kl+k+l)+1 ,

also ist mnmn ungerade.

(d) Angenommen, a≠ba\ne b. Dann ist a−b≠0a-b\ne0, also ∣a−b∣>0|a-b|>0, und ε=12∣a−b∣\varepsilon=\frac12|a-b| ist positiv. Die Voraussetzung gibt für dieses ε\varepsilon:

∣a−b∣≤12∣a−b∣.|a-b|\le\tfrac12|a-b|.

Subtraktion von 12∣a−b∣\frac12|a-b| (O1) ergibt 12∣a−b∣≤0\frac12|a-b|\le0, das heißt ε≤0\varepsilon\le 0 – im Widerspruch zu ε>0\varepsilon>0. Die Annahme a≠ba\ne b diente dazu, ein positives ε\varepsilon wählen zu dürfen.

Ausblick. So beweist man in der Analysis Gleichheiten: Man zeigt, dass der Abstand kleiner ist als jede positive Zahl. Daraus folgt später, dass eine Folge höchstens einen Grenzwert hat.

B7

(a) Für x∈Xx\in X gilt nach Regel 1.3:

x∉⋃i∈IAi  ⟺  ¬(∃i∈I: x∈Ai)  ⟺  ∀i∈I: x∉Ai  ⟺  x∈⋂i∈I(X∖Ai).x\notin\bigcup_{i\in I}A_i\iff\neg\bigl(\exists i\in I:\ x\in A_i\bigr)\iff\forall i\in I:\ x\notin A_i\iff x\in\bigcap_{i\in I}(X\setminus A_i).

Beide Seiten der ersten Regel sind Teilmengen von XX und haben dieselben Elemente. Die zweite Regel ebenso: Für x∈Xx\in X gilt x∉⋂iAi  ⟺  ¬(∀i: x∈Ai)  ⟺  ∃i: x∉Ai  ⟺  x∈⋃i(X∖Ai)x\notin\bigcap_iA_i\iff\neg(\forall i:\ x\in A_i)\iff\exists i:\ x\notin A_i\iff x\in\bigcup_i(X\setminus A_i). Der Beweis benutzt nichts über II. Für I=∅I=\emptyset lauten die Regeln X∖∅=XX\setminus\emptyset=X und X∖X=∅X\setminus X=\emptyset.

(b) f(R∖{1})f(\mathbb{R}\setminus\{1\}) enthält f(−1)=1f(-1)=1, aber R∖f({1})=R∖{1}\mathbb{R}\setminus f(\{1\})=\mathbb{R}\setminus\{1\} enthält 11 nicht; die erste Inklusion ist falsch. Umgekehrt liegt −1-1 in R∖{1}\mathbb{R}\setminus\{1\}, aber nicht in f(R∖{1})f(\mathbb{R}\setminus\{1\}), weil x2≥0x^2\ge 0 für jedes xx gilt (O3); die zweite Inklusion ist falsch.

(c) Injektiv. Sei ff injektiv und y∈f(X∖A)y\in f(X\setminus A), also y=f(x)y=f(x) mit x∉Ax\notin A. Läge yy in f(A)f(A), so wäre y=f(a)y=f(a) mit a∈Aa\in A, und aus f(a)=f(x)f(a)=f(x) folgte a=x∈Aa=x\in A – Widerspruch. Also y∈Y∖f(A)y\in Y\setminus f(A). Ist ff nicht injektiv, etwa f(x)=f(x′)f(x)=f(x') mit x≠x′x\ne x', so wähle A={x′}A=\{x'\}: Dann liegt f(x)f(x) in f(X∖A)f(X\setminus A) und in f(A)f(A), die Inklusion ist verletzt.

Surjektiv. Sei ff surjektiv und y∉f(A)y\notin f(A). Es gibt xx mit f(x)=yf(x)=y, und x∉Ax\notin A (sonst wäre y∈f(A)y\in f(A)), also y∈f(X∖A)y\in f(X\setminus A). Gilt umgekehrt die Inklusion für alle AA, so für A=∅A=\emptyset: Y⊆f(X)Y\subseteq f(X), also ist ff surjektiv.

Folglich gilt f(X∖A)=Y∖f(A)f(X\setminus A)=Y\setminus f(A) für alle AA genau dann, wenn ff bijektiv ist. Das Urbild verträgt sich dagegen nach Satz 1.11 mit allen Mengenoperationen, ohne Voraussetzung an ff.

B8

(a) Anfang n=1n=1: ∣x1∣≤∣x1∣|x_1|\le|x_1|. Schritt: Gelte die Ungleichung für nn. Mit Satz 1.23 und (O1):

∣∑k=1n+1xk∣=∣∑k=1nxk+xn+1∣≤∣∑k=1nxk∣+∣xn+1∣≤∑k=1n∣xk∣+∣xn+1∣=∑k=1n+1∣xk∣.\Bigl|\sum_{k=1}^{n+1}x_k\Bigr|=\Bigl|\sum_{k=1}^{n}x_k+x_{n+1}\Bigr|\le\Bigl|\sum_{k=1}^{n}x_k\Bigr|+|x_{n+1}|\le\sum_{k=1}^{n}|x_k|+|x_{n+1}|=\sum_{k=1}^{n+1}|x_k|.

(b) Man schiebt die Null −xb+xb-xb+xb ein:

xy−ab=(xy−xb)+(xb−ab)=x(y−b)+b(x−a).xy-ab=(xy-xb)+(xb-ab)=x(y-b)+b(x-a).

Dreiecksungleichung und ∣uv∣=∣u∣ ∣v∣|uv|=|u|\,|v| ergeben die Behauptung. Ist ∣x−a∣≤1|x-a|\le1, so ist ∣x∣=∣(x−a)+a∣≤∣x−a∣+∣a∣≤1+∣a∣|x|=|(x-a)+a|\le|x-a|+|a|\le1+|a|, und Multiplikation mit ∣y−b∣≥0|y-b|\ge0 (O2) gibt ∣x∣ ∣y−b∣≤(∣a∣+1)∣y−b∣|x|\,|y-b|\le(|a|+1)|y-b|. Addiert man auf beiden Seiten ∣b∣ ∣x−a∣|b|\,|x-a| (O1) und verkettet mit der ersten Ungleichung (O0), so folgt die Behauptung.

Ausblick. Die rechte Seite hängt nur noch von den Abständen ∣x−a∣|x-a|, ∣y−b∣|y-b| und den festen Zahlen aa, bb ab. Sind xx nahe bei aa und yy nahe bei bb, so ist xyxy nahe bei abab; das ist der Kern der Produktregel für Grenzwerte. Die Bedingung ∣x−a∣≤1|x-a|\le1 dient nur dazu, den Faktor ∣x∣|x| durch eine feste Zahl zu ersetzen.

(c) Für jedes u∈Ru\in\mathbb{R} ist ∣u∣2=∣u2∣=u2|u|^2=|u^2|=u^2, weil u2≥0u^2\ge0 (O3). Also

∣x+y∣2=x2+2xy+y2,(∣x∣+∣y∣)2=x2+2∣xy∣+y2.|x+y|^2=x^2+2xy+y^2,\qquad(|x|+|y|)^2=x^2+2|xy|+y^2 .

Für u,v≥0u,v\ge0 gilt u=v  ⟺  u2=v2u=v\iff u^2=v^2: „⇒\Rightarrow“ ist klar; aus u2=v2u^2=v^2 folgt (u−v)(u+v)=0(u-v)(u+v)=0, also u=vu=v oder u+v=0u+v=0, und im zweiten Fall ist 0≤u≤u+v=00\le u\le u+v=0, also u=v=0u=v=0. (Benutzt wird, dass ein Produkt reeller Zahlen nur null ist, wenn ein Faktor null ist – Körpereigenschaft, Einheit 2.) Mit u=∣x+y∣u=|x+y|, v=∣x∣+∣y∣v=|x|+|y| folgt:

∣x+y∣=∣x∣+∣y∣  ⟺  xy=∣xy∣  ⟺  xy≥0,|x+y|=|x|+|y|\iff xy=|xy|\iff xy\ge0,

der letzte Schritt nach Definition 1.22 (für z<0z<0 ist ∣z∣=−z≠z|z|=-z\ne z). In Worten: In der Dreiecksungleichung gilt genau dann Gleichheit, wenn xx und yy nicht entgegengesetzte Vorzeichen haben.

V1

Die Rekursion greift auf zwei Vorgänger zurück; der Schritt braucht deshalb die Aussage für nn und für n−1n-1. Wir benutzen Satz 1.14 mit n0=1n_0=1.

Anfang: f1=1<2f_1=1<2. Schritt: Seien f1<21,…,fn<2nf_1<2^1,\dots,f_n<2^n bereits gezeigt. Für n=1n=1 greift die Rekursion nicht (sie gilt erst für n≥2n\ge 2 und würde sonst f0f_0 verlangen); hier prüft man direkt f2=1<4f_2=1<4. Für n≥2n\ge 2 ist

fn+1=fn+fn−1<2n+2n−1<2n+2n=2n+1.f_{n+1}=f_n+f_{n-1}<2^n+2^{n-1}<2^n+2^n=2^{n+1}.

Wer nur f1f_1 prüft und den Schritt ohne Fallunterscheidung führt, hat den Übergang von 11 auf 22 nicht bewiesen; das ist dieselbe Fehlerquelle wie in (G3). Gleichwertig kann man die verstärkte Aussage „fn<2nf_n<2^n und fn+1<2n+1f_{n+1}<2^{n+1}“ mit gewöhnlicher Induktion beweisen; auch dort steckt die Prüfung von f2f_2 im Anfang.

V2

(a) Sei A(n)A(n) eine Aussage mit A(1)A(1) und A(n)⇒A(n+1)A(n)\Rightarrow A(n+1) für alle nn. Angenommen, A(n)A(n) gilt nicht für alle nn. Dann ist M={n∈N: A(n) ist falsch}M=\{n\in\mathbb{N}:\ A(n)\text{ ist falsch}\} nicht leer und hat nach der Wohlordnung ein kleinstes Element mm. Wegen A(1)A(1) ist m≠1m\ne 1, also existiert m−1∈Nm-1\in\mathbb{N}. Wegen m−1<mm-1<m liegt m−1m-1 nicht in MM; A(m−1)A(m-1) ist also wahr. Nach dem Schritt ist dann A((m−1)+1)=A(m)A\bigl((m-1)+1\bigr)=A(m) wahr – Widerspruch zu m∈Mm\in M.

Benutzt wurden die Wohlordnung, die Existenz des Vorgängers und m−1<mm-1<m. Im Kapitel ist die Vorgängereigenschaft aus (P3) gewonnen. Die Gleichwertigkeit von Induktion und Wohlordnung ist deshalb so zu lesen: Unter den übrigen Eigenschaften von N\mathbb{N}, insbesondere der Vorgängereigenschaft, folgt jede der beiden Aussagen aus der anderen.

(b) Sei T⊆WT\subseteq W nicht leer. Enthält TT eine natürliche Zahl, so hat T∩NT\cap\mathbb{N} nach Satz 1.16 ein kleinstes Element tt, und tt ist auch kleiner als ω\omega, also kleinstes Element von TT. Andernfalls ist T={ω}T=\{\omega\} mit kleinstem Element ω\omega. Sei nun A(x)A(x) die Aussage „x∈Nx\in\mathbb{N}“. A(1)A(1) gilt; für n∈Nn\in\mathbb{N} folgt A(n+1)A(n+1); für x=ωx=\omega ist A(ω)⇒A(ν(ω))A(\omega)\Rightarrow A(\nu(\omega)) die Implikation A(ω)⇒A(ω)A(\omega)\Rightarrow A(\omega), also wahr. Trotzdem ist A(ω)A(\omega) falsch. Es fehlt die Vorgängereigenschaft: ω≠1\omega\ne 1 ist kein Nachfolger eines anderen Elements. Der Beweis aus (a) bricht an der Stelle „m≠1m\ne 1, also existiert m−1m-1“ ab, wenn das kleinste Gegenbeispiel m=ωm=\omega ist.

V3

Für 1≤k≤n1\le k\le n gilt

k(nk)=k⋅n!k! (n−k)!=n⋅(n−1)!(k−1)! ((n−1)−(k−1))!=n(n−1k−1).k\binom{n}{k}=\frac{k\cdot n!}{k!\,(n-k)!}=\frac{n\cdot(n-1)!}{(k-1)!\,\bigl((n-1)-(k-1)\bigr)!}=n\binom{n-1}{k-1}.

Der Summand zu k=0k=0 ist null. Also ist mit der Indexverschiebung j=k−1j=k-1 und Folgerung 1.21

∑k=0nk(nk)=n∑k=1n(n−1k−1)=n∑j=0n−1(n−1j)=n 2n−1.\sum_{k=0}^{n}k\binom{n}{k}=n\sum_{k=1}^{n}\binom{n-1}{k-1}=n\sum_{j=0}^{n-1}\binom{n-1}{j}=n\,2^{n-1}.

Deutung: Links zählt man alle Paare aus einer Teilmenge und einem ausgezeichneten Element darin. Rechts wählt man zuerst das Element (nn Möglichkeiten) und dann eine beliebige Teilmenge der übrigen n−1n-1 Elemente.

V4

(a) Bernoulli mit x=1n≥−1x=\frac1n\ge-1: (1+1n)n≥1+n⋅1n=2\left(1+\frac1n\right)^n\ge 1+n\cdot\frac1n=2.

(b) Wegen an>0a_n>0 genügt an+1an≥1\frac{a_{n+1}}{a_n}\ge 1. Es ist

an+1an=(n+2n+1)n+1(n+1n)n=(n(n+2)(n+1)2)n+1⋅n+1n=(1−1(n+1)2)n+1⋅n+1n,\frac{a_{n+1}}{a_n}=\frac{\left(\frac{n+2}{n+1}\right)^{n+1}}{\left(\frac{n+1}{n}\right)^{n}}=\left(\frac{n(n+2)}{(n+1)^2}\right)^{n+1}\cdot\frac{n+1}{n}=\left(1-\frac{1}{(n+1)^2}\right)^{n+1}\cdot\frac{n+1}{n},

denn n(n+2)=(n+1)2−1n(n+2)=(n+1)^2-1. Bernoulli mit x=−1(n+1)2≥−1x=-\frac{1}{(n+1)^2}\ge-1 und Exponent n+1n+1 gibt

(1−1(n+1)2)n+1≥1−n+1(n+1)2=1−1n+1=nn+1.\left(1-\frac{1}{(n+1)^2}\right)^{n+1}\ge 1-\frac{n+1}{(n+1)^2}=1-\frac{1}{n+1}=\frac{n}{n+1}.

Also ist an+1an≥nn+1⋅n+1n=1\frac{a_{n+1}}{a_n}\ge\frac{n}{n+1}\cdot\frac{n+1}{n}=1.

Die Folge (an)(a_n) wächst also. Später kommt hinzu, dass sie nach oben beschränkt ist; ihr Grenzwert ist die Zahl ee.

V5

(a) „⇐\Leftarrow“: 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'. „⇒\Rightarrow“: Sei ff injektiv und x0∈Xx_0\in X fest (hier wird X≠∅X\ne\emptyset gebraucht). Setze g(y)=xg(y)=x, falls y=f(x)y=f(x) für ein x∈Xx\in X – dieses xx ist wegen der Injektivität eindeutig –, und g(y)=x0g(y)=x_0, falls y∉f(X)y\notin f(X). Dann ist g(f(x))=xg(f(x))=x für alle xx.

(b) Für y∈Yy\in Y ist y=f(h(y))y=f(h(y)), also liegt yy im Bild von ff.

(c) Ist ff surjektiv, so ist jede der Mengen f−1({y})f^{-1}(\{y\}) nicht leer, und eine Rechtsinverse hh entsteht, indem man aus jeder dieser Mengen ein Element h(y)h(y) auswählt. Für endliches YY geht das durch Induktion über die Elementzahl. Für unendliches YY gibt es im Allgemeinen keine Vorschrift, die alle Auswahlen zugleich festlegt; dass eine solche Auswahlfunktion dennoch existiert, ist der Inhalt des Auswahlaxioms. In (a) trat das Problem nicht auf, weil g(y)g(y) dort eindeutig bestimmt oder einheitlich gleich x0x_0 war.

(d) X=∅X=\emptyset, Y={1}Y=\{1\}, f ⁣:∅→Yf\colon\emptyset\to Y die leere Abbildung (Abschnitt 1.5). Sie ist injektiv: Es gibt keine x,x′x,x', an denen die Bedingung verletzt sein könnte. Eine Abbildung g ⁣:{1}→∅g\colon\{1\}\to\emptyset gibt es aber nicht, denn g(1)g(1) müsste ein Element der leeren Menge sein.

V6

(a) Reflexiv: a=1⋅aa=1\cdot a. Transitiv: Aus b=kab=ka und c=lbc=lb folgt c=(lk)ac=(lk)a mit lk∈Nlk\in\mathbb{N}. Antisymmetrisch: Aus b=kab=ka und a=lba=lb folgt a=lkaa=lka, also a(lk−1)=0a(lk-1)=0 und wegen a≠0a\ne0 dann lk=1lk=1. Wäre k≥2k\ge2, so wäre lk≥k≥2lk\ge k\ge2 (wegen l≥1l\ge1); also k=1k=1 und b=ab=a.

Nicht total: 2∤32\nmid3, denn 2k2k ist 22 für k=1k=1 und mindestens 44 für k≥2k\ge2; und 3∤23\nmid2, denn 3k≥33k\ge3 für jedes k∈Nk\in\mathbb{N}.

(b) Reflexivität und Transitivität bleiben mit derselben Rechnung erhalten. Die Antisymmetrie geht verloren: −1=(−1)⋅1-1=(-1)\cdot1 und 1=(−1)⋅(−1)1=(-1)\cdot(-1), also 1∣−11\mid-1 und −1∣1-1\mid1, aber 1≠−11\ne-1. Im Beweis aus (a) bricht der Schluss „lk=1⇒k=1lk=1\Rightarrow k=1“: In Z\mathbb{Z} ist auch k=l=−1k=l=-1 möglich. Die Voraussetzung k∈Nk\in\mathbb{N} wird also genau an dieser Stelle gebraucht.

(c) Ist b=kab=ka mit k≥1k\ge1, so ist b−a=(k−1)a≥0b-a=(k-1)a\ge0 nach (O2), weil k−1≥0k-1\ge0 und a>0a>0.

(d) Sei mm kleinstes Element und x⪯mx\preceq m. Da auch m⪯xm\preceq x, folgt x=mx=m aus der Antisymmetrie; mm ist minimal. Ist m′m' ein weiteres minimales Element, so gilt m⪯m′m\preceq m', und die Minimalität von m′m' ergibt m=m′m=m'. Sei nun ⪯\preceq total und mm minimal. Für x∈Mx\in M gilt x⪯mx\preceq m oder m⪯xm\preceq x; im ersten Fall ist x=mx=m und m⪯xm\preceq x wegen der Reflexivität. Also ist m⪯xm\preceq x für alle xx.

(e) Eine Primzahl ist eine Zahl p≥2p\ge2, deren einzige Teiler in N\mathbb{N} die Zahlen 11 und pp sind. Ein m∈Mm\in M ist minimal, wenn jeder Teiler x∈Mx\in M von mm gleich mm ist. Die Teiler von mm in N\mathbb{N} sind 11 und die Teiler ≥2\ge2, und diese liegen in MM. Also ist mm genau dann minimal, wenn 11 und mm seine einzigen Teiler sind: Die minimalen Elemente sind genau die Primzahlen. Insbesondere sind 22 und 33 minimal. Nach (d) hätte ein kleinstes Element das einzige minimale Element zu sein; es gibt also keines.

Vergleich mit Satz 1.16: Bezüglich ≤\le hat MM das kleinste Element 22. Ob eine Menge ein kleinstes Element hat, hängt von der Ordnung ab, nicht von der Menge allein. Das Supremum ist in Abschnitt 1.9 als kleinste obere Schranke erklärt; in der totalen Ordnung ≤\le auf R\mathbb{R} fallen „minimal“ und „kleinst“ nach (d) zusammen, in einer nicht totalen Ordnung nicht.