R1. Beweisen Sie durch Induktion: k=1∑nk2=6n(n+1)(2n+1) für alle n∈N.
R2. Verneinen Sie, ohne das Zeichen ¬ vor einem Quantor stehen zu lassen:
(a) ∀x∈R∃n∈N:n>x
(b) ∃x∈R∀y∈R:xy=y
(c) ∀ε>0∃δ>0∀x∈R:(∣x−1∣<δ⇒∣x2−1∣<ε)
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 x3 in (2x−1)5.
R4. Bestimmen Sie alle x∈R mit ∣2x−3∣<5.
R5. Für n∈N sei
An={x∈R:n1≤x≤2−n1},Bn={x∈R:−n1<x<1+n1}.
Bestimmen Sie ⋃n∈NAn und ⋂n∈NBn 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>0 gibt es ein n∈N mit n1<t.
An welcher Stelle wird (A) gebraucht, an welcher nicht?
R6. (a) Bestimmen Sie alle x∈R mit ∣x−1∣+∣x+2∣≤5.
(b) Zeigen Sie mit der Dreiecksungleichung, ohne Fallunterscheidung, dass ∣x−1∣+∣x+2∣≥3 für alle x∈R gilt. Für welche x gilt Gleichheit?
Stufe B – Beweisen
B1. Zeigen Sie k=1∑nk⋅k!=(n+1)!−1 für alle n∈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→Y und g:Y→Z Abbildungen. Zeigen Sie:
(a) Ist g∘f injektiv, so ist f injektiv.
(b) Ist g∘f surjektiv, so ist g surjektiv.
(c) Geben Sie Abbildungen f,g:N→N an, für die g∘f=idN gilt, f aber nicht surjektiv und g nicht injektiv ist. Warum kann es ein solches Beispiel mit einer endlichen Menge X=Y=Z nicht geben?
B3. (a) Zeigen Sie für n∈N0: k=0∑n(kn)2k=3n.
(b) Sei X eine Menge mit n Elementen. Zeigen Sie mit (a): Es gibt genau 3n Paare (S,T) von Teilmengen von X mit S⊆T.
B4. Sei f:X→Y. Zeigen Sie: Genau dann gilt f(A1∩A2)=f(A1)∩f(A2) für alle A1,A2⊆X, wenn f injektiv ist.
B5. Auf X=Z×N sei (a,b)∼(c,d), wenn ad=bc. Zeigen Sie, dass ∼ 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)] wohldefiniert ist.
B6. (a) Zeigen Sie, dass ((A⇒B)∧(B⇒C))⇒(A⇒C) für alle Wahrheitswerte von A, B, C wahr ist. Es genügt, die Belegungen zu untersuchen, in denen A⇒C falsch ist – warum?
(b) Zeigen Sie, dass (A⇒B)⇒C und A⇒(B⇒C) nicht gleichwertig sind.
(c) Beweisen Sie durch Kontraposition: Sind m,n∈Z und ist mn gerade, so ist m gerade oder n gerade.
(d) Beweisen Sie durch Widerspruch: Sind a,b∈R und gilt ∣a−b∣≤ε für jedes ε>0, so ist a=b.
B7. Sei (Ai)i∈I eine Familie von Teilmengen einer Menge X.
(a) Führen Sie den Beweis der Regeln von De Morgan für Familien aus (Abschnitt 1.4), einschließlich des Falls I=∅.
(b) Für f:R→R, f(x)=x2, und A={1} zeigen Sie: Weder f(R∖A)⊆R∖f(A) noch R∖f(A)⊆f(R∖A) gilt. Das Bild verträgt sich also nicht mit dem Komplement.
(c) Zeigen Sie für eine beliebige Abbildung f:X→Y: Es gilt f(X∖A)⊆Y∖f(A) für alle A⊆X genau dann, wenn f injektiv ist, und Y∖f(A)⊆f(X∖A) für alle A⊆X genau dann, wenn f surjektiv ist.
B8. (a) Zeigen Sie durch Induktion für reelle Zahlen x1,…,xn:
k=1∑nxk≤k=1∑n∣xk∣.
(b) Zeigen Sie für alle a,b,x,y∈R:
∣xy−ab∣≤∣x∣∣y−b∣+∣b∣∣x−a∣,
und folgern Sie: Ist ∣x−a∣≤1, so gilt ∣xy−ab∣≤(∣a∣+1)∣y−b∣+∣b∣∣x−a∣.
(c) Zeigen Sie: ∣x+y∣=∣x∣+∣y∣ gilt genau dann, wenn xy≥0 ist.
Stufe V – Vertiefen
V1. Die Fibonacci-Zahlen sind durch f1=f2=1 und fn+1=fn+fn−1 für n≥2 erklärt. Zeigen Sie fn<2n für alle n∈N. Erklären Sie, warum im Induktionsschritt zwei Vorgänger gebraucht werden und warum deshalb f2 gesondert geprüft werden muss.
V2. Setzen Sie voraus: N mit der üblichen Anordnung erfüllt die Wohlordnung (jede nichtleere Teilmenge hat ein kleinstes Element), und jedes n∈N mit n=1 hat einen Vorgänger n−1∈N mit n−1<n und (n−1)+1=n.
(a) Leiten Sie daraus das Induktionsprinzip her.
(b) Sei W=N∪{ω} mit einem neuen Element ω, das größer als jede natürliche Zahl ist, und sei ν(n)=n+1, ν(ω)=ω. Zeigen Sie: Jede nichtleere Teilmenge von W hat ein kleinstes Element, aber das Induktionsprinzip „aus A(1) und A(x)⇒A(ν(x)) für alle x∈W folgt A(x) für alle x∈W“ ist falsch. Welche Voraussetzung aus (a) fehlt?
V3. Zeigen Sie für n∈N: k=0∑nk(kn)=n2n−1.
V4. Sei an=(1+n1)n für n∈N. Zeigen Sie mit der Bernoullischen Ungleichung:
(a) an≥2 für alle n,
(b) an+1≥an für alle n.
V5. Sei f:X→Y eine Abbildung und X=∅. Zeigen Sie:
(a) f ist genau dann injektiv, wenn es ein g:Y→X mit g∘f=idX gibt.
(b) Gibt es ein h:Y→X mit f∘h=idY, so ist f surjektiv.
(c) Wo liegt die Schwierigkeit bei der Umkehrung von (b)?
(d) Zeigen Sie an einem Beispiel, dass in (a) auf X=∅ nicht verzichtet werden kann.
V6. Für a,b∈N schreibe man a∣b („a teilt b“), wenn es ein k∈N mit b=ka gibt.
(a) Zeigen Sie, dass ∣ eine Ordnung auf N ist, aber keine totale.
(b) Auf Z sei a∣b entsprechend mit k∈Z erklärt. Welche der drei Eigenschaften einer Ordnung gehen verloren, und an welcher Stelle Ihres Beweises aus (a)?
(c) Zeigen Sie: Aus a∣b folgt a≤b (für a,b∈N).
(d) Sei ⪯ eine Ordnung auf einer Menge M. Ein m∈M heißt kleinstes Element, wenn m⪯x für alle x∈M gilt, und minimal, wenn aus x∈M und x⪯m stets x=m folgt. Zeigen Sie: Ein kleinstes Element ist minimal, und es ist dann das einzige minimale Element. Ist ⪯ total, so ist jedes minimale Element ein kleinstes.
(e) Bestimmen Sie für M={2,3,4,…} mit der Ordnung ∣ alle minimalen Elemente und zeigen Sie, dass M kein kleinstes Element hat. Vergleichen Sie mit Satz 1.16.
denn (n+2)(2n+3)=2n2+7n+6. Das ist die Formel für n+1.
R2
(a) Verneinung: ∃x∈R∀n∈N:n≤x. Die ursprüngliche Aussage (a) ist wahr; sie besagt, dass die natürlichen Zahlen in R nicht beschränkt sind. Ihr Beweis gehört zu Einheit 2 (archimedische Eigenschaft).
(b) Verneinung: ∀x∈R∃y∈R:xy=y. Die ursprüngliche Aussage (b) ist wahr: x=1 leistet das Verlangte.
(c) Verneinung: ∃ε>0∀δ>0∃x∈R:(∣x−1∣<δ∧∣x2−1∣≥ε). Die Implikation im Inneren wird nach Satz 1.2 (3) zu „Voraussetzung und nicht Behauptung“; die Einschränkungen ε>0 und δ>0 bleiben stehen (Abschnitt 1.2). Die Aussage (c) selbst ist wahr: Zu ε>0 wähle man δ=ε/3, falls ε≤3, und sonst δ=1. Aus ∣x−1∣<δ folgt ∣x+1∣≤∣x−1∣+2<3 und damit ∣x2−1∣=∣x−1∣∣x+1∣<3δ≤ε. Sie besagt, dass x↦x2 an der Stelle 1 stetig ist; der Begriff folgt später.
R3
Nach dem Binomialsatz mit a=2x, b=−1 ist der Summand mit x3 der zu k=2:
(25)(2x)3(−1)2=10⋅8x3=80x3.
Der Koeffizient ist 80.
R4
Nach Abschnitt 1.8 gilt ∣y∣<c⟺−c<y<c für c>0. Mit den strengen Regeln (O5) folgt
∣2x−3∣<5⟺−5<2x−3<5⟺−2<2x<8⟺−1<x<4
(zweiter Schritt: 3 addieren; dritter: mit 21>0 multiplizieren). Die Lösungsmenge ist das offene Intervall (−1,4): alle Punkte, deren Abstand von 23 kleiner als 25 ist, denn ∣2x−3∣<5⟺∣x−23∣<25.
R5
Vorbemerkung. Für n≥m gilt n1≤m1, und stets n1>0 ((O6) und (O3)).
Vereinigung. Behauptung: ⋃nAn={x∈R:0<x<2}.
„⊆“: Liegt x in einem An, so ist 0<n1≤x und x≤2−n1<2. Hier wird (A) nicht gebraucht.
„⊇“: Sei 0<x<2. Dann sind x>0 und 2−x>0. Nach (A) gibt es n1 mit n11<x und n2 mit n21<2−x. Für n=max{n1,n2} ist n1≤n11<x und n1≤n21<2−x, also n1≤x≤2−n1, das heißt x∈An.
Durchschnitt. Behauptung: ⋂nBn={x∈R:0≤x≤1}.
„⊇“: Aus 0≤x≤1 folgt −n1<0≤x≤1<1+n1 für jedes n. Hier wird (A) nicht gebraucht.
„⊆“: Sei x in allen Bn. Angenommen, x<0. Dann ist −x>0, und nach (A) gibt es n mit n1<−x, also x<−n1; dann liegt x nicht in Bn – Widerspruch. Angenommen, x>1. Dann gibt es nach (A) ein n mit n1<x−1, also x>1+n1, und x∈/Bn – Widerspruch. Also ist 0≤x≤1.
Deutung. Jedes An enthält seine Randpunkte, die Vereinigung keinen; jedes Bn 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<n1}=∅ des Abschnitts 1.4.
R6
(a) Nach Definition 1.22 ist ∣x−1∣=x−1 für x≥1 und =1−x für x<1, ebenso ∣x+2∣=x+2 für x≥−2 und =−x−2 für x<−2. Drei Fälle:
x≥1: Die Summe ist (x−1)+(x+2)=2x+1, und 2x+1≤5⟺x≤2. Lösungen: 1≤x≤2.
−2≤x<1: Die Summe ist (1−x)+(x+2)=3≤5. Lösungen: alle x mit −2≤x<1.
x<−2: Die Summe ist (1−x)+(−x−2)=−2x−1, und −2x−1≤5⟺−2x≤6⟺x≥−3 (Multiplikation mit −21 dreht die Ungleichung um, (O2)). Lösungen: −3≤x<−2.
Zusammen: {x∈R:−3≤x≤2}. Geometrisch: alle Punkte, deren Abstände zu 1 und zu −2 zusammen höchstens 5 betragen.
(b) Mit ∣−u∣=∣u∣ und der Dreiecksungleichung:
3=(x+2)+(1−x)≤∣x+2∣+∣1−x∣=∣x+2∣+∣x−1∣.
Gleichheit: Nach der Fallunterscheidung aus (a) ist die Summe im mittleren Fall gleich 3, im ersten Fall 2x+1=3 nur für x=1, im dritten Fall −2x−1=3 nur für x=−2, das nicht zum dritten Fall gehört. Also gilt Gleichheit genau für −2≤x≤1, das heißt für die Punkte zwischen −2 und 1 einschließlich der Endpunkte. (Vergleich mit B8 (c): Gleichheit genau, wenn (x+2)(1−x)≥0, und das ist dieselbe Bedingung.)
B1
Induktion. Anfang n=1: links 1⋅1!=1, rechts 2!−1=1. Schritt: Gilt die Formel für n, so ist
denn jede Fakultät von 2! bis n! tritt einmal mit Plus und einmal mit Minus auf. Wegen 1!=1 ist das die Behauptung. Der zweite Weg erklärt, warum gerade (n+1)!−1 herauskommt; der erste setzt die Formel als bekannt voraus.
B2
(a) Sei f(x)=f(x′). Dann ist g(f(x))=g(f(x′)), und weil g∘f injektiv ist, folgt x=x′.
(b) Sei z∈Z. Weil g∘f surjektiv ist, gibt es x∈X mit g(f(x))=z. Dann ist y=f(x)∈Y ein Element mit g(y)=z.
(c) f(n)=n+1 und g(1)=1, g(n)=n−1 für n≥2 (Vorgänger, Abschnitt 1.6). Dann ist g(f(n))=g(n+1)=n, also g∘f=idN. f nimmt den Wert 1 nicht an (P2), und g(1)=g(2)=1.
Für eine endliche Menge X mit n Elementen ist eine injektive Abbildung f:X→X auch surjektiv: f ist eine Bijektion von X auf f(X), also hat die Teilmenge f(X)⊆X genau n Elemente und ist nach den Zählregeln des Abschnitts 1.7 ganz X. Nach (a) wäre f injektiv, also bijektiv, und dann wäre g=g∘f∘f−1=f−1 ebenfalls bijektiv. Das Beispiel zeigt, dass sich unendliche Mengen anders verhalten: 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=1 und b=2 gibt 3n=(1+2)n=∑k=0n(kn)1n−k2k=∑k=0n(kn)2k.
(b) Für 0≤k≤n sei Pk die Menge der gesuchten Paare (S,T), bei denen T genau k Elemente hat. Jedes Paar liegt in genau einem Pk, denn T⊆X hat nach den Zählregeln eine eindeutig bestimmte Elementzahl k≤n. Halten wir eine k-elementige Teilmenge T fest. Die Paare (S,T) mit diesem T entsprechen umkehrbar eindeutig den Teilmengen S von T, vermöge (S,T)↦S und S↦(S,T); nach Folgerung 1.21 sind es 2k. Nach Satz 1.19 gibt es (kn) solche T, und Paare mit verschiedenem T sind verschieden. Also zerfällt Pk in (kn) disjunkte Teile mit je 2k Elementen und hat nach der Zählregel für disjunkte Vereinigungen (kn)2k Elemente. Dieselbe Regel, auf P0,…,Pn angewandt, ergibt mit (a) insgesamt ∑k=0n(kn)2k=3n Paare.
Deutung. Ein Paar (S,T) legt für jedes x∈X eine von drei Möglichkeiten fest: x∈S, oder x∈T∖S, oder x∈/T. Das macht die Zahl 3n plausibel; ein Beweis auf diesem Weg bräuchte eine Zählregel für Auswahlen, die Abschnitt 1.7 nicht bereitstellt. Für n=1, X={x}, sind es die drei Paare (∅,∅), (∅,X) und (X,X).
B4
„⇐“: Sei f injektiv. Die Inklusion „⊆“ gilt immer (Satz 1.11 (3)). Sei y∈f(A1)∩f(A2). Dann gibt es a1∈A1 und a2∈A2 mit f(a1)=y=f(a2). Aus der Injektivität folgt a1=a2; dieses Element liegt in A1∩A2, also y∈f(A1∩A2).
„⇒“: Kontraposition. Sei f nicht injektiv; dann gibt es x=x′ mit f(x)=f(x′). Für A1={x}, A2={x′} ist A1∩A2=∅, also f(A1∩A2)=∅, aber f(A1)∩f(A2)={f(x)}=∅.
B5
Reflexiv: ab=ba. Symmetrisch: Aus ad=bc folgt cb=da. Transitiv: Sei (a,b)∼(c,d) und (c,d)∼(e,f), also ad=bc und cf=de. Dann ist
(af)d=(ad)f=(bc)f=b(cf)=b(de)=(be)d,
also d(af−be)=0. Wegen d=0 folgt af=be, das heißt (a,b)∼(e,f). Genau hier geht d=0 ein, zusammen mit der Nullteilerfreiheit von Z. Ließe man die zweite Komponente 0 zu, wäre (1,1)∼(0,0) und (0,0)∼(2,1), aber nicht (1,1)∼(2,1).
Wohldefiniertheit: Sei (a,b)∼(a′,b′) und (c,d)∼(c′,d′), also ab′=a′b und cd′=c′d. Zu zeigen ist (ad+bc)b′d′=(a′d′+b′c′)bd. Es ist
Außerdem liegt bd wieder in N, das Ergebnis also in X.
B6
(a) Eine Implikation P⇒Q ist nur dann falsch, wenn Q falsch und P wahr ist. Es genügt also, die Belegungen zu betrachten, in denen Q=(A⇒C) falsch ist, und dort zu zeigen, dass P falsch ist. A⇒C ist genau dann falsch, wenn A wahr und C falsch ist. Ist dann B wahr, so ist B⇒C falsch; ist B falsch, so ist A⇒B falsch. In beiden Fällen ist (A⇒B)∧(B⇒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 A falsch, B beliebig, C falsch: A⇒B ist wahr, also ist (A⇒B)⇒C falsch. Dagegen ist A⇒(B⇒C) wahr, weil A falsch ist. Die Klammerung bei mehrfachen Implikationen ist also nicht gleichgültig.
(c) Die Verneinung der Behauptung „m gerade oder n gerade“ ist nach Satz 1.2 (1) „m ungerade und n ungerade“ (jede ganze Zahl ist entweder gerade oder ungerade). Zu zeigen ist also: Sind m und n ungerade, so ist mn ungerade. Mit m=2k+1, n=2l+1, k,l∈Z, ist
mn=4kl+2k+2l+1=2(2kl+k+l)+1,
also ist mn ungerade.
(d) Angenommen, a=b. Dann ist a−b=0, also ∣a−b∣>0, und ε=21∣a−b∣ ist positiv. Die Voraussetzung gibt für dieses ε:
∣a−b∣≤21∣a−b∣.
Subtraktion von 21∣a−b∣ (O1) ergibt 21∣a−b∣≤0, das heißt ε≤0 – im Widerspruch zu ε>0. Die Annahme a=b diente dazu, ein positivesε 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.
Beide Seiten der ersten Regel sind Teilmengen von X und haben dieselben Elemente. Die zweite Regel ebenso: Für x∈X gilt x∈/⋂iAi⟺¬(∀i:x∈Ai)⟺∃i:x∈/Ai⟺x∈⋃i(X∖Ai). Der Beweis benutzt nichts über I. Für I=∅ lauten die Regeln X∖∅=X und X∖X=∅.
(b) f(R∖{1}) enthält f(−1)=1, aber R∖f({1})=R∖{1} enthält 1 nicht; die erste Inklusion ist falsch. Umgekehrt liegt −1 in R∖{1}, aber nicht in f(R∖{1}), weil x2≥0 für jedes x gilt (O3); die zweite Inklusion ist falsch.
(c) Injektiv. Sei f injektiv und y∈f(X∖A), also y=f(x) mit x∈/A. Läge y in f(A), so wäre y=f(a) mit a∈A, und aus f(a)=f(x) folgte a=x∈A – Widerspruch. Also y∈Y∖f(A). Ist f nicht injektiv, etwa f(x)=f(x′) mit x=x′, so wähle A={x′}: Dann liegt f(x) in f(X∖A) und in f(A), die Inklusion ist verletzt.
Surjektiv. Sei f surjektiv und y∈/f(A). Es gibt x mit f(x)=y, und x∈/A (sonst wäre y∈f(A)), also y∈f(X∖A). Gilt umgekehrt die Inklusion für alle A, so für A=∅: Y⊆f(X), also ist f surjektiv.
Folglich gilt f(X∖A)=Y∖f(A) für alle A genau dann, wenn f bijektiv ist. Das Urbild verträgt sich dagegen nach Satz 1.11 mit allen Mengenoperationen, ohne Voraussetzung an f.
B8
(a) Anfang n=1: ∣x1∣≤∣x1∣. Schritt: Gelte die Ungleichung für n. Mit Satz 1.23 und (O1):
Dreiecksungleichung und ∣uv∣=∣u∣∣v∣ ergeben die Behauptung. Ist ∣x−a∣≤1, so ist ∣x∣=∣(x−a)+a∣≤∣x−a∣+∣a∣≤1+∣a∣, und Multiplikation mit ∣y−b∣≥0 (O2) gibt ∣x∣∣y−b∣≤(∣a∣+1)∣y−b∣. Addiert man auf beiden Seiten ∣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∣, ∣y−b∣ und den festen Zahlen a, b ab. Sind x nahe bei a und y nahe bei b, so ist xy nahe bei ab; das ist der Kern der Produktregel für Grenzwerte. Die Bedingung ∣x−a∣≤1 dient nur dazu, den Faktor ∣x∣ durch eine feste Zahl zu ersetzen.
(c) Für jedes u∈R ist ∣u∣2=∣u2∣=u2, weil u2≥0 (O3). Also
∣x+y∣2=x2+2xy+y2,(∣x∣+∣y∣)2=x2+2∣xy∣+y2.
Für u,v≥0 gilt u=v⟺u2=v2: „⇒“ ist klar; aus u2=v2 folgt (u−v)(u+v)=0, also u=v oder u+v=0, und im zweiten Fall ist 0≤u≤u+v=0, also u=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∣, v=∣x∣+∣y∣ folgt:
∣x+y∣=∣x∣+∣y∣⟺xy=∣xy∣⟺xy≥0,
der letzte Schritt nach Definition 1.22 (für z<0 ist ∣z∣=−z=z). In Worten: In der Dreiecksungleichung gilt genau dann Gleichheit, wenn x und y nicht entgegengesetzte Vorzeichen haben.
V1
Die Rekursion greift auf zwei Vorgänger zurück; der Schritt braucht deshalb die Aussage für n und für n−1. Wir benutzen Satz 1.14 mit n0=1.
Anfang: f1=1<2. Schritt: Seien f1<21,…,fn<2n bereits gezeigt. Für n=1 greift die Rekursion nicht (sie gilt erst für n≥2 und würde sonst f0 verlangen); hier prüft man direkt f2=1<4. Für n≥2 ist
fn+1=fn+fn−1<2n+2n−1<2n+2n=2n+1.
Wer nur f1 prüft und den Schritt ohne Fallunterscheidung führt, hat den Übergang von 1 auf 2 nicht bewiesen; das ist dieselbe Fehlerquelle wie in (G3). Gleichwertig kann man die verstärkte Aussage „fn<2n und fn+1<2n+1“ mit gewöhnlicher Induktion beweisen; auch dort steckt die Prüfung von f2 im Anfang.
V2
(a) Sei A(n) eine Aussage mit A(1) und A(n)⇒A(n+1) für alle n. Angenommen, A(n) gilt nicht für alle n. Dann ist M={n∈N:A(n) ist falsch} nicht leer und hat nach der Wohlordnung ein kleinstes Element m. Wegen A(1) ist m=1, also existiert m−1∈N. Wegen m−1<m liegt m−1 nicht in M; A(m−1) ist also wahr. Nach dem Schritt ist dann A((m−1)+1)=A(m) wahr – Widerspruch zu m∈M.
Benutzt wurden die Wohlordnung, die Existenz des Vorgängers und m−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, insbesondere der Vorgängereigenschaft, folgt jede der beiden Aussagen aus der anderen.
(b) Sei T⊆W nicht leer. Enthält T eine natürliche Zahl, so hat T∩N nach Satz 1.16 ein kleinstes Element t, und t ist auch kleiner als ω, also kleinstes Element von T. Andernfalls ist T={ω} mit kleinstem Element ω. Sei nun A(x) die Aussage „x∈N“. A(1) gilt; für n∈N folgt A(n+1); für x=ω ist A(ω)⇒A(ν(ω)) die Implikation A(ω)⇒A(ω), also wahr. Trotzdem ist A(ω) falsch. Es fehlt die Vorgängereigenschaft: ω=1 ist kein Nachfolger eines anderen Elements. Der Beweis aus (a) bricht an der Stelle „m=1, also existiert m−1“ ab, wenn das kleinste Gegenbeispiel m=ω ist.
Deutung: Links zählt man alle Paare aus einer Teilmenge und einem ausgezeichneten Element darin. Rechts wählt man zuerst das Element (n Möglichkeiten) und dann eine beliebige Teilmenge der übrigen n−1 Elemente.
denn n(n+2)=(n+1)2−1. Bernoulli mit x=−(n+1)21≥−1 und Exponent n+1 gibt
(1−(n+1)21)n+1≥1−(n+1)2n+1=1−n+11=n+1n.
Also ist anan+1≥n+1n⋅nn+1=1.
Die Folge (an) wächst also. Später kommt hinzu, dass sie nach oben beschränkt ist; ihr Grenzwert ist die Zahl e.
V5
(a) „⇐“: Aus f(x)=f(x′) folgt x=g(f(x))=g(f(x′))=x′. „⇒“: Sei f injektiv und x0∈X fest (hier wird X=∅ gebraucht). Setze g(y)=x, falls y=f(x) für ein x∈X – dieses x ist wegen der Injektivität eindeutig –, und g(y)=x0, falls y∈/f(X). Dann ist g(f(x))=x für alle x.
(b) Für y∈Y ist y=f(h(y)), also liegt y im Bild von f.
(c) Ist f surjektiv, so ist jede der Mengen f−1({y}) nicht leer, und eine Rechtsinverse h entsteht, indem man aus jeder dieser Mengen ein Element h(y) auswählt. Für endliches Y geht das durch Induktion über die Elementzahl. Für unendliches Y 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) dort eindeutig bestimmt oder einheitlich gleich x0 war.
(d) X=∅, Y={1}, f:∅→Y die leere Abbildung (Abschnitt 1.5). Sie ist injektiv: Es gibt keine x,x′, an denen die Bedingung verletzt sein könnte. Eine Abbildung g:{1}→∅ gibt es aber nicht, denn g(1) müsste ein Element der leeren Menge sein.
V6
(a) Reflexiv:a=1⋅a. Transitiv: Aus b=ka und c=lb folgt c=(lk)a mit lk∈N. Antisymmetrisch: Aus b=ka und a=lb folgt a=lka, also a(lk−1)=0 und wegen a=0 dann lk=1. Wäre k≥2, so wäre lk≥k≥2 (wegen l≥1); also k=1 und b=a.
Nicht total:2∤3, denn 2k ist 2 für k=1 und mindestens 4 für k≥2; und 3∤2, denn 3k≥3 für jedes k∈N.
(b) Reflexivität und Transitivität bleiben mit derselben Rechnung erhalten. Die Antisymmetrie geht verloren: −1=(−1)⋅1 und 1=(−1)⋅(−1), also 1∣−1 und −1∣1, aber 1=−1. Im Beweis aus (a) bricht der Schluss „lk=1⇒k=1“: In Z ist auch k=l=−1 möglich. Die Voraussetzung k∈N wird also genau an dieser Stelle gebraucht.
(c) Ist b=ka mit k≥1, so ist b−a=(k−1)a≥0 nach (O2), weil k−1≥0 und a>0.
(d) Sei m kleinstes Element und x⪯m. Da auch m⪯x, folgt x=m aus der Antisymmetrie; m ist minimal. Ist m′ ein weiteres minimales Element, so gilt m⪯m′, und die Minimalität von m′ ergibt m=m′. Sei nun ⪯ total und m minimal. Für x∈M gilt x⪯m oder m⪯x; im ersten Fall ist x=m und m⪯x wegen der Reflexivität. Also ist m⪯x für alle x.
(e) Eine Primzahl ist eine Zahl p≥2, deren einzige Teiler in N die Zahlen 1 und p sind. Ein m∈M ist minimal, wenn jeder Teiler x∈M von m gleich m ist. Die Teiler von m in N sind 1 und die Teiler ≥2, und diese liegen in M. Also ist m genau dann minimal, wenn 1 und m seine einzigen Teiler sind: Die minimalen Elemente sind genau die Primzahlen. Insbesondere sind 2 und 3 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 ≤ hat M das kleinste Element 2. 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 ≤ auf R fallen „minimal“ und „kleinst“ nach (d) zusammen, in einer nicht totalen Ordnung nicht.