Vorkurs Skript

Vorkurs Mathematik für Mathematiker SS 2014Universität Bielefeld, Fakultät für Mathematik

Ralf Kemper

10. März 2014

Inhaltsverzeichnis

1 Vorwort 4

2 Für wen ist dieser Vorkurs geeignet? 5

3 Ablauf des Vorkurses 5

4 Ziel des Vorkurses 6

5 Form von Lehrveranstaltungen 6

5.a Was ist eine Vorlesung? . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5.b Was ist ein Tutorium (Übung) und was ist eine Präsenzübung? . . . 7

5.c Was ist ein Lernzentrum Mathematik? . . . . . . . . . . . . . . . . . . 7

6 Informationen für Schüler und Studienanfänger 8

6.a Schwierigkeiten beim Studienbeginn . . . . . . . . . . . . . . . . . . 8

7 Rat von Professorinnen und Professoren 8

8 Warum Mathematik? Ein Anwendungsbeispiel 8

1

INHALTSVERZEICHNIS 2

9 Axiome, Definitionen, Vermutungen, Behauptungen, Sätze und Bewei-se 9

9.a Peano-Axiome und elementare Definitionen und Aussagen . . . . . 9

9.b Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

9.c Vermutungen, Behauptungen und Sätze . . . . . . . . . . . . . . . . 13

9.c.1 Positive Beispiele und Gegenbeispiele . . . . . . . . . . . . . . 13

9.d Beweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

9.d.1 Positive Beispiele und Gegenbeispiele . . . . . . . . . . . . . . 14

9.e Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

10 Direkte Beweise und Beweise durch Widerspruch, Kontraposition undFallunterscheidung 15

10.a Direkter Beweis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

10.a.1 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 16

10.b Beweis durch Widerspruch . . . . . . . . . . . . . . . . . . . . . . . . 17

10.b.1 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 20

10.c Beweis durch Kontraposition . . . . . . . . . . . . . . . . . . . . . . . 20

10.c.1 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 20

10.d Beweis durch Fallunterscheidung . . . . . . . . . . . . . . . . . . . . 20

10.d.1 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 21

11 Beweis durch vollständige Induktion 22

11.a Der Irrtum von Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

11.b Summenformel von Maurolicus . . . . . . . . . . . . . . . . . . . . . 23

11.c Summenformel von Gauß . . . . . . . . . . . . . . . . . . . . . . . . . 25

11.d Summenformel der endlichen geometrischen Reihe . . . . . . . . . 27

11.e Teiler natürlicher Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 27

11.f Alle Dinge sind identisch . . . . . . . . . . . . . . . . . . . . . . . . . 28

11.g Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2

INHALTSVERZEICHNIS 3

12 Aussagenlogik und Quantoren 29

12.a Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29


12.b Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32


13 Mengen 33

13..2 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 37

13..3 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 40

14 Relationen und Äquivalenzrelationen 40

14.a Relationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

14.b Äquivalenzrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41



15 Abbildungen 45

15..3 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 54

15.a Verknüpfungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56


16 Restklassenrechnung 58

16..2 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 60

17 Kardinalitäten und Elementare Kombinatorik 60

17.a Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

18 Reelle Zahlen 68

18.a Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

18.b Vollständigkeit der reellen Zahlen . . . . . . . . . . . . . . . . . . . . 73

18.c Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

18.d Abschließende Bemerkung zum Axiomensystem von R . . . . . . . 78

3

1 VORWORT 4

19 Folgen und Konvergenz 78

19.a Folgen, Betragsfunktion und Konvergenz von Folgen . . . . . . . . . 78



19.b Algebraische Operationen von konvergenten Folgen . . . . . . . . . 85


19.c Monotone Folgen, Teilfolgen und Häufungspunkte . . . . . . . . . . 90

19.c.1 Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . 93

20 Lehrbücher zu Analysis I, II und Lineare Algebra I, II 93

21 Griechisches Alphabet 95

22 Mathematisches Wörterbuch (englisch) 95

23 Studienberatung 95

24 Zusammenfassung aller im Text enthaltenen Übungsaufgaben 96

24.a Übungsblatt 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

24.b Übungsblatt 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

24.c Übungsblatt 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

24.d Übungsblatt 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

25 Weitere Übungsaufgaben für die Hörsaalübungen 105

1 Vorwort

Das Skript ist grundsätzlich für ein Selbststudium geeignet. Eine Teilnahme amVorkurs wird aber empfohlen. Denn auf viele Fragen zu der Vorlesung, den Übungs-aufgaben und allgemein zum Studium gibt es von den Tutoren (Bachelor- oderMasterstudierenden) oder von anderen TeilnehmerInnen Antworten. Die für dasStudium wichtige Fähigkeit der mathematischen Kommunikation kann hier be-reits erlernt werden. Und oftmals bilden sich im Vorkurs schon die ersten für einerfolgreiches Studium wichtigen Arbeitsgruppen.

4

3 ABLAUF DES VORKURSES 5

Ein hinreichendes Verständnis einer Vorlesung wird erst durch das Nachberei-ten der Vorlesung und durch das Bearbeiten vieler mit der Vorlesung zusam-menhängender Übungsaufgaben erreicht. Solche Übungsaufgaben sind in denKapiteln oder Abschnitten enthalten. Dieselben Aufgaben sind zusätzlich im vor-letzten Kapitel auf vier Übungsblättern zusammengefasst. Das letzte Kapitel be-steht aus einer Sammlung weiterer Übungsaufgaben für die Hörsaalübungen.

Das Skript ist zu einem Drittel in großen Teilen aus dem Vorkursskript von Dr.Fabian Meier (Universität Bielefeld, Vorkurs, WS 10/11) entstanden. Die Kapitel„Kardinalitäten und Elementare Kombinatorik” und „Folgen und Konvergenz”wurden ebenfalls in großen Teilen und das Kapitel „Reelle Zahlen” zur Hälfte ei-nem Skript von Prof. Dr. Daniel Grieser (Universität Oldenburg, Analysis I, WS09/10) entnommen. Die Kapitel „Mengen“ und „Abbildungen“ basieren auf ei-nem Kapitel des Vorkursskripts von Dr. Martin Fluch (Universität Bielefeld, Vor-kurs, SS 12). Ich möchte allen genannten Autoren für ihre Zustimmung zur Ver-wendung ihrer Skripte danken. Herrn Dr. Jason Uhing und der Fachschaft Ma-thematik (alle Universität Bielefeld, Fakultät für Mathematik) möchte ich für ih-re Vorschläge zu dem Skript und der Fachschaft zudem für ein erstes Korrektur-lesen danken.

2 Für wen ist dieser Vorkurs geeignet?

Der Vorkurs ist für die Studiengänge Bachelor Mathematik, Bachelor Wirtschafts-mathematik und Lehramt Mathematik Gymnasium und Gesamtschule, Sekun-darstufe II, geeignet. Für andere Studiengänge ist er nur dann geeignet, wennmathematische Lehrveranstaltungen aus den obigen Studiengängen (trifft in Ana-lysis I auf Studierende der Physik zu) oder ähnliche mathematische Lehrveran-staltungen belegt werden. Letztere gibt es in Physik und in sehr begrenztem Um-fang ähnlich in den Fächern Bioinformatik, Genomforschung, Kognitive Infor-matik und Naturwissenschaftliche Informatik.

Studierende der Studiengänge Lehramt Grund-Haupt-und Realschule und Phy-sik finden für die Zeit vor dem SS 2014 auf den Seiten der zentralen Studienbe-ratung

http://www.uni-bielefeld.de/Universitaet/Einrichtungen/ZSB/vorkurse.html

eigene Vorkurse. Für Hörer anderer Studienfächer ist für eine Auffrischung schul-mathematischer Kenntnisse der Vorkurs ”Mathematik für Lehramt“ für Höreraller Fakultäten und Fächer geöffnet. Dieser Vorkurs hier ist dafür nicht geeig-net.

3 Ablauf des Vorkurses

Der Vorkurs wird vom 11.3.14 - 4.4.14 wie folgt stattfinden.

5

5 FORM VON LEHRVERANSTALTUNGEN 6

10.15 - 11.45 Vorlesung (in den letzten Tagen Hörsaalübungen statt Vorlesung)11.45 - 13.15 Pause13.15 - 14.15 Uhr Vorlesungsnachbereitung unter Anleitung von Tutoren14.15 - 14.30 Pause14.30 - 15.45 Uhr Übungen unter Anleitung von Tutoren

Vorlesung in Hörsaal H 16

Es finden vier Gruppen für die Vorlesungsnachbereitung und für die Übungenparallel statt. Jeder kann seine Übungsgruppe wählen.

• Mirko Getzin (Raum V3-204, am 19.03.14 U5-133)

• Jonas Jalowy (Raum V4-112, am 03.04.14 U5-133)

• Nils Romaker (Raum V4-116)

• Arthur Sinulis (Raum V5-148)

4 Ziel des Vorkurses

Universitäts- und Schulmathematik unterscheiden sich in ihren Inhalten undMethoden sehr. Dieser Vorkurs soll den Übergang erleichtern. Dabei wird esnicht darum gehen, Schulmathematik zu wiederholen, sondern darum, einenZugang zu der Denk- und Arbeitsweise der Universitätsmathematik zu finden.Für das Studium können Vorkenntnisse zentraler mathematischer Begriffe undBeweismethoden sehr hilfreich sein. Ebenso das bereits zuvor erlernte Erkennenvon Zusammenhängen von Axiomen, Definitionen und mathematischen Sätzeneiner Vorlesung und der Zusammenhänge von Vorlesung und Übungsaufgaben.

5 Form von Lehrveranstaltungen

Vorlesungen, Tutorien (= Übungen), Präsenzübungen und ggf. freiwillig die Be-treuung im Lernzentrum Mathematik werden in den nächsten zwei Semesternin Analysis I, II und Lineare Algebra I, II die Veranstaltungsformen des Studi-ums sein. Zum Nachbereiten der Vorlesung gibt es während des Studiums keineLehrveranstaltung. Diese für das Verständnis sehr wichtige Nachbereitung kön-nen Studierende alleine oder in selbst gebildeten Arbeitsgruppen durchführen.

6

5 FORM VON LEHRVERANSTALTUNGEN 7

5.a Was ist eine Vorlesung?

Eine Vorlesung vermittelt Inhalte in komprimierter Form. Etwa 90 Minuten langerklärt ein Dozent an der Tafel Definitionen, Sätze und Beweise, während dieStudierenden zuhören und (sofern von dem Dozenten kein Skript herausge-geben wird) mitschreiben. Kurze Zwischenfragen können gestellt werden, ei-ne Diskussion kommt aber normalerweise nicht zustande. Studierende solltenso viel wie möglich während der Vorlesung nachvollziehen, und sich Notizenzur Vorbereitung der Vorlesungsnachbereitung machen. Alle Details einer gera-de stattfindenden Vorlesung zu verstehen, ist kaum möglich. Daher besteht ne-ben der Bearbeitung der Übungsaufgaben ein großer Teil des Studiums aus demNachbereiten der Vorlesungen. Manche können dies besser, wenn es in Grup-pen stattfindet, andere besser alleine. Ob Lehrbücher hierfür hilfreich sind, soll-te jeder ausprobieren. Meistens genügt das Skript oder die Mitschrift der Vorle-sung.

5.b Was ist ein Tutorium (Übung) und was ist eine Präsenzübung?

Zu jeder Vorlesung gibt es ein Tutorium (Übung) und zu den Vorlesungen Ana-lysis I, II und Lineare Algebra I, II zusätzlich eine Präsenzübung. Sie finden inwesentlich kleineren Gruppen statt als Vorlesungen; in der Regel etwa 20 Teil-nehmerInnen. Betreut werden sie fast immer von Tutoren. Es gibt zwei Artenvon Übungen. In den klassischen Übungen (Tutorien) werden die Lösungen derAufgaben besprochen, die die Studierenden in der zurückliegenden Woche zuHause bearbeitet haben. Und es können Fragen zur Vorlesung gestellt werden.In den Präsenzübungen werden unter Anleitung von einem Tutor zusätzlicheÜbungsaufgaben in Gruppen bearbeitet.

5.c Was ist ein Lernzentrum Mathematik?

Im Lernzentrum der Fakultät für Mathematik

http://www.math.uni-bielefeld.de/lernzentrum/

werden während der Vorlesungszeit 18 Stunden in der Woche Studierende derVorlesungen Analysis I, II und Lineare Algebra I, II, die selbstständig mathema-tisch aktiv die Übungsaufgaben dieser Vorlesungen bearbeiten oder die Vorle-sung nachbereiten, durch drei wissenschaftliche Mitarbeiter mit Tipps, Hinwei-sen und Erklärungen unterstützt. Die Teilnahme ist freiwillig. Jede(r) kann kom-men und gehen, wann sie/er will. Eine Anmeldung ist nicht notwendig.

7

8 WARUM MATHEMATIK? EIN ANWENDUNGSBEISPIEL 8

6 Informationen für Schüler und Studienanfänger

Auf der folgenden Seite der Fakultät für Mathematik der Universität Bielefeldsind einige Informationen für die Zeit vor dem Studium zusammengefasst.

http://www.math.uni-bielefeld.de/studium/studieninteressierte/

6.a Schwierigkeiten beim Studienbeginn

Insbesondere die typischen Schwierigkeiten beim Studienbeginn im Fach Ma-thematik sind auf der folgenden Seite beschrieben.

http://www.math.uni-bielefeld.de/studieninteressierte/schwierigkeiten-beim-studienbeginn/

7 Rat von Professorinnen und Professoren

Herr Prof. Dr. Manfred Lehn (Universität Mainz) hat aufgeschrieben, wie einÜbungsblatt sinnvoll bearbeitet werden sollte.

http://www.mathematik.uni-mainz.de/Members/lehn/le/uebungsblatt

Wie sich Studierende auf eine Prüfung vorbereiten sollten, hat Frau Prof. Dr. Bir-git Richter (Universität Hamburg) dargestellt.

http://www.math.uni-hamburg.de/home/richter/pruefungen.html

Herr Prof. Dr. Claus Scheiderer (Universität Konstanz) hat Empfehlungen an dieHörer einer Erstsemestervorlesung formuliert.

http://www.math.uni-konstanz.de/~scheider/vorles/1213ws/LA.html

8 Warum Mathematik? Ein Anwendungsbeispiel

Auf der folgenden Seite des Mathematischen Instituts der Universität Köln isteine Annäherung an den Sinn der Mathematik formuliert. Es wird insbeson-dere die zu dem mathematischen Teilgebiet Funktionalanalysis gehörende so-genannte Radon-Transformation als mathematische Grundlage der modernenComputer-Tomographie allgemein verständlich beschrieben.

http://www.mi.uni-koeln.de/home-institut/Alle/Lehre-Studium/Studiengaenge/Warum_Mathematik.de.html

8

9 AXIOME, DEFINITIONEN, VERMUTUNGEN, BEHAUPTUNGEN, SÄTZEUND BEWEISE 9

9 Axiome, Definitionen, Vermutungen, Behauptungen, Sät-ze und Beweise

Universitätsmathematik besteht vereinfacht gesagt fast nur aus Axiomen, Defi-nitionen, Vermutungen, Behauptungen, Sätzen und Beweisen.

9.a Peano-Axiome und elementare Definitionen und Aussagen

Ein Axiom kann in einer gegebenen mathematischen Theorie nicht bewiesenwerden. Es ist Teil eines Axiomensystems, und dieses System bildet die Grund-lage der Theorie.

Wie sollen Mathematiker die Menge {1,2,3...} der natürlichen Zahlen definieren?Auf diese Frage fanden 1888 Richard Dedekind1 und 1889 der italienische Ma-thematiker Giuseppe Peano2 eine Antwort. Die Peano-Axiome (auch Dedekind-Peano-Axiome oder Peano-Postulate) charakterisieren die natürlichen Zahlenund ihre Eigenschaften.

1. 1 ist eine natürliche Zahl.

2. Zu jeder natürlichen Zahl n gibt es genau einen Nachfolger n′, der eben-falls eine natürliche Zahl ist.

3. Es gibt keine natürliche Zahl, deren Nachfolger 1 ist.

4. Jede natürliche Zahl ist Nachfolger höchstens einer natürlichen Zahl.

5. Für jede Menge X , welche die beiden Eigenschaften

• 1 ist ein Element von X

• Ist eine natürliche Zahl n ein Element von X , so ist n′ ein Elementvon X

erfüllt, gilt, dass jede natürliche Zahl ein Element von X ist.

1Julius Wilhelm Richard Dedekind (? 6. Oktober 1831 in Braunschweig; † 12. Februar 1916ebenda) war ein deutscher Mathematiker. Er gab 1888 in der Schrift „Was sind und was sollendie Zahlen’?” die erste exakte Einführung der natürlichen Zahlen durch Axiome. In seiner SchriftStetigkeit und Irrationalzahlen von 1872 gab er die erste exakte Definition der reellen Zahlen mitHilfe der Dedekindschen Schnitte (Quelle: http://de.wikipedia.org/wiki/Richard_Dedekind).

2Giuseppe Peano (? 27. August 1858 in Spinetta, heute Teil von Cuneo, Piemont; † 20.April 1932 in Turin bei Messina) war ein italienischer Mathematiker. Er arbeitete in Tu-rin und befasste sich mit mathematischer Logik, mit der Axiomatik der natürlichen Zah-len (Entwicklung der Peano-Axiome) und mit Differentialgleichungen erster Ordnung (Quelle:http://de.wikipedia.org/wiki/Giuseppe_Peano).

9


Durch das letzte Axiom wird die Menge der natürlichen Zahlen die „kleinsteMenge”, welche die beiden in diesem Axiom formulierten Eigenschaften hat.Durch dieses Axiom ist sichergestellt, dass eine Aussage, die für 1 und für jedenNachfolger jeder natürlichen Zahl gilt, für jede natürliche Zahl gilt. Dies ist dieGrundlage der später folgenden Beweismethode der sogenannten VollständigenInduktion.

Damit wir im Folgenden vor Einführung des Mengenbegriffs bereits mathemati-sche Definitionen und Aussagen formulieren können, ziehen wir einige einfacheDefinitionen vor. Manche davon sind vorläufig, wir werden sie später präzisie-ren.

Ist M eine Menge und x ein Objekt, so schreiben wir x ∈ M (bzw. x ∉ M), wenn xin der Menge M enthalten (bzw. nicht enthalten) ist, und sagen, dass x ein (bzw.kein) Element von M ist. Ist eine Menge M nach Definition gleich einer MengeN , so schreiben wir M := N . Für die Menge M := {2,4,6} gilt beispielsweise 4 ∈ Mund 5 ∉ M .

Sind M und N Mengen, und gilt für jedes Element x ∈ M x ∈ N , so heißt M eineTeilmenge von N , und wir schreiben M ⊆ N , andernfalls M * N . Beispielsweisegilt für die obige Menge M und für die Menge N := {2,4,6,8} M ⊆ N .

Im Folgenden seien

N := {1,2,3...} die Menge der natürlichen Zahlen,

Z := {...,−2,−1,0,1,2, ...} die Menge der ganzen Zahlen,

N0 := {0,1,2,3...} die Menge der natürlichen Zahlen einschließlich der ganzenZahl 0,

Q die Menge der rationalen Zahlen, d. h. die Menge aller Quotienten ab mit a,b ∈

Z und b 6= 0,

R die Menge der reellen Zahlen,

Nn := {1,2, . . . ,n} für n ∈N.

P := {2,3,5,7,11, ...} sei die Menge der Primzahlen, d. h., die Menge der natürli-chen Zahlen n größer als 1, die nur durch 1 und durch n teilbar sind.

„+” bezeichnet die übliche Addition und „·” die übliche Multiplikation von reel-len Zahlen.

Sind x und y reelle Zahlen, so schreiben wir x < y (x É y , x > y , x ≥ y), wenn xkleiner als y (x kleiner oder gleich y , x größer als y , x größer oder gleich y) ist.

Gilt für eine reelle Zahl x x > 0 (bzw. x < 0), so heißt x positiv (bzw. negativ).

Ist eine reelle Zahl x nach Definition gleich einer reellen Zahl y , so schreiben wirx := y . Ein Beispiel ist x :=−1.

10


Für jede reelle Zahl x ≥ 0 istp

x := y die eindeutig bestimmte reelle Zahl y ≥ 0mit y2 = x.

Für eine reelle Zahl x und n ∈ N sei wie üblich xn := x · x · ... · x (n-Faktoren),x0 := 1, und im Fall x 6= 0 sei x−n := 1

xn .

Des weiteren seien die üblichen Rechenregeln für reelle Zahlen bekannt. Als Bei-spiel notieren wir die sogenannten binomischen Formeln.

Für alle a,b ∈R gilt a2 −b2 = (a −b) · (a +b) und (a ±b)2 = a2 ±2 ·a ·b +b2.

Sofern kein Missverständnis möglich ist, schreiben wir ab := a ·b für a,b ∈R.

Eine natürliche Zahl n ∈ {1,3,5, ...} heißt ungerade.

Bemerkung 9(1). Mittels der Peano-Axiome können wir auf der Menge N eineAddition und eine Multiplikation definieren. Für alle n,m ∈N seien

n +1 := n′, n +m′ := (n +m)′

undn ·1 := n, n ·m′ := (n ·m)+n.

Dass hierdurch für alle natürlichen Zahlen m und n m +n und m ·n definiertist, folgt später mittels der bereits erwähnten vollständigen Induktion.

Bemerkung 9(2). Lassen wir von den Peano-Axiomen einzelne Axiome weg,so erhalten wir nicht die Menge der natürlichen Zahlen. Andererseits gibt esvon der Menge N der natürlichen Zahlen verschiedene Mengen, die alle Peano-Axiome erfüllen.

1. Sei M := {q ∈Q | 1 É q}(gelesen: M ist definiert als die Menge der rationalen Zahlen q mit q grö-ßer oder gleich 1)und für q ∈ M sei der Nachfolger definiert als q ′ := q + 1. Dann sind dieersten vier Peano-Axiome, wegen M *N nicht aber das fünfte, erfüllt.

2. Sei M := {n ∈N | n ist ungerade} und für n ∈ M sei der Nachfolger definiertals n′ := n +2. Dann sind alle fünf Peano-Axiome erfüllt.

Tatsächlich wird die Menge N der natürlichen Zahlen durch die fünf Peano-Axiome auch nur „im wesentlichen” eindeutig festgelegt. Solche mengentheo-retischen Betrachtungen werden wir hier aber nicht durchführen.

11


9.b Definitionen

Eine Definition legt mathematische Begriffe, wie z. B. Menge, Abbildung und Re-lation, fest. Sie darf sich dabei nur auf bereits bekannte mathematische Axiome,Definitionen und Sätze stützen. Nicht zulässig sind hingegen anschauliche Be-schreibungen oder unpräzise Begriffe.

Es folgen einige Beispiele mathematischer Definitionen.

Definition 9(3). 1. z ∈Z heißt gerade, wenn es ein k ∈Zmit z = 2k gibt.

2. 2Z := {2z | z ∈Z} sei die Menge aller geraden ganzen Zahlen.

3. 2N := {2n | n ∈N} sei die Menge aller geraden natürlichen Zahlen.

4. z ∈Z heißt ungerade, wenn es ein k ∈Zmit z = 2k −1 gibt.

5. 2Z−1 := {2z −1 | z ∈Z} sei die Menge aller ungeraden ganzen Zahlen.

6. 2N−1 := {2n−1 | n ∈N} sei die Menge aller ungeraden natürlichen Zahlen.

Definition 9(4). Eine rationale Zahl r heißt bezüglich der Multiplikation „·” in-vertierbar, wenn es eine rationale Zahl q mit r ·q = 1 gibt.

Definition 9(5). Eine ganze Zahl z heißt durch eine ganze Zahl k teilbar, wennes eine ganze Zahl l mit z = l ·k gibt. In diesem Fall heißt k ein Teiler von z, undwir schreiben k | z.

Beispielsweise ist wegen 10 = 5 ·2 10 durch 2 teilbar, 2 ist ein Teiler von 10, d. h.2 | 10. Nach Definition 9(5) gilt 0 | 0, denn die Forderung 0 = l ·0 für ein l ∈ Z istsogar für jedes l ∈Z erfüllt.

Und nun ein unpräziser Versuch einer Definition.

Keine Definition 9(6). Eine Zahl heißt gerade, wenn sie eine der Zahlen 2,4,6, . . .ist.

Statt Zahl sollte es natürliche Zahl heißen. Eine mögliche Fortsetzung von 2,4,6, . . .ist 2,4,6,4,8,12,8,16,24, ... . Also wäre 10 keine gerade natürliche Zahl. Da keineEindeutigkeit des zu definierenden Begriffs gegeben ist, liegt hier keine Defini-tion vor.

12


9.c Vermutungen, Behauptungen und Sätze

In einer Vermutung macht ein Mathematiker über zuvor definierte mathemati-sche Begriffe, seltener auch Axiome, eine Aussage, von der er annimmt, dass siewahr ist. Bei einer Behauptung handelt es sich um eine Vermutung, bei der einMathematiker sich schon sehr sicher ist, dass sie wahr ist.

In beiden Fällen werden dabei in der Regel verschiedene Definitionen und Sät-ze, ggf. auch Axiome, verknüpft.

9.c.1 Positive Beispiele und Gegenbeispiele

Nach obiger Definition 9(5) ist folgende Aussage eine Behauptung. Diese kannwahr oder falsch sein.

Behauptung 9(7). Jede durch 4 teilbare ganze Zahl ist durch 2 teilbar.

Die beiden nächsten Aussagen sind dagegen keine Vermutung oder Behaup-tung.

Keine Vermutung oder Behauptung 9(8). Sei r eine rationale Zahl. Dann ist rdurch 3 teilbar.

Für eine rationale Zahl, die keine ganze Zahl ist, ist „durch 3 teilbar” nicht defi-niert.

Keine Vermutung oder Behauptung 9(9). Die Menge der reellen Zahlen ist diekleinste Obermenge der Menge der rationalen Zahlen, die auch noch viele Zah-len enthält, die nicht rational sind.

Die Begriffe „Obermenge”, „kleinste Obermenge”, „viele Zahlen” und „nicht ra-tional” sind nicht definiert.

Eine der wesentlichen Absichten eines forschenden Mathematikers ist es, Ver-mutungen oder Behauptungen aufzustellen, oder bereits bekannte aufzugrei-fen, und auf ihren Wahrheitsgehalt hin zu überprüfen, und ggf. zu beweisen.Dies geschieht mit Hilfe des im nächsten Abschnitt zu besprechenden Beweises.Gibt es zu einer Vermutung oder Behauptung einen Beweis, so heißt die Vermu-tung bzw. Behauptung ab dann Satz oder bei einem sehr wichtigen Satz Theo-rem. Sätze, die nur ein Hilfsmittel für den Beweis anderer Sätze sind, heißenHilfssatz oder Lemma. Ein Satz heißt ein Korollar, wenn seine Gültigkeit mehroder weniger direkt aus der Aussage eines vorherigen Satzes folgt. Es ist dannkein Beweis oder nur ein sehr kurzer Beweis erforderlich. Die Abgrenzung zwi-schen Satz und Korollar ist dabei sehr subjektiv. Da das Skript neben den Defi-nitionen und Beweisen fast nur aus Sätzen, Hilfssätzen und Korollaren besteht,wird die Unterscheidung dadurch deutlich werden.

13


9.d Beweise

Beweise bilden den Hauptteil der kreativen Arbeit von Studierenden und vonan Universitäten forschenden Mathematikern. Entgegen einer weit verbreitetenMeinung geht es nämlich nicht um das Rechnen, sondern um das Beweisen. Willjemand eine Aussage A beweisen, so wird zuerst geprüft, ob es sich bei A umeine korrekt formulierte Vermutung oder Behauptung handelt. Notwendig ist,dass alle verwendeten Begriffe definiert sind, und die Aussage präzise formuliertist. Ein Beweis fängt immer bei Definitionen oder bei bereits bekannten Sätzen,seltener bei Axiomen, an.

Aus den in einer Vermutung oder Behauptung verwendeten Begriffen wird nunggf. unter Verwendung bereits bekannter Sätze in „logisch einwandfreien Schrit-ten” die Aussage der Vermutung oder der Behauptung gefolgert. Gelingt dies, soerhalten wir einen Satz.

9.d.1 Positive Beispiele und Gegenbeispiele

Es folgen drei Beispiele korrekter Beweise.

Satz 9(10). Ist eine ganze Zahl p durch eine ganze Zahl k teilbar, so ist für jedeganze Zahl q q ·p durch k teilbar.

Beweis. Nach Voraussetzung und nach Definition 9(5) gibt es eine ganze Zahl lmit p = l ·k. Es folgt q ·p = (q · l ) ·k mit q · l ∈ Z. Damit ist q ·p nach Definition9(5) durch k teilbar.

Satz 9(11). Die ganzen Zahlen p und q seien durch eine ganze Zahl k teilbar.Dann sind p +q und p −q durch k teilbar.

Beweis. Nach Voraussetzung und nach Definition 9(5) gibt es ganze Zahlen lund m mit p = l · k und q = m · k. Es folgt p ± q = l · k ±m · k = (l ±m) · k mitl ±m ∈Z. Also ist p ±q nach Definition 9(5) durch k teilbar.

Nun beweisen wir unsere obige Behauptung 9(7), und formulieren diese als Satz.

Satz 9(12). Jede durch 4 teilbare ganze Zahl ist durch 2 teilbar.

Beweis. Sei z eine durch 4 teilbare ganze Zahl. Dann gibt es nach Definition 9(5)eine ganze Zahl l mit z = l ·4. Da 4 = 2 ·2 nach Definition 9(5) durch 2 teilbar ist,ist nach Satz 9(10) z = l ·4 durch 2 teilbar.

14

10 DIREKTE BEWEISE UND BEWEISE DURCH WIDERSPRUCH,KONTRAPOSITION UND FALLUNTERSCHEIDUNG 15

Der folgende Beweis von Satz 9(12) ist dagegen schlecht aufgeschrieben.

Kein Beweis. Sei z durch 4 teilbar. Sei k die größte gerade Zahl, die z teilt. Danngibt es nach Definition 9(5) eine Zahl l mit z = l ·k. Die 2 steckt nun in der gera-den Zahl k, also auch in z.

Zu ungenau; der relevante Satz 9(10) wird nicht zitiert. Stattdessen wird an derStelle „Die 2 steckt nun in...” „anschaulich” argumentiert. Es sollte auch ganzeZahl l statt nur Zahl l heißen. Und „größte gerade Zahl”, die einer Eigenschaftgenügt, wurde nicht definiert. Dass k die „größte gerade Zahl” ist, die n teilt,wird im Beweis nicht benötigt, und ist deshalb verwirrend.

9.e Übungsaufgaben

1. Beweisen Sie: Gilt für a,b, p, q ∈ Z, dass a durch p teilbar (9(5)) ist und bdurch q teilbar ist, so ist a ·b durch p ·q teilbar.

Hinweis: Verwenden Sie drei mal Definition 9(5).

2. Seien z ∈Z und k ∈N. Beweisen Sie, dass genau eine der ganzen Zahlen

z +1, ..., z +k

durch k teilbar (9(5)) ist.

Hinweis: Sie können ohne Beweis verwenden, dass es l ∈Z und r ∈N0 mitr É k −1 und z = l ·k + r gibt. Beweisen Sie 1 É k − r É k und k | z +k − r .Folgern Sie dann aus k | z+m für ein m ∈ {1, ...,k} mit Satz 9(11) m = k−r .

3. Beweisen Sie: Zu jeder ungeraden natürlichen Zahl (9(3) 6.) n gibt es eineganze Zahl m mit n2 = 8m +1.

4. Beweisen Sie: Es gibt nur einen Primzahldrilling, d. h. es gibt nur einePrimzahl p, so dass auch p +2 und p +4 Primzahlen sind.

Hinweis: Betrachten Sie unter Verwendung der zweiten Übungsaufgabe9.e zwei mal für drei aufeinanderfolgende natürliche Zahlen die Teilbar-keit durch 3.

10 Direkte Beweise und Beweise durch Widerspruch, Kon-traposition und Fallunterscheidung

Beweise lassen sich in der Regel nicht mechanisch führen; es braucht fast immerden Einfallsreichtum des Mathematikers. Dennoch gibt es einige Methoden, wiesich ein Beweis aufbauen lässt. Oftmals müssen diese Methoden kombiniert ver-wendet werden. Die wichtigsten werden wir nun vorstellen.

15


10.a Direkter Beweis

Die Beweise der Sätze 9(10). 9(11) und 9(12) sind sogenannte direkte Beweise.Es folgen drei weitere Beispiele solcher Beweise.

In dem ersten Beispiel wird eine gesuchte natürliche Zahl zu Beginn des Bewei-ses definiert, und dann auf direktem Weg nachgewiesen, dass sie die geforderteEigenschaft hat.

Hilfssatz 10(1). Seien a,b,c,d natürliche Zahlen mit a := 2b und c := 2d . Dannexistiert eine natürliche Zahl e mit a + c = 2e.

Beweis. Für e := b +d gilt e ∈N und a + c = 2b +2d = 2(b +d) = 2e.

Im nächsten Beispiel wird die linke Seite der behaupteten Gleichung durch Ver-wendung einer Definition und bekannten „Rechenregeln” für reelle Zahlen indie rechte Seite überführt.

Hilfssatz 10(2). Für alle a,b,c ∈R gilt (a+b+c)2 = a2+b2+c2+2ab+2ac+2bc.

Beweis. Es gilt(a +b + c)2 = (a +b + c)(a +b + c) = a(a +b + c)+b(a +b + c)+ c(a +b + c)= a2 +ab +ac +ba +b2 +bc + ca + cb + c2 = a2 +b2 + c2 +2ab +2ac +2bc.

Der Beweis des nächsten Satzes ist etwas schwieriger, aber methodisch ebenfallsein direkter Beweis.

Satz 10(3). Ist q ∈Z ungerade (9(3)), so ist q2 −1 durch 8 teilbar (9(5)).

Beweis. Da q − 1 gerade ist, gibt es eine ganze Zahl k mit q − 1 = 2k. Es folgtq + 1 = 2(k + 1). Nach der zweiten Übungsaufgabe 9.e ist k oder k + 1 durch 2teilbar, und nach der ersten Übungsaufgabe 9.e ist dann q −1 oder q +1 durch 4teilbar. Da q −1 und q +1 durch 2 teilbar sind, ist q2−1 = (q −1)(q +1) nach derersten Übungsaufgabe 9.e durch 8 teilbar.

10.a.1 Übungsaufgaben

1. Beweisen Sie für a,b ∈R die Gültigkeit der Gleichung

(a +b)(a −b)3 − (a −b)(a +b)3 =−4ab(a +b)(a −b).

Hinweis: Schreiben Sie den Term auf der linken Seite der Gleichung als einProdukt, indem Sie gemeinsame Faktoren „ausklammern”.

16


2. Für welche a,b ∈R sind die Terme in der Gleichung

a

a +b+ b

a −b+ 2ab

b2 −a2 = a −b

a +b

definiert? Beweisen Sie für solche a,b die Gültigkeit dieser Gleichung.

Hinweis: Multiplizieren Sie für b2 − a2 6= 0 im Beweis die Gleichung mitb2 −a2.

3. Beweisen Sie, dass für jede Primzahl p ≥ 5 p2 −1 durch 24 teilbar (9(5))ist.

Hinweis: Verwenden Sie Satz 10(3) und die zweite Übungsaufgabe 9.e.

10.b Beweis durch Widerspruch

Zu jeder Aussage A gibt es eine gegenteilige Aussage, die wir (nicht A) nennen.Ist z. B. für n ∈N A die Aussage „n ist eine Primzahl”, so ist (nicht A) die Aussage„n ist keine Primzahl”. Die Aussage (nicht A) ist genau dann falsch (bzw. wahr),wenn die Aussage A wahr (bzw. falsch) ist. Ein wichtiges mathematisches Prinzipist

Mathematisches Prinzip. Lässt sich aus einer mathematischen Aussage A einefalsche Aussage B folgern, dann ist die Aussage A falsch.

Beispiel 10(4). Sei A die Aussage „Es gibt eine ganze Zahl z, die gerade undungerade ist”. Dann gibt es nach Definition 9(3) k, l ∈Zmit z = 2k und z = 2l −1.Es folgt 2k = 2l −1, und daraus 2(l −k) = 1. Die letzte Aussage ist sowohl für k = lals auch für k 6= l ein Widerspruch. Nach obigem mathematischen Prinzip ist dieAussage A also falsch.

Aus diesem Prinzip lässt sich folgende Beweismethode ableiten.

Satz 10(5). Es gilt die Aussage A.

Beweis durch Widerspruch 1. Angenommen, es gilt die Aussage (nicht A). Nunfolgern wir Schritt für Schritt aus (nicht A) weitere Aussagen, solange, bis wireine Aussage erhalten, die schon als falsch bekannt ist. Dann wissen wir, dassdie Aussage (nicht A) falsch ist. Also ist die Aussage A wahr.

Den folgenden Satz beweisen wir nun durch einen Widerspruchsbeweis.

Satz 10(6). Es gibt keine kleinste positive rationale Zahl.

17


Beweis. Angenommen, es gibt eine kleinste positive rationale Zahl q . Da q ∈ Qpositiv ist, ist q

2 ∈Q positiv. Aus unserer Annahme folgt

q É q

2. Division durch q > 0 führt auf 1 É 1

2.

Die letzte Aussage ist bekanntlich falsch. Also gibt es keine kleinste positive ra-tionale Zahl.

Im Beweis des nächsten Satzes werden wir das Lemma von Euklid3 (Elemente,Buch VII, Postulat 30) ohne Beweis verwenden.

Lemma von Euklid 10(7). Seien a, b natürliche Zahlen und p eine Primzahl. Istp ein Teiler von ab, so ist p ein Teiler von a oder ein Teiler von b.

Definition 10(8). Seien a,b ∈Zmit a 6= 0 oder b 6= 0.

1. Der größte gemeinsame Teiler von a und b, in Zeichen ggt(a,b), ist diegrößte natürliche Zahl k mit k | a ∧k | b.

2. Im Fall ggt(a,b) = 1 heißen a und b teilerfremd.

Eine irrationale Zahl ist definiert als eine reelle Zahl, die nicht rational ist. Bei-spielsweise ist die Kreiszahlπ irrational, wie Johann Heinrich Lambert4 1761 (imDruck 1768) bewies.

Es folgt der erste bekannte Widerspruchsbeweis in der Geschichte der Mathe-matik. Er stammt von Euklid.

Satz 10(9).p

2 ist irrational.

3Euklid von Alexandria war ein griechischer Mathematiker, der wahrscheinlich im 3. Jahr-hundert v. Chr. in Alexandria gelebt hat. Die überlieferten Werke umfassen sämtliche Bereicheder antiken griechischen Mathematik: das sind die theoretischen Disziplinen Arithmetik undGeometrie (Die Elemente, Data), Musiktheorie (Die Teilung des Kanon), eine methodische An-leitung zur Findung von planimetrischen Problemlösungen von bestimmten gesicherten Aus-gangspunkten aus (Porismen) sowie die physikalischen bzw. angewandten Werke (Optik, astro-nomische Phänomene).In seinem berühmtesten Werk Elemente trug er das Wissen der griechi-schen Mathematik seiner Zeit zusammen. Er zeigte darin die Konstruktion geometrischer Ob-jekte, natürlicher Zahlen sowie bestimmter Größen und untersuchte deren Eigenschaften. Da-zu benutzte er Definitionen, Postulate (nach Aristoteles Grundsätze, die akzeptiert oder abge-lehnt werden können) und Axiome (nach Aristoteles allgemeine und unbezweifelbare Grund-sätze). Viele Sätze der Elemente stammen offenbar nicht von Euklid selbst. Seine Hauptleistungbesteht vielmehr in der Sammlung und einheitlichen Darstellung des mathematischen Wissenssowie der strengen Beweisführung, die zum Vorbild für die spätere Mathematik wurde (Quelle:http://de.wikipedia.org/wiki/Euklid_von_Alexandria).

4Johann Heinrich Lambert (? 26. August 1728 in Mülhausen (Elsass); † 25. Septem-ber 1777 in Berlin) war ein schweizerisch-elsässischer Mathematiker, Logiker, Physikerund Philosoph der Aufklärung, der u. a. die Irrationalität der Zahl Pi bewies (Quelle:http://de.wikipedia.org/wiki/Johann_Heinrich_Lambert).

18


Beweis. Angenommen,p

2 ist rational. Dann gibt es teilerfremde natürliche Zah-len a und b mit

p2 = a

b . Ausp

2 = ab folgt 2b2 = a2. Nach dem Lemma von Eu-

klid (10(7)) ist dann 2 ein Teiler von a. Daher gibt es c ∈ N mit a = 2c. Dann ist2b2 = a2 = (2c)2 = 4c2, und daher b2 = 2c2. Wie oben folgt, dass 2 ein Teiler von bist. Nun haben a und b beide den Teiler 2, und dies ist ein Widerspruch. UnsereAnnahme, dass

p2 rational ist, ist daher falsch. Folglich ist

p2 irrational.

Die Erkenntnissp

2 ∉ Q hat vor mehr als 2300 Jahren die griechischen Philoso-phen und Mathematiker sehr erschüttert. Denn sie dachten lange Zeit, dass sichalle reellen Zahlen als Quotienten von ganzen Zahlen schreiben lassen. ZumBeispiel ist ja

p2 einfach die Länge der Diagonale in einem Quadrat, dessen Sei-

ten die Länge 1 haben.

Der folgende Satz und sein Beweis durch Widerspruch stammen ebenfalls vonEuklid (Elemente, Buch IX, § 20). Im Beweis werden wir ohne Beweis verwenden,dass zu jeder natürlichen Zahl m > 1, die keine Primzahl ist, eine Primzahl k mitk | m existiert. Diese Aussage folgt später durch vollständige Induktion.

Satz 10(10). Es gibt unendlich viele Primzahlen.

Beweis. Angenommen, es gibt nur endlich viele Primzahlen p1, ..., pn , wobei neine natürliche Zahl ist. Dann ist

a := p1 · ... ·pn +1 ∈N

wegen a > pi für i ∈Nn keine Primzahl. Folglich gibt es eine Primzahl q mit q | a.Wegen q = pl für ein l ∈Nn gilt nach Satz 9(11) pl | a −p1 · ... ·pn , und damit derWiderspruch pl | 1. Unsere Annahme, dass es nur endlich viele Primzahlen gibt,ist also falsch. Damit gibt es unendlich viele Primzahlen.

Ein Widerspruch ist logisch gesehen eine Aussage der Form

Es gilt A, und es gilt (nicht A).

Beispielsweise im Beweis von Satz 10(6): Es gibt zwei rationale Zahlen a und bmit a > b und a ≤ b (nämlich a = 1 und b = 1

2 ). Ein Widerspruch ist immer einefalsche Aussage.

Wir wissen nun, dass eine Aussage falsch ist, wenn aus ihr eine falsche Aussagefolgt. Eine Aussage ist aber nicht dadurch wahr, dass eine wahre Aussage ausihr folgt. Aus der Aussage 1 = 2 in R lassen sich viele Aussagen folgern, manchedavon sind wahr, manche falsch. Multiplizieren wir z. B. die Gleichung 1 = 2 aufbeiden Seiten mit 0, so folgt 0 = 0, eine wahre Aussage. Bei Multiplikation mit 2folgt 2 = 4, eine in R falsche Aussage.

19


10.b.1 Übungsaufgaben

1. Beweisen Sie, dass es keine größte negative rationale Zahl gibt.

2. Beweisen Sie für jede Primzahl p, dassp

p irrational ist.

10.c Beweis durch Kontraposition

Hat ein Satz die Form, dass aus der Gültigkeit einer Aussage A auf die Gültigkeiteiner Aussage B geschlossen wird, so lässt sich dieser Satz so beweisen, dass ausder Aussage (nicht B) die Aussage (nicht A) gefolgert wird. Die Rechtfertigungdieser Beweismethode „Beweis durch logische Kontraposition” werden wir imKapitel über Aussagenlogik geben.

Ein Beispiel ist der Beweis des nächsten Satzes.

Definition 10(11). Eine ganze (bzw. natürliche) Zahl z heißt Quadratzahl, wennes ein l ∈Z (bzw. l ∈N) mit z = l 2 gibt.

Satz 10(12). Sei n ∈N eine Quadratzahl (10(11)). Ist n gerade (9(3)), so ist auchpn gerade.

Beweis. Da n nach Voraussetzung eine Quadratzahl ist, istp

n ∈ N. Seip

n un-gerade, d. h. es gibt ein k ∈Nmit

pn = 2k −1. Dann folgt n = (

pn)2 = (2k −1)2 =

4k2 −4k +1 = 2(2k2 −2k +1)−1 mit 2k2 −2k +1 ∈ Z. Also ist n ungerade, unddamit ist der Satz durch logische Kontraposition bewiesen.

10.c.1 Übungsaufgaben

1. Beweisen Sie durch Kontraposition: Sei n ∈ N eine Quadratzahl (10(11)).Ist n ungerade (9(3)), so ist auch

pn ungerade.

10.d Beweis durch Fallunterscheidung

Häufig ist es sinnvoll, eine zu beweisende Aussage in mehrere Teilaussagen, so-genannte Fälle, zu unterteilen, und diese einzeln zu beweisen. Wichtig bei einerFallunterscheidung ist, dass sie vollständig ist, d. h. die Gültigkeit aller Teilaussa-gen muss die Gültigkeit der zu beweisenden Aussage implizieren. Die Vollstän-digkeit muss offensichtlich sein oder bewiesen werden. Die untersuchten Fällemüssen sich nicht gegenseitig ausschließen.

Als erstes Beispiel werden wir den folgenden Satz durch einen Beweis durch Fall-unterscheidung beweisen.

Satz 10(13). Für jede ganze Zahl z ist z3 +2z durch 3 teilbar (9(5)).

20


Beweis. Wir unterscheiden zwei Fälle, wobei der zweite Fall in zwei Unterfälleaufgeteilt wird.

1. z ist durch 3 teilbar. Dann ist z3 + 2z = z(z2 + 2) nach Satz 9(10) durch 3teilbar.

2. z ist nicht durch 3 teilbar. Dann ist nach der zweiten Übungsaufgabe 9.ez +1 oder z +2 durch 3 teilbar.

(a) Ist z +1 durch 3 teilbar, so ist z2 +2 = (z +1)2 −2(z +1)+3 nach denSätzen 9(10) und 9(11) durch 3 teilbar.

(b) Ist z +2 durch 3 teilbar, so ist z2 +2 = (z +2)2 −4(z +2)+6 nach denSätzen 9(10) und 9(11) durch 3 teilbar.

Also ist z3 +2z = z(z2 +2) nach Satz 9(10) durch 3 teilbar.

Da in Fall 1. und in Fall 2. z3 +2z durch 3 teilbar ist, ist die Behauptung damitbewiesen.

Satz 10(14). Sei p eine Primzahl ungleich 2. Dann gibt es entweder eine natürli-che Zahl k mit p = 4k +1 oder eine natürliche Zahl l mit p = 4l +3.

Beweis. Da p bei der Division durch 4 den Rest 0, 1, 2, oder 3 hat, gibt es einenatürliche Zahl k mit

p = 4k oder p = 4k +1 oder p = 4k +2 oder p = 4 ·k +3.

Im ersten (bzw. dritten) dieser Fälle ist p durch 4 teilbar (bzw. p ist durch 2 teilbarund p ist größer als 2) und damit keine Primzahl. Folglich gilt p = 4k + 1 oderp = 4k + 3. Angenommen, es gibt k, l ∈ N mit 4k + 1 = p = 4l + 3. Dann folgt4(k−l ) = 2 mit k−l ∈Z, ein Widerspruch. Also liegt genau einer der beiden Fällevor.

10.d.1 Übungsaufgaben

1. Beweisen Sie durch Fallunterscheidung: Für jede ganze Zahl z ist z2+3z+7ungerade.

Hinweis: Betrachten Sie die Fälle „z ist gerade” und „z ist ungerade”.

2. Beweisen Sie durch Fallunterscheidung: Für jede ganze Zahl z ist 5 entwe-der ein Teiler (9(5)) von z oder von z4 −1.

Hinweis: Betrachten Sie {z −1, z, z +1, z +2, z +3}, und verwenden Sie diezweite Übungsaufgabe 9.e.

21

11 BEWEIS DURCH VOLLSTÄNDIGE INDUKTION 22

11 Beweis durch vollständige Induktion

11.a Der Irrtum von Fermat

Pierre de Fermat56 betrachtete die später nach ihm benannten natürlichen Zah-len der Form

Fn := 22n +1

für n ∈N0. Die ersten fünf dieser Fermat-Zahlen sind

F0 = 3

F1 = 5

F2 = 17

F3 = 257

F4 = 65537.

Dies sind alles Primzahlen und so vermutete Fermat im Jahr 1637, dass alle wei-teren Zahlen Fn mit n ≥ 5 ebenfalls Primzahlen sind.

Ein solcher Schluß wird in der Logik „Induktion” genannt. Es wird von einer Teil-menge an Beispielen auf die Gesamtheit geschlossen. Logisch gesehen sind sol-che Schlüsse in dieser Form nicht zulässig. Selbst wenn sehr viele Beispiele be-kannt sind, lässt sich so nicht auf die Gesamtheit schließen.

Im Jahr 1732 entdeckte Leonhard Euler7, dass die nächste Fermat-Zahl

F5 = 4294967297 = 641 ·6700417

keine Primzahl ist. Inzwischen wird sogar vermutet, dass alle weiteren Fermat-Zahlen Fn mit n ≥ 5 keine Primzahlen sind. Aber ein Beweis oder ein Gegenbei-spiel (also eine weitere Fermat-Zahl, die eine Primzahl ist) steht noch aus.

5Pierre de Fermat (? in der zweiten Hälfte des Jahres 1607 in Beaumont-de-Lomagne, Tarn-et-Garonne; † 12. Januar 1665 in Castres) war ein französischer Mathematiker und Jurist. Von ihmstammt die sogenannte Fermatsche Vermutung, die erst 1995 von dem britischen MathematikerAndrew John Wiles bewiesen wurde (Quelle: http://de.wikipedia.org/wiki/Pierre_de_Fermat).

6Sir Andrew John Wiles (? 11. April 1953 in Cambridge) ist ein britischer Mathematiker.Berühmt wurde er 1995 durch seinen Beweis der Taniyama-Shimura-Vermutung für semi-stabile elliptische Kurven, woraus sich ein Beweis der Fermatschen Vermutung ergibt (Quelle:http://de.wikipedia.org/wiki/Andrew_John_Wiles).

7Leonhard Euler (? 15. April 1707 in Basel; † 7. September (jul.)/ 18. September greg.1783 (greg.) in Sankt Petersburg) war ein Schweizer Mathematiker, der wegen seiner Beiträ-ge zur Analysis, zur Zahlentheorie und zu vielen weiteren Teilgebieten der Mathematik als ei-ner der bedeutendsten Mathematiker gilt. Euler war extrem produktiv: Insgesamt gibt es 866Publikationen von ihm. Ein großer Teil der heutigen mathematischen Symbolik geht auf Eu-ler zurück (z. B. e, π, i, Summenzeichen

∑, f (x) als Darstellung des Wertes einer Funkti-

on f an der Stelle x). 1748 publizierte er das Grundlagenwerk Introductio in analysin infi-nitorum, in dem zum ersten Mal der Begriff der Funktion die zentrale Rolle spielt (Quelle:http://de.wikipedia.org/wiki/Leonhard_Euler).

22


Die kleinste Fermat-Zahl, von der nicht bekannt ist, ob sie prim oder nicht primist, ist F33; F2478782 ist die größte, von der ein Faktor bekannt ist. Insgesamt weißman von 230 Fermat-Zahlen, dass sie nicht prim sind(Quelle: http://de.wikipedia.org/wiki/Fermat-Zahl).

11.b Summenformel von Maurolicus

Wir wollen hier ein anderes Beispiel betrachten. Sehen wir uns für n ∈ N dieSumme der ersten n ungeraden natürlichen Zahlen an. Für n = 1,2,3,4,5 ist dieSumme

1 = 1

1+3 = 4

1+3+5 = 9

1+3+5+7 = 16

1+3+5+7+9 = 25.

Es fällt auf, dass für n = 1,2,3,4,5 auf der rechten Seite stets eine Quadratzahl,nämlich n2, steht. Bevor wir uns mit der Vermutung, dass dies für alle n ∈ Nso ist, beschäftigen, führen wir die folgende Summen- und Produktnotation fürreelle Zahlen ein.

Definition 11(1). Seien m,n ∈N0 und ak ∈R für k = m,m +1, ...,n.

Für m É n sei (vorläufige Definition)

n∑k=m

ak := am +am+1 + ...+an undn∏

k=mak := am ·am+1 · ... ·an ,

und für n < m sein∑

k=mak := 0 und

n∏k=m

ak := 1.

Der folgende Hilfssatz ist eine Folgerung aus a+b = b+a und a(b+c) = ab+acfür alle a,b,c ∈R. Der Beweis wird später im Rahmen der Übungen erfolgen.

Hilfssatz 11(2). Seien m,n ∈N0, ak ,bk ∈R für k = m,m+1, ...,n und γ ∈R. Danngilt

n∑k=m

(ak +bk ) =n∑

k=mak +

n∑k=m

bk

undn∑

k=mγ ·ak = γ ·

n∑k=m

ak .

23


Obige Vermutung lässt sich nun mit Hilfe der Summennotation für jedes n ∈N formulieren. Diese Vermutung hatte schon Franciscus Maurolicus8 im Jahr1575, und er konnte ihre Gültigkeit mittels vollständiger Induktion, die im Fol-genden eingeführt wird, beweisen.

Satz 11(3). Für alle n ∈N gilt

n∑k=1

(2k −1) = n2.

Für n ∈ {1,2,3,4,5} haben wir die Gültigkeit dieser Vermutung bereits bewiesen.Aber das Beispiel der Fermat-Zahlen lehrt uns, dass Beispiele nichts über dieGesamtheit aller Fälle aussagen. Und wir können nicht alle Fälle für n ∈ N mitn ≥ 6 nachrechnen, weil es unendlich viele sind.

Die Lösung des Problems ist ein Beweisverfahren, das unter dem Namen „voll-ständige Induktion” bekannt ist. Gegeben sei eine Aussage A(n) in Abhängigkeitvon n ∈N. In unserem Fall ist für n ∈N A(n) die Aussage

n∑k=1

(2k −1) = n2.

Wir haben oben notiert, dass die Aussagen A(1) bis A(5) wahr sind, möchtenaber beweisen, dass die Aussage A(n) für alle n ∈ N wahr ist. Die vollständigeInduktion geht nun in zwei Schritten vor:

1) Der Induktionsanfang (n = 1): Es wird die Aussage A(1) bewiesen.

2) Der Induktionsschritt (auch Induktionsschluß) (n n +1): Wir beweisenfür alle n ∈N: Ist die Aussage A(n) wahr, so folgt, dass die Aussage A(n+1)wahr ist.

Sind die Aussagen 1) und 2) bewiesen, so ist gemäß diesem Beweisverfahren dervollständigen Induktion bewiesen, dass die Aussage A(n) für alle n ∈Nwahr ist.Dies zeigt der folgende

Satz 11(4). Für jedes n ∈N sei A(n) eine Aussage. Gilt dann, dass A(1) gültig ist,und dass für jedes n ∈N aus der Gültigkeit von A(n) die Gültigkeit von A(n +1)folgt, so gilt A(n) für jedes n ∈N.

Beweis. Sei M := {n ∈ N | A(n) ist wahr}. Nach Voraussetzung gilt 1 ∈ N und n ∈M impliziert n +1 ∈ M . Nach dem 5-ten Peano Axiom gilt dann N ⊆ M . WegenM ⊆N folgt M =N, und damit die Behauptung.

8Franciscus Maurolicus (? 16. September 1494 in Messina; † 21./ 22. Juli 1575 bei Messina;auch Francesco Maurolico, griech. Frangiskos Maurolykos) war ein bedeutender Universalgelehr-ter des 16. Jahrhunderts (Quelle: http://de.wikipedia.org/wiki/Franciscus_Maurolicus).

24


Im Detail können wir uns das so vorstellen: Der Induktionsanfang beinhaltet dieGültigkeit der Aussage A(1). Jetzt wenden wir den Induktionsschritt für n = 1 anund erhalten, dass A(2) wahr ist. Jetzt können wir den Induktionsschritt für n = 2anwenden und erhalten, dass A(3) wahr ist, und so weiter.

Für den Induktionsanfang ist statt n = 1 auch n = 0 bzw. n = m für eine natürli-che Zahl m ≥ 2 zulässig. Die Aussage A(n) ist dann nach Induktionsanfang undInduktionsschritt für alle n ∈N0 bzw. für alle n ∈Nmit n ≥ m bewiesen.

Nun beweisen wir Satz 11(3) durch vollständige Induktion.

Beweis. Der Induktionsanfang (n = 1) wurde schon oben bewiesen.Induktionsschritt (n n +1): Sei n ∈ N beliebig, so dass A(n) wahr ist, d. h. esgilt

n∑k=1

(2k −1) = n2.

Zu zeigen ist, dass aus dieser Voraussetzung die Gültigkeit von A(n + 1) folgt.Dies zeigt die folgende Rechnung:

n+1∑k=1

(2k −1) =( n∑

k=1(2k −1)

)+ (

2(n +1)−1) IV= n2 +2n +1 = (n +1)2.

Das kleine „IV” (Induktionsvoraussetzung) bezeichnet die Stelle, an der die Gül-tigkeit von A(n) verwendet wird. Satz 11(3) ist übrigens auch für n = 0 wahr.Daher hätten wir als Induktionsanfang auch n = 0 wählen können.

11.c Summenformel von Gauß

Es wird eine Anekdote9 über den Mathematiker Carl-Friedrich Gauß10 erzählt.Weil er als 8-jähriger Schüler die anderen Aufgaben schon gelöst hatte, erhielt er

9Sartorius von Waltershausen: Gauss zum Gedächtniss, 1856, S. 12 (Quelle:http://de.wikipedia.org/wiki/Wolfgang_Sartorius_von_Waltershausen).

10Johann Carl Friedrich Gauß (latinisiert Carolus Fridericus Gauß; ? 30. April 1777 in Braun-schweig; † 23. Februar 1855 in Göttingen) war ein deutscher Mathematiker, Astronom, Geo-dät und Physiker mit einem breit gefächerten Feld an Interessen. Seine überragenden wissen-schaftlichen Leistungen waren schon seinen Zeitgenossen bewusst. Mit 18 Jahren entwickelte erdie Grundlagen der modernen Ausgleichsrechnung und der mathematischen Statistik (Metho-de kleinster Quadrate), mit der er 1800 die Wiederentdeckung des ersten Asteroiden Ceres er-möglichte. Am 29. März 1796, wenige Wochen vor seinem neunzehnten Geburtstag, bewies erdie Konstruierbarkeit des regelmäßigen Siebzehnecks und lieferte damit die erste nennenswerteErgänzung euklidischer Konstruktionen seit 2000 Jahren. Dies war aber nur ein Nebenergebnisbei der Arbeit für sein zahlentheoretisch viel weiterreichendes Werk „Disquisitiones Arithmeti-cae”. Dieses Lehrbuch der Zahlentheorie schrieb Gauß 1798 mit nur 21 Jahren. Das Buch ist alseines der letzten großen mathematischen Werke in Latein verfasst. Es werden sowohl die ele-

25


von seinem Klassenlehrer Büttner die Aufgabe, die natürlichen Zahlen von 1 bis100 zu addieren. Er sollte also die Summe

100∑i=1

i

berechnen. Laut der Anekdote soll Carl-Friedrich seinen Lehrer damit überraschthaben, in kurzer Zeit auf das richtige Ergebnis 5050 zu kommen. Wir werden denvon ihm verwendeten Trick statt für n = 100 allgemein für n ∈N formulieren.

Gaußsche Summenformel 11(5). Sei n ∈N und Sn :=∑ni=1 i . Dann gilt

Sn = 1 + 2 + . . .+ n,

Sn = n + n −1 + . . .+ 1,

und folglich

2Sn = (n +1) + (n +1) + . . .+ (n +1) (n Summanden).

Also gilt 2Sn = n(n +1). Unter Verwendung der Summennotation und Hilfssatz11(2) können wir obigen Trick wie folgt formulieren.

2Sn =n∑

i=1i +

n∑i=1

i =n∑

i=1i +

n∑i=1

(n−(i−1)) =n∑

i=1(i+(n−(i−1))) =

n∑i=1

(n+1) = n(n+1).

Hieraus folgt

Sn = n(n +1)

2.

Aufgrund dieser Anekdote trägt die Formel

n∑i=1

i = n(n +1)

2

den Namen „Gaußsche Summenformel” oder „der kleine Gauß”. Für n = 100 er-gibt sich gerade 100·101

2 = 5050. Die Gültigkeit dieser Formel lässt sich auch durchvollständige Induktion nach n beweisen. Sei dazu für n ∈N A(n) die Aussage

n∑i=1

i = n(n +1)

2.

mentare Zahlentheorie behandelt als auch die Grundlagen der algebraischen Zahlentheorie ge-legt. Auf Gauß gehen die nicht-euklidische Geometrie, zahlreiche mathematische Funktionen,Integralsätze, die gaußsche Glockenkurve, erste Lösungen für elliptische Integrale und die gauß-sche Osterformel zurück. 1807 wurde er zum Universitätsprofessor und Sternwartendirektor inGöttingen berufen. Bereits 1856 ließ der König von Hannover Gedenkmünzen mit dem Bild vonGauß und der Inschrift „Mathematicorum Principi” (deutsch: „dem Fürsten der Mathematiker”)prägen (Quelle: http://de.wikipedia.org/wiki/Carl_Friedrich_Gauß

26


Beweis. Induktionsanfang (n = 1): Wegen 1 = 1·22 ist die Aussage A(1) wahr.

Induktionsschritt (n n +1): Sei n ∈N beliebig und A(n) sei wahr. Es folgt

n+1∑i=1

i =( n∑

i=1i)+n +1

IV= n(n +1)

2+ 2(n +1)

2= (n +1)(n +2)

2.

Also ist A(n +1) wahr, und die Behauptung ist damit bewiesen.

11.d Summenformel der endlichen geometrischen Reihe

Satz 11(6). Für alle x ∈R\ {1} und für alle n ∈N0 gilt

n∑k=0

xk = 1−xn+1

1−x.

Beweis. Induktionsanfang (n = 0): Es gilt∑0

k=0 xk = x0 = 1 = 1−x1

1−x .Induktionsschritt (n n +1): Die Behauptung gelte für n ∈N0. Dann folgt

n+1∑k=0

xk =( n∑

k=0xk

)+xn+1 IV= 1−xn+1

1−x+ xn+1 · (1−x)

1−x= 1−xn+2

1−x.

11.e Teiler natürlicher Zahlen

Viele Teileraussagen über natürliche Zahlen lassen sich durch vollständige In-duktion beweisen. Wir betrachten hier das folgende Beispiel.

Satz 11(7). Für alle n ∈N0 ist 32n +7 durch 8 teilbar.

Beweis. Induktionsanfang (n = 0): Es ist 32·0 +7 = 8 durch 8 teilbar.Induktionsschritt (n n +1): Sei n ∈N0 beliebig und 32n +7 sei durch 8 teilbar.Dann ist

32·(n+1) +7 = 32n+2 +7 = 32 ·32·n +7 = 9 ·32·n +7 = (32·n +7)+8 ·32·n

durch 8 teilbar, da 32·n + 7 nach Induktionsvoraussetzung und 8 · 32·n durch 8teilbar sind (9(10)).

Nun können wir auch den vorläufigen Teil der Summen-und Produktnotation11(1) mittels der vollständigen Induktion definieren (sogenannte induktive De-finition).

27


Definition 11(8). Seien m,n ∈ N0 mit m É n und ak ∈ R für k = m,m +1, ...,n.Dann seien

m∑k=m

ak := am undn+1∑k=m

ak :=( n∑

k=mak

)+an+1

undm∏

k=mak := am und

n+1∏k=m

ak :=( n∏

k=mak

)·an+1.

11.f Alle Dinge sind identisch

Zum Schluß des Abschnitts über vollständige Induktion folgt noch ein falscher„Beweis”. Er zeigt, dass wir, wie immer in der Mathematik, bei Beweisen sehrgenau hinsehen müssen. Es wird die Aussage

„Alle Studierenden an der Universität Bielefeld studieren dasselbe Fach.”

„bewiesen”. Mathematisch präzisiert ist für n ∈N unsere Behauptung die Aussa-ge A(n), dass in jeder Teilmenge M von n Studierenden der Universität Bielefeldalle dasselbe Fach studieren.

Beweis. Induktionsanfang (n = 1): Dass in jeder Teilmenge bestehend aus ei-nem Studierenden jeder dasselbe Fach studiert, ist offensichtlich wahr.Induktionsschritt (n n + 1): Nehmen wir an, die Aussage A(n) sei für n ∈ Nbewiesen. Sei M := {a1, a2, . . . , an+1} eine beliebige Teilmenge von n +1 Studie-renden. In den Mengen

M ′ := {a2, a3, . . . , an+1} ⊆ M und M̃ := {a1, a2, . . . , an} ⊆ M

studieren nach Induktionsvoraussetzung alle dasselbe Fach. Sei nun k ∈ {2, ...,n}beliebig. Dann folgt wegen a1, ak ∈ M̃ und ak , an+1 ∈ M ′, dass a1 dasselbe stu-diert wie ak und ak dasselbe wie an+1. Also studiert a1 dasselbe wie an+1. Daherstudiert in M ′ jeder dasselbe wie in M̃ , und folglich studiert in M = M ′∪M̃ jederdasselbe. Damit ist die Aussage A(n) für n ∈N „bewiesen”.

Mit n := „Anzahl der Studierenden an der Universität Bielefeld” zeigt die AussageA(n) die Behauptung. Natürlich lässt sich dieser Beweis nun für beliebige end-liche Mengen führen. Alle Bücher heißen identisch, alle Häuser sind identischhoch und so weiter. Wo genau der Fehler in der obigen Argumentation liegt, soll-te möglichst jeder selbst entdecken.

28

12 AUSSAGENLOGIK UND QUANTOREN 29

11.g Übungsaufgaben

1. Beweisen Sie für jedes n ∈N0 durch vollständige Induktion 2n ≥ n.

2. Beweisen Sie für jedes n ∈ N0 durch vollständige Induktion: 23n + 13 istdurch 7 teilbar (9(5)).

3. Beweisen Sie für jedes n ∈N0 durch vollständige Induktion

n∑i=1

i 2 = n(n +1)(2n +1)

6.

4. Beweisen Sie für jedes n ∈N durch vollständige Induktion

n∏k=2

(1− 1

k

)= 1

n.

5. Seien m,n ∈ N0, ak ,bk ∈ R für k = m,m + 1, ...,n und es seien α,β ∈ R.Beweisen Sie durch vollständige Induktion nach n

n∑k=m

(α ·ak +β ·bk ) =α ·n∑

k=mak +β ·

n∑k=m

bk .

Wie folgt hieraus Hilfssatz 11(2)?

Bemerkung 11(9). Für n ∈N ist n(n+1)(2n+1)6 eine sogenannte Quadratische Py-

ramidalzahl. Es sind 1 und 4900 die einzigen natürlichen Zahlen, die zugleichQuadratzahl und quadratische Pyramidalzahl sind. Dies wurde von G. N. Wat-son 1918 bewiesen.

12 Aussagenlogik und Quantoren

12.a Aussagenlogik

Für zwei mathematische Aussagen A und B schreiben wir für die Aussage „ausA folgt B” von nun an „A =⇒ B”. Dies muss nicht heißen, dass es eine inhaltlicheBeziehung zwischen den Aussagen A und B gibt, sondern nur, dass es eine be-stimmte Beziehung der Wahrheitswerte von A und B gibt. Die folgende Wahr-heitstafel, in der „w” bzw. „f” bedeutet, dass die entsprechende Aussage wahrbzw. falsch ist, beschreibt diese Beziehung.

A B A =⇒ Bw w ww f ff w wf f w

29


Nach dieser Wahrheitstafel gilt also: Wenn A =⇒ B wahr und B falsch ist, dannist A falsch. Dies ist das Prinzip, welches dem Beweis durch Widerspruch (10(5))zugrunde liegt.

Beispiele für Aussagen der Form A =⇒ B ohne inhaltliche Beziehung in der Rei-henfolge obiger Wahrheitstafel sind nach Satz 10(10)

1 = 1 =⇒ Es gibt unendlich viele Primzahlen (w)

1 = 1 =⇒ Es gibt nur endlich viele Primzahlen (f)

1 = 2 =⇒ Es gibt unendlich viele Primzahlen (w)

1 = 2 =⇒ Es gibt nur endlich viele Primzahlen (w).

Sind die Aussagen A =⇒ B und B =⇒ A wahr, so bezeichnen wir diese Aussagezusammengefasst als A ⇐⇒ B . In diesem Fall sagen wir, dass die Aussagen Aund B äquivalent sind, oder sprechen von einer Äquivalenz von A und B . DieAussagen A und B sind dann beide wahr oder beide falsch. Ist eine Aussage Anach Definition gleich einer Aussage B , so schreiben wir A :⇐⇒ B .

Hiervon zu unterscheiden ist die Gleichheit „=”. Das Gleichheitszeichen „=”steht zwischen Mengen A und B , sofern diese beiden Mengen identisch sind,oder zwischen reellen Zahlen x und y , sofern diese identisch sind.

Beispiel 12(1). Für n ∈N sei A(n) die Aussage „4 | n(n +1)(n +2)(n +3)“. Dannschreiben wir diese Definition der Aussage A(n) kürzer als

A(n) :⇐⇒ 4 | n(n +1)(n +2)(n +3).

Die folgende Wahrheitstafel gibt die Wahrheitswerte der Aussagen A ⇐⇒ B , A∨B (gelesen: A oder B) und A ∧B (gelesen: A und B) in Abhängigkeit von denWahrheitswerten von A und B an.

A B A ⇐⇒ B A∨B A∧Bw w w w ww f f w ff w f w ff f w f f

Wie oben schon gesagt, ist die Aussage A ⇐⇒ B nach Definition genau dannwahr, wenn A und B beide wahr oder beide falsch sind. Die Aussage A∨B (bzw.A ∧B) ist nach der Definition in obiger Wahrheitstafel genau dann wahr, wennA oder B wahr ist (bzw. A und B wahr sind).

Für eine Aussage A sei von nun an ¬A := (nicht A). Die Aussage des nächstenSatzes liefert die Beweismethode der logischen Kontraposition (Beispiel 10(12)).

Satz 12(2). Für alle Aussagen A und B gilt (A =⇒ B) ⇐⇒ (¬B =⇒¬A).

30


Beweis. Der Beweis wird durch die Angabe der Wahrheitstafel geführt.

A B A =⇒ B ¬A ¬B ¬B =⇒¬Aw w w f f ww f f f w ff w w w f wf f w w w w

Die Spalten von A =⇒ B und ¬B =⇒¬A sind gleich. Damit ist der Satz bewiesen.

Bei dem folgenden Satz handelt es sich um eines der beiden De Morganschen11

Gesetze der Aussagenlogik.

Satz 12(3). Für alle Aussagen A und B gilt ¬(A∨B) ⇐⇒ (¬A)∧ (¬B).

Beweis. Auch hier wird der Beweis durch die Angabe der Wahrheitstafel geführt.

A B A∨B ¬(A∨B) ¬A ¬B (¬A)∧ (¬B)w w w f f f fw f w f f w ff w w f w f ff f f w w w w

Die Spalten von ¬(A∨B) und (¬A)∧ (¬B) sind gleich. Damit ist der Satz bewie-sen.


1. Beweisen Sie durch Angabe der Wahrheitstafel: Für alle Aussagen A und Bgilt

(1) A =⇒ A∨B 2) A∧B =⇒ A.

2. Beweisen Sie durch Angabe der Wahrheitstafel das zweite De MorganscheGesetz der Aussagenlogik: Für alle Aussagen A und B gilt

¬(A∧B) ⇐⇒ (¬A)∨ (¬B).

11Augustus De Morgan (? 27. Juni 1806 in Madurai, Indien; † 18. März 1871 in London) war einenglischer Mathematiker. Er war Mitbegründer und erster Präsident der London MathematicalSociety (Quelle: http://de.wikipedia.org/wiki/Augustus_De_Morgan).

31


12.b Quantoren

Wir definieren die folgenden Schreibweisen.

Definition und Beispiele 12(4). Seien M und N Mengen und A eine Aussage.

• ∀m ∈ M : A (gelesen „Für jedes Element m ∈ M gilt A” oder „Für alle m ∈ Mgilt A” oder „Für jedes m ∈ M gilt A”)∀ heißt All-Quantor und ∀m ∈ M : A heißt All-AussageBeispiel: ∀n ∈N : n >−1 (gelesen „Für alle natürlichen Zahlen n gilt n istgrößer als −1”).

• ∃m ∈ M : A (gelesen „Es gibt (mindestens) ein m ∈ M , so dass A gilt” oder„Es existiert (mindestens) ein m ∈ M , für das A gilt”)∃ heißt Existenz-Quantor und ∃ m ∈ M : A heißt Existenz-AussageBeispiel: ∃ n ∈ N : n ist Primzahl (gelesen „Es existiert (mindestens) einenatürliche Zahl n, so dass n eine Primzahl ist”).

• ∃! m ∈ M : A (gelesen „Es gibt genau ein m ∈ M , so dass A gilt” oder „Esexistiert genau ein m ∈ M , für das A gilt”)∃! heißt Existenz-Quantor und ∃! m ∈ M : A heißt Existenz-AussageBeispiel: ∃! n ∈N : n ist gerade und n ist Primzahl (gelesen „Es existiert ge-nau eine natürliche Zahl n, so dass n gerade und n eine Primzahl ist”).

• ∀m ∈ M ∃ n ∈ N : A (gelesen „Für jedes Element m ∈ M gibt es (minde-stens) ein Element n ∈ N mit A” oder „Für alle m ∈ M gibt es (mindestens)ein Element n ∈ N mit A”).Beispiel: ∀n ∈N ∃ m ∈N : m > n (gelesen „Für jede natürliche Zahl n gibtes (mindestens) eine natürliche Zahl m, die größer als n ist”).

• ∃ m ∈ M ∀n ∈ N : A (gelesen „Es gibt (mindestens) ein Element m ∈ Mso dass für alle Elemente n ∈ N A gilt” oder „Es existiert (mindestens) einm ∈ M so dass für alle n ∈ N A gilt”).Beispiel: ∃ n ∈ N ∀m ∈ N : n É m (gelesen „Es gibt (mindestens) eine na-türliche Zahl n, so dass jede natürliche Zahl m größer oder gleich n ist”).

All-Aussagen und Existenz-Aussagen hängen eng miteinander zusammen. Seidazu M eine Menge und A(m) eine Aussage, die von m ∈ M abhängt. Dann giltfolgende Äquivalenz

¬(∀m ∈ M : A(m)) ⇐⇒ ∃ m ∈ M : ¬A(m).

In Worten: Wenn eine Aussage nicht für alle Elemente einer Menge M gilt, so istdies äquivalent dazu, dass es (mindestens) ein Element in M gibt, für das dieAussage nicht gilt.

32

13 MENGEN 33

Ist z. B. für m ∈ N A(m) die Aussage „m ist eine Primzahl”, so ist die Aussage¬(∀m ∈N : A(m)

)nach obiger Äquivalenz wahr, denn z. B. ist A(4) nicht wahr.

Daher lassen sich All-Aussagen durch die Angabe eines einzigen Gegenbeispielswiderlegen. Es folgt ein weiteres Beispiel.

Sei für p ∈ P A(p) die Aussage „p ist ungerade”. Dann ist die Aussage ∀p ∈ P :A(p) falsch, denn wegen 2 ∈P ist A(2) falsch.

All-Quantoren und Existenz-Quantoren sind im allgemeinen nicht vertausch-bar. Vertauschen wir z. B. in der obigen wahren Aussage

∀n ∈N ∃ m ∈N : m > n

∀n ∈Nmit ∃ m ∈N, so erhalten wir die falsche Aussage

∃ m ∈N ∀n ∈N : m > n.

Dagegen sind All-Quantoren mit All-Quantoren und Existenz-Quantoren mitExistenz-Quantoren vertauschbar.


1. Schreiben Sie die sogenannte starke Goldbachsche12 Vermutung: „Jede ge-rade natürliche Zahl größer als 2 ist eine Summe von zwei Primzahlen.“und deren Negation unter Verwendung von Quantoren (12(4)) ohne dasNegationszeichen ¬.

Hinweis: Sie können die Menge M := {n ∈N | n Ê 2} verwenden.

2. Formulieren Sie eine wahre mathematische Aussage der Form ∃ ∀ ∃ : Amit Quantoren (12(4)) und in Worten, und formulieren Sie die Negation¬(∃ ∀ ∃ : A) dieser Aussage ohne das Negationszeichen ¬ mit Quantorenund in Worten.

13 Mengen

Wir haben schon, ohne den Begriff der Menge definiert zu haben, die Mengender natürlichen, ganzen, rationalen und reellen Zahlen, die Menge der Primzah-len usw. verwendet. Eine präzise Definition des Begriffs Menge geschieht in der

12Christian Goldbach (? 18. März 1690 in Messina; † 20. November (jul.)/ 1. Dezember 1764(greg.) in Moskau) war ein deutscher Mathematiker. Goldbach unternahm wichtige Arbeiten imBereich der Mathematik. Er ist heute besonders wegen seiner bis heute weder bewiesenen nochwiderlegten Goldbachschen Vermutung bekannt, die er im Jahr 1742 in einem Brief an Euler for-mulierte. Die Goldbachsche Vermutung gehört zu den ältesten und bedeutendsten ungelöstenProblemen der Zahlentheorie (Quelle: http://de.wikipedia.org/wiki/Christian_Goldbach).

33

13 MENGEN 34

Axiomatischen Mengenlehre, d. h. üblicherweise in der sogenannten Zermelo13-Fraenkel14-Mengenlehre, womit wir uns hier und auch in den ersten Semesternnicht beschäftigen werden. Im Rahmen der in Abgrenzung zur AxiomatischenMengenlehre heute sogenannten Naiven Mengenlehre hat Cantor15 den Men-genbegriff 1895 definiert.

Definition 13(1). Unter einer Menge verstehen wir jede Zusammenfassung Mvon bestimmten wohlunterschiedenen Objekten m unserer Anschauung oderunseres Denkens (welche die Elemente von M genannt werden) zu einem Gan-zen.

Diese Definition erfüllt nicht unsere in einem früheren Kapitel formulierten For-derungen, denn z. B. wurden die Begriffe „Zusammenfassung”, „Objekt“, „Gan-zen” und „wohlunterschieden“ nicht definiert.

Mengen sind ohne die Theorie der Axiomatischen Mengenlehre ein problemati-scher Begriff. Zum Beispiel führt die Annahme, dass die Menge aller Mengen, diesich selbst nicht als Element enthalten, existiert, auf einen Widerspruch. Diesesogenannte Russellsche Antinomie ist ein von Bertrand Russell16 und Ernst Zer-melo entdecktes Paradoxon der Naiven Mengenlehre, das Russell 1903 publi-zierte, und das daher seinen Namen trägt. Dieses Paradoxon wurde allgemeinerfür Klassen statt für Mengen formuliert. Da wir hier keine Klassen betrachten,formulieren wir es für Mengen.

Russellsche Antinomie 13(2). Angenommen, es existiert die Menge

M := {A | A ist eine Menge ∧ A ∉ A}.

Dann gilt M ∈ M oder M ∉ M . Nach Definition von M folgt

M ∈ M =⇒ M ∉ M ∧ M ∉ M =⇒ M ∈ M .

13Ernst Friedrich Ferdinand Zermelo (? 27. Juli 1871 in Berlin; † 21. Mai 1953in Freiburg im Breisgau) war ein deutscher Mathematiker (Quelle: Wikipediahttp://de.wikipedia.org/wiki/Zermelo).

14Adolf Abraham Halevi Fraenkel (∗ 17. Februar 1891 in München;† 15. Oktober 1965 inJerusalem) war ein deutsch-israelischer Mathematiker. Weltbekannt wurde Fraenkel für sei-ne Arbeiten zur Mengenlehre. Die Einleitung in die Mengenlehre, sein erstes bedeutendesWerk zu dem Thema, das er später selbst ins Englische und Hebräische übertrug, schrieb er1917/18, und es erschien 1919. Er knüpfte an die Arbeit von Ernst Zermelo an und optimier-te die Zermelo-Mengenlehre von 1907, vor allem indem er 1921 das Ersetzungsaxiom ergänzte,das fester Bestandteil der heute maßgeblichen Zermelo-Fraenkel-Mengenlehre wurde (Quelle:http://de.wikipedia.org/wiki/Adolf_Abraham_Halevi_Fraenkel).

15Georg Cantor (? 19. Februar (jul.)/ 3. März 1845 (greg.) in Sankt Petersburg; † 6. Januar 1918in Halle an der Saale) war ein deutscher Mathematiker. Cantor ist bekannt als der Begründer derMengenlehre (Quelle: http://de.wikipedia.org/wiki/Georg_Cantor).

16Bertrand Arthur William Russell, 3. Earl Russell (∗ 18. Mai 1872 bei Trellech, Monmouthshi-re, Wales; † 2. Februar 1970 in Penrhyndeudraeth, Gwynedd, Wales) war ein britischer Philosoph,Mathematiker und Logiker. Zusammen mit Alfred N. Whitehead veröffentlichte er mit den Prin-cipia Mathematica eines der bedeutendsten Werke des 20. Jahrhunderts über die Grundlagen derMathematik (Quelle: http://de.wikipedia.org/wiki/Bertrand_Russell).

34

13 MENGEN 35

In beiden Fällen erhalten wir also einen Widerspruch.

Somit war eine strenge Formulierung der Grundlagen der Naiven Mengenlehrenotwendig, wodurch insbesondere ausgeschlossen werden musste, dass obigesKonstrukt M eine Menge ist.

Zudem ist die gleichzeitige Auswahl von Elementen aus unendlich vielen Men-gen nur durch das sogenannte Auswahlaxiom möglich. Das Auswahlaxiom istein die Zermelo-Fraenkel-Mengenlehre ergänzendes Axiom. Es wurde erstmalsvon Ernst Zermelo 1904 formuliert. Es besagt, dass zu jeder Menge von nicht-leeren Mengen eine Auswahlfunktion existiert, nämlich eine Funktion, die jederdieser nichtleeren Mengen ein Element derselben zuordnet, und somit ein Ele-ment dieser Menge ”auswählt“. Für endlich viele nichtleere Mengen ist diesesAxiom nicht notwendig, da sich in diesem Fall die Existenz der Auswahlfunktionaus den anderen Axiomen der Zermelo-Fraenkel-Mengenlehre folgern lässt.

Die Zermelo-Fraenkel-Mengenlehre ohne Auswahlaxiom wird mit Z F bezeich-net, mit Auswahlaxiom mit Z FC (wobei das C für das engl. Wort choice, alsoAuswahl oder Wahl steht). Z FC wird heute als das grundlegende Axiomensy-stem für die Mathematik angesehen. Wir werden uns hier auf die Naive Men-genlehre und das Auswahlaxiom, auf die Nennung einiger Beispiele für Axiomein Z F , und ansonsten ohne Zitate auf die stillschweigende Verwendung von Z Fbeschränken.

Definition 13(3). 1. Sei M eine Menge und x ein Objekt. Wir schreiben x ∈M , wenn x ein Element der Menge M ist, und andernfalls x ∉ M .

2. Seien M und N Mengen. N heißt eine Teilmenge von M (Schreibweise:N ⊆ M), wenn gilt: Für jedes a ∈ N gilt a ∈ M . Ist N ⊆ M , so sprechen wirauch von einer Inklusion von N in M . Andernfalls schreiben wir N * M .

Beispiele für Axiome in ZF 1. 1. Leermengenaxiom Es gibt eine Menge ;,die keine Elemente enthält.

2. Potenzmengenaxiom Für jede Menge M gibt es die Potenzmenge P (M),deren Elemente genau die Teilmengen von M sind.

Ein Beispiel einer Potenzmenge ist

P ({1,2,3}) = {;, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

Der Beweis dieser Gleichheit besteht einfach aus einer Aufzählung aller Teil-mengen von {1,2,3} mit 0,1,2 oder 3 Elementen.

Teilmengen einer Menge M können auch wie folgt über eine Eigenschaft E defi-niert werden.

N := {a ∈ M |a erfüllt Eigenschaft E

}⊆ M .

35

13 MENGEN 36

Diese Definition liest sich wie folgt: „N ist definiert als die Menge aller Elementea aus M , welche die Eigenschaft E haben”.

E muss dabei eine mathematisch definierte Eigenschaft sein, die von jedema ∈ M entweder erfüllt wird oder nicht. Das erfordert jedoch nicht, dass wir diesauch für jedes Element a ∈ M entscheiden oder in einer bestimmten Zeit ent-scheiden können.

Beispiele für solche Teilmengen sind die in einem früheren Kapitel bereits defi-nierten

2Z= {2z | z ∈Z} = {a | ∃z ∈Z : a = 2z} ⊆Zund

2Z−1 = {2z −1 | z ∈Z} = {a | ∃z ∈Z : a = 2z −1} ⊆Z.

Weitere Beispiele sind {n ∈ N |n > 1000} ⊆ N und {x ∈ R |x >p2} ⊆ R. Für eine

Menge M können wir die Potenzmenge von M nun schreiben als

P (M) = {N | N ⊆ M }.

Definition 13(4). Seien M und N Mengen.

1. M und N heißen gleich (Schreibweise: M = N ), genau dann, wenn N ⊆ Mund M ⊆ N gilt.

2. M ∪N := {a | a ∈ M ∨a ∈ N } heißt Vereinigung von M und N .

3. M ∩N := {a | a ∈ M ∧a ∈ N } heißt Durchschnitt von M und N .

4. M und N heißen disjunkt, wenn M ∩N =; gilt.

5. N \M := {a ∈ N | a ∉ M } heißt Restmenge (auch Komplement oder Komple-mentärmenge) von M in N .

Beispielsweise gilt für N := {1,2,3,6} und M := {6,7,8} M ∪ N = {1,2,3,6,7,8},M∩N = {6}, N \M = {1,2,3}. Des weiteren giltN\2N−1 = 2N undN\2N= 2N−1.

Für jede Teilmenge M ⊆R sei −M := {−x | x ∈ M }.

Wir listen nun einige uns schon bekannte Mengen auf.

Auflistung 13(5). 1. N ist die nach den Peano-Axiomen existierende Mengeder natürlichen Zahlen.

2. N0 =N∪{0}. In manchen Büchern und Skripten wird die Menge der natür-lichen Zahlen als {0,1,2,3, . . .} definiert.

3. Für n ∈N istNn = {k ∈N | k É n}.

4. Z=N0 ∪−N ist die Menge der ganzen Zahlen. Es giltN⊆Z.

36

13 MENGEN 37

5. Q= { rs | r, s ∈Z∧ s 6= 0} ist die Menge der rationalen Zahlen. Es gilt Z⊆Q.

6. R ist die Menge der reellen Zahlen, und wird später axiomatisch einge-führt. Es gilt Q ⊆ R. Aber es gibt unendlich viele reelle Zahlen, die nichtrational sind. Denn wie wir bereits wissen gilt

p2 ∈ R \Q und π ∈ R \Q.

Und daraus folgt für jedes q ∈Q\ {0} q ·p2 ∈R\Q und q ·π ∈R\Q.

Nun beweisen wir einige Aussagen über die Gleichheit von Mengen.

Hilfssatz 13(6). Für alle Mengen M und N gilt N ∩M =;⇐⇒ N \ M = N .

Beweis. „=⇒”: N \ M ⊆ N gilt nach Definition (13(4)). Sei also x ∈ N . Wegen N ∩M =; ist x ∉ M . Also gilt x ∈ N \ M . Es folgt N ⊆ N \ M , und damit N \ M = N .„⇐=”: Angenommen, es gibt ein x ∈ N ∩M . Dann ist x ∈ N und x ∈ M , folglichx ∉ N \ M = N , ein Widerspruch. Also gilt N ∩M =;.

Satz 13(7). Für alle Mengen M und N gelten die Aussagen

1. P (M)∩P (N ) =P (M ∩N ) 2. P (M)∪P (N ) ⊆P (M ∪N ).

Beweis. Für alle Objekte A gilt

1. A ∈P (M)∩P (N ) ⇐⇒ A ∈P (M)∧ A ∈P (N ) ⇐⇒ A ⊆ M ∧ A ⊆ N⇐⇒ A ⊆ M ∩N ⇐⇒ A ∈P (M ∩N ).

2. A ∈P (M)∪P (N ) ⇐⇒ A ∈P (M)∨ A ∈P (N ) ⇐⇒ A ⊆ M ∨ A ⊆ N=⇒ A ⊆ M ∪N ⇐⇒ A ∈P (M ∪N ).

Definition 13(8). Hat eine Menge M für ein n ∈ N0 genau n Elemente, so sei|M | := n, ansonsten sei |M | :=∞. |M| heißt die Anzahl der Elemente (auch Kardi-nalität oder Mächtigkeit) von M . Im Fall |M | = n ∈N0 heißt M endlich, und imFall |M | =∞ unendlich.

Das Symbol ∞ im Fall |M | = ∞ bedeutet hier lediglich, dass der Fall |M | ∈ N0

nicht vorliegt. Die Menge M hat dann keine endliche Anzahl von Elementen.

13..2 Übungsaufgaben

1. Beweisen Sie: Für alle Mengen A,B ,C gilt A \ (B ∪C ) = A \ B ∩ A \C .

Hinweis: Verwenden Sie Definition 13(4).

37

13 MENGEN 38

2. Beweisen Sie: Für Mengen M und N gilt im allgemeinen nichtP (M)∪P (N ) =P (M ∪N ).

Hinweis: Analysieren Sie den Beweis von Satz 13(7). Es gibt Gegenbeispielemit |M | = |N | = 1 (13(8)).

Wir hatten bereits Vereinigung und Durchschnitt von zwei Mengen definiert(13(4)). Diese Definition wird nun auf beliebig viele Mengen verallgemeinert.

Definition 13(9). Sei I eine Menge und für jedes i ∈ I sei Mi eine Menge.⋃i∈I

Mi := {m | ∃ i ∈ I : m ∈ Mi } ist die Vereinigung der Mengen Mi über alle i ∈ I ,⋂i∈I

Mi := {m | ∀i ∈ I : m ∈ Mi } ist der Durchschnitt der Mengen Mi über alle i ∈ I .

Beispiele 13(10). 1. Sei Mi := {1, i } für i ∈N. Dann gilt wegen i ∈ Mi für jedesi ∈ N ⋃

i∈NMi = N und es gilt ∀i , j ∈ N mit i 6= j : Mi ∩ M j = {1} und∀i ∈N : Mi 6= ;.

2. Sei Mi := N∩ {i − 1} für i ∈ N. Dann gilt wegen i ∈ Mi+1 für jedes i ∈N

⋃i∈NMi =N und es gilt ∀i , j ∈Nmit i 6= j : Mi ∩M j =; und M1 =;.

3. Sei Mi := {i } für i ∈N. Dann gilt wegen i ∈ Mi für jedes i ∈N ⋃i∈NMi =N

und es gilt ∀i , j ∈Nmit i 6= j : Mi ∩M j =; und ∀i ∈N : Mi 6= ;.

In den obigen drei Beispielen gilt⋃

i∈NMi =N. Im Sinne des folgenden Begriffsder Partition einer Menge handelt es sich nur in dem dritten Beispiel um einePartition.

Definition 13(11). Seien M und I 6= ; Mengen. Ein System Mi ⊆ M , i ∈ I , heißtPartition (auch Zerlegung) von M , wenn gilt:

1. ∀i ∈ I : Mi 6= ;.

2.⋃i∈I

Mi = M .

3. ∀i , j ∈ I : i 6= j =⇒ Mi ∩M j =;.

Sind nur die Eigenschaften 2. und 3. in Definition 13(11) erfüllt, so heißt M dis-junkte Vereinigung der Mengen Mi , i ∈ I .

Bemerkung 13(12). Ist eine Partition einer Menge M gegeben, so folgt aus derDefinition der Partition, dass M 6= ; ist. Eine Partition einer Menge M ist dieUnterteilung von M in ein System von Teilmengen ; 6= Mi ⊆ M , i ∈ I , so dassjedes x ∈ M in genau einer der Teilmengen Mi enthalten ist. Das obige SystemMi := {i }, i ∈N, (13(10) 3.) ist eine Partition von N. Weitere Beispiele folgen nachder nächsten Definition.

38

13 MENGEN 39

Definition 13(13). 1. Seien x und y zwei Objekte. Dann heißt

(x, y) := {{;, {x}}, {y}}

geordnetes Paar.

2. Seien X und Y Mengen. Dann heißt die Menge

X ×Y := {(x, y) | x ∈ X ∧ y ∈ Y }

der geordneten Paare (x, y) mit x ∈ X und y ∈ Y das direkte Produkt (auchkartesische Produkt) der Mengen X und Y .

3. Für jede Menge X sei X 2 := X ×X . X 2 heißt auch die 2-te Potenz von X .

Hilfssatz 13(14). Seien X und Y Mengen. Für alle (x1, y1), (x2, y2) ∈ X ×Y gilt

(x1, y1) = (x2, y2) ⇐⇒ x1 = x2 ∧ y1 = y2.

Beweis. Es gilt (x1, y1) = (x2, y2) ⇐⇒ {{;, {x1}}, {y1}} = {{;, {x2}}, {y2}}⇐⇒ {;, {x1}} = {;, {x2}}∧ {y1} = {y2} ⇐⇒ x1 = x2 ∧ y1 = y2.

Als weiteres Beispiel für die Gleichheit von Mengen beweisen wir nun den fol-genden

Hilfssatz 13(15). Für alle Mengen A,B ,C und D gilt

(A∪B)× (C ∪D) = (A×C )∪ (A×D)∪ (B ×C )∪ (B ×D).

Beweis. Es gilt(A∪B)× (C ∪D) = {(x, y) | x ∈ A∪B ∧ y ∈C ∪D}= {(x, y) | (x ∈ A∧ y ∈C )∨ (x ∈ A∧ y ∈ D)∨ (x ∈ B ∧ y ∈C )∨ (x ∈ B ∧ y ∈ D)}

= {(x, y) | x ∈ A∧ y ∈C }∪ {(x, y) | x ∈ A∧ y ∈ D}

∪ {(x, y) | x ∈ B ∧ y ∈C }∪ {(x, y) | x ∈ B ∧ y ∈ D}

= (A×C )∪ (A×D)∪ (B ×C )∪ (B ×D).

Es folgen nun weitere Beispiele für Partitionen.

Beispiele 13(16). 1. Sei I := {1,2,3} und seien M1 := {x ∈ R | x < 0}, M2 := {0}und M3 := {x ∈ R | x > 0}. Dann ist das System Mi ⊆ R, i ∈ I , eine PartitionvonR, denn für jedes i ∈ I ist Mi 6= ;, es gilt

⋃3i=1 Mi =R und für alle i , j ∈ I

mit i 6= j ist Mi ∩M j =;.

39

14 RELATIONEN UND ÄQUIVALENZRELATIONEN 40

2. Für r ∈ R sei Mr := {(x, x + r ) | x ∈ R}. Dann ist das System Mr ⊆ R2,r ∈ R,eine Partition von R2.

Beweis. Für jedes r ∈ R ist wegen (0,r ) ∈ Mr Mr 6= ;. Ist (a,b) ∈ R2, so giltfür x := a und r := b − a (a,b) = (x, x + r ) ∈ Mr . Daher ist

⋃r∈RMr = R2.

Angenommen, es gibt für r1,r2 ∈Rmit r1 6= r2 (a,b) ∈ Mr1∩Mr2 . Dann gibtes x, y ∈ R mit (a,b) = (x, x + r1) = (y, y + r2). Hieraus folgt nach Hilfssatz13(14) x = y und x + r1 = y + r2, und daraus der Widerspruch r1 = r2. Alsogilt für r1 6= r2 Mr1 ∩Mr2 =;.


1. Beweisen Sie: Für alle Mengen A,B ,C und D gilt

(A∩B)× (C ∩D) = (A×C )∩ (A×D)∩ (B ×C )∩ (B ×D).

Hinweis: Studieren Sie den Beweis von Hilfssatz 13(15), und verwendenSie die Definitionen 13(13) und 13(4).

2. Die MengeN1 (bzw.N2) hat genau eine Partition (13(11)) (bzw. genau zweiPartitionen), nämlich {1} (bzw. {1,2} und {1}, {2}). Wie viele und welche Par-titionen hat die MengeNn für n = 3 und für n = 4?

Hinweis: Mit der Bellzahl (http://de.wikipedia.org/wiki/Bellzahl) könnenSie kontrollieren, ob die von Ihnen gefundenen Anzahlen der Partitionenrichtig sind.

14 Relationen und Äquivalenzrelationen

14.a Relationen

Definition 14(1). Seien X und Y Mengen. Eine Relation R zwischen den Men-gen X und Y ist eine Teilmenge R ⊆ X × Y . Wir schreiben für alle x ∈ X , y ∈Y xR y , genau dann, wenn (x, y) ∈ R ist.

Ist X eine Menge und R eine Relation zwischen X und X , so sprechen wir voneiner Relation auf X . Wir betrachten einige Beispiele für Relationen.

Beispiele 14(2). 1. Für eine beliebige Menge X sei

R := {(x, x) | x ∈ X } ⊆ X ×X .

Dann ist für x, y ∈ X xR y genau dann, wenn x = y ist. R ist eine Relationauf X .

40


2. SeiR := {(x, y) | x, y ∈Z∧∃z ∈Z : x · z = y} ⊆Z×Z.

Dann ist für x, y ∈ Z xR y genau dann, wenn x | y gilt. R ist eine Relationauf Z.

3. SeiR := {(x, y) | x ∈N, y ∈Z∧x + y = 0} ⊆N×Z.

R ist eine Relation zwischenN und Z.

4. Sei

R := {(x, y) | x, y ∈R∧ y ≤ x} ⊆R×R.

x R

y R

R ist eine Relation auf R.

14.b Äquivalenzrelationen

Wie gesehen gibt es sehr verschiedene Arten von Relationen. Uns interessierennun zunächst Relationen ähnlich der Gleichheitsrelation „=”. Diese nennen wirÄquivalenzrelationen.

Definition 14(3). Sei X 6= ; eine Menge.

1. Eine Relation „∼” auf X heißt eine Äquivalenzrelation auf X , wenn die fol-genden drei Eigenschaften erfüllt sind.

(a) Reflexivität ∀x ∈ X : x ∼ x.

(b) Symmetrie ∀x, y ∈ X : x ∼ y =⇒ y ∼ x.

(c) Transitivität ∀x, y, z ∈ X : (x ∼ y ∧ y ∼ z) =⇒ x ∼ z.

2. Sei „∼” eine Äquivalenzrelation auf X . Zwei Elemente x, y ∈ X heißen äqui-valent wenn x ∼ y gilt. Für jedes x ∈ X sei

[x] := {y ∈ X | x ∼ y}

die Äquivalenzklasse von x. Eine Teilmenge V ⊆ X , die aus jeder Äqui-valenzklasse genau ein Element enthält, heißt ein Vertretersystem (auchRepräsentantensystem) von „∼”.

41


Bemerkung 14(4). Ist „∼” eine Äquivalenzrelation auf einer Menge X , so folgtdie Existenz eines Vertretersystems V ⊆ X von „∼” aus dem Auswahlaxiom.

Beispiele 14(5). 1. Für jede Menge X 6= ; ist das einfachste Beispiel einerÄquivalenzrelation auf X die Gleichheit „=”. Für x, y ∈ X definieren wir al-so x ∼ y :⇐⇒ x = y . Offensichtlich sind die drei Eigenschaften einer Äqui-valenzrelation erfüllt.

2. Die Relation „∼” auf Z sei definiert durch x ∼ y genau dann, wenn x − y ∈2Z ist. Dann ist „∼” eine Äquivalenzrelation auf Z. Die Äquivalenzklassenvon „∼” sind [2] = 2Z und [1] = 2Z−1. Zum Beispiel ist die Menge {1,2} einVertretersystem von „∼”.

Beweis. Für x ∈Z gilt wegen x −x = 0 = 2 ·0 ∈ 2Z x ∼ x, d. h. „∼” ist reflexiv.Für x, y ∈ Z mit x ∼ y folgt y − x = −(x − y) ∈ 2Z, also y ∼ x. Die Relation„∼” ist also symmetrisch. Für x, y, z ∈Zmit x ∼ y und y ∼ z folgt

x − z = (x − y)+ (y − z) ∈ 2Z,

d. h. x ∼ z. Also ist „∼” transitiv, und damit eine Äquivalenzrelation auf Z.Für x ∈Z gilt

x ∈ 2Z⇐⇒ x −2 ∈ 2Z⇐⇒ x ∼ 2 ⇐⇒ x ∈ [2].

Es folgt [2] = 2Z. Für x ∈Z gilt

x ∈ 2Z−1 ⇐⇒ x −1 ∈ 2Z⇐⇒ x ∼ 1 ⇐⇒ x ∈ [1].

Es folgt [1] = 2Z−1. Folglich ist {1,2} ein Vertretersystem von „∼”.

3. Die Relation „∼” auf R sei definiert durch x ∼ y genau dann, wenn x2 = y2

ist. Dann ist „∼” offensichtlich eine Äquivalenzrelation auf R. Die Äquiva-lenzklassen von „∼” sind [0] = {0} und für x ∈R\ {0} [x] = {−x, x}. Damit istz. B. die Menge {y ∈R | y ≥ 0} ein Vertretersystem von „∼”.

4. Die Relation „∼” aufR2 sei definiert durch (a,b) ∼ (c,d) genau dann, wenna = c oder b = d ist. Dann ist „∼” keine Äquivalenzrelation auf R2, denn z.B. gilt (1,0) ∼ (1,1) ∼ (0,1), aber nicht (1,0) ∼ (0,1). Diese Relation ist alsonicht transitiv, und daher keine Äquivalenzrelation auf R2.

Auf R2 definieren wir im Folgenden eine Relation. Im Vorgriff auf die VorlesungLineare Algebra I nennen wir die geordneten Paare (x, y) ∈ R2 Vektoren, undschreiben (x, y) als sogenannten Spaltenvektor

(xy

). Für

(xy

) ∈ R2 ist die Skalar-

multiplikation des Vektors(x

y

)mit einem Skalar λ ∈R definiert als

λ ·(

x

y

):=

(λx

λy

).

42


Beispiel 14(6). Für Vektoren(x1

y1

),(x2

y2

) ∈R2 sei(x1

y1

)∼

(x2

y2

), wenn es eine reelle Zahl λ mit

(x1

y1

)=λ ·

(x2

y2

)gibt.

Die Relation „∼” ist nicht symmetrisch, denn z. B. gilt(0

0

)= 0 ·

(1

1

)=⇒

(0

0

)∼

(1

1

), und wegen λ ·

(0

0

)=

(0

0

)für jedes λ ∈R

gibt es kein λ ∈Rmit

(1

1

)=λ ·

(0

0

). Also gilt nicht

(1

1

)∼

(0

0

).

Die Relation „∼” ist daher keine Äquivalenzrelation auf R2.

Wir ändern die Definition von „∼” in Beispiel 14(6) wie folgt.

Beispiel 14(7). Für Vektoren(x1

y1

),(x2

y2

) ∈R2 sei(x1

y1

)∼

(x2

y2

), wenn es eine reelle Zahl λ> 0 mit

(x1

y1

)=λ ·

(x2

y2

)gibt.

Die Reflexivität ist gegeben, denn für alle(x

y

) ∈R2 gilt(x

y

)= 1 ·

(x

y

)=⇒

(x

y

)∼

(x

y

).

Die Symmetrie ist ebenfalls erfüllt, denn ist(x1

y1

)∼

(x2

y2

), so gibt es eine reelle Zahl λ> 0 mit

(x1

y1

)=λ ·

(x2

y2

).

Es folgt

(x2

y2

)= 1

λ·(

x1

y1

), und daher wegen

1

λ> 0

(x2

y2

)∼

(x1

y1

).

Die Relation „∼” ist auch transitiv, denn ist(x1

y1

)∼

(x2

y2

)und

(x2

y2

)∼

(x3

y3

),

so gibt es reelle Zahlen λ> 0, µ> 0 mit(x1

y1

)=λ ·

(x2

y2

)∧

(x2

y2

)=µ ·

(x3

y3

).

43


Es folgt(x1

y1

)=λ ·

(x2

y2

)= (λ ·µ) ·

(x3

y3

), und daraus wegen λ ·µ> 0

(x1

y1

)∼

(x3

y3

).

Daher ist die Relation „∼” transitiv, und damit eine Äquivalenzrelation auf R2.

Geometrisch erhalten wir in Beispiel 14(7) folgendes Bild: Die Äquivalenzklas-sen von „∼” sind die von

(00

)ausgehenden Strahlen jeweils ohne den Punkt

(00

)und die Menge {

(00

)}. Wenn wir in Beispiel 14(7)λ> 0 durchλ 6= 0 ersetzen, erhal-

ten wir ebenfalls eine Äquivalenzrelation auf R2. Die Äquivalenzklassen hiervonsind alle „Geraden” durch

(00

)jeweils ohne den Punkt

(00

), und die Menge {

(00

)}.


1. Auf N0 sei für k, l ∈N0 die Relation (14(1)) „∼” definiert durch k ∼ l , wennk·l > 0 ist. Beweisen Sie, dass „∼” symmetrisch (14(3)) und transitiv (14(3)),aber nicht reflexiv (14(3)) ist.

2. Ist die Relation „∼” auf N, definiert durch a ∼ b, wenn ein n ∈N0 existiertmit a = b

2n oder b = a2n , eine Äquivalenzrelation (14(3)) aufN? Beweisen Sie

Ihre Antwort.

Wir werden in den beiden nächsten Sätzen beweisen, dass die Menge aller Äqui-valenzrelationen auf einer Menge M 6= ; in einer „1-1 Beziehung“ zu der Mengeder Partitionen von M steht. Genauer gilt: Für jede Menge M 6= ; partitionierteine Äquivalenzrelation auf M die Menge M , und umgekehrt wird durch einePartition der Menge M eine Äquivalenzrelation auf M definiert.

Satz 14(8). Seien M 6= ; eine Menge, „∼” eine Äquivalenzrelation auf M und V ⊆M ein Vertretersystem von „∼”. Dann bildet das System [x], x ∈V , eine Partitionvon M .

Beweis. Wegen M 6= ; ist V 6= ;. Für jedes x ∈V gilt wegen x ∼ x x ∈ [x]. Also ist[x] 6= ;. Wegen x ∈ [x] für jedes x ∈ M gilt

M = ⋃x∈M

[x].

Wegen V ⊆ M und nach Definition von V gilt⋃x∈M

[x] = ⋃x∈V

[x], und hieraus folgt M = ⋃x∈V

[x].

Seien x, y ∈V mit x 6= y . Angenommen, es gibt ein z ∈ [x]∩ [y]. Dann folgt z ∼ xund z ∼ y . Wegen der Symmetrie von „∼” ist dann x ∼ z, und aus der Transitivitätvon „∼” folgt x ∼ y . Dann gilt x, y ∈ [x], und dies ist wegen x, y ∈ V und x 6= ynach Definition von V ein Widerspruch. Also folgt für x 6= y [x]∩ [y] =;.

44

15 ABBILDUNGEN 45

Satz 14(9). Seien M und I 6= ; Mengen. Sei Mi ⊆ M , i ∈ I , eine Partition von M .Die durch

x ∼ y :⇐⇒ ∃i ∈ I : x, y ∈ Mi

auf M definierte Relation ist eine Äquivalenzrelation auf M . Für jedes i ∈ I undfür jedes x ∈ Mi gilt Mi = [x].

Beweis. Sei x ∈ M . Wegen M = ⋃i∈I

Mi gibt es ein i ∈ I mit x ∈ Mi . Also gilt nach

Definition von „∼” x ∼ x, d. h. die Relation „∼” ist reflexiv. Die Symmetrie von„∼” ist offensichtlich. Zu x, y, z ∈ M mit x ∼ y und y ∼ z gibt es i , j ∈ I mit x, y ∈Mi und y, z ∈ M j . Dann ist y ∈ Mi ∩M j , und daraus folgt i = j . Folglich gilt x, z ∈Mi , d. h. x ∼ z. Also ist „∼” transitiv, und damit eine Äquivalenzrelation auf M .Für alle i ∈ I , x ∈ Mi und y ∈ M gilt y ∈ Mi ⇐⇒ y ∼ x ⇐⇒ y ∈ [x]. Es folgt Mi =[x].


1. Beweisen Sie, dass die Mengen A := {(x, y) ∈ R2 | x < 0}, B := {(x, y) ∈ R2 |x = 0} und C := {(x, y) ∈ R2 | x > 0} eine Partition (13(11)) von R2 bilden.Geben Sie die zugehörige Äquivalenzrelation (14(9)) „∼” und unendlichviele paarweise verschiedene Vertretersysteme (14(3)) von „∼” an.

15 Abbildungen

Definition 15(1). Seien X und Y Mengen. Eine Abbildung (auch Funktion oderlinkstotale und rechtseindeutige Relation)

f : X → Y

ist eine Relation f ⊆ X ×Y , welche die folgende Eigenschaft erfüllt:

∀x ∈ X ∃!y ∈ Y : x f y.

Für dieses für jedes x ∈ X eindeutig bestimmte y ∈ Y mit x f y schreiben wirf (x) := y , und nennen f (x) Bildpunkt oder Bild von x unter f . X heißt Definiti-onsmenge (auch Definitionsbereich) von f und Y heißt Zielmenge (auch Werte-vorratsmenge) von f .

Beispiele 15(2). 1. Die Relation f := {(n,n2) | n ∈ N} ⊆ N×N ist eine Abbil-dung, denn für jedes n ∈ N gibt es genau ein m ∈ N mit n f m, nämlichm = n2. Gemäß 15(1) schreiben wir f : N → N mit f (n) := n2 für jedesn ∈N.

45

15 ABBILDUNGEN 46

2. Die Relation f := {(1,1), (1,2)} ⊆R×R ist keine Abbildung, da für x := 1 ∈Rzwei Elemente y ∈Rmit x f y existieren.

Hilfssatz 15(3). Für Abbildungen f : X → Y und g : X → Y gilt nach Definition15(1) f = g genau dann, wenn für alle x ∈ X f (x) = g (x) ist.

Bemerkung 15(4). Ist f : X → Y eine Abbildung, so gibt es für Y auch die Be-zeichnungen Wertemenge oder Wertebereich von f . Diese Bezeichnungen wer-den teils aber auch für die sogenannte Bildmenge von f (s. unten) verwendet,so dass die jeweilige Definition nachgelesen werden muss.

Definition 15(5). Sei f : X → Y eine Abbildung.

1. Für A ⊆ X heißt die Menge

f (A) := { f (x) | x ∈ A}

die Bildmenge von A unter f . Speziell heißt f (X ) die Bildmenge von f .

2. Für B ⊆ Y heißt die Menge

f −1(B) := {x ∈ X | f (x) ∈ B}

die Urbildmenge von B unter f .

3. Für y ∈ Y heißtf −1[y] := f −1({y})

die Urbildmenge von y unter f. Ein Element x ∈ f −1[y] heißt Urbild von yunter f .

Beispiel 15(6). Sei f :R→R die Abbildung f (x) := x2.

1. Das Urbild eines Elements y ∈R unter f ist im allgemeinen nicht eindeu-tig bestimmt, denn es gilt z. B. f −1[4] = {−2,2}.

2. Es existiert nicht für alle y ∈R ein Urbild unter f . Zum Beispiel gilt f −1[−1] =;, da es kein x ∈ R mit x2 =−1 gibt. Allgemeiner gilt f −1({y ∈ R | y < 0}) =;.

3. f (R) = {y ∈R | y ≥ 0} ist die Bildmenge von f .

Bemerkung 15(7). Wird eine Abbildung f : X → Y definiert, so müssen wir, so-fern es nicht offensichtlich ist, auch die Wohldefiniertheit der Abbildung f : X →Y beweisen. Das heißt zunächst, für jedes x ∈ X müssen wir f (x) ∈ Y beweisen.Es gibt mehrere andere Formen einer nachzuweisenden Wohldefiniertheit, diespäter besprochen werden.

46

15 ABBILDUNGEN 47

Beispiele 15(8). 1. Sind X 6= ; und Y 6= ; Mengen und y ∈ Y , so heißt dieAbbildung f : X → Y , definiert durch f (x) := y für jedes x ∈ X , konstanteAbbildung (auch konstant). Offensichtlich ist f wohldefiniert.

2. Sei f : N→ N definiert durch f (n) := n3+32 . Dann gilt z. B. f (2) = 11

2 ∉ N.Also ist f nicht wohldefiniert, und daher keine Abbildung.

3. Sei f :N→ R definiert durch f (n) := n3−1n−1 . Dann ist f nicht wohldefiniert,

denn f (1) ist nicht definiert, da der Quotient n3−1n−1 für n = 1 nicht definiert

ist. Also ist f keine Abbildung.

4. Sei f :N→Z definiert durch f (n) := n4−1n2+1 . Dann ist f wohldefiniert, denn

für jedes n ∈N gilt n2 +1 > 0 und wegen n4 −1 = (n2 −1)(n2 +1) ist f (n) =n2 −1 ∈Z für jedes n ∈N.

Es gibt Abbildungen f : X → Y , bei denen die in Beispiel 15(6) beschriebenenFälle f −1(B) = ; für ; 6= B ⊆ Y oder | f −1[y]| > 1 für y ∈ Y nicht auftreten. Diesführt zu der folgenden Definition, welche in fast allen Teilgebieten der Mathe-matik von zentraler Bedeutung ist.

Definition 15(9). Sei f : X → Y eine Abbildung.

1. f heißt injektiv, wenn gilt

∀x1, x2 ∈ X : f (x1) = f (x2) =⇒ x1 = x2.

2. f heißt surjektiv, wenn gilt

∀y ∈ Y ∃x ∈ X : f (x) = y,

d. h. es gilt Y ⊆ f (X ).

3. f heißt bijektiv, wenn f injektiv und surjektiv ist.

Zu bemerken ist, dass für eine Abbildung f : X → Y die Inklusion f (X ) ⊆ Y im-mer gilt. Die Surjektivität von f : X → Y ist also äquivalent zu Y = f (X ).

Die folgenden Beispiele in Abbildung 1 veranschaulichen die Injektivität, Sur-jektivität und Bijektivität von Abbildungen.

Beispiele 15(10). 1. Seien a,b ∈ R mit a 6= 0. Die Abbildung f : R→ R mitf (x) := ax +b ist injektiv und surjektiv, also auch bijektiv.

Beweis. Seien x1, x2 ∈ R mit f (x1) = f (x2). Nach Definition von f ist dannax1 +b = ax2 +b. Es folgt ax1 = ax2, und wegen a 6= 0 x1 = x2. f ist also

injektiv. Sei nun y ∈ R. Wegen a 6= 0 können wir x := y−ba ∈ R definieren.

Wegen f (x) = y ist f surjektiv, und damit auch bijektiv.

47

15 ABBILDUNGEN 48

Abbildung 1: Zur Injektivität, Surjektivität und Bijektivität von Abbildungen

(a) Eine injektive, surjektive undbijektive Abbildung

X Y

1

2

3

4

a

b

c

d

(b) Eine injektive, nicht surjektiveund nicht bijektive Abbildung

X Y

1

2

3

a

b

c

d

(c) Eine surjektive, nicht injektiveund nicht bijektive Abbildung

X Y

1

2

3

4

a

b

c

(d) Die Abbildung erfüllt keineder drei Eigenschaften

X Y

1

2

3

a

b

c

d

2. Die Abbildung f :R\ {0} →Rmit f (x) := 1x ist injektiv, aber nicht surjektiv,

und daher nicht bijektiv.

Beweis. Seien x1, x2 ∈R\{0} mit f (x1) = f (x2). Dann gilt 1x1

= 1x2

, und daraus

folgt x1 = x2. Also ist f injektiv. Zu y := 0 ∈R gibt es kein x ∈R\{0} mit 1x = y .

Folglich ist f nicht surjektiv, und daher nicht bijektiv.

3. Sei f :N→ {0,1} für n ∈N definiert durch f (n) := 1, wenn n ungerade undf (n) := 0, wenn n gerade ist. f ist surjektiv, aber nicht injektiv, denn für0 ∈ {0,1} ist f (2) = f (4) = 0, und für 1 ∈ {0,1} ist f (1) = 1.

4. f :N×N→N sei definiert durch f ((m,n)) := m+n+m ·n. f ist nicht injek-tiv, denn es gilt f ((n,m)) = f ((m,n)) für alle m,n ∈N. f ist nicht surjektiv,

48

15 ABBILDUNGEN 49

denn für 1 ∈ N gibt es kein (m,n) ∈ N×N mit f ((m,n)) = 1, da für allem,n ∈Nm +n +m ·n ≥ 3 ist.

Nun werden die Begriffe der Injektivität, Surjektivität und Bijektivität einer Ab-bildung f : X → Y in einer äquivalenten Form formuliert.

Bemerkung 15(11). Sei f : X → Y eine Abbildung. Dann gelten die folgendenÄquivalenzen.

• f ist injektiv ⇐⇒ Für jedes y ∈ Y hat die Urbildmenge f −1[y] höchstensein Element.

f ist also injektiv genau dann, wenn es für jedes y ∈ Y höchstens ein x ∈ Xmit f (x) = y gibt.

• f ist surjektiv ⇐⇒ Für jedes y ∈ Y hat die Urbildmenge f −1[y] mindestensein Element.

f ist also surjektiv genau dann, wenn es für jedes y ∈ Y mindestens einx ∈ X mit f (x) = y gibt.

• f ist bijektiv ⇐⇒ Für jedes y ∈ Y hat die Urbildmenge f −1[y] genau einElement.

f ist also bijektiv genau dann, wenn es für jedes y ∈ Y genau ein x ∈ X mitf (x) = y gibt.

Beispiel 15(12). Sei f : {1,2} → {1,2,3} definiert durch f (x) := x. Dann ist f nachBemerkung 15(11) injektiv, aber nicht surjektiv, denn für y ∈ {1,2,3} gibt es füry 6= 3 genau ein x ∈ {1,2} mit f (x) = y , nämlich x = y , und für y = 3 gibt es keinx ∈ {1,2} mit f (x) = y .

Definition 15(13). Sei f : X → Y eine bijektive Abbildung. Dann heißt die Ab-bildung

f −1 : Y → X ,

definiert durch f −1(y) := x für y ∈ Y und für das eindeutig bestimmte x ∈ X mitf (x) = y , die Umkehrabbildung (auch inverse Abbildung) von f .

Beispiel 15(14). 1. Nach Beispiele 15(10) 1. ist für a,b ∈ R mit a 6= 0 die Ab-bildung f :R→Rmit f (x) := ax +b bijektiv. Für jedes y ∈R gilt

f (y −b

a) = a · y −b

a+b = y.

Folglich ist nach Definition 15(13) die Abbildung

f −1 :R→R mit f −1(y) = y −b

a

die Umkehrabbildung von f .

49

15 ABBILDUNGEN 50

2. Die Abbildung f :Z→ 2Z, definiert durch f (z) := 2z, ist nach Bemerkung15(11) bijektiv. Denn für jedes y ∈ 2Z gibt es genau ein z ∈Z, nämlich z =12 y , mit f (z) = y . Folglich ist nach Definition 15(13) die Abbildung f −1 :2Z→Zmit f −1(y) = 1

2 y die Umkehrabbildung von f .

Satz 15(15). Für jede bijektive Abbildung f : X → Y gelten die Aussagen

1. Die Umkehrabbildung f −1 : Y → X von f ist bijektiv.

2. Es gilt ( f −1)−1 = f .

Beweis. 1. Sei x ∈ X beliebig. Nach Definition 15(13) ist f −1(y) = x genau füry = f (x) erfüllt. Es gibt also für jedes x ∈ X genau ein y ∈ Y mit f −1(y) = x.Daher ist f −1 nach Bemerkung 15(11) bijektiv.

2. ( f −1)−1 : X → Y ist nach Definition 15(13) für x ∈ X definiert durch ( f −1)−1(x) =y , wobei f −1(y) = x ist. Die letzte Gleichung ist nach Definition 15(13)äquivalent zu f (x) = y . Es folgt ( f −1)−1(x) = y = f (x), und dann aus Hilfs-satz 15(3) ( f −1)−1 = f .

Aus mathematischen Objekten werden oftmals neue Objekte derselben Art kon-struiert. Dies geschieht für Abbildungen in einer ersten Form in der nächstenDefinition.

Definition 15(16). Seien f : X → Y und g : Y ′ → Z Abbildungen mit Y ⊆ Y ′.Dann heißt die Abbildung

g ◦ f : X → Z mit (g ◦ f )(x) := g ( f (x))

die Verkettung (auch das Kompositum) von g und f .

Beispiel 15(17). Seien f :N→Z und g :Z→Q definiert durch

f (n) := n −n2 für n ∈N und g (z) := 1

z2 +1für z ∈Z.

Dann sind f und g wegen n −n2 ∈Z für n ∈N, z2 +1 ∈Z\ {0} für z ∈Zwohldefi-niert. g ◦ f :N→Q ist die Abbildung

(g ◦ f )(n) = g ( f (n)) = g (n −n2) = 1

(n −n2)2 +1für n ∈N.

Die Verkettung von Abbildungen ist im Sinne des folgenden Satzes „assoziativ”.

Satz 15(18). (Assoziativgesetz für Abbildungen) Für alle Abbildungen f : A → B ,g : B ′ →C und h : C ′ → D mit B ⊆ B ′ und C ⊆C ′ gilt

h ◦ (g ◦ f ) = (h ◦ g )◦ f .

50

15 ABBILDUNGEN 51

Beweis. Für jedes a ∈ A gilt

(h ◦ (g ◦ f ))(a) = h((g ◦ f )(a)) = h(g ( f (a))) = (h ◦ g )( f (a)) = ((h ◦ g )◦ f )(a).

Aus Hilfssatz 15(3) folgt h ◦ (g ◦ f ) = (h ◦ g )◦ f .

Abbildung 2: Zur Assoziativität der Verkettung von Abbildungen f : A → B , g :B →C und h : C → D

A B C Df g h

g ◦ f

h ◦ (g ◦ f )

(h ◦ g )◦ f

h ◦ g

Wie verhalten sich die Injektivität, die Surjektivität und die Bijektivität von Ab-bildungen bei einer Verkettung? Eine Antwort gibt der folgende

Satz 15(19). Seien f : X → Y und g : Y ′ → Z Abbildungen mit Y ⊆ Y ′. Danngelten die folgenden Aussagen.

1. Ist g ◦ f injektiv, so ist f injektiv.

2. Ist g ◦ f surjektiv, so ist g surjektiv.

3. Sind f und g injektiv, so ist g ◦ f injektiv.

4. Sind f und g surjektiv und gilt Y = Y ′, so ist g ◦ f surjektiv.

Beweis. 1. Seien x1, x2 ∈ X mit f (x1) = f (x2). Dann ist

(g ◦ f )(x1) = g ( f (x1)) = g ( f (x2)) = (g ◦ f )(x2).

Da g ◦ f injektiv ist, folgt x1 = x2. Also ist f injektiv.

2. Für jedes z ∈ Z gibt es wegen der Surjektivität von g ◦ f ein x ∈ X mit z =(g ◦ f )(x) = g ( f (x)). Also ist g surjektiv.

51

15 ABBILDUNGEN 52

3. Seien x1, x2 ∈ X mit (g ◦ f )(x1) = (g ◦ f )(x2). Dann ist g ( f (x1)) = g ( f (x2)).Wegen der Injektivität von g folgt f (x1) = f (x2), und daraus, da f injektivist, x1 = x2. Also ist g ◦ f injektiv.

4. Für jedes z ∈ Z gibt es wegen der Surjektivität von g ein y ∈ Y ′ mit z = g (y).Wegen Y = Y ′ und der Surjektivität von f gibt es ein x ∈ X mit y = f (x). Esfolgt z = g (y) = g ( f (x)) = (g ◦ f )(x). Also ist g ◦ f surjektiv.

Korollar 15(20). Die Verkettung g ◦ f : X → Z zweier bijektiver Abbildungenf : X → Y und g : Y → Z ist bijektiv.

Definition 15(21). 1. Sind X und Y Mengen mit X ⊆ Y , so heißt die Abbil-dung in : X → Y , definiert durch in(x) := x, Inklusionsabbildung. Für eineInklusionsabbildung in : X → Y wird auch die Schreibweise in : X ,→ Yverwendet.

2. Für jede Menge X heißt die Inklusionsabbildung in : X → X Identitätsab-bildung, und wird mit idX : X → X bezeichnet.

Bemerkung 15(22). 1. Für jede Menge X ist die Identitätsabbildung idX :X → X nach Bemerkung 15(11) bijektiv.

2. Sind X und Y Mengen mit X ⊆ Y , so ist für X 6= Y die Inklusionsabbildungin : X ,→ Y injektiv (15(9)), nicht surjektiv (15(9)), und damit nicht bijektiv(15(9)).

3. Die Abbildungen idN :N→N und idZ :Z→Z sind surjektiv, aber idZ ◦ idN :N→ Z ist nicht surjektiv. Denn für z ∈ Z mit z É 0 gibt es kein n ∈ N mit(idZ ◦ idN)(n) = z. Die Voraussetzung Y = Y ′ in Satz 15(19) 4. kann alsonicht fallengelassen werden.

4. Für jede Abbildung f : X → Y gilt idY ◦ f = f = f ◦ idX .

Beweis. Für jedes x ∈ X gilt (idY ◦ f )(x) = idY ( f (x)) = f (x) = f (idX (x)) =( f ◦ idX )(x). Daraus folgt nach Hilfssatz 15(3) idY ◦ f = f = f ◦ idX .

Beispiel 15(23). Nach Beispiele 15(10) 1. ist für a,b ∈Rmit a 6= 0 die Abbildungf : R→ R mit f (x) := ax + b bijektiv. Für a,b ∈ R mit a 6= 0 sei die Abbildungg :R→R definiert durch

g (y) := y −b

a.

Dann gilt für jedes x ∈R

(g ◦ f )(x) = g ( f (x)) = g (ax +b) = ax +b −b

a= x = idX (x),

52

15 ABBILDUNGEN 53

und für jedes y ∈R

( f ◦ g )(y) = f (g (y)) = f (y −b

a) = a · y −b

a+b = y = idY (y).

Aus Hilfssatz 15(3) folgt g ◦ f = idX und f ◦ g = idY .

Der folgende Satz verallgemeinert das Beispiel 15(23).

Satz 15(24). Für jede Abbildung f : X → Y mit X 6= ; gelten die folgenden Aus-sagen.

1. f ist injektiv ⇐⇒ Es gibt eine Abbildung g : Y → X mit g ◦ f = idX .

2. f ist surjektiv ⇐⇒ Es gibt eine Abbildung g : Y → X mit f ◦ g = idY .

3. f ist bijektiv ⇐⇒ Es gibt eine Abbildung g : Y → X mit g ◦ f = idX undf ◦ g = idY .

4. Ist g : Y → X eine Abbildung mit g ◦ f = idX und f ◦g = idY , so gilt g = f −1

und f = g−1.

Beweis. 1. „=⇒”: Wegen X 6= ; gibt es x0 ∈ X . Die Abbildung g : Y → X seifür y ∈ Y wie folgt definiert. Für y ∈ f (X ) gibt es ein eindeutig bestimmtesx ∈ X mit y = f (x). Dann sei g (y) := x, und im Fall y ∉ f (X ) sei g (y) := x0.Für jedes x ∈ X gilt (g ◦ f )(x) = g ( f (x)) = x = idX (x), also ist g ◦ f = idX .„⇐=”: idX = g ◦ f ist injektiv. Folglich ist f nach Satz 15(19) 1. injektiv.

2. „=⇒”: Die Abbildung g : Y → X sei wie folgt definiert. Für jedes y ∈ Ygibt es wegen der Surjektivität von f ein x ∈ X mit y = f (x). Nach demAuswahlaxiom ist dann durch g (y) := x die Abbildung g : Y → X wohlde-finiert. Für jedes y ∈ Y gilt mit x := g (y) ( f ◦ g )(y) = f (g (y)) = f (x) = y =idY (y), also ist f ◦ g = idY .„⇐=”: idY = f ◦ g ist surjektiv. Folglich ist f nach Satz 15(19) 2. surjektiv.

3. „=⇒”: Wegen der Injektivität von f gibt es nach 1. eine Abbildung g1 : Y →X mit g1 ◦ f = idX . Wegen der Surjektivität von f gibt es nach 2. eine Ab-bildung g2 : Y → X mit f ◦ g2 = idY . Nach Satz 15(18) folgt

g1 = g1 ◦ idY = g1 ◦ ( f ◦ f −1) = (g1 ◦ f )◦ f −1 = idX ◦ f −1 = f −1

und

g2 = idX ◦g2 = ( f −1 ◦ f )◦ g2 = f −1 ◦ ( f ◦ g2) = f −1 ◦ idY = f −1.

Es folgt g1 = g2 und damit g1 ◦ f = idX und f ◦ g1 = idY .„⇐=”: Diese Implikation gilt nach den Aussagen 1. und 2..

53

15 ABBILDUNGEN 54

4. Nach dem Beweis von Aussage 3. gilt g = f −1. Nach Satz 15(13) folgt hierausf = g−1.

Bemerkung 15(25). Nach Satz 15(24) 4. gilt für die in Beispiel 15(23) definiertenAbbildungen f und g , dass f und g bijektiv sind mit f −1 = g und f = g−1.

Im folgenden werden Summe, Differenz, Produkt und Quotient reellwertiger Ab-bildungen definiert.

Definition 15(26). Sei X ⊆ R und seien f : X → R und g : X → R Abbildungen.Dann heißen die Abbildungen

1. f ± g : X →R, definiert durch ( f ± g )(x) := f (x)± g (x), Summe bzw. Diffe-renz von f und g .

2. f · g : X →R, definiert durch ( f · g )(x) := f (x) · g (x), Produkt von f und g .

3. Ist g (x) 6= 0 für jedes x ∈ X , so heißt fg : X → R, definiert durch

( fg

)(x) :=

f (x)g (x) , Quotient von f und g .

Beispiel 15(27). Seien f :R→R und g :R→R definiert durch f (x) := x4 −1 undg (x) := x2+1. Dann gilt für jedes x ∈R ( f +g )(x) = x4+x2, ( f −g )(x) = x4−x2−2,

( f · g )(x) = x6 +x4 −x2 −1 und( f

g

)(x) = x4−1

x2+1 = x2 −1.

Bemerkung 15(28). Für die Summe, die Differenz, das Produkt und den Quo-tienten von Abbildungen gelten keine Satz 15(19) entsprechenden Aussagen. Soist z. B. die Abbildung idR : R→ R bijektiv, aber das Produkt idR · idR : R→ R istwegen (idR · idR)(x) = x2 für alle x ∈Rweder injektiv noch surjektiv.


1. Seien X 6= ; und Y Mengen und f : X → Y eine Abbildung. Ordnen Sie fol-genden Aussagen die Adjektive injektiv (15(9)), surjektiv (15(9)), konstant(15(8)) oder trivial zu.

(a) ∀y ∈ Y ∃x ∈ X : f (x) = y .

(b) ∀x ∈ X ∃y ∈ Y : f (x) = y .

(c) ∃x1 ∈ X ∃x2 ∈ X : f (x1) = f (x2) =⇒ x1 = x2.

(d) ∃y ∈ Y ∀x ∈ X : f (x) = y .

54

15 ABBILDUNGEN 55

2. Beweisen Sie, dass die Abbildung f :N→N, definiert durch

f (n) := (2n −1)n(2n +1)

3,

wohldefiniert (15(7)) ist. Ist f injektiv (15(9))? Ist f surjektiv (15(9))?

Hinweis: Betrachten Sie im Beweis der Wohldefiniertheit von f für n ∈ Ndie Menge {2n −1,2n,2n +1}, und verwenden Sie die zweite Übungsauf-gabe (9.e) und das Lemma von Euklid (10(7)).

3. Seien M eine endliche Menge und f : M → M eine Abbildung. BeweisenSie die Gültigkeit der Äquivalenzen

1. f ist bijektiv (15(9)) ⇐⇒ 2. f ist injektiv (15(9)) ⇐⇒ 3. f ist surjektiv(15(9)).

Hinweis: Es genügt z. B. die Aussagen 1. =⇒ 2. =⇒ 3. =⇒ 1. zu beweisen.Warum?

4. Geben Sie jeweils mit Beweis eine Menge M und eine Abbildung f : M →M an, die

(a) injektiv (15(9)) und nicht surjektiv (15(9)) ist,

(b) surjektiv (15(9)) und nicht injektiv (15(9)) ist.

Hinweis zu (a): Betrachten Sie die Zuordnung in Hilberts17 18 „Hotel”(z. B. auf http://de.wikipedia.org/wiki/Hilberts_Hotel).

5. Es seien f : X → Y eine Abbildung und A,B ⊆ X . Beweisen Sie:

1. f (A∪B) = f (A)∪ f (B) 2. f (A∩B) ⊆ f (A)∩ f (B)

3. f (A) \ f (B) ⊆ f (A \ B).

17David Hilbert (∗ 23. Januar 1862 in Königsberg; † 14. Februar 1943 in Göttingen) war ein deut-scher Mathematiker. Er gilt als einer der bedeutendsten Mathematiker der Neuzeit. Viele seinerArbeiten auf dem Gebiet der Mathematik und mathematischen Physik begründeten eigenstän-dige Forschungsgebiete. Mit seinen Vorschlägen begründete er die bis heute bedeutsame forma-listische Auffassung von den Grundlagen der Mathematik und veranlasste eine kritische Analy-se der Begriffsdefinitionen der Mathematik und des mathematischen Beweises. Diese Analysenführten zum Gödelschen4 Unvollständigkeitssatz, der unter anderem zeigt, dass das sogenannte”Hilbertprogramm“ nicht gänzlich erfüllt werden kann. Hilberts programmatische Rede auf deminternationalen Mathematikerkongress in Paris im Jahr 1900, in der er eine Liste von 23 mathe-matischen Problemen vorstellte, beeinflusste die mathematische Forschung des 20. Jahrhundertsnachhaltig (Quelle: http://de.wikipedia.org/wiki/David_Hilbert).

18Kurt Friedrich Gödel (∗ 28. April 1906 in Brünn, Österreich-Ungarn, heute Tschechien; † 14.Januar 1978 in Princeton, New Jersey) war ein österreichisch-amerikanischer Mathematiker undeiner der bedeutendsten Logiker des 20. Jahrhunderts. Er leistete maßgebliche Beiträge zur Prä-dikatenlogik (Vollständigkeit und Entscheidungsproblem in der Arithmetik und der axiomati-schen Mengenlehre), zu den Beziehungen der intuitionistischen Logik sowohl zur klassischenLogik als auch zur Modallogik, und zur Relativitätstheorie in der Physik. Auch seine philoso-phischen Erörterungen zu den Grundlagen der Mathematik fanden weite Beachtung (Quelle:http://de.wikipedia.org/wiki/Kurt_Friedrich_Gödel.

55

15 ABBILDUNGEN 56

Zeigen Sie jeweils durch ein Beispiel, dass in 2. und in 3. im allgemeinennicht die Gleichheit gilt.

Hinweis: Verwenden Sie die Definitionen 13(4) und 15(5).

6. Beweisen Sie, dass die Abbildung ϕ : Z→ Z mit ϕ(k) := k + (−1)k bijektiv(15(9)) ist, und geben Sie die zu ϕ inverse Abbildung (15(13)) an.

Hinweis: Betrachten Sie die Werte ϕ(k) für k ∈ N4, stellen Sie dann eineVermutung über die zu ϕ inverse Abbildung auf, und verwenden Sie Satz15(24) 3..

7. Seien X und Y Mengen mit Y 6= ;. Sei f : X → Y eine surjektive (15(9))Abbildung. Beweisen Sie, dass durch

X y := f −1[y] für y ∈ Y

eine Partition (13(11)) X y ⊆ X , y ∈ Y , von X gegeben ist.

15.a Verknüpfungen

Definition 15(29). Sei X eine Menge.

1. Eine Verknüpfung auf X ist eine Abbildung ∗ : X ×X → X .

Für x, y ∈ X wird statt ∗((x, y)) meistens x ∗ y :=∗((x, y)) geschrieben.

2. Eine Verknüpfung ∗ : X ×X → X heißt assoziativ, wenn

∀x, y, z ∈ X : x ∗ (y ∗ z) = (x ∗ y)∗ z gilt.

3. Eine Verknüpfung ∗ : X ×X → X heißt kommutativ, wenn

∀x, y ∈ X : x ∗ y = y ∗x gilt.

Definition 15(30). Ist eine Verknüpfung ∗ : X × X → X assoziativ, so schreibenwir

x ∗ y ∗ z := (x ∗ y)∗ z ∀x, y, z ∈ X .

Beispiele 15(31). 1. + : Z×Z→ Z mit +((a,b)) := a +b für a,b ∈ Z ist asso-ziativ und kommutativ.

2. · :Z×Z→Zmit ·((a,b)) := a ·b für a,b ∈Z ist assoziativ und kommutativ.

3. ∗ : P (M)×P (M) → P (M) mit ∗((A,B)) := A ∪B ist assoziativ und kom-mutativ.

Beweis. Für alle A,B ,C ∈P (M) gilt (A∗B)∗C = (A∪B)∗C = (A∪B)∪C =A∪ (B ∪C ) = A∗ (B ∪C ) = A∗ (B ∗C ) und A∗B = A∪B = B ∪ A = B ∗ A.

56

15 ABBILDUNGEN 57

4. Für jede Menge X sei

Abb(X , X ) := { f | f : X → X ist eine Abbildung}.

Dann ist die Abbildung

◦ : Abb(X , X )× Abb(X , X ) → Abb(X , X ),

definiert durch ◦(( f , g )) := f ◦g , eine assoziative Verknüpfung auf Abb(X , X ).Die Assoziativität von ◦ folgt aus Satz 15(18).

Definition 15(32). Sei ∗ : X ×X → X eine Verknüpfung.

1. Dann heißt A ⊆ X abgeschlossen unter der Verknüpfung ∗, wenn

∀x, y ∈ A : x ∗ y ∈ A gilt.

2. Wird∗Addition (bzw. Multiplikation) genannt, so heißt eine unter∗ abge-schlossene Teilmenge A ⊆ X additiv (bzw. multiplikativ) abgeschlossen.

Beispiele 15(33). 1. Da für k, l ∈ Z 2k + 2l = 2(k + l ) ∈ 2Z und 2k · 2l = 2 ·(2kl ) ∈ 2Z gilt, folgt, dass 2Z ⊆ Z unter der Addition „+” additiv abge-schlossen und unter der Multiplikation „·” multiplikativ abgeschlossen ist.

2. P ist weder unter der Addition „+” noch unter der Multiplikation „·” abge-schlossen, denn z. B. gilt 2,3,5 ∈P, aber 3+5 = 8 ∉P und 2 ·3 = 6 ∉P.

3. Sei ∗ : X × X → X eine Verknüpfung. Dann sind ; ⊆ X und X ⊆ X abge-schlossen unter der Verknüpfung ∗.

Beweis. Für ; ist die Abgeschlossenheit unter ∗ trivial erfüllt. Ebenso fürdie Menge X , denn da ∗ : X ×X → X eine Abbildung ist, gilt für alle x, y ∈ Xx ∗ y =∗((x, y)) ∈ X .

4. M := {n2 | n ∈ N} ⊆ N ist bezüglich der Multiplikation „·” abgeschlossen,aber bezüglich der Addition „+” nicht abgeschlossen.

Beweis. Für x, y ∈ M gibt es n,m ∈N mit x = n2 und y = m2. Es folgt x y =(nm)2 ∈ M , also ist M multiplikativ abgeschlossen. Wegen z. B. 12,22 ∈ M ,aber 12 +22 = 5 ∉ M ist M nicht additiv abgeschlossen.

Bemerkung 15(34). Die obige Menge M = {n2 | n ∈ N} ⊆ N hat, obwohl siebezüglich der Addition „+” nicht abgeschlossen ist, die Eigenschaft, dass füru, v ∈Nmit u > v

x := u2 − v2 ∈N, y := 2uv ∈N x2 ∈ M , y2 ∈ M und x2 + y2 = (u2 + v2)2 ∈ M

ist. Für u, v ∈ N mit u > v sind (u2 − v2,2uv,u2 + v2) die sogenannten pythago-räischen19 Zahlentripel, und diese sind die Lösungsgesamtheit der ganzzahligenpositiven Lösungen (x, y, z) der Gleichung x2 + y2 = z2.

19Pythagoras von Samos (? um 570 v. Chr. auf Samos; † nach 510 v. Chr. in Metapont in

57

16 RESTKLASSENRECHNUNG 58


1. Beweisen Sie: Die Verknüpfung (15(29)) ∗ : P (M)×P (M) → P (M) mit∗((A,B)) := A\B ist nicht assoziativ (15(29)) und nicht kommutativ (15(29)).

16 Restklassenrechnung

Viele mathematische Objekte (z. B. Mengen) sind sehr komplex und unüber-sichtlich. Eine Partition einer Menge M kann M übersichtlicher machen, da dieBetrachtung der Äquivalenzklassen (Sätze 14(8) und 14(9)) einfacher sein kann,als die Menge M als Ganzes zu betrachten. Wir werden nun eine Möglichkeitkennenlernen, ganze Zahlen in Äquivalenzklassen einzuteilen. Dies wollen wiram Beispiel „Teilen durch 5” einmal genauer betrachten. Alle ganzen Zahlen las-sen bei Teilung durch 5 einen Rest, wobei auch 0 ein Rest ist. Diese Reste 0, 1,2, 3, 4 definieren unsere Restklassen. Jede ganze Zahl gehört in genau eine derRestklassen

[k]5 := k +5Z für k ∈ {0,1,2,3,4},

je nachdem, welchen Rest sie beim Teilen durch 5 lässt. Diese Restklassen hei-ßen genauer Restklassen modulo 5.

Wir haben die Menge Z also durch [k]5,k ∈ {0,1,2,3,4}, partitioniert (13(11)),und können uns folglich die hiervon induzierte Äquivalenzrelation (14(9)) an-sehen. Statt der Teilbarkeit durch 5 betrachten wir allgemeiner die Teilbarkeitdurch eine natürliche Zahl m.

[k]m := k +mZ für k ∈ {0,1, ...,m −1}

heißen die Restklassen modulo m. Dann gilt der folgende

Satz 16(1). Sei m ∈N. Für a,b ∈Z sei

a ∼m b :⇐⇒ m | a −b.

Dann ist ∼m eine Äquivalenzrelation auf Z. Für jedes a ∈ Z gilt [a] = [a]m . MitV := {0,1, ...,m −1} ist das System [a]m ⊆Z, a ∈V , eine Partition von Z.

der Basilicata) war ein antiker griechischer Philosoph (Vorsokratiker) und Gründer einer ein-flussreichen religiös-philosophischen Bewegung. Als Vierzigjähriger verließ er seine griechi-sche Heimat und wanderte nach Süditalien aus. Dort gründete er eine Schule und betätig-te sich auch politisch. Trotz intensiver Bemühungen der Forschung gehört er noch heute zuden rätselhaftesten Persönlichkeiten der Antike. Manche Historiker zählen ihn zu den Pionie-ren der beginnenden griechischen Philosophie, Mathematik und Naturwissenschaft, andere mei-nen, er sei vorwiegend oder ausschließlich ein Verkünder religiöser Lehren gewesen (Quelle:http://de.wikipedia.org/wiki/Pythagoras_von_Samos).

58

16 RESTKLASSENRECHNUNG 59

Beweis. Für a ∈ Z gilt a − a = 0 = 0 ·m, folglich m | a − a. Also gilt a ∼m a. DieRelation ∼m ist also reflexiv. Sind a,b ∈Zmit a ∼m b, so gilt m | −(a −b) = b −a,d. h. es gilt b ∼m a. Also ist ∼m symmetrisch. Seien nun a,b,c ∈ Z mit a ∼m bund b ∼m c. Aus m | (a −b)+ (b − c) = a − c folgt a ∼m c, d. h. ∼m ist transitiv.Damit ist ∼m eine Äquivalenzrelation auf Z. Für a,b ∈Z gilt

b ∈ [a] ⇐⇒ a ∼m b ⇐⇒ m | a −b ⇐⇒ b ∈ [a]m .

Also gilt für jedes a ∈Z [a] = [a]m . Die Menge V ist ein Vertretersystem von ∼m ,und damit ist nach Satz 14(8) [a]m ⊆Z, a ∈V , eine Partition von Z.

Definition 16(2). Für m ∈N heißt Zm := {[0]m , [1]m ,...,[m −1]m} die Menge derRestklassen modulo m.

Auf der Menge Zm wollen wir nun eine Addition + : Zm ×Zm → Zm definieren.Wir suchen also für a,b ∈Z ein k ∈Zmit

+(([a]m , [b]m)) := [k]m .

Damit uns diese Addition etwas nützt, wollen wir, dass sie die folgende Eigen-schaft erfüllt.

Addieren wir zwei ganze Zahlen a und b, so soll die Summe ihrer Restklassen[a]m + [b]m gleich der Restklasse ihrer Summe a +b, d. h. gleich [a +b]m sein.

Wir wählen daher die folgende Definition der Addition „+”.

Definition 16(3). Für m ∈ N sei die Addition + : Zm ×Zm → Zm wie folgt defi-niert: Für a,b ∈ Z sei k ∈ {0,1, ...,m −1} der Rest von a +b beim Teilen durch m.Dann sei +(([a]m , [b]m)) := [k]m .

Nun müssen wir eine weitere Form der Wohldefiniertheit einer Abbildung, näm-lich der Abbildung „+”, nachweisen. Denn jede Äquivalenzklasse hat verschie-dene Elemente. Zum Beispiel muss wegen [6]5 = [21]5 und [7]5 = [17]5 die Glei-chung +(([6]5, [7]5)) =+(([21]5, [17]5)), äquivalent [13]5 = [38]5, gelten.

Seien zum Nachweis der Wohldefiniertheit von „+” a,b,c,d ∈Z mit [a]m = [c]m

und [b]m = [d ]m . Dann gilt m | a − c und m | b −d , und daraus folgt

m | (a − c)+ (b −d) = (a +b)− (c +d).

Daher gilt [a +b]m = [c +d ]m . Es folgt

+(([a]m , [b]m)) = [a +b]m = [c +d ]m =+(([c]m , [d ]m)).

Also ist die Abbildung „+” wohldefiniert.

Für m ∈N lässt sich auf der Menge Zm wie folgt auch eine Subtraktion und eineMultiplikation definieren.

59

17 KARDINALITÄTEN UND ELEMENTARE KOMBINATORIK 60

Definition 16(4). Sei m ∈N.

1. Die Abbildung − : Zm ×Zm → Zm sei definiert durch −(([a]m , [b]m)) :=[k]m , wobei a,b ∈Z und k der Rest von a −b beim Teilen durch m ist.

2. Die Abbildung · :Zm ×Zm →Zm sei definiert durch ·(([a]m , [b]m)) := [k]m ,wobei a,b ∈Z und k der Rest von ab beim Teilen durch m ist.

Hier muss wie bei der Addition + :Zm ×Zm →Zm die Wohldefiniertheit der Ab-bildungen − :Zm ×Zm →Zm und · :Zm ×Zm →Zm nachgewiesen werden. Die-ser Beweis erfolgt im Rahmen der Übungsaufgaben.

Restklassenrechnung kann bei der Lösung von Problemen hilfreich sein. Dazubetrachten wir das folgende

Beispiel 16(5). Sei n ∈N und

a :=n−1∑k=0

10k ∈N (a besteht aus genau n Einsen).

Dann ist a genau dann eine Quadratzahl, wenn n = 1 ist.

Beweis: Ist n = 1, so ist a = 1 eine Quadratzahl. Sei also n > 1. Angenommen, esgibt b ∈Nmit a = b2. Sei

c :=n−3∑k=0

10k ∈N0.

Dann gilt a = c · 100 + 11, und 4 | c · 100. Daher ist [b]4 · [b]4 = [b2]4 = [a]4 =[11]4 = [3]4. Wir können also o. E. d. A. b ∈ {0,1,2,3} annehmen. Für b ∈ {0,2}gilt [b2]4 = [0]4 6= [3]4, und für b ∈ {1,3} gilt [b2]4 = [1]4 6= [3]4, jeweils ein Wider-spruch. Damit ist a für n > 1 keine Quadratzahl.


1. Beweisen Sie, dass für m ∈ N die obigen Abbildungen − : Zm ×Zm → Zm

und · :Zm ×Zm →Zm (16(4)) wohldefiniert sind.

17 Kardinalitäten und Elementare Kombinatorik

Wir beweisen zunächst einen Satz über die Kardinalität der Vereinigung vonzwei endlichen Mengen.

Satz 17(1). Seien A und B endliche Mengen. Dann gilt

|A∪B | = |A|+ |B |− |A∩B |.

60


Beweis. Seien n,m, l ∈ N0 mit |A| = n, |B | = m und |A ∩B | = l . Dann gilt l Én, l É m, und es gibt für 1 É l Elemente c1, ...,cl ∈ A ∩ B , für l < n Elementeal+1, ..., an ∈ A und für l < m Elemente bl+1, ...,bm ∈ B mit

A∩B = {c1, ...,cl }, A = {c1, ...,cl , al+1, ..., an} und B = {c1, ...,cl ,bl+1, ...,bm}.

Es folgtA∪B = {c1, ...,cl , al+1, ..., an ,bl+1, ...,bm}

mit |A∪B | = l + (n − l )+ (m − l ) = n +m − l = |A|+ |B |− |A∩B |.Satz 17(2). Sind M und N endliche Mengen, so gilt |M ×N | = |M | · |N |.

Beweis. In den Fällen M =; oder N =; ist die Behauptung offensichtlich wahr.Sei also M 6= ; und N 6= ;. Wir beweisen die Behauptung durch vollständigeInduktion nach n := |M |. Sei für l := |N | ∈N {ni | i ∈Nl } := N .

Induktionsanfang (n = 1): Sei {m} := M . Dann ist |M × N | = |{m} × {n1, ...,nl }|= |{(m,n1), ..., (m,nl )}| = l = |M | · |N |.Induktionsschritt (n n + 1): Die Behauptung gelte für n ∈ N. O. E. d. A. seiM := Nn+1. Es ist |Nn | = n, und mit A := {n +1} gilt |A| = 1, Nn+1 = Nn ∪ A undNn ∩ A =;. Dann ist nach einer Übungsaufgabe

(Nn ×N )∩ (A×N ) = (Nn ∩ A)×N =;×N =;,

und aus den Sätzen 13(15) und 17(1) folgt

|M ×N | = |(Nn ∪ A)×N | = |(Nn ×N )∪ (A×N )| = |Nn ×N |+ |A×N |IV= |Nn | · |N |+ |N | = n · |N |+1 · |N | = |M | · |N |.

Die folgende Definition des n-Tupels bzw. des n-fachen direkten Produkts vonM stimmt für jede Menge M für n = 2 mit der früheren Definition 13(13) desgeordneten Paares bzw. des direkten Produkts M 2 überein.

Definition 17(3). Sei M eine Menge.

1. Für n ∈ N0 und mi ∈ M für i ∈ Nn wird das n-Tupel (m1, ...,mn) induktivdefiniert durch (m1, ...,mn) :=; für n = 0 und

(m1, ...,mn) := {(m1, ...,mn−1), {mn}} für n ∈N.

2. Für n ∈N seiM n := {(m1, ...,mn) | mi ∈ M für i ∈Nn}.

M n heißt n-faches direktes Produkt (auch n-faches kartesisches Produktoder n-te Potenz) von M .

61


Für eine Menge M heißt ein n-Tupel (m1, ...,mn) ∈ M n auch einfach Tupel.

Hilfssatz 17(4). Sei M eine Menge. Für alle n ∈ N und (m1, ...,mn), (l1, ..., ln) ∈M n gilt

(m1, ...,mn) = (l1, ..., ln) ⇐⇒∀i ∈Nn : mi = li .

Beweis. Induktionsanfang (n = 1): Es gilt (m1) = (l1) ⇐⇒ {;, {m1}} = {;, {l1}} ⇐⇒{m1} = {l1} ⇐⇒ m1 = l1.Induktionsschritt (n n +1): Die Behauptung gelte für n ∈N. Dann folgt

(m1, ...,mn+1) = (l1, ..., ln+1) ⇐⇒ {(m1, ...,mn), {mn+1}} = {(l1, ..., ln), {ln+1}} ⇐⇒(m1, ...,mn) = (l1, ..., ln)∧ {mn+1} = {ln+1}

IV⇐⇒ mi = li für i ∈Nn+1.

Satz 17(5). Für jede endliche Menge M und für alle m ∈N gilt |M m | = |M |m .

Beweis. Induktionsanfang (m = 1): |M 1| = |M | = |M |1.Induktionsschritt (m m +1): Die Behauptung gelte für m ∈N. Dann folgt aus

Satz 17(2) |M m+1| = |M m ×M | = |M m | · |M | IV= |M |m · |M | = |M |m+1.

Wir hatten bereits |P ({1,2,3})| = 8 = 23 gesehen. Als Verallgemeinerung bewei-sen wir den folgenden

Satz 17(6). Sei n ∈N0. Für jede Menge M mit |M | = n gilt |P (M)| = 2n .

Beweis. Induktionsanfang (n = 0): Wegen M =; gilt |P (M)| = 1 = 20.Induktionsschritt (n n + 1): Die Behauptung gelte für n ∈ N0. O. E. d. A. seiM := Nn+1. Wir unterscheiden für A ⊆ M die Fälle n + 1 ∉ A und n + 1 ∈ A. Istn+1 ∉ A, so ist A ⊆Nn , und nach Induktionsvoraussetzung gibt es für A genau 2n

Möglichkeiten. Ist n+1 ∈ A, so gibt es nach Induktionsvoraussetzung für A \{n+1} ⊆Nn ebenfalls genau 2n Möglichkeiten. Also gibt es für A = A \{n+1}∪ {n+1}genau 2n Möglichkeiten. Damit ist |P (M)| = 2 ·2n = 2n+1.

Definition 17(7). Die Abbildung Fakultät ! : N0 → N wird induktiv definiertdurch !(0) := 0! := 1 und !(n +1) := (n +1)! := n! · (n +1) für n ∈N0.

Die ersten Werte nach 0! = 1 sind 1! = 0! · 1 = 1, 2! = 1! · 2 = 2, 3! = 2! · 3 = 6 und4! = 3! ·4 = 24. Für jedes n ∈N0 gilt

n! =n∏

k=1k.

Definition 17(8). Für k,n ∈ N0 sei der Binomialkoeffizient(n

k

)(gelesen: n über

k) definiert durch

(n

k

):= n!

k ! · (n −k)!für k ≤ n und

(n

k

):= 0 für k > n.

62


Beispielsweise ist

(5

3

)= 5!

3! · (5−3)!= 120

6 ·2= 10.

Einige häufig vorkommende Binomialkoeffizienten sind

Beispiele 17(9). Für jedes n ∈N gilt(n

0

)=

(n

n

)= 1,

(n

1

)=

(n

n −1

)= n.

In Verallgemeinerung von Beispiel 17(9) beweisen wir den folgenden

Satz 17(10). Für n,k ∈N0 mit k ≤ n gilt

(n

k

)=

(n

n −k

)= n · (n −1) · (n −2) · · · (n −k +1)

k !.

Beweis. Es gilt(n

k

)= n!

k ! · (n −k)!= n!

(n −k)! · (n − (n −k))!=

(n

n −k

)und (

n

k

)=

n!(n−k)!

k !·(n−k)!(n−k)!

= n · (n −1) · (n −2) · · · (n −k +1)

k !.

Satz 17(11). Für n,k ∈N0 mit k ≤ n gilt

(n

k

)+

(n

k +1

)=

(n +1

k +1

).

Beweis. Für k = n gilt die Behauptung nach Definition 17(8) und nach Beispiele17(9). Sei also k < n. Dann gilt nach Definition 17(8)(

n

k

)+

(n

k +1

)= n!

k ! · (n −k)!+ n!

(k +1)! · (n − (k +1))!= n! · (k +1)

(k +1)! · (n −k)!+ n! · (n −k)

(k +1)! · (n −k)!

= (n +1)!

(k +1)! · ((n +1)− (k +1))!=

(n +1

k +1

).

63


Bemerkung 17(12). Aus Satz 17(11) folgt, dass sich für n,k ∈ N mit k < n dieBinomialkoeffizienten

(nk

)nacheinander mittels des sogenannten Pascal’schen20

Dreiecks berechnen lassen. Jeder Binomialkoeffizient im Inneren ist die Summeder beiden links und rechts darüberstehenden Binomialkoeffizienten.

(00

)(10

) (11

)(20

) (21

) (22

)(30

) (31

) (32

) (33

)...

11 1

1 2 11 3 3 1

...

Zunächst werden wir nun den Begriff der Permutation (von lateinisch permu-tare vertauschen), d.h., der Anordnung von Objekten in einer bestimmten Rei-henfolge, definieren.

Definition 17(13). Für n ∈N und für jede Menge M mit |M | = n heißt eine bijek-tive Abbildung π : M → M eine n-stellige Permutation ohne Wiederholung (auchPermutation).

Beispiel 17(14). Sei n ∈N. Die Abbildung π :Nn →Nn sei definiert durch π(k) :=k +1 für k ∈Nn mit k < n und π(n) := 1. Für die Abbildung τ :Nn →Nn , definiertdurch τ(k) := k −1 für k ∈Nn mit k > 1 und τ(1) := n, gilt

τ◦π(n) = τ(1) = n und für k ∈Nn mit k < n τ◦π(k) = τ(k +1) = k,

π◦τ(1) =π(n) = 1 und für k ∈Nn mit k > 1 π◦τ(k) =π(k −1) = k.

Nach Hilfssatz 15(3) folgt

τ◦π= idNn und π◦τ= idNn .

Nach Satz 15(24) 3. sind π und τ daher bijektiv und sind folglich Permutationen(17(13)). Zudem gilt nach Satz 15(24) 4. π= τ−1 und τ=π−1.

Bemerkung 17(15). Eine Permutationπ :Nn →Nn wird häufig in der sogenann-ten

Tupelschreibweise (π(1),π(2), ...,π(n))

oder in der

Zweizeilenform

(1 2 ... n

π(1) π(2) ... π(n)

)20Blaise Pascal (? 19. Juni 1623 in Clermont-Ferrand; † 19. August 1662 in Paris)

war ein französischer Mathematiker, Physiker, Literat und christlicher Philosoph (Quelle:http://de.wikipedia.org/wiki/Blaise_Pascal).

64


notiert. Beispielsweise ist für n := 4 die Permutation π in Beispiel 17(14) in die-sen Schreibweisen also

π= (2,3,4,1) oder π=(1 2 3 42 3 4 1

).

Wir stellen nun die Frage, ob sich mittels Fakultät und Binomialkoeffizient prak-tische Fragestellungen beantworten lassen. Wie allgemein üblich, sprechen wirin den folgenden Beispielen von Anordnungen statt von Permutationen, müs-sen aber in Sätzen und Beweisen den oben definierten Begriff der Permutationverwenden.

Beispiele 17(16). 1. Die Zahlen 1,2,3 haben 6 = 3! Anordnungen, nämlich123,132,213,231,312,321.

2. Von den Zahlen 1,2,3,4 gibt es folgende 12 Anordnungen von je zwei Ele-menten:

12,21,13,31,14,41,23,32,24,42,34,43.

Jeweils die erste und zweite, dritte und vierte usw. bilden dieselbe zwei-elementige Teilmenge von {1,2,3,4}. Also gibt es 6 = (4

2

)zwei-elementige

Teilmengen von {1,2,3,4}.

Der folgende Satz verallgemeinert diese Beispiele.

Satz 17(17). Seien n ∈N und M eine Menge mit |M | = n. Dann gelten die Aus-sagen

1. Für k ∈Nmit k É n gibt es für k verschiedene Elemente von M insgesamt(d.h. über alle Teilmengen von M mit k Elementen)

n!

(n −k)!Permutationen.

2. Für die Elemente von M gibt es n! Permutationen.

3. Für k ∈N0 mit k É n gibt es(n

k

)k-elementige Teilmengen von M .

Beweis. 1. Induktionsanfang (n = 1): Dann ist k = 1, und für das Element min {m} := M gibt es 1 = 1!

(1−1)! Permutationen.Induktionsschritt (n n+1): Die Behauptung gelte für n ∈N. O. E. d. A. seiM := Nn+1. Für a ∈ M sei Ra := M \ {a}. In der folgenden Tabelle sind allePermutationen von k Elementen aus M nach der ersten vorkommendenZahl in der Permutation sortiert. Wegen |Ra | = n für jedes a ∈ M gilt imFall k ≥ 2 nach Induktionsvoraussetzung

65


Erste Zahl a der Permutation Ra Anzahl der Permutationen vonvon k Elementen aus M k −1 Elementen aus Ra

1 {2,3, . . . ,n +1}n!

(n − (k −1))!

2 {1,3, . . . ,n +1}n!

(n − (k −1))!...

......

n +1 {1,2, . . . ,n}n!

(n − (k −1))!

Für k ≥ 2 gibt es also

(n +1) · n!

(n − (k −1))!= (n +1)!

(n +1−k)!

Permutationen von k Elementen aus M . Für k = 1 ist (n+1)!(n+1−k)! = n +1 die

Anzahl der Permutationen von einem Element aus M . Damit ist die Be-hauptung bewiesen.

2. Mit n! = n!

(n −n)!folgt die Behauptung aus 1..

3. Sei Pk die Menge aller Permutationen von k verschiedenen Elementen ausM in der Tupelschreibweise, und sei Tk := {N |N ⊆ M ∧ |N | = k}. Die Abbil-dung f : Pk → Tk sei definiert durch f ((a1, ..., ak )) := {a1, ..., ak }. Für jedesY ∈ Tk gilt nach 2. | f −1[Y ]| = k !, denn f −1[Y ] ist die Menge aller Permuta-tionen der k verschiedenen Elemente aus Y . Also ist

Pk = ⋃Y ∈Tk

f −1[Y ]

die disjunkte Vereinigung von |Tk | k !-elementigen Teilmengen von Pk . Da-her gilt |Pk | = |Tk | ·k !, und daraus, aus 1. und aus Definition 17(8) folgt

|Tk | =1

k !· |Pk | =

1

k !· n!

(n −k)!=

(n

k

).

Es gibt also(n

k

)k-elementige Teilmengen von M .

Nach Satz 17(17) 3. gibt es bei dem Lottospiel „6 aus 49”(49

6

)= 13983816

Möglichkeiten, aus 49 Zahlen 6 Zahlen auszuwählen.

Wegen(0

0

)= 1 ∈N und Satz 17(17) 3. erhalten wir das folgende

66


Korollar 17(18). Für jedes n ∈N0 und für jedes k ∈N0 mit k É n gilt(n

k

) ∈N.

Satz 17(19). (Binomischer Satz) Für jedes n ∈N0 und für alle a,b ∈R gilt

(a +b)n =n∑

k=0

(n

k

)an−k bk =

n∑k=0

(n

k

)ak bn−k .

Beweis. Induktionsanfang (n = 0): (a +b)0 = 1 = (00

)a0 ·b0.

Induktionsschritt (n n+1): Die Behauptung gelte für n ∈N0. Dann folgt unterVerwendung von Hilfssatz 11(2) und Satz 17(11)

(a +b)n+1 = (a +b)(a +b)n

IV= (a +b)n∑

k=0

(n

k

)an−k bk =

n∑k=0

(n

k

)an+1−k bk +

n∑k=0

(n

k

)an−k bk+1

= an+1 +n∑

k=1

(n

k

)an+1−k bk +

n−1∑k=0

(n

k

)an−k bk+1 +bn+1

= an+1 +n∑

k=1

(n

k

)an+1−k bk +

n∑k=1

(n

k −1

)an−(k−1)b(k−1)+1 +bn+1

= an+1 +n∑

k=1

((n

k

)+

(n

k −1

))an+1−k bk +bn+1

= an+1 +n∑

k=1

(n +1

k

)an+1−k bk +bn+1 =

n+1∑k=0

(n +1

k

)an+1−k bk .

Damit ist

(a +b)n =n∑

k=0

(n

k

)an−k bk

für jedes n ∈N0 bewiesen. Für jedes n ∈N0 folgt wegen (a +b)n = (b +a)n durchVertauschung von a und b in dieser bewiesenen Gleichung

(a +b)n =n∑

k=0

(n

k

)ak bn−k .

Korollar 17(20). Es gelten die folgenden Aussagen.

1. Für jedes n ∈N0 giltn∑

k=0

(nk

)= 2n .

67

18 REELLE ZAHLEN 68

2. Für jedes n ∈N giltn∑

k=0(−1)k · (n

k

)= 0.

Korollar 17(21). Für alle a,b ∈R gelten die folgenden Aussagen.

1. (a ±b)2 = a2 ±2ab +b2.

2. (a ±b)3 = a3 ±3a2b +3ab2 ±b3.

17.a Übungsaufgaben

1. Seien n ∈N0 und M eine Menge mit |M | = n. Wie viele Relationen (14(1))gibt es auf M?

2. Beweisen Sie für jedes n ∈N0(2n

2

)= 2 ·

(n

2

)+n2 und

n∑k=0

k ·(

n

k

)= n ·2n−1.

Hinweis: Verwenden Sie Definition (17(8)). Beweisen Sie die erste Identitätnicht durch vollständige Induktion, sondern direkt.

3. Beweisen Sie für alle n ∈N0 und m ∈N\ {1}

mn = (m −1)n ·n∑

k=0

(n

k

)· (m −1)−k .

Hinweis: Verwenden Sie den Binomischen Satz 17(19).

18 Reelle Zahlen

Die Menge R der reellen Zahlen ist die Grundmenge der reellen eindimensio-nalen Analysis. Diese Menge ist eine Erfindung. Wie Schachfiguren haben reelleZahlen nur eine Bedeutung im Rahmen der Regeln. Diese Regeln heißen hierAxiome.

Als eine Menge R von reellen Zahlen bezeichnen wir eine Menge, auf der es zweiVerknüpfungen + :R×R→R und · :R×R→R gibt, so dass die folgenden Axiome(A1) bis (A9) und die späteren Axiome (A10) bis (A14) sowie das spätere Supre-mumsaxiom erfüllt sind.

Für a,b ∈ R sei wie üblich a + b := +((a,b)) und a · b := ·((a,b)). Sofern keinMissverständnis möglich ist, schreiben wir für a,b ∈R ab := a ·b.

68

18 REELLE ZAHLEN 69

Axiome (A1) bis (A9) der reellen Zahlen 1.

(A1) Assoziativaxiom bzgl. + a + (b + c) = (a +b)+ c ∀a,b,c ∈R(A2) Assoziativaxiom bzgl. · a · (b · c) = (a ·b) · c ∀a,b,c ∈R(A3) Kommutativaxiom bzgl. + a +b = b +a ∀a,b ∈R(A4) Kommutativaxiom bzgl. · a ·b = b ·a ∀a,b ∈R(A5) Existenz eines neutralen Elements bzgl. + ∃0 ∈R : a +0 = a ∀a ∈R(A6) Existenz eines neutralen Elements bzgl. · ∃1 ∈R : a ·1 = a ∀a ∈R(A7) Existenz eines inversen Elements bzgl. + ∀a ∈R ∃−a ∈R : a + (−a) = 0

(A8) Existenz eines inversen Elements bzgl. · ∀a ∈R\ {0} ∃a−1 ∈R : a ·a−1 = 1

(A9) Distributivaxiom a · (b + c) = a ·b +a · c ∀a,b,c ∈R

Die Axiome (A1) bis (A9) heißen Körperaxiome. Auch die Menge Q mit der be-kannten Addition + :Q×Q→Q und der bekannten Multiplikation · :Q×Q→Q

erfüllt die Axiome (A1) bis (A9). Die Menge R der reellen Zahlen ist durch dieseKörperaxiome also nicht eindeutig bestimmt.

Es sei angemerkt, dass die obigen Bezeichnungen für die Elemente 0, 1 undfür die inversen Elemente, d. h. −a für a ∈ R und a−1 für a ∈ R \ {0}, erst danngerechtfertigt sind, wenn bewiesen wurde, dass diese Elemente eindeutig be-stimmt sind. Für das Element 0 erfolgt der Beweis in dem nächsten Hilfssatz,und für die anderen Elemente in den Übungsaufgaben.

Hilfssatz 18(1). Für jede MengeR, welche die Axiome (A1) bis (A9) erfüllt, geltendie folgenden Aussagen.

1. Es gibt genau ein Element 0 ∈Rmit a +0 = a ∀a ∈R.

2. Es gilt a ·0 = 0 ∀a ∈R.

Beweis. 1. Die Existenz folgt direkt aus (A5). Zum Beweis der Eindeutigkeitsei 0̃ ∈ R mit a + 0̃ = a ∀a ∈ R. Daraus folgt mit a := 0 nach (A3) 0 = 0+ 0̃ =0̃+0 = 0̃.

2. Sei a ∈R und b := a ·0. Dann gilt nach (A5) und (A9) b = a ·(0+0) = a ·0+a ·0 = b +b. Aus (A1), (A5) und (A7) folgt dann 0 = b + (−b) = (b +b)+ (−b) =b + (b + (−b)) = b +0 = b. Folglich gilt a ·0 = b = 0.

69

18 REELLE ZAHLEN 70

Aus den Axiomen (A1) bis (A9) lassen sich weitere Rechenregeln herleiten. Dieseseien von nun an bekannt.

Definition 18(2). Für a,b ∈R seien a −b := a + (−b) und für b 6= 0 ab := ab−1.

Wie schon oben geschrieben, muss unsere Menge Rmit den Verknüpfungen + :R×R→ R und · : R×R→ R neben den Axiomen (A1) bis (A9) weitere Axiomeerfüllen. Es folgen nun zunächst die Axiome (A10) bis (A14).

Axiome (A10) bis (A14) der reellen Zahlen 1. Auf der MengeRmit den Verknüp-fungen + :R×R→R und · :R×R→R sei eine Relation „≤” gegeben, so dass diefolgenden Axiome (A10) bis (A14) (sogenannte Anordnungsaxiome) erfüllt sind.

(A10) Totalität ∀a,b ∈R: a ≤ b ∨ b ≤ a.

(A11) Antisymmetrie ∀a,b ∈R: (a ≤ b ∧ b ≤ a) =⇒ a = b.

(A12) Transitivität ∀a,b,c ∈R: (a ≤ b ∧ b ≤ c) =⇒ a ≤ c.

(A13) Monotonie der Addition ∀a,b,c ∈R: a ≤ b =⇒ a + c ≤ b + c.

(A14) Monotonie der Multiplikation ∀a,b,c ∈R: (a ≤ b ∧ 0 ≤ c) =⇒ ac ≤ bc.

Auch die Menge Q mit der bekannten „kleiner–gleich–Relation ≤” auf Q erfülltdiese Anordnungsaxiome. Die Menge der reellen Zahlen ist also auch durch dieAxiome (A1) bis (A14) nicht eindeutig bestimmt.

Hilfssatz 18(3). Für alle a,b,c,d ∈R gelten die Aussagen

1. a ≤ b ∧ c ≤ d =⇒ a + c ≤ b +d .

2. 0 ≤ b ∧ a ≤ b ∧ 0 ≤ c ≤ d =⇒ ac ≤ bd .

Beweis. 1. Aus a ≤ b folgt nach (A3) und (A13) a + c ≤ b + c = c +b ≤ d +b =b +d . Aus (A12) folgt nun a + c ≤ b +d .

2. Aus a ≤ b folgt nach (A4) und (A14) ac ≤ bc = cb ≤ db = bd . Aus (A12) folgtnun ac ≤ bd .

Weitere Rechenregeln für Ungleichungen, die sich aus den Axiomen (A1) bis(A14) herleiten lassen, seien von nun an bekannt. Beispielsweise folgt für allea,b,c ∈R : (a ≤ b ∧ c ≤ 0) =⇒ bc ≤ ac.

Definition 18(4). Die Relationen „<”, „>” und „≥” auf R seien für a,b ∈ R defi-niert durch

70

18 REELLE ZAHLEN 71

1. a < b :⇐⇒ a ≤ b und a 6= b

2. a > b :⇐⇒ b < a

3. a ≥ b :⇐⇒ b ≤ a

Definition 18(5). Seien a,b ∈Rmit a < b. Dann heißt

1. (a,b) := {x ∈R | a < x < b} offenes Intervall

2. [a,b] := {x ∈R | a ≤ x ≤ b} abgeschlossenes Intervall

3. (a,b] := {x ∈R | a < x ≤ b} links offenes und rechts abgeschlossenes Intervall

4. [a,∞) := {x ∈R | a ≤ x}

5. (−∞,b) := {x ∈R | x < b}.

Entsprechend werden für a,b ∈ R mit a < b die Intervalle [a,b), (−∞,b] und(a,∞) definiert. Zudem sei (−∞,∞) :=R. Die Symbole −∞ und ∞ sind hier, wieschon im Fall der Bezeichnung der Kardinalität einer unendlichen Menge durch∞, nur als symbolische Schreibweisen zu verstehen.

Die Lösungsmengen mancher Ungleichungen sind Intervalle. Dazu betrachtenwir das folgende

Beispiel 18(6). Sei

L :={

x ∈R\ {3}∣∣∣2x −3

x −3≥ 4

}.

Für alle x ∈R\ {3} gilt

2x −3

x −3= 2(x −3)+3

x −3= 2+ 3

x −3und 2+ 3

x −3≥ 4 ⇐⇒ 3

x −3≥ 2.

Es folgt x > 3, und für alle x > 3 gilt

3

x −3≥ 2 ⇐⇒ x −3

3≤ 1

2⇐⇒ x ≤ 9

2.

Folglich ist L ein Intervall, nämlich L =(3, 9

2

].

71

18 REELLE ZAHLEN 72

18.a Übungsaufgaben

1. Für welche a,b ∈R ist sowohl

c :=a+b

a + a−bb

1a + 1

b

als auch c−1 definiert? Vereinfachen Sie für solche a,b ∈R c−1 soweit wiemöglich.

2. Bestimmen Sie für a,b ∈R

L :={

x ∈R\ {a,b}∣∣∣ x +a

x −b+ x +b

x −a≤ 0

}.

Hinweis: Sie können ohne Beweis die folgende Aussage verwenden.

Für c,d ∈R gilt c ·d < 0 ⇐⇒ (c < 0∧d > 0)∨ (c > 0∧d < 0).

3. Beweisen Sie: Sind a,b ∈Rmit ab = 0 so folgt a = 0 oder b = 0.

Hinweis: Wenn a = 0 ist, gilt die Behauptung. Wenn diese Bemerkung inIhrem Beweis enthalten ist, können Sie also a 6= 0 annehmen.

4. Beweisen Sie die Eindeutigkeit von 0 ∈ R, −a ∈ R für a ∈ R und a−1 ∈ R füra ∈R\ {0} in den Axiomen (A5), (A7) und (A8) der reellen Zahlen.

5. Beweisen Sie für n ∈ N0 und x ∈ R mit x ≥ −1 die Bernoullische21 Unglei-chung

(1+x)n ≥ 1+nx.

6. Beweisen Sie für a,b ∈Rmit a > 0 und b > 0 die Ungleichungen

21a + 1

b

≤p

ab ≤ a +b

2

zwischen dem harmonischen, dem geometrischen und dem arithmetischenMittelwert von a und b. Für welche Werte von a und b gilt jeweils statt „É”die Gleichheit „=”?

7. Schreiben Sie die Menge

M := {x ∈R | x É 5 ∧ x2 +2 · x −2 ·p2 ≥p2 · x}

als Vereinigung von zwei Intervallen (18(5)).


Für a,b ∈R gilt a ·b ≥ 0 ⇐⇒ (a ≥ 0∧b ≥ 0)∨ (a É 0∧b É 0).

21Jakob I. Bernoulli (∗ 27. Dezember 1654 jul. bzw. 6. Januar 1655 greg. in Ba-sel; † 16. August 1705 ebenda) war ein Schweizer Mathematiker und Physiker (Quelle:http://de.wikipedia.org/wiki/Jakob_I._Bernoulli).

72

18 REELLE ZAHLEN 73

8. Sei c ∈R. Finden Sie a,b ∈R, so dass die Gleichung

(x2 −ax y +by2)(x2 +ax y +by2) = x4 +4c2 y4

für alle x, y ∈ R erfüllt ist. Welche bemerkenswerte Gleichung erhalten Siefür y := c := 1?

18.b Vollständigkeit der reellen Zahlen

Wie schon gesagt, gelten die Körper- und Anordnungsaxiome (A1) bis (A14) so-wohl fürR als auch fürQ. Was unterscheidet nunR vonQ? Die Antwort lässt sichin verschiedenen Weisen formulieren, aber alle drücken aus, dass Q „Lücken”hat, während dies fürRnicht zutrifft. Die Lückenhaftigkeit vonQ zeigt sich schondarin, dass die Gleichung x2 = 2 wegen der Irrationalität von

p2 (10(9)) keine

Lösung in Q hat. In R hingegen hat diese Gleichung eine Lösung, wenn wir dieLückenfreiheit von R sicherstellen. Es gibt hierzu verschiedene Möglichkeiten.Mittels „Dedekindscher Schnitte”, mittels Konvergenz von Cauchy22-Folgen, odermittels des Supremumsaxioms. Wir wählen den Zugang über das Supremumsaxi-om.

Zuvor definieren wir einige Begriffe, die später benötigt werden.

Definition 18(7). Sei M ⊆R.

1. Eine obere Schranke bzw. untere Schranke von M ist ein b ∈ R bzw. eina ∈Rmit x ≤ b bzw. a ≤ x für alle x ∈ M .

2. M heißt nach oben beschränkt bzw. nach unten beschränkt, wenn M eineobere Schranke bzw. eine untere Schranke hat.

3. M heißt beschränkt, wenn M nach oben und nach unten beschränkt ist.

4. b ∈R bzw. a ∈R heißt Maximum bzw. Minimum von M , wenn b ∈ M bzw.a ∈ M ist und b eine obere Schranke bzw. a eine untere Schranke von Mist.

Im Fall der Existenz sei max M := b bzw. im Fall der Existenz sei min M :=a.

22Augustin Louis Cauchy (? 21. August 1789 in Paris; † 23. Mai 1857 in Sceaux) war ein fran-zösischer Mathematiker. Als ein Pionier der Analysis entwickelte er die von Gottfried WilhelmLeibniz und Sir Isaac Newton aufgestellten Grundlagen weiter, wobei er die fundamentalen Aus-sagen auch formal bewies. Insbesondere in der Funktionentheorie stammen viele zentrale Sätzevon ihm. Seine fast 800 Publikationen decken im Großen und Ganzen die komplette Bandbreiteder damaligen Mathematik ab. Nach dem Tode Leonhard Eulers3 hatten viele den Eindruck, dassdie Mathematik fast vollständig erforscht und keine wesentlichen Probleme mehr übrig seien. Eswaren insbesondere Carl Friedrich Gauß und Cauchy, die diesen Eindruck relativieren konnten(Quelle: http://de.wikipedia.org/wiki/Augustin-Louis_Cauchy).

73

18 REELLE ZAHLEN 74

5. b ∈R bzw. a ∈R heißt Supremum bzw. Infimum von M , wenn gilt:

b ist obere Schranke bzw. a ist untere Schranke von M und für jede obereSchranke d von M bzw. für jede untere Schranke c von M gilt b ≤ d bzw.c ≤ a.

Im Fall der Existenz sei sup M := b bzw. im Fall der Existenz sei inf M := a.

Mit anderen Worten: Im Fall der Existenz ist sup M die kleinste obere Schrankevon M und im Fall der Existenz ist inf M die größte untere Schranke von M .

Beispiele 18(8). 1. Das Intervall (0,1) ist nach oben beschränkt (z. B. durchd1 := 1 und durch d2 := 2) und nach unten beschränkt (z. B. durch c1 := 0und durch c2 :=−1).

2. N ist nur nach unten beschränkt (z. B. durch c1 := 1 und durch c2 :=−1).

3. Z ist weder nach oben noch nach unten beschränkt.

4. Für M := [1,2) ist sup M = 2. M hat kein Maximum.

Beweis. Offensichtlich ist 2 eine obere Schranke von M . Angenommen, esist d ∈Rmit d < 2 eine obere Schranke von M . Dann folgt d ∈ M und daherist y := 1

2 d + 12 2 ∈ M mit y > d , ein Widerspruch. Also folgt sup M = 2, und

M hat kein Maximum.

5. Für M := (1,2] ist max M = sup M = 2.

6. M := [3,∞) ist nicht nach oben beschränkt, und es gilt min M = inf M = 3.

Zunächst geben wir nun für eine nach oben beschränkte Teilmenge ; 6= M ⊆ Rein Kriterium für die Eigenschaft an, dass eine obere Schranke b von M kleinsteobere Schranke von M , d. h. b = sup M , ist.

Satz 18(9). Sei ; 6= M ⊆R nach oben beschränkt und b sei eine obere Schrankevon M . Dann gilt

b = sup M ⇐⇒ ∀ε> 0 ∃x ∈ M : x > b −ε.

Beweis. „=⇒”: Sei ε> 0 beliebig. Wegen b = sup M ist b−ε keine obere Schrankevon M . Daher gibt es ein x ∈ M mit x > b −ε.„⇐=”: Angenommen, es gibt eine obere Schranke d von M mit d < b. Sei ε :=b−d

2 . Dann ist ε > 0, und nach Voraussetzung gibt es ein x ∈ M mit x > b − ε =b − b−d

2 = 12 b + 1

2 d > d , ein Widerspruch. Also ist b kleinste obere Schranke vonM , d. h. b = sup M .

Die Menge {x ∈Q | x > 0∧ x2 < 2} ⊆Q ist nicht-leer und nach oben beschränkt,hat aber wegen der Irrationalität von

p2 (10(9)) kein Supremum inQ. Für R for-

dern wir diese „Lückenfreiheit” axiomatisch.

74

18 REELLE ZAHLEN 75

Supremumsaxiom 1. (auch Vollständigkeitsaxiom): Jede nicht-leere und nachoben beschränkte Teilmenge M ⊆R hat ein Supremum in R.

Hieraus folgt zunächst das Analogon für das Infimum.

Satz 18(10). Jede nicht-leere und nach unten beschränkte Teilmenge M ⊆R hatein Infimum in R. Es gilt inf M =−sup(−M).

Beweis. Sei ; 6= M ⊆ R nach unten beschränkt. Dann ist ; 6= −M nach obenbeschränkt, also existiert nach dem Supremumsaxiom (1) s := −sup(−M) ∈ R.Dann ist s eine untere Schranke von M , denn ist x ∈ M , so gilt −x É −s, äqui-valent s É x. Sei a ∈ R eine untere Schranke von M . Dann gilt für jedes x ∈ Ma É x, äquivalent −x É −a. Also ist −a eine obere Schranke von −M . Damitist sup(−M) É −a, d. h. a É s. Also ist s größte untere Schranke von M , d. h.inf M = s =−sup(−M).

Das Analogon zu Satz 18(9) ist der folgende

Satz 18(11). Sei ; 6= M ⊆Rnach unten beschränkt und a sei eine untere Schran-ke von M . Dann gilt

a = inf M ⇐⇒ ∀ε> 0 ∃x ∈ M : x < a +ε.

Beweis. Nach den Sätzen 18(9) und 18(10) gilt

a = inf M ⇐⇒−a = sup(−M) ⇐⇒∀ε> 0 ∃y ∈−M : y >−a −ε⇐⇒∀ε> 0 ∃y ∈−M : −y < a +ε⇐⇒∀ε> 0 ∃x ∈ M : x < a +ε

Als Beispiel für die Anwendung der Sätze 18(9) und 18(11) betrachten wir dasfolgende

Beispiel 18(12). Sei M := (0,1). Dann ist sup M = 1 und inf M = 0.

Beweis. Sei ε > 0 und o. E. d. A. sei ε < 2. Dann ist x := 1− 12ε ∈ M mit x > 1−ε.

Also ist nach Satz 18(9) sup M = 1. Es gilt y := 12ε ∈ M mit y < 0+ε. Daher ist nach

Satz 18(11) inf M = 0.

Satz 18(13). Sei ; 6= M ⊆R. Dann gelten die Aussagen

1. Wenn min M existiert, so existiert max(−M) mit max(−M) =−min M .

2. Wenn max M existiert, so existiert min(−M) mit min(−M) =−max M .

3. Wenn max M existiert, so existiert sup M mit sup M = max M .

4. Wenn min M existiert, so existiert inf M mit inf M = min M .

75

18 REELLE ZAHLEN 76

Beweis. 1. Sei a := min M . Wegen a ∈ M ist −a ∈ −M . Für jedes y ∈ −Mist −y ∈ M . Also gilt a É −y , folglich y É −a. Also ist max(−M) = −a =−min M .

2. Sei b := max M . Dann ist b ∈ M , und somit −b ∈ −M . Sei y ∈ −M , somit−y ∈ M . Dann ist −y É b, äquivalent −b É y . Es folgt min(−M) = −b =−max M .

3. Sei b := max M . Dann ist b eine obere Schranke von M , und für jede obereSchranke d von M gilt wegen b ∈ M b ≤ d . Also ist b kleinste obere Schran-ke von M , d. h. sup M = b = max M .

4. M ist durch min M nach unten beschränkt. Also existiert nach Satz 18(10)inf M und nach Satz 18(10) und nach 1. und 3. gilt min M =−max(−M) =−sup(−M) = inf M .

Beispiel 18(14). Sei M := { 1n | n ∈N}.

1. Es ist 1 ∈ M und für alle n ∈N gilt 1n ≤ 1. Also ist 1 = max M und nach Satz

18(13) 3. 1 = sup M .

2. min M existiert nicht, denn für jedes n ∈N gilt y := 1n+1 ∈ M mit y < 1

n .

3. Es gilt inf M = 0. Diese Aussage folgt aus Satz 18(11) und dem Archimedi-schen23 Prinzip, das im nächsten Satz folgt.

Satz 18(15). (Archimedisches Prinzip) Es gelten die folgenden Aussagen.

1. Für jedes x ∈R existiert ein n ∈Nmit n > x.

2. Für jedes x ∈Rmit x > 0 existiert ein n ∈Nmit 1n < x.

Beweis. 1. Sei x ∈ R. Angenommen, x ist eine obere Schranke von N. WegenN 6= ; existiert dann nach dem Supremumsaxiom (1) b := supN. Dann gibtes nach Satz 18(9) ein n ∈Nmit n > b−1, d. h. n+1 > b. Letzteres ist wegenn +1 ∈N und b = supN ein Widerspruch. Also ist x keine obere SchrankevonN. Daher existiert ein n ∈Nmit n > x.

2. Nach 1. gibt es ein n ∈Nmit n > 1x , äquivalent 1

n < x.

23Archimedes von Syrakus (? um 287 v. Chr. vermutlich in Syrakus auf Sizilien; † 212v. Chr. ebenda) war ein antiker griechischer Mathematiker, Physiker und Ingenieur. Er giltals einer der bedeutendsten Mathematiker der Antike. Seine Werke waren auch noch im16. und 17. Jahrhundert bei der Entwicklung der höheren Analysis von Bedeutung (Quelle:http://de.wikipedia.org/wiki/Archimedes_von_Syrakus).

76

18 REELLE ZAHLEN 77

Bemerkung 18(16). Das Archimedische Prinzip (18(15)) lässt sich nicht alleineaus den Körper- und Anordnungsaxiomen (A1) bis (A14) herleiten. Es gibt an-geordnete Körper (d. h. Körper, die neben den Axiomen (A1) bis (A9) auch dieAnordnungsaxiome (A10) bis (A14) erfüllen), welche das Archimedische Prin-zip nicht erfüllen. Solche angeordnete Körper heißen nicht-archimedisch. EinBeispiel eines nicht-archimedischen Körpers lässt sich ausgehend von dem so-genannten Polynomring R[x] über dem Körper R in einer Unbestimmten x kon-struieren. Wegen des Aufwands werden wir diese Konstruktion hier nicht durch-führen.

Nun kommen wir für m ∈ N noch einmal kurz auf unsere Menge Zm = {[0]m ,[1]m ,...,[m −1]m} der Restklassen modulo m (16(2)) zurück.

Bemerkung 18(17). Für m ∈ N \P ist Zm kein Körper, denn es gibt k, l ∈ N \{1,m} mit m = k · l . Dann ist [k]m · [l ]m = [kl ]m = [m]m = [0]m . Daraus folgt, dass[k]m 6= [0]m bezüglich der Multiplikation „·” kein inverses Element hat. Also istdas Analogon zu Axiom (A8) nicht erfüllt, und daher ist Zm für m ∈ N \P keinKörper.

Ausblick 18(18). Für jede Primzahl m istZm mit der obigen Addition (16(3)) undMultiplikation (16(4)) ein endlicher Körper mit m Elementen.Zm erfüllt also dieden Axiomen (A1) bis (A9) der reellen Zahlen entsprechenden Axiome. In diesemKörper gilt, anders als

m ·1 = m 6= 0 in dem Körper R, m · [1]m :=m∑

i=1[1]m = [m]m = [0]m .

Endliche Körper kommen beispielsweise in der algebraischen Kodierungstheo-rie vor.

18.c Übungsaufgaben

1. Beweisen Sie, dass

A :={n2 +n

n2 +1

∣∣∣n ∈N}

und B :={x|x = (−1

2 )m − 3n mit m,n ∈N}

nach oben und nach unten beschränkt (18(7)) sind. Bestimmen Sie oh-ne Beweise das Infimum (18(7)) und das Supremum (18(7)) und ggf. dasMinimum (18(7)) und das Maximum (18(7)) von A und B .

2. Seien ; 6= A ⊆ R und ; 6= B ⊆ R nach oben beschränkt (18(7)). BeweisenSie, dass für die Summe A +B := {a +b|a ∈ A, b ∈ B} A +B 6= ; gilt, unddass A+B nach oben beschränkt ist mit sup(A+B) = sup(A)+sup(B) (18(7)5.).

Hinweis: Beginnen Sie den Beweis der behaupteten Gleichheit mit denUngleichungen

a +b É sup(A+B) und a +b É sup(A)+ sup(B) für a ∈ A, b ∈ B.

77

19 FOLGEN UND KONVERGENZ 78

18.d Abschließende Bemerkung zum Axiomensystem von R

Die Axiome (A1) bis (A14) und das Supremumsaxiom (1) sind ausreichend fürdie für die Analysis notwendigen Eigenschaften von R. Eine gewisse Eindeutig-keit von R zeigt der folgende Satz, den wir hier ohne Beweis wiedergeben. DieVollständigkeit bedeutet hierbei, dass das Supremumsaxiom (1) erfüllt ist.

Satz 18(19). Es gibt bis auf Isomorphie höchstens einen vollständigen angeord-neten Körper. D. h. sind K und L zwei vollständige angeordnete Körper, so gibt eseine bijektive Abbildung f : K → L, die die algebraischen und die Anordnungs-eigenschaften erhält, d. h. für alle a,b ∈R gilt

f (a +b) = f (a)+ f (b) , f (ab) = f (a) f (b) , f (0K ) = 0L , f (1K ) = 1L und

a < b =⇒ f (a) < f (b) .

Ohne die Vollständigkeit stimmt dies nicht, da es zum Beispiel zwischen Q undR keine bijektive Abbildung gibt.

Woher wissen wir, dass die Axiome (A1) bis (A14) und das Supremumsaxiom (1)nicht schon zu viele Axiome sind? Das heißt, woher wissen wir, dass es über-haupt einen vollständigen angeordneten Körper gibt? Dies ist viel schwieriger zubeantworten. Die Frage lässt sich auch so formulieren: Woher wissen wir, dassdie Axiome widerspruchsfrei sind, wir aus ihnen also keinen Widerspruch her-leiten können? Gödel hat 1931 bewiesen, dass wir dies nicht wissen können, ge-nauer, dass wir die Widerspruchsfreiheit grundsätzlich nicht beweisen können.Es gilt aber Folgendes:

Wenn die Peano-Axiome für die natürlichen Zahlen (oder allgemeiner die Axio-me in Z F ) widerspruchsfrei sind, so sind es auch die Axiome der reellen Zahlen.Ob sie es wirklich sind, lässt sich wiederum nicht beweisen. Aber vielleicht wir-ken die Peano-Axiome noch elementarer und unmittelbar einsichtiger als dieAxiome (A1) bis (A14) und das Supremumsaxiom (1) der reellen Zahlen R. Unddie Menge R der reellen Zahlen lässt sich ausgehend von den Peano-Axiomenkonstruieren.

19 Folgen und Konvergenz

19.a Folgen, Betragsfunktion und Konvergenz von Folgen

Definition 19(1). Sei M eine Menge. Eine Abbildung a :N→ M heißt eine Folgein M . Eine Folge a wird meistens mit (an), (an)n , (an)n∈N oder (a1, a2, ...) be-zeichnet. Für n ∈ N heißt an das n-te Folgenglied der Folge (an)n∈N. Ist M = R,so heißt (an)n∈N eine reelle Folge.

78


Wir betrachten in diesem Skript nur reelle Folgen.

Beispiele 19(2). 1. an := 0 für n ∈N, also (an)n∈N = (0,0,0, . . . ).

2. an := 1n für n ∈N, also (an)n∈N = (1, 1

2 , 13 , . . . ).

3. an := (−1)n für n ∈N, also (an)n∈N = (−1,1,−1,1, . . . ).

4. a1 := a2 := 1, an+2 := an+1 + an für n ∈ N, also (an)n∈N = (1,1,2,3,5,8, ...).Diese rekursiv definierte Folge (an)n∈N heißt Fibonaccifolge24.

Wir wollen die Beobachtung präzisieren, dass sich die Folgenglieder im zweitenBeispiel „immer mehr der Null annähern”. Hierzu wird zunächst die Betrags-funktion definiert.

Definition 19(3). Die Abbildung | | :R→Rmit | |(x) := |x| :={

x für x ≥ 0

−x für x < 0,

heißt Betragsfunktion. Für x, y ∈R heißt |x − y | der Abstand von x und y .

Satz 19(4). Für x, y, z ∈R, n ∈N und xi ∈R für i ∈Nn gelten die Aussagen

1. x ≤ |x|∧−x ≤ |x|.2. |x| ≥ 0∧|x| = 0 ⇐⇒ x = 0.

3. |x| ≤ y ⇐⇒ x ≤ y ∧−x ≤ y .

4. |x · y | = |x| · |y |.5. |x − y | = |y −x|.6. |x + y | ≤ |x|+ |y | (sogenannte Dreiecksungleichung).

7. |x − z| ≤ |x − y |+ |y − z|.8. ||x|− |y || ≤ |x − y |.9. |∑n

i=1 xi | ≤∑ni=1 |xi |.

Beweis. 1. Für x ≥ 0 gilt x = |x|, und für x < 0 x ≤ −x = |x|. Es folgt für jedesx ∈ R x ≤ |x|. Durch Ersetzung von x durch −x folgt für jedes x ∈ R −x ≤|−x| = |x|.

2. Für alle x ∈ R gilt |x| ≥ 0 nach Definition, und ebenso |0| = 0. Ist x ∈ R mit|x| = 0, so gilt x = 0 oder −x = 0, folglich x = 0.

24Leonardo da Pisa, auch Fibonacci genannt (∗ um 1180? in Pisa; † nach 1241? ebenda) warRechenmeister in Pisa und gilt als der bedeutendste Mathematiker des Mittelalters (Quelle:http://de.wikipedia.org/wiki/Leonardo_da_Pisa).

79


3. „=⇒”: Sei |x| ≤ y . Wegen |x| ≥ 0 ist dann y ≥ 0. Für x < 0 gilt x < 0 ≤ y , alsox É y , und −x = |x| ≤ y , also −x ≤ y . Für x ≥ 0 gilt x = |x| ≤ y , also x ≤ y ,und −x ≤ 0 ≤ y , also −x ≤ y .

„⇐=”: Für x < 0 gilt |x| = −x ≤ y . Für x ≥ 0 gilt |x| = x ≤ y .

4. Es gilt |x y | = |(−x)y | = |x(−y)| = |(−x)(−y)| und |x||y | = |−x||y | = |x||−y | =|− x|| − y |. Daher kann o. E. d. A. x ≥ 0 und y ≥ 0 angenommen werden.Dann gilt x y ≥ 0, und damit |x y | = x y = |x||y |.

5. Nach 4. gilt |x − y | = |−1||x − y | = |(−1)(x − y)| = |y −x|.6. Aus 1. folgt x + y ≤ |x| + |y | und −(x + y) = (−x)+ (−y) ≤ |x| + |y |. Daraus

folgt nach 3. |x + y | ≤ |x|+ |y |.7. Nach 6. gilt |x − z| = |(x − y)+ (y − z)| ≤ |x − y |+ |y − z|.8. Für alle x, y ∈ R gilt nach 6. |x| = |y + (x − y)| ≤ |y | + |x − y |. Hieraus folgt

|x| − |y | ≤ |x − y |. Vertauschung von x und y in der letzten Ungleichungimpliziert nach 5. −(|x|− |y |) = |y |− |x| ≤ |y − x| = |x − y |. Aus 3. folgt nun||x|− |y || ≤ |x − y |.

9. Induktionsanfang (n = 1): Wegen |x1| = |x1| gilt die Behauptung.Induktionsschritt (n n+1): Die Behauptung sei für ein n ∈Nwahr. Dannfolgt nach 6.

∣∣∣n+1∑i=1

xi

∣∣∣=∣∣∣( n∑i=1

xi

)+xn+1

∣∣∣≤∣∣∣ n∑i=1

xi

∣∣∣+|xn+1|IV≤

( n∑i=1

|xi |)+|xn+1| =

n+1∑i=1

|xi |.

Auch „geometrisch offensichtliche” Aussagen über den Abstand oder den Betraglassen sich beweisen. Als Beispiele beweisen wir die beiden nächsten Hilfssätze.

Hilfssatz 19(5). Für x, y ∈R gilt |x − y | ≤ x

2=⇒ y ≥ x

2.

Beweis. Wegen x − y ≤ |x − y | ≤ x2 folgt y = x − (x − y) ≥ x − x

2 = x2 .

Hilfssatz 19(6). Eine Menge ; 6= M ⊆ R ist genau dann beschränkt, wenn einc > 0 existiert mit |x| ≤ c für alle x ∈ M .

Beweis. Ist M beschränkt, so gibt es nach Definition 18(7) 3. a,b ∈ R mit a É xund x É b für alle x ∈ M . O. E. d. A seien a < 0 und 0 < b. Dann ist c := b −a > 0und es gilt −c = a − b < a ≤ x ≤ b < b − a = c. Es folgt −c ≤ x ≤ c, äquivalent|x| ≤ c. Gilt umgekehrt für ein c > 0 |x| ≤ c für alle x ∈ M , so ist −c É x É c für allex ∈ M . Also ist M nach Definition 18(7) 3. beschränkt.

80


In dem folgenden Satz sind x, y ∈R in der Voraussetzung und in der Behauptungsymmetrisch. D. h., vertauschen wir x und y in der Voraussetzung und in der Be-hauptung, so ändert sich weder die Voraussetzung noch die Behauptung. Daherkönnen wir uns im Beweis o. E. d. A. etwa auf den Fall x ≥ y beschränken.

Satz 19(7). Für alle x, y ∈R gilt

1. min{x, y} = 1

2(x + y −|x − y |) 2. max{x, y} = 1

2(x + y +|x − y |).

Beweis. 1. Im Fall x ≥ y gilt

1

2(x + y −|x − y |) = 1

2(x + y − (x − y)) = y = min{x, y}.

Wegen der Symmetrie von x und y folgt die Behauptung.

2. Nach 1. und den Sätzen 18(13) 1. und 19(4) 5. gilt

max{x, y} =−min{−x,−y} =−1

2((−x)+ (−y)−|(−x)− (−y)|)

= 1

2(x + y +|y −x|) = 1

2(x + y +|x − y |).


1. Die Folgen (19(1)) (an)n∈N und (bn)n∈N seien rekursiv definiert durch

a1 := 5 und an+1 := an +9 für n ∈N

undb1 := 2 und bn+1 := b2

n für n ∈N.

Geben Sie eine „Formel” für an und für bn für jedes n ∈N an, und bewei-sen Sie deren Gültigkeit durch vollständige Induktion.

Hinweis: Für jedes n ∈ N dürfen in den „Formeln” an = ? und bn = ? aufder rechten Seite nur reelle Zahlen, auch n, vorkommen, nicht aber Fol-genglieder der Folgen (an)n∈N bzw. (bn)n∈N.

2. Bestimmen Sie mit Beweis⋃k∈N

[−2+ 1

k,5− 1

k

].


81


3. Bestimmen Sie alle x ∈Rmit |3x −6| ≤ |x +1| ((19(3))).

Hinweis: Verwenden Sie Definition (19(3)). Betrachten Sie kombinierte Fall-unterscheidungen. Es sind vier Fälle, z. B. x ≥ 2 ⇐⇒ |3x −6| = 3x −6 kom-biniert mit x ≥−1 ⇐⇒ |x +1| = x +1.

4. Beweisen Sie, dass die Abbildung ϕ : R→ ]−1,1[ mit ϕ(x) := x1+|x| wohl-

definiert (15(7)) und bijektiv (15(9)) ist, und geben Sie die zu ϕ inverseAbbildung (15(13)) an.

Hinweis: Lösen Sie für die Berechnung der zu ϕ inversen Abbildung füry ∈ ]−1,1[ die Gleichungϕ(x) = y mit x ∈Rdurch eine Fallunterscheidungnach x auf. Fassen Sie dann beide Fälle zusammen.


A :={ |x|

1+|x|∣∣∣x ∈R

}nach oben und nach unten beschränkt (18(7)) ist. Bestimmen Sie ohneBeweis das Infimum (18(7)) und das Supremum (18(7)) und ggf. das Mini-mum (18(7)) und das Maximum (18(7)) von A.

Wir werden nun einen der zentralen Begriffe der Analysis, die Konvergenz vonFolgen, definieren.

Definition 19(8). Sei (an)n∈N eine Folge.

1. Sei a ∈ R. Dann heißt die Folge (an)n∈N konvergent mit Grenzwert a, inZeichen

limn→∞an = a (auch an −−−−→

n→∞ a oder an → a),

wenn die folgende Aussage gilt:

∀ε> 0 ∃n0 ∈N ∀n ≥ n0 : |an −a| < ε.

2. Gilt für eine konvergente Folge (an)n∈N limn→∞an = 0, so heißt (an)n∈N Null-

folge.

Der folgende Satz besagt, dass der Grenzwert einer konvergenten Folge eindeu-tig bestimmt ist.

Satz 19(9). Sei (an)n∈N eine konvergente Folge und seien a,b ∈Rmit limn→∞an = a

und limn→∞an = b. Dann folgt a = b.

82


Beweis. Seien n ∈ N und ε := 12n . Dann gibt es n0 ∈ N mit |an − a| < ε für alle

n ≥ n0. Und es gibt n1 ∈ N mit |an − b| < ε für alle n ≥ n1. Dann gilt für allen ≥ max{n0,n1} nach der Dreiecksungleichung

|a −b| = |a −an +an −b| ≤ |a −an |+ |an −b| < 2 ·ε= 1

n.

Nach dem archimedischen Prinzip 18(15) folgt |a −b| = 0, und daraus a = b.

Der folgende Hilfssatz ist ein beweistechnisches Hilfsmittel für den Nachweisder Konvergenz einer Folge (an)n∈N gegen den Grenzwert a ∈R.

Hilfssatz 19(10). Seien K ∈Rmit K > 0, (an)n∈N eine Folge und a ∈R. Dann gilt

limn→∞an = a ⇐⇒∀ε> 0 ∃n0 ∈N ∀n ≥ n0 : |an −a| < K ·ε.

Beweis. „=⇒”: Sei ε> 0 beliebig. Zu ε1 := K ·ε> 0 gibt es nach Voraussetzung einn0 ∈N, so dass für alle n ≥ n0 |an −a| < ε1 = K ·ε ist.

„⇐=”: Sei ε> 0 beliebig. Zu ε1 := εK > 0 gibt es nach Voraussetzung ein n0 ∈N, so

dass für alle n ≥ n0 |an −a| < K ·ε1 = ε ist.

Definition 19(11). Sei (an)n∈N eine Folge.

1. (an)n∈N heißt konvergent :⇐⇒ ∃a ∈ R: (an)n∈N ist konvergent mit Grenz-wert a.

2. (an)n∈N heißt divergent :⇐⇒ (an)n∈N ist nicht konvergent.

Beispiele 19(12). 1. Sei an := 0 für n ∈ N. Dann ist (an)n∈N eine Nullfolge.Denn für jedes ε > 0 und alle n ∈ N gilt |an | = 0 < ε. Wir können also inDefinition 19(8) 1. z. B. n0 := 1 wählen.

2. Sei an := 1n für n ∈N. Dann ist (an)n∈N eine Nullfolge. Denn zu jedem ε> 0

gibt es nach dem archimedischen Prinzip (18(15)) ein n0 ∈ N mit 1n0

< ε.

Für n ≥ n0 gilt dann |an | = 1n É 1

n0< ε.

3. Sei an := (−1)n für n ∈N. Angenommen, (an)n∈N ist konvergent. Dann gibtes a ∈Rmit lim

n→∞an = a. Für ε := 1 gibt es daher nach Definition 19(8) 1. ein

n0 ∈Nmit |an −a| < ε für jedes n ∈Nmit n ≥ n0. Es folgt der Widerspruch2 = |1−a+1+a| É |1−a|+|1+a| < 2·ε= 2. Also ist (an)n∈N nicht konvergent.

4. Sei an := 3+ 1n für n ∈ N. Nach 2. ist (an − 3)n∈N = ( 1

n )n∈N eine Nullfolge.Aus Definition 19(8) 1. folgt die Konvergenz von (an)n∈N mit lim

n→∞an = 3.

83


Bemerkung 19(13). Es kommt auch hier wesentlich auf die Reihenfolge derQuantoren an. Werden beispielsweise ∀ε> 0 und ∃n0 ∈N in der Definition 19(8)1. vertauscht, so erhalten wir die Bedingung

∃n0 ∈N ∀ε> 0 ∀n ≥ n0 : |an −a| < ε.

Beispielsweise folgt im Fall a = 0 für alle n ≥ n0 an = 0. Demnach wäre z. B. dieFolge

( 1n

)n∈N im Widerspruch zu Beispiele 19(12) 2. keine Nullfolge.

Hilfssatz 19(14). Für jede Folge (an)n∈N und für jedes a ∈R gelten die Aussagen

1. limn→∞an = a ⇐⇒ Für jedes ε > 0 sind nur endlich viele Folgenglieder der

Folge (an)n∈N außerhalb von (a −ε, a +ε).

2. limn→∞an 6= a ⇐⇒ Es gibt ein ε> 0, so dass unendlich viele Folgenglieder der

Folge (an)n∈N außerhalb von (a −ε, a +ε) liegen.

Beweis. 1. „=⇒”: Zu ε> 0 gibt es nach Definition 19(8) 1. ein n0 ∈N, so dassfür alle n ≥ n0 |an −a| < ε, äquivalent a−ε< an < a+ε, ist. Außerhalb von(a −ε, a +ε) liegt daher nur eine Teilmenge von {a1, ..., an0−1}. Also gilt dieBehauptung.

„⇐=”: Sei ε > 0 beliebig. Aus der Voraussetzung folgt, dass es ein n0 ∈ Ngibt, so dass nur eine Teilmenge von {a1, ..., an0−1} außerhalb von (a−ε, a+ε) liegt. Für alle n ≥ n0 gilt dann a −ε< an < a +ε, äquivalent |an −a| < ε.Daher gilt nach Definition 19(8) 1. lim

n→∞an = a.

2. Die Negationen der äquivalenten Aussagen in 1. sind ebenfalls äquivalent.

Beispiel 19(15). Die Folge (an)n∈N sei für n ∈ N definiert durch an := 1n , wenn

n gerade, und an := 1, wenn n ungerade ist, also (an)n∈N = (1, 12 ,1, 1

4 , . . . ). DieseFolge ist nach Hilfssatz 19(14) 2. keine Nullfolge, da zum Beispiel für ε := 1

2 undfür alle ungeraden n ∈N an außerhalb von (−ε,ε) liegt.

Eine wichtige Beobachtung ist, dass es bei der Konvergenz einer Folge nur aufdas Verhalten der Folgenglieder ab einem beliebigen Index n0 ∈N ankommt.

Hilfssatz 19(16). Sind (an)n∈N und (bn)n∈N Folgen und gibt es ein n0 ∈ N mitan = bn für alle n ≥ n0, so gilt:

Ist (an)n∈N konvergent und a ∈ R mit limn→∞an = a, so ist (bn)n∈N konvergent mit

limn→∞bn = a.

Beweis. Wegen limn→∞an = a gibt es für ε > 0 ein n1 ∈ N, so dass für alle n ≥ n1

|an −a| < ε ist. Für alle n ≥ max{n0,n1} ist dann |bn −a| = |an −a| < ε. Daher giltnach Definition 19(8) 1. lim

n→∞bn = a.

84



1. Geben Sie Folgen (an)n∈N und (bn)n∈N an, so dass

(an)n∈N konvergent (19(11)) und (bn)n∈N divergent ist mit a2n = b2n füralle n ∈N.

2. Geben Sie eine nicht konvergente Folge (19(11)) (an)n∈N und ein a ∈R an,so dass die folgende Bedingung erfüllt ist: Es gibt ein ε> 0, so dass für allen ∈N |an −a| < ε ist.

19.b Algebraische Operationen von konvergenten Folgen

Wir untersuchen nun, wie sich die Konvergenz von Folgen mit algebraischenOperationen (z. B. Addition und Multiplikation) und mit Ungleichungen „ver-trägt”.

Zunächst definieren wir den Begriff der Beschränkheit einer Folge (an)n∈N.

Definition 19(17). Eine Folge (an)n∈N heißt beschränkt (bzw. nach unten be-schränkt, bzw. nach oben beschränkt), wenn die Menge A := {an | n ∈ N} be-schränkt (bzw. nach unten beschränkt, bzw. nach oben beschränkt) ist.

Eine Folge (an)n∈N ist also nach den Definitionen 19(17) und 18(7) 3. genau dannbeschränkt, wenn sie nach oben und nach unten beschränkt ist.

Satz 19(18). Jede konvergente Folge (an)n∈N ist beschränkt.

Beweis. Nach Voraussetzung gibt es ein a ∈ R mit limn→∞an = a. Dann existiert

nach Definition 19(8) 1. zu ε := 1 ein n0 ∈ N, so dass für alle n ≥ n0 |an − a| < 1ist. Es folgt für alle n ≥ n0

|an | = |(an −a)+a| ≤ |an −a|+ |a| < 1+|a|.

Für c := max{1+ |a|, |a1|, ..., |an0−1|} > 0 gilt dann für alle n ∈ N |an | ≤ c. Also ist(an)n∈N nach Hilfssatz 19(6) und nach Definition 19(17) beschränkt.

Hilfssatz 19(19). Sei (an)n∈N eine konvergente Folge mit an 6= 0 für alle n ∈ Nund für a := lim

n→∞an sei a 6= 0. Dann gibt es ein c ∈ R mit c > 0 und |an | ≥ c für

alle n ∈N.

Beweis. Wegen limn→∞an = a und Satz 19(4) 8. gibt es wegen |a|

2 > 0 ein n0 ∈N, so

dass für alle n ≥ n0 ||a|− |an || = ||an |− |a|| É |an −a| < |a|2 ist. Aus Hilfssatz 19(5)

folgt |an | ≥ |a|2 für n ≥ n0. Dann ist

c := min{ |a|

2, |a1|, . . . , |an0−1|

}> 0, und erfüllt |an | ≥ c für alle n ∈N.

85


Satz 19(20). Seien (an)n∈N und (bn)n∈N konvergente Folgen, a,b ∈Rmit limn→∞an = a

und limn→∞bn = b und λ ∈R. Dann gelten die Aussagen

1. limn→∞(an +bn) = a +b.

2. limn→∞anbn = ab.

3. limn→∞(an −bn) = a −b.

4. Im Fall bn 6= 0 für alle n ∈N und b 6= 0 gilt limn→∞

an

bn= a

b.

5. limn→∞λbn =λb.

Beweis. Sei ε> 0 beliebig. Wegen limn→∞an = a und lim

n→∞bn = b gibt es n0,n1 ∈Nmit |an −a| < ε für n ≥ n0 und |bn −b| < ε für n ≥ n1. Für n2 := max{n0,n1} undalle n ≥ n2 gilt dann |an −a| < ε und |bn −b| < ε. Diese Aussage wird im Beweisvon 1., 2. und 4. verwendet.

1. Nach der Dreiecksungleichung gilt für alle n ≥ n2

|(an +bn)− (a +b)| = |(an −a)+ (bn −b)| ≤ |an −a|+ |bn −b| < 2ε .

Aus Hilfssatz 19(10) folgt limn→∞(an +bn) = a +b.

2. Nach der Dreiecksungleichung gilt für alle n ∈N|anbn −ab| = |anbn −anb +anb −ab| = |an(bn −b)+ (an −a)b|≤ |an | · |bn −b|+ |an −a| · |b|.Da (an)n∈N als konvergente Folge nach Satz 19(18) beschränkt ist, gibt esein c ∈ R mit c > 0 und |an | ≤ c für alle n ∈ N. Für alle n ≥ n2 folgt wegen|an −a| < ε und |bn −b| < ε

|anbn −ab| < c ·ε+ε · |b| = (c +|b|) ·ε.

Wegen 0 < c +|b| folgt aus Hilfssatz 19(10) limn→∞anbn = ab.

3. Für die Folge (cn)n∈N mit cn := −1 für n ∈ N gilt limn→∞cn =−1. Daher folgt

aus 1. und 2.

limn→∞(an −bn) = lim

n→∞(an + cnbn) = limn→∞an + lim

n→∞cnbn = a + (−1) ·b = a −b.

86


4. Wegen anbn

= an · 1bn

und ab = a · 1

b genügt es wegen 2. limn→∞

1bn

= 1b zu zeigen.

Nach Hilfssatz 19(19) gibt es ein c > 0 mit |bn | ≥ c für alle n ∈ N. Für allen ≥ n1 und K := 1

|b|·c gilt dann

∣∣∣ 1

bn− 1

b

∣∣∣= |b −bn ||b| · |bn |

< ε

|b| · c= K ·ε.

Aus Hilfssatz 19(10) folgt

limn→∞

1

bn= 1

bund daraus, wie oben bemerkt, lim

n→∞an

bn= a

b.

5. Die Folge (cn)n∈N sei definiert durch cn := λ für jedes n ∈ N. Dann ist(cn)n∈N konvergent mit lim

n→∞cn =λ. Aus 2. folgt

limn→∞λbn = lim

n→∞cnbn =λb.

Wegen limn→∞

1n = 0 (19(12) 2.) erhalten wir aus Satz 19(20) 2. durch vollständige

Induktion das folgende

Korollar 19(21). Für jedes k ∈N gilt limn→∞

1

nk= 0.

Beispiel 19(22). Die Folge (an)n∈N sei definiert durch

an := 4 ·n5 +5 ·n2 −8

2 ·n5 +5 ·n

für alle n ∈N. Wegen

an =4·n5

n5 + 5·n2

n5 − 8n5

2·n5

n5 + 5·nn5

=4+ 5

n3 − 8n5

2+ 5n4

für jedes n ∈N folgt aus Satz 19(20) und Korollar (19(21))

limn→∞an =

limn→∞4+ lim

n→∞5

n3 − limn→∞

8n5

limn→∞2+ lim

n→∞5

n4

= 4+0−0

2+0= 2.

Nun beschäftigen wir uns mit der Verträglichkeit der Konvergenz von Folgenmit Ungleichungen. Das folgende sogenannte „Sandwich-Lemma” wird oft zumNachweis der Konvergenz einer Folge verwendet.

87


Satz 19(23). Seien (an)n∈N, (bn)n∈N und (cn)n∈N Folgen und a,b ∈ R. Dann gel-ten die Aussagen

1. (Sandwich-Lemma (auch Einschließungs- oder Quetsch-Lemma)) Es sei-en (an)n∈N und (cn)n∈N konvergent mit lim

n→∞an = a = limn→∞cn und für jedes

n ∈N sei an ≤ bn ≤ cn . Dann ist (bn)n∈N konvergent mit limn→∞bn = a.

2. Es seien (an)n∈N und (bn)n∈N konvergent mit limn→∞an = a und lim

n→∞bn = b

und für jedes n ∈N sei an ≤ bn . Dann gilt a ≤ b.

Beweis. 1. Sei ε> 0 beliebig. Dann gibt es n0,n1 ∈Nmit |an−a| < ε für n ≥ n0

und |cn −a| < ε für n ≥ n1. Sei n ≥ n2 := max{n0,n1} beliebig. Aus |an −a| <ε folgt nach Satz 19(4) 3. a − ε < an . Aus |cn − a| < ε folgt entsprechendcn < a +ε. Also gilt

a −ε< an ≤ bn ≤ cn < a +ε .

Daraus folgta −ε< bn < a +ε ,

äquivalent −ε< bn −a < ε. Also gilt für alle n ≥ n2 |bn −a| < ε, und damitist (bn)n∈N konvergent mit lim

n→∞bn = a.

2. Sei ε > 0 beliebig. Dann gibt es n0,n1 ∈ N mit |an − a| < ε für n ≥ n0 und|bn −b| < ε für n ≥ n1. Für alle n ≥ max{n0,n1} folgt ähnlich wie in 1.

a −ε< an ≤ bn < b +ε.

Dann ist a −ε< b +ε, folglich a < b +2ε für alle ε> 0. Daher gilt a ≤ b.

Beispiel 19(24). Für jedes n ∈N gilt

0 É 1

n5 +n2 +8É 1

n.

Wegen limn→∞

1n = 0 (19(12) 2.) folgt aus dem Sandwich-Lemma 19(23) 1.

limn→∞

1

n5 +n2 +8= 0.

Eine zweifache Anwendung von Satz 19(23) 2. impliziert das folgende

Korollar 19(25). Seien a,b ∈ R und (cn)n∈N eine Folge mit a É cn É b für jedesn ∈N. Ist (cn)n∈N konvergent mit c := lim

n→∞cn , so folgt a É c É b.

Bemerkung 19(26). Sind (an)n∈N und (bn)n∈N konvergente Folgen mit an < bn

für alle n ∈N und a,b ∈ R mit limn→∞an = a und lim

n→∞bn = b, so folgt im allgemei-

nen nicht a < b, sondern a ≤ b. Sei hierzu an := 0 und bn := 1n für alle n ∈ N.

Dann ist an < bn für alle n ∈N und limn→∞an = 0 = lim

n→∞bn .

88



1. Geben Sie Folgen (an)n∈N und (bn)n∈N mit den folgenden Eigenschaftenan.

(a) (an)n∈N ist konvergent (19(11)), (bn)n∈N ist divergent (19(11)) und (anbn)n∈Nist konvergent.

(b) (an)n∈N ist konvergent, (bn)n∈N ist divergent und (anbn)n∈N ist diver-gent.

(c) (an)n∈N und (bn)n∈N sind divergent und (anbn)n∈N ist konvergent.

2. Sei (an)n∈N eine beschränkte Folge (19(17)) und (bn)n∈N eine Nullfolge(19(8)). Beweisen Sie, dass (anbn)n∈N eine Nullfolge ist.

3. Sei

an := 1

n· 1+ (−1)n+1

2+ 1+ (−1)n

2 ·pn

für n ∈N. Beweisen Sie, dass (an)n∈N eine Nullfolge (19(8)) ist.

4. Untersuchen Sie die Folgen (an)n∈N,...,(en)n∈N auf Konvergenz (19(8)) undbestimmen Sie ggf. den Grenzwert (19(8)).

an :=pn +1−p

n bn := 1

n2

n∑i=1

i cn :=n∑

k=1

1

4k2 −1

dn := (−6)n +3n

7n +5n en := n2 +2

3 · (n +1)2

für n ∈N.

Hinweis: Verwenden Sie bei mehreren Aufgaben Satz 19(20).

Hinweis zu (an)n∈N: Für alle n ∈N gilt

an = an ·p

n +1+pnp

n +1+pn

.

Hinweis zu (bn)n∈N: Verwenden Sie die Gaußsche Summenformel (11(5)).

Hinweis zu (cn)n∈N: Beweisen Sie zunächst für jedes k ∈N

1

4k2 −1= 1

2·( 1

2k −1− 1

2k +1

).

89


19.c Monotone Folgen, Teilfolgen und Häufungspunkte

Für den Nachweis der Konvergenz einer Folge können wir die Definition 19(8)nur dann verwenden, wenn der in ihr enthaltene Grenzwert als Vermutung oderBehauptung bekannt ist. In diesem Abschnitt lernen wir ein Kriterium kennen,mit dem die Konvergenz mancher Folgen ohne Kenntnis ihres Grenzwertes be-wiesen werden kann.

Definition 19(27). Eine Folge (an)n∈N heißt

1. monoton wachsend, wenn für alle n ∈N an É an+1 ist.

2. streng monoton wachsend, wenn für alle n ∈N an < an+1 ist.

3. monoton fallend, wenn für alle n ∈N an+1 É an ist.

4. streng monoton fallend, wenn für alle n ∈N an+1 < an ist.

Hilfssatz 19(28). Für jede Folge (an)n∈N gelten die Aussagen:

1. (an)n∈N ist monoton wachsend ⇐⇒∀m,n ∈N : m É n =⇒ am É an .

2. (an)n∈N ist streng monoton wachsend ⇐⇒∀m,n ∈N : m < n =⇒ am < an .

3. (an)n∈N ist monoton fallend ⇐⇒∀m,n ∈N : m É n =⇒ an É am .

4. (an)n∈N ist streng monoton fallend ⇐⇒∀m,n ∈N : m < n =⇒ an < am .

Beweis. 1. „=⇒”: Induktionsanfang (n = m): Dann gilt am = an .Induktionsschritt (n n +1): Nach Induktionsvoraussetzung gilt für m Én am É an und nach Definition 19(27) an É an+1. Es folgt am É an+1.„⇐=”: Für jedes n ∈N gilt an É an+1 nach Voraussetzung. Also ist (an)n∈Nmonoton wachsend (19(27)).

2. „=⇒”: Induktionsanfang (n = m + 1): Dann gilt am < an nach Definition19(27).Induktionsschritt (n n +1): Nach Induktionsvoraussetzung gilt für m <n am < an und nach Definition 19(27) an < an+1. Es folgt am < an+1.„⇐=”: Für jedes n ∈N gilt an < an+1 nach Voraussetzung. Also ist (an)n∈Nstreng monoton wachsend (19(27)).

3. Die Behauptung folgt aus 1., angewendet auf die Folge (−an)n∈N.

4. Die Behauptung folgt aus 2., angewendet auf die Folge (−an)n∈N.

90


Satz 19(29). Es gelten die folgenden Aussagen.

1. Jede monoton wachsende und nach oben beschränkte Folge (an)n∈N istkonvergent mit lim

n→∞an = sup{an | n ∈N}.

2. Jede monoton fallende und nach unten beschränkte Folge (an)n∈N ist kon-vergent mit lim

n→∞an = inf{an | n ∈N}.

Beweis. 1. Für die Menge M := {an | n ∈ N} existiert mit Definition 19(17)nach Voraussetzung und nach dem Supremumsaxiom (1) b := sup M . Zuε > 0 gibt es nach Satz 18(9) ein n0 ∈ N mit an0 > b − ε. Für n ≥ n0 folgtb − ε < an0 É an É b < b + ε, und daraus |an − b| < ε. Daher ist (an)n∈Nkonvergent mit lim

n→∞an = b.

2. Die Folge (−an)n∈N ist monoton wachsend und nach oben beschränkt.Nach 1. konvergiert daher (−an)n∈N mit c := lim

n→∞(−an) = sup{−an | n ∈N}.

Aus Satz 19(20) 5. folgt die Konvergenz von (an)n∈N mit limn→∞an =−c. Aus

Satz 18(10) folgt nun limn→∞an =−sup{−an | n ∈N} = inf{an | n ∈N}.

Definition 19(30). Seien X ,Y ⊆R. Eine Abbildung f : X → Y heißt

1. monoton steigend ⇐⇒∀x, y ∈ X : x É y =⇒ f (x) É f (y).

2. streng monoton steigend ⇐⇒∀x, y ∈ X : x < y =⇒ f (x) < f (y).

3. monoton fallend ⇐⇒∀x, y ∈ X : x É y =⇒ f (x) ≥ f (y).

4. streng monoton fallend ⇐⇒∀x, y ∈ X : x < y =⇒ f (x) > f (y).

Bemerkung 19(31). Eine Folge (an)n∈N ist nach Definition 19(27) und Hilfssatz19(28) genau dann monoton wachsend (bzw. streng monoton wachsend bzw.monoton fallend bzw. streng monoton fallend), wenn die Abbildung a : N→ R

monoton steigend (bzw. streng monoton steigend bzw. monoton fallend bzw.streng monoton fallend) ist.

Definition 19(32). Sei (an)n∈N eine Folge und ϕ : N→ N eine streng monotonsteigende Abbildung (19(30)). Dann heißt die Folge (bn)n∈N mit bn := aϕ(n) fürjedes n ∈N eine Teilfolge der Folge (an)n∈N.

Beispiele 19(33). Die Folge (an)n∈N sei definiert durch an := 1n für n ∈N.

91


1. Die Abbildung ϕ :N→N sei definiert durch ϕ(n) := 2n. Dann ist ϕ strengmonoton steigend und daher ist die Folge (bn)n∈N mit bn := aϕ(n) für n ∈N, d.h.

(bn)n∈N =(1

2,

1

4,

1

6. . .

),

eine Teilfolge von (an)n∈N.

2. Die Abbildung ϕ :N→N sei definiert durch ϕ(n) := 2n . Dann ist ϕ strengmonoton steigend und daher ist die Folge (cn)n∈N mit cn := aϕ(n) für n ∈N,d.h.

(cn)n∈N =(1

2,

1

4,

1

8, . . .

),

eine Teilfolge von (an)n∈N.

Hilfssatz 19(34). Seien (an)n∈N eine konvergente Folge, a ∈ R mit limn→∞an = a.

Dann ist jede Teilfolge (bn)n∈N von (an)n∈N konvergent mit limn→∞bn = a.

Beweis. Nach Definition 19(32) gibt es eine streng monoton steigende Abbil-dung ϕ : N→ N mit bn = aϕ(n) für jedes n ∈ N. Sei ε > 0 beliebig. Dann gibt esn0 ∈Nmit |an −a| < ε für alle n ≥ n0. Für jedes n ≥ n0 giltϕ(n) ≥ϕ(n0) ≥ n0, unddann |bn −a| = |aϕ(n) −a| < ε. Also ist (bn)n∈N konvergent mit lim

n→∞bn = a.

Definition 19(35). Sei (an)n∈N eine Folge und a ∈ R. Dann heißt a Häufungs-punkt von (an), wenn es für jedes ε > 0 unendlich viele n ∈ N mit |an − a| < ε

gibt.

Beispiele 19(36). 1. Ist (an)n∈N eine konvergente Folge und a ∈Rmit limn→∞an = a,

so ist a ein Häufungspunkt von (an)n∈N. Denn für jedes ε > 0 gibt es einn0 ∈Nmit |an −a| < ε für alle n ≥ n0.

2. Die Folge (an)n∈N mit an := (−1)n für alle n ∈Nhat die Häufungspunkte−1und 1. Denn für jedes ε> 0 gilt |an −1| = 0 < ε für n ∈ 2N und |an − (−1)| =0 < ε für n ∈ 2N−1.

Satz 19(37). Für jede Folge (an)n∈N und für jedes a ∈R gilt

a ist Häufungspunkt von (an)n∈N⇐⇒ Es gibt eine konvergente Teilfolge (bn)n∈Nvon (an)n∈N mit lim

n→∞bn = a.

Beweis. „=⇒”: Wir konstruieren induktiv eine streng monoton steigende Abbil-dung (19(30)) ϕ :N→Nmit |aϕ(n) −a| < 1

n für jedes n ∈N.Induktionsanfang (n = 1): Nach Voraussetzung gibt es ein m1 ∈Nmit |am1 −a| <1. Sei ϕ(1) := m1.Induktionsschritt (n n +1): Nach Voraussetzung gibt es ein mn+1 ∈Nmit

mn+1 >ϕ(n) und |amn+1 −a| < 1

n +1.

92

20 LEHRBÜCHER ZU ANALYSIS I, II UND LINEARE ALGEBRA I, II 93

Sei ϕ(n +1) := mn+1. Dann gilt

ϕ(n) <ϕ(n +1) und |aϕ(n+1) −a| < 1

n +1.

Damit ist die Induktionsbehauptung bewiesen. Die Folge (bn)n∈N sei definiertdurch bn := aϕ(n) für jedes n ∈N. Für jedes ε> 0 gibt es ein n0 ∈Nmit 1

n0< ε. Für

alle n ≥ n0 folgt

|bn −a| = |aϕ(n) −a| < 1

nÉ 1

n0< ε.

Also ist die Folge (bn)n∈N eine konvergente Teilfolge von (an)n∈N mit limn→∞bn = a.

„⇐=”: Sei (bn)n∈N eine konvergente Teilfolge von (an)n∈N mit limn→∞bn = a. Dann

existiert eine streng monoton steigende Abbildung (19(30)) ϕ : N→ N mit bn =aϕ(n) für jedes n ∈N. Für jedes ε> 0 gibt es ein n0 ∈Nmit |aϕ(n) −a| = |bn −a| <ε für alle n ≥ n0. Da ϕ : N→ N streng monoton steigend ist, ist a folglich einHäufungspunkt von (an)n∈N.

19.c.1 Übungsaufgaben

1. Die Folge (an)n∈N sei rekursiv definiert durch a1 := 14 und an+1 := a2

n + 14

für jedes n ∈N.

(a) Beweisen Sie 0 É an É 12 für jedes n ∈N.

(b) Beweisen Sie, dass die Folge (an)n∈N monoton wachsend und kon-vergent ist.

(c) Berechnen Sie limn→∞an .

Hinweis zu c): Sie können ohne Beweis limn→∞an = lim

n→∞an+1 verwenden.

2. Ist die Folge (an)n∈N mitan := 2((−1)n ) + 2

n

für jedes n ∈N konvergent?

Hinweis: Diese Frage können Sie mit den Sätzen 19(14) 2. und 19(20) 1.beantworten.

20 Lehrbücher zu Analysis I, II und Lineare Algebra I, II

Das Studium mathematischer Literatur ist in den ersten zwei Semestern nichtunbedingt notwendig. Ein Vergleich der Darstellung des Lehrstoffs der Vorle-sungen mit der Darstellung in Lehrbüchern kann aber das Verständnis vertie-fen. Zudem ist die erlernte Verwendung mathematischer Literatur nützlich fürdas Studium in höheren Semestern.

93

20 LEHRBÜCHER ZU ANALYSIS I, II UND LINEARE ALGEBRA I, II 94

Zu Analysis I, II:

1. Amann Escher Analysis I, II

2. Barner Flohr AN I

3. Berends Analysis Band 1, 2

4. Beutelspacher Analysis

5. Busam Epp Prüfungstrainer Analysis

6. Fichtenholz Differential- und Integralrechnung 1, 2

7. Fritzsche Grundkurs Analysis 1, 2

8. Heuser Analysis Teil 1, Teil 2

9. Hildebrand Analysis

10. Otto Forster Analysis I, II

11. Otto Forster Übungsbuch Analysis I, II

12. Otto Forster Übungsbuch Lösungen Analysis I, II

13. Königsberger Analysis I, II

14. Timmann Repetitorium der Analysis Teil 1, 2

15. Walter Einführung in die Analysis 1

16. Wolff Gloor Richard Analysis Alive

Zu Lineare Algebra I, II:

1. Beutelspacher Lineare Algebra

2. Bosch Lineare Algebra

3. Brieskorn Lineare Algebra und analytische Geometrie I

4. Busam Epp Prüfungstrainer Lineare Algebra

5. Gerd Fischer Lineare Algebra

6. Gerd Fischer Lineare Algebra und Analytische Geometrie

7. Klaus Jänich Lineare Algebra

94

23 STUDIENBERATUNG 95

8. Köcher Lineare Algebra und analytische Geometrie

9. Kowalsky Michler Lineare Algebra

10. Lorenz Lineare Algebra I, II

11. Muthsam Lineare Algebra und ihre Anwendungen

12. Stammbach Lineare Algebra

13. Wille Repetitorium der Linearen Algebra, Teil 1

14. Holz und Wille Repetitorium der Linearen Algebra, Teil 2

Zu Analysis I und zu Lineare Algebra I:

1. Modler Kreh Tutorium Analysis 1 und Lineare Algebra 1

21 Griechisches Alphabet

Griechische Buchstaben werden in mathematischen Texten sehr oft verwendet.Eine Liste gibt es beispielsweise auf

http://www.math.uni-trier.de/~schulz/galphabet.html

22 Mathematisches Wörterbuch (englisch)

In der Regel sind mindestens in den ersten zwei Semestern keine Englischkennt-nisse notwendig. Später sind mathematische Wörterbücher manchmal hilfreich.Ein solches für deutsch-englich und englisch-deutsch gibt es für die TeilgebieteGrundlagen, Analysis, Lineare Algebra und Numerik auf der Seite

http://www.math.uni-goettingen.de/baule/wbuch.html

23 Studienberatung

Auf der folgenden Seite sind alle Möglichkeiten der Akademischen und Studen-tischen Studienberatung an der Fakultät für Mathematik der Universität Biele-feld aufgelistet.

http://ekvv.uni-bielefeld.de/pers_publ/publ/EinrichtungDetail.jsp?orgId=7096296

95

24 ZUSAMMENFASSUNG ALLER IM TEXT ENTHALTENENÜBUNGSAUFGABEN 96

24 Zusammenfassung aller im Text enthaltenen Übungs-aufgaben

24.a Übungsblatt 1

1. Beweisen Sie: Gilt für a,b, p, q ∈ Z, dass a durch p teilbar (9(5)) ist und bdurch q teilbar ist, so ist a ·b durch p ·q teilbar.

Hinweis: Verwenden Sie drei mal Definition 9(5).

2. Seien z ∈Z und k ∈N. Beweisen Sie, dass genau eine der ganzen Zahlen

z +1, ..., z +k

durch k teilbar (9(5)) ist.

Hinweis: Sie können ohne Beweis verwenden, dass es l ∈Z und r ∈N0 mitr É k −1 und z = l ·k + r gibt. Beweisen Sie 1 É k − r É k und k | z +k − r .Folgern Sie dann aus k | z+m für ein m ∈ {1, ...,k} mit Satz 9(11) m = k−r .

3. Beweisen Sie: Zu jeder ungeraden natürlichen Zahl (9(3) 6.) n gibt es eineganze Zahl m mit n2 = 8m +1.

4. Beweisen Sie: Es gibt nur einen Primzahldrilling, d. h. es gibt nur einePrimzahl p, so dass auch p +2 und p +4 Primzahlen sind.

Hinweis: Betrachten Sie unter Verwendung der zweiten Übungsaufgabe9.e zwei mal für drei aufeinanderfolgende natürliche Zahlen die Teilbar-keit durch 3.

5. Beweisen Sie für a,b ∈R die Gleichung

(a +b)(a −b)3 − (a −b)(a +b)3 =−4ab(a +b)(a −b).

Hinweis: Schreiben Sie den Term auf der linken Seite der Gleichung als einProdukt, indem Sie gemeinsame Faktoren „ausklammern”.

6. Für welche a,b ∈R sind die Terme in der Gleichung

a

a +b+ b

a −b+ 2ab

b2 −a2 = a −b

a +b

definiert? Beweisen Sie für solche a,b die Gültigkeit dieser Gleichung.

Hinweis: Multiplizieren Sie für b2 − a2 6= 0 im Beweis die Gleichung mitb2 −a2.

7. Beweisen Sie, dass für jede Primzahl p ≥ 5 p2 −1 durch 24 teilbar (9(5))ist.

Hinweis: Verwenden Sie Satz 10(3) und die zweite Übungsaufgabe 9.e.

96


8. Beweisen Sie, dass es keine größte negative rationale Zahl gibt.

9. Beweisen Sie für jede Primzahl p, dassp

p irrational ist.

10. Beweisen Sie durch Kontraposition: Sei n ∈ N eine Quadratzahl (10(11)).Ist n ungerade (9(3)), so ist auch

pn ungerade.

11. Beweisen Sie durch Fallunterscheidung: Für jede ganze Zahl z ist z2+3z+7ungerade.

Hinweis: Betrachten Sie die Fälle „z ist gerade” und „z ist ungerade”.

12. Beweisen Sie durch Fallunterscheidung: Für jede ganze Zahl z ist 5 entwe-der ein Teiler (9(5)) von z oder von z4 −1.

Hinweis: Betrachten Sie {z −1, z, z +1, z +2, z +3}, und verwenden Sie diezweite Übungsaufgabe 9.e.

13. Beweisen Sie für jedes n ∈N0 durch vollständige Induktion 2n ≥ n.

14. Beweisen Sie für jedes n ∈ N0 durch vollständige Induktion: 23n + 13 istdurch 7 teilbar (9(5)).

15. Beweisen Sie für jedes n ∈N0 durch vollständige Induktion

n∑i=1

i 2 = n(n +1)(2n +1)

6.

16. Beweisen Sie für jedes n ∈N durch vollständige Induktion

n∏k=2

(1− 1

k

)= 1

n.

17. Seien m,n ∈ N0, ak ,bk ∈ R für k = m,m + 1, ...,n und es seien α,β ∈ R.Beweisen Sie durch vollständige Induktion nach n

n∑k=m

(α ·ak +β ·bk ) =α ·n∑

k=mak +β ·

n∑k=m

bk .

Wie folgt hieraus Hilfssatz 11(2)?

24.b Übungsblatt 2

18. Beweisen Sie durch Angabe der Wahrheitstafel: Für alle Aussagen A und Bgilt

(1) A =⇒ A∨B 2) A∧B =⇒ A.

97


19. Beweisen Sie durch Angabe der Wahrheitstafel das zweite De MorganscheGesetz der Aussagenlogik: Für alle Aussagen A und B gilt

¬(A∧B) ⇐⇒ (¬A)∨ (¬B).

20. Schreiben Sie die sogenannte starke Goldbachsche Vermutung: „Jede ge-rade natürliche Zahl größer als 2 ist eine Summe von zwei Primzahlen.“und deren Negation unter Verwendung von Quantoren (12(4)) ohne dasNegationszeichen ¬.

Hinweis: Sie können die Menge M := {n ∈N | n Ê 2} verwenden.

21. Formulieren Sie eine wahre mathematische Aussage der Form ∃ ∀ ∃ : Amit Quantoren (12(4)) und in Worten, und formulieren Sie die Negation¬(∃ ∀ ∃ : A) dieser Aussage ohne das Negationszeichen ¬ mit Quantorenund in Worten.

22. Beweisen Sie: Für alle Mengen A,B ,C gilt A \ (B ∪C ) = A \ B ∩ A \C .


23. Beweisen Sie: Für Mengen M und N gilt im allgemeinen nichtP (M)∪P (N ) =P (M ∪N ).

Hinweis: Analysieren Sie den Beweis von Satz 13(7). Es gibt Gegenbeispielemit |M | = |N | = 1 (13(8)).

24. Beweisen Sie: Für alle Mengen A,B ,C und D gilt

(A∩B)× (C ∩D) = (A×C )∩ (A×D)∩ (B ×C )∩ (B ×D).

Hinweis: Studieren Sie den Beweis von Hilfssatz 13(15), und verwendenSie die Definitionen 13(13) und 13(4).

25. Die MengeN1 (bzw.N2) hat genau eine Partition (13(11)) (bzw. genau zweiPartitionen), nämlich {1} (bzw. {1,2} und {1}, {2}). Wie viele und welche Par-titionen hat die MengeNn für n = 3 und für n = 4?

Hinweis: Mit der Bellzahl (http://de.wikipedia.org/wiki/Bellzahl) könnenSie kontrollieren, ob die von Ihnen gefundenen Anzahlen der Partitionenrichtig sind.

26. Auf N0 sei für k, l ∈N0 die Relation (14(1)) „∼” definiert durch k ∼ l , wennk·l > 0 ist. Beweisen Sie, dass „∼” symmetrisch (14(3)) und transitiv (14(3)),aber nicht reflexiv (14(3)) ist.

27. Ist die Relation „∼” auf N, definiert durch a ∼ b, wenn ein n ∈N0 existiertmit a = b

2n oder b = a2n , eine Äquivalenzrelation (14(3)) aufN? Beweisen Sie

Ihre Antwort.

98


28. Beweisen Sie, dass die Mengen A := {(x, y) ∈ R2 | x < 0}, B := {(x, y) ∈ R2 |x = 0} und C := {(x, y) ∈ R2 | x > 0} eine Partition (13(11)) von R2 bilden.Geben Sie die zugehörige Äquivalenzrelation (14(3)) „∼” und unendlichviele paarweise verschiedene Vertretersysteme (14(3)) von „∼” an.

29. Seien X 6= ; und Y Mengen und f : X → Y eine Abbildung. Ordnen Sie fol-genden Aussagen die Adjektive injektiv (15(9)), surjektiv (15(9)), konstant(15(8)) oder trivial zu.

(a) ∀y ∈ Y ∃x ∈ X : f (x) = y .

(b) ∀x ∈ X ∃y ∈ Y : f (x) = y .

(c) ∃x1 ∈ X ∃x2 ∈ X : f (x1) = f (x2) =⇒ x1 = x2.

(d) ∃y ∈ Y ∀x ∈ X : f (x) = y .

30. Beweisen Sie, dass die Abbildung f :N→N, definiert durch

f (n) := (2n −1)n(2n +1)

3,

wohldefiniert (15(7)) ist. Ist f injektiv (15(9))? Ist f surjektiv (15(9))?

Hinweis: Betrachten Sie im Beweis der Wohldefiniertheit von f für n ∈ Ndie Menge {2n −1,2n,2n +1}, und verwenden Sie die zweite Übungsauf-gabe (9.e) und das Lemma von Euklid (10(7)).

31. Seien M eine endliche Menge und f : M → M eine Abbildung. BeweisenSie die Gültigkeit der Äquivalenzen

1. f ist bijektiv (15(9)) ⇐⇒ 2. f ist injektiv (15(9)) ⇐⇒ 3. f ist surjektiv(15(9)).

Hinweis: Es genügt z. B. die Aussagen 1. =⇒ 2. =⇒ 3. =⇒ 1. zu beweisen.Warum?

24.c Übungsblatt 3

32. Geben Sie jeweils mit Beweis eine Menge M und eine Abbildung f : M →M an, die

(a) injektiv (15(9)) und nicht surjektiv (15(9)) ist,

(b) surjektiv (15(9)) und nicht injektiv (15(9)) ist.

Hinweis zu (a): Betrachten Sie die Zuordnung in Hilberts „Hotel”(z. B. auf http://de.wikipedia.org/wiki/Hilberts_Hotel).

33. Es seien f : X → Y eine Abbildung und A,B ⊆ X . Beweisen Sie:

1. f (A∪B) = f (A)∪ f (B) 2. f (A∩B) ⊆ f (A)∩ f (B)

99


3. f (A) \ f (B) ⊆ f (A \ B).

Zeigen Sie jeweils durch ein Beispiel, dass in 2. und in 3. im allgemeinennicht die Gleichheit gilt.

Hinweis: Verwenden Sie die Definitionen 13(4) und 15(5).

34. Beweisen Sie, dass die Abbildung ϕ : Z→ Z mit ϕ(k) := k + (−1)k bijektiv(15(9)) ist, und geben Sie die zu ϕ inverse Abbildung (15(13)) an.

Hinweis: Betrachten Sie die Werte ϕ(k) für k ∈ N4, stellen Sie dann eineVermutung über die zu ϕ inverse Abbildung auf, und verwenden Sie Satz15(24) 3..

35. Seien X und Y Mengen mit Y 6= ;. Sei f : X → Y eine surjektive (15(9))Abbildung. Beweisen Sie, dass durch

X y := f −1[y] für y ∈ Y

eine Partition (13(11)) X y ⊆ X , y ∈ Y , von X gegeben ist.

36. Beweisen Sie: Die Verknüpfung (15(29)) ∗ : P (M)×P (M) → P (M) mit∗((A,B)) := A\B ist nicht assoziativ (15(29)) und nicht kommutativ (15(29)).

37. Beweisen Sie, dass für m ∈ N die obigen Abbildungen − : Zm ×Zm → Zm

und · :Zm ×Zm →Zm (16(4)) wohldefiniert sind.

38. Seien n ∈N0 und M eine Menge mit |M | = n. Wie viele Relationen (14(1))gibt es auf M?

39. Beweisen Sie für jedes n ∈N0(2n

2

)= 2 ·

(n

2

)+n2 und

n∑k=0

k ·(

n

k

)= n ·2n−1.

Hinweis: Verwenden Sie Definition (17(8)). Beweisen Sie die erste Identitätnicht durch vollständige Induktion, sondern direkt.

40. Beweisen Sie für alle n ∈N0 und m ∈N\ {1}

mn = (m −1)n ·n∑

k=0

(n

k

)· (m −1)−k .

Hinweis: Verwenden Sie den Binomischen Satz 17(19).

41. Für welche a,b ∈R ist sowohl

c :=a+b

a + a−bb

1a + 1

b

100


als auch c−1 definiert? Vereinfachen Sie für solche a,b ∈R c−1 soweit wiemöglich.

42. Bestimmen Sie für a,b ∈R

L :={

x ∈R\ {a,b}∣∣∣ x +a

x −b+ x +b

x −a≤ 0

}.


Für c,d ∈R gilt c ·d < 0 ⇐⇒ (c < 0∧d > 0)∨ (c > 0∧d < 0).

43. Beweisen Sie: Sind a,b ∈Rmit ab = 0 so folgt a = 0 oder b = 0.

Hinweis: Wenn a = 0 ist, gilt die Behauptung. Wenn diese Bemerkung inIhrem Beweis enthalten ist, können Sie also a 6= 0 annehmen.

44. Beweisen Sie die Eindeutigkeit von 0 ∈ R, −a ∈ R für a ∈ R und a−1 ∈ R füra ∈R\ {0} in den Axiomen (A5), (A7) und (A8) der reellen Zahlen.

45. Beweisen Sie für n ∈ N0 und x ∈ R mit x ≥ −1 die Bernoullische Unglei-chung

(1+x)n ≥ 1+nx.

24.d Übungsblatt 4

46. Beweisen Sie für a,b ∈Rmit a > 0 und b > 0 die Ungleichungen

21a + 1

b

≤p

ab ≤ a +b

2

zwischen dem harmonischen, dem geometrischen und dem arithmetischenMittelwert von a und b. Für welche Werte von a und b gilt jeweils statt „É”die Gleichheit „=”?

47. Schreiben Sie die Menge

M := {x ∈R | x É 5 ∧ x2 +2 · x −2 ·p2 ≥p2 · x}

als Vereinigung von zwei Intervallen (18(5)).


Für a,b ∈R gilt a ·b ≥ 0 ⇐⇒ (a ≥ 0∧b ≥ 0)∨ (a É 0∧b É 0).

48. Sei c ∈R. Finden Sie a,b ∈R, so dass die Gleichung

(x2 −ax y +by2)(x2 +ax y +by2) = x4 +4c2 y4

für alle x, y ∈ R erfüllt ist. Welche bemerkenswerte Gleichung erhalten Siefür y := c := 1?

101



A :={n2 +n

n2 +1

∣∣∣n ∈N}

und B :={x|x = (−1

2 )m − 3n mit m,n ∈N}

nach oben und nach unten beschränkt (18(7)) sind. Bestimmen Sie oh-ne Beweise das Infimum (18(7)) und das Supremum (18(7)) und ggf. dasMinimum (18(7)) und das Maximum (18(7)) von A und B .

50. Seien ; 6= A ⊆ R und ; 6= B ⊆ R nach oben beschränkt (18(7)). BeweisenSie, dass für die Summe A +B := {a +b|a ∈ A, b ∈ B} A +B 6= ; gilt, unddass A+B nach oben beschränkt ist mit sup(A+B) = sup(A)+sup(B) (18(7)5.).

Hinweis: Beginnen Sie den Beweis der behaupteten Gleichheit mit denUngleichungen

a +b É sup(A+B) und a +b É sup(A)+ sup(B) für a ∈ A, b ∈ B.

51. Die Folgen (19(1)) (an)n∈N und (bn)n∈N seien rekursiv definiert durch

a1 := 5 und an+1 := an +9 für n ∈Nund

b1 := 2 und bn+1 := b2n für n ∈N.

Geben Sie eine „Formel” für an und für bn für jedes n ∈N an, und bewei-sen Sie deren Gültigkeit durch vollständige Induktion.

Hinweis: Für jedes n ∈ N dürfen in den „Formeln” an = ? und bn = ? aufder rechten Seite nur reelle Zahlen, auch n, vorkommen, nicht aber Fol-genglieder der Folgen (an)n∈N bzw. (bn)n∈N.

52. Bestimmen Sie mit Beweis⋃k∈N

[−2+ 1

k,5− 1

k

].


53. Bestimmen Sie alle x ∈Rmit |3x −6| ≤ |x +1| ((19(3))).

Hinweis: Verwenden Sie Definition (19(3)). Betrachten Sie kombinierte Fall-unterscheidungen. Es sind vier Fälle, z. B. x ≥ 2 ⇐⇒ |3x −6| = 3x −6 kom-biniert mit x ≥−1 ⇐⇒ |x +1| = x +1.

54. Beweisen Sie, dass die Abbildung ϕ : R→ ]−1,1[ mit ϕ(x) := x1+|x| wohl-

definiert (15(7)) und bijektiv (15(9)) ist, und geben Sie die zu ϕ inverseAbbildung (15(13)) an.

Hinweis: Lösen Sie für die Berechnung der zu ϕ inversen Abbildung füry ∈ ]−1,1[ die Gleichungϕ(x) = y mit x ∈Rdurch eine Fallunterscheidungnach x auf. Fassen Sie dann beide Fälle zusammen.

102



A :={ |x|

1+|x|∣∣∣x ∈R

}nach oben und nach unten beschränkt (18(7)) ist. Bestimmen Sie ohneBeweis das Infimum (18(7)) und das Supremum (18(7)) und ggf. das Mini-mum (18(7)) und das Maximum (18(7)) von A.

56. Geben Sie Folgen (an)n∈N und (bn)n∈N an, so dass

(an)n∈N konvergent (19(11)) und (bn)n∈N divergent ist mit a2n = b2n füralle n ∈N.

57. Geben Sie eine nicht konvergente Folge (19(11)) (an)n∈N und ein a ∈R an,so dass die folgende Bedingung erfüllt ist: Es gibt ein ε> 0, so dass für allen ∈N |an −a| < ε ist.

58. Geben Sie Folgen (an)n∈N und (bn)n∈N mit den folgenden Eigenschaftenan.

(a) (an)n∈N ist konvergent (19(11)), (bn)n∈N ist divergent (19(11)) und (anbn)n∈Nist konvergent.

(b) (an)n∈N ist konvergent, (bn)n∈N ist divergent und (anbn)n∈N ist diver-gent.

(c) (an)n∈N und (bn)n∈N sind divergent und (anbn)n∈N ist konvergent.

59. Sei (an)n∈N eine beschränkte Folge (19(17)) und (bn)n∈N eine Nullfolge(19(8)). Beweisen Sie, dass (anbn)n∈N eine Nullfolge ist.

60. Sei

an := 1

n· 1+ (−1)n+1

2+ 1+ (−1)n

2 ·pn

für n ∈N. Beweisen Sie, dass (an)n∈N eine Nullfolge (19(8)) ist.

61. Untersuchen Sie die Folgen (an)n∈N,...,(en)n∈N auf Konvergenz (19(8)) undbestimmen Sie ggf. den Grenzwert (19(8)).

an :=pn +1−p

n bn := 1

n2

n∑i=1

i cn :=n∑

k=1

1

4k2 −1

dn := (−6)n +3n

7n +5n en := n2 +2

3 · (n +1)2

für n ∈N.

Hinweis: Verwenden Sie bei mehreren Aufgaben Satz 19(20).

Hinweis zu (an)n∈N: Für alle n ∈N gilt

103


an = an ·p

n +1+pnp

n +1+pn

.

Hinweis zu (bn)n∈N: Verwenden Sie die Gaußsche Summenformel (11(5)).

Hinweis zu (cn)n∈N: Beweisen Sie zunächst für jedes k ∈N

1

4k2 −1= 1

2·( 1

2k −1− 1

2k +1

).

62. Die Folge (an)n∈N sei rekursiv definiert durch a1 := 14 und an+1 := a2

n + 14

für jedes n ∈N.

(a) Beweisen Sie 0 É an É 12 für jedes n ∈N.

(b) Beweisen Sie, dass die Folge (an)n∈N monoton wachsend und kon-vergent ist.

(c) Berechnen Sie limn→∞an .

Hinweis zu c): Sie können ohne Beweis limn→∞an = lim

n→∞an+1 verwenden.

63. Ist die Folge (an)n∈N mitan := 2((−1)n ) + 2

n

für jedes n ∈N konvergent?

Hinweis: Diese Frage können Sie mit den Sätzen 19(14) 2. und 19(20) 1.beantworten.

104

25 WEITERE ÜBUNGSAUFGABEN FÜR DIE HÖRSAALÜBUNGEN 105

25 Weitere Übungsaufgaben für die Hörsaalübungen

Der unter jeder Aufgabe stehende Dateiname gibt die Quelle der Aufgabe an.Diese Dateien enthalten auch die Lösungen, und werden etwa zwei Tage vordem Ende des Vorkurses allen Teilnehmern zur Verfügung gestellt.

1. Beweisen Sie für jedes n ∈N0: n3 +5n ist durch 6 teilbar.

Hinweis: Sie können diese Aussage durch vollständige Induktion oder we-gen n3 +5n = n3 −n +6n für jedes n ∈N0 mit der zweiten Übungsaufgabe9.e und mit Satz 9(10) beweisen.(1.pdf A 1)

2. Ist die Folge (an)n∈N mit

an := 3n3 −4n +p3

15n3 +7n2 − 2n

für n ∈N konvergent (19(8))? Berechnen Sie ggf. den Grenzwert (19(8)) von(an)n∈N.

Hinweis: Verwenden Sie Satz 19(20) und studieren Sie Beispiel 19(22).(2.pdf A Rechenteil 3b)

3. Beweisen Sie für alle a,b ∈Rmit a ≥ 0,b ≥ 0 und für alle n ∈Nnp

a +b É np

a + npb.

Hinweis: Sie können ohne Beweis verwenden, dass die behauptete Unglei-chung äquivalent zu der Ungleichung

a +b É ( np

a + npb)n

ist. Verwenden Sie dann den Binomischen Satz 17(19).(3.pdf A 5(1))

4. Berechnen Sie

limn→∞

n∑k=1

1

k · (k +1).

Hinweis: Beweisen Sie

1

k · (k +1)= 1

k− 1

k +1

105


für jedes k ∈N und berechnen Sie dann zunächst

n∑k=1

1

k · (k +1).

(4.pdf A 3b)

5. Beweisen Sie durch vollständige Induktion für jedes c ∈R\{1} und für jedesn ∈N0

n∑k=1

k · ck = n · cn+1

c −1− cn+1 − c

(c −1)2 .

(5.pdf A 4)

6. Berechnen Sie

limn→∞

(n +2)2 − (n +1)2

n.

Hinweis: Verwenden Sie Satz 19(20).(6.pdf A 3a)

7. Berechnen Sie für jedes n ∈Nmit n ≥ 2

n∑k=2

1(k2

) .

Hinweis: Beweisen Sie zunächst

1(k2

) = 2·( 1

k −1− 1

k

)für jedes k ∈Nmit k ≥ 2.(7.pdf A 4a)

8. Ist die Menge

M :={

x ∈R | x =(

n

k

)für n,k ∈Nmit

n

2É k É n

}beschränkt (18(7))? Bestimmen Sie im Fall der Existenz min M , inf M , max Mund sup M (18(7)).

Hinweis: Betrachten Sie insbesondere für n ≥ 2 k := n −1.(8.pdf A 5b)

9. Bestimmen Sie das Supremum (18(7)) der Menge

M :={

x ∈R | x = (−1)n · (2− 1n ) mit n ∈N

}und ggf. das Maximum (18(7)) von M .(9.pdf A 3a)

106


10. Untersuchen Sie die folgenden Mengen M1 und M2 auf die Existenz vonMinimum (18(7)), Infimum (18(7)), Maximum (18(7)) und Supremum (18(7)),und bestimmen Sie ggf. diese Werte.

M1 := {x ∈Q | x2 < 9} und M2 := {x ∈R | x2 +x +1 ≥ 0}.

(10.pdf A 2)

11. Untersuchen Sie die Folge (an)n∈N mit

an :=n∑

k=1

1

n2 +k

für n ∈ N auf Konvergenz (19(11)) und berechnen Sie ggf. den Grenzwert(19(8)) dieser Folge.Hinweis: Beweisen Sie für jedes n ∈N und für alle k = 1, ...,n

1

n2 +kÉ 1

n2 +1,

folgern Sie für jedes n ∈N

0 É an É n · 1

n2 +1,

und verwenden Sie dann das Sandwich-Lemma (19(23)).(11.pdf A 4a)

12. Beweisen Sie für jedes n ∈Nn∑

k=1k4 É n5.

Hinweis: Beweisen Sie diese Aussage nicht durch vollständige Induktion,sondern direkt als Folgerung aus k É n für k = 1, ...,n.(12.pdf A 1a)

13. Berechnen Sien∑

k=1k · (k +1).

Hinweis: Verwenden Sie Hilfssatz 11(2), die Gaußsche Summenformel (11(5))und eine Übungsaufgabe (3).(13.pdf A 1b)

14. Beweisen Sie durch vollständige Induktion für jedes n ∈N0

n∑k=1

(−1)k k2 = (−1)n

(n +1

2

).

(14.pdf A 1)

107


15. Seien (bn)n∈N eine Folge, (an)n∈N eine konvergente (19(8)) Folge und a ∈Rmit lim

n→∞an = a. Beweisen Sie:

(a) Ist limn→∞(an−bn) = 0, so ist (bn)n∈N konvergent (19(8)) mit lim

n→∞bn = a.

(b) Gibt es ein n0 ∈Nmit an = bn für alle n ∈Nmit n ≥ n0, so ist (bn)n∈Nkonvergent mit lim

n→∞bn = a.

Hinweis: (a) Für alle n ∈N gilt bn = an − (an −bn). Verwenden Sie nun Satz19(20) 3.(b) Studieren Sie die relevanten Sätze und Hilfssätze im Skript.

(15.pdf A 3)

16. Sei S die Menge aller Lehramtsstudenten im ersten Semester. Sei L ⊆ S dieTeilmenge der zukünftigen Lehrer. Sei A die Aussage

A :⇐⇒ „Alle Lehramtsstudenten werden Lehrer.”

(a) Formulieren Sie A mit Quantoren (12(4)).

(b) Negieren Sie A in Worten und mit Quantoren.

(16.pdf A 1)

17. Lösen Sie die folgenden Aufgaben.

(a) Bestimmen Sie alle n ∈Nmit nn > n!.

(b) Beweisen Sie für alle n ∈N2n∑j=1

(−1) j

j=−

2n∑j=n+1

1

j.

Hinweis: (a) Ein direkter Beweis ist möglich. Bei einem Beweis durch voll-ständige Induktion müssen Sie den Induktionsanfang geeignet wählen.(b) Beweisen Sie die Behauptung durch vollständige Induktion.(17.pdf A 1)

18. Sei x ∈Rmit 0 < x É 1 und n ∈N. Beweisen Sie die folgenden Aussagen.

(a)1−x

1+ (n −1)x< 1

1+nx.

(b)(1−x)n < (1+nx)−1.

108


Hinweis: (a) Multiplikation der behaupteten Ungleichung mit einer posi-tiven reellen Zahl ist eine Äquivalenzumformung.(b) Diese Aussage können Sie unter Verwendung von (a) durch vollständi-ge Induktion beweisen.(18.pdf A 1)

19. Beweisen Sie durch vollständige Induktion für alle n ∈N0(2n

n

)≥ 2n .

(19.pdf A 1)

20. Lösen Sie die folgenden Aufgaben.

(a) Beweisen Sie für alle a,b,c,d ∈Rmit b 6= 0 und d 6= 0

a

b· c

d= ac

bd.

Führen Sie im Beweis in jeder Zeile nur jeweils eine Umformung aus,und geben Sie das verwendete Axiom an.

(b) Beweisen Sie für alle n ∈N durch vollständige Induktion

n

6+ n2

2+ n3

3∈N.

(20.pdf A 2)

21. Entscheiden Sie für die Folge (an)n∈N mit

an := (3−n)3

3n3 −1

für n ∈ N, ob sie (a) beschränkt (18(7)) und (b) konvergent (19(8)) oderdivergent (19(11)) ist. Bestimmen Sie ggf. den Grenzwert (19(8)).

Hinweis: Beachten Sie im Fall der Konvergenz von (an)n∈N Satz 19(18).(21.pdf A 3a)

22. Bestimmen Sie alle x ∈Rmit

|x −1| É |3x −6|.

Hinweis: Verwenden Sie Definition (19(3)). Betrachten Sie kombinierte Fall-unterscheidungen. Es sind vier Fälle, z. B. x ≥ 2 ⇐⇒ |3x −6| = 3x −6 kom-biniert mit x ≥ 1 ⇐⇒ |x −1| = x −1.(22.pdf A 3)

109


23. Es sei ; 6= M ⊆ R nach oben beschränkt (18(7)). Sei b := sup M (18(7)).Beweisen Sie: Es gibt eine konvergente Folge (an)n∈N in M mit lim

n→∞an = b.

Hinweis: Verwenden Sie Satz 19(29) 1..(23.pdf A 6)

24. Sei (an)n∈N eine Folge.

(a) Geben Sie die Definition der Beschränktheit (19(17)) von (an)n∈N an.

(b) Beweisen Sie: Ist (an)n∈N nicht beschränkt (19(17)), so ist (an)n∈Nnicht konvergent.

Hinweis: (b) Studieren Sie die relevanten Sätze und Hilfssätze im Skript.(24.pdf A 7)

25. Sei n ∈N und seien xk ∈Rmit 0 < xk < 1 für k = 1, ...,n. Beweisen Sie durchvollständige Induktion

n∏k=1

(1−xk ) ≥ 1−n∑

k=1xk .

(25.pdf A 9)

26. Die Abbildung f : [0,∞) →R sei definiert durch f (x) := x3+1. Ist f injektiv(15(9))? Ist f surjektiv (15(9))? Beweisen Sie Ihre Antworten.(26.pdf A B1)

27. Für x, y ∈R sei die Relation (14(1)) „∼” auf R definiert durch

x ∼ y :⇐⇒∃q ∈Q : x = q + y.

Beweisen Sie, dass „∼” eine Äquivalenzrelation (14(3)) auf R mit minde-stens zwei Äquivalenzklassen (14(3)) ist.(27.pdf A 3)

28. Seien f :R→R, g :R→R und h :R→R Abbildungen.

(a) Beweisen Sie (g +h)◦ f = g ◦ f +h ◦ f .

(b) Beweisen Sie, dass f ◦ (g +h) = f ◦g + f ◦h im allgemeinen nicht gilt.

Hinweis: Beachten Sie in (a) und in (b) Hilfssatz 15(3) und Definition 15(16).(28.pdf A 5)

29. Finden Sie den Fehler in dem folgenden „Beweis” der Aussage ∀n ∈ N0 :−n = n.„Beweis”: Für n = 0 ist die Aussage wahr. Ist die Aussage für n ∈ N0 wahr,so folgt

−(n +1) = −n

n· (n +1) = n

n· (n +1) = 1 · (n +1) = n +1.

110


Also ist die Aussage durch vollständige Induktion bewiesen.(29.pdf A 7)

30. Beweisen Sie für alle k ∈N0

k

(k +1)!= 1

k !− 1

(k +1)!,

und berechnen Sie

limn→∞

n∑k=0

k

(k +1)!.

(30.pdf A 8b)

31. Seien a ∈Rmit 0 É a É 1 und n ∈N0. Beweisen Sie

(1+a)n É 1+ (2n −1)a.

Hinweis: Sie können diese Behauptung durch vollständige Induktion odermit dem Binomischen Satz 17(19) beweisen.(31.pdf A 1)

32. Sei (an)n∈N eine konvergente Folge, und seien a,b ∈Rmit a 6= b und limn→∞an =

a. Beweisen Sie die Aussage

∃n0 ∈N ∀n ≥ n0 : an 6= b.

Hinweis: Verwenden Sie für ε := |a −b| > 0 Definition 19(8) 1..(32.pdf A 2)

33. Beweisen Sie durch vollständige Induktion für alle n ∈Nn∑

k=1

1pkÉ 2

pn −1.

(33.pdf A 1c)

34. Sei A die Aussage A :⇐⇒∀x ∈R ∃a ∈R : (a 6= x ∧ (∀b ∈R : ab 6= 1)).

(a) Formulieren Sie A in Worten.

(b) Formulieren Sie ¬A mit Quantoren (12(4)).

(c) Beweisen Sie A oder ¬A.

(34.pdf A 1)

35. Untersuchen Sie die Folge (an)n∈N mit

an :=n∑

k=1

n4

4n5 +k2

111


für alle n ∈N auf Konvergenz (19(11)).

Hinweis: Beweisen Sie für alle n ∈N und für alle k = 1, ...,n

n4

4n5 +n2 É n4

4n5 +k2 É n4

4n5 ,

folgern Sie daraus für alle n ∈N

n · n4

4n5 +n2 É an É n · n4

4n5 ,

und verwenden Sie dann das Sandwich-Lemma (19(23)).(35.pdf A 5)

36. Für a,b ∈Rmit 0 < a < b seien a1 := a, b1 := b, und für jedes n ∈N seien

an+1 :=√

an ·bn und bn+1 := an +bn

2.

Beweisen Sie die folgenden Aussagen.

(a) Für jedes n ∈N gilt 0 < an < bn .

(b) Die Folge (an)n∈N ist streng monoton wachsend (19(27)).

(c) Die Folge (bn)n∈N ist streng monoton fallend (19(27)).

Hinweis: Sie können Aussage (a) durch vollständige Induktion beweisen,und dann die Aussagen (b) und (c) aus (a) folgern.(36.pdf A 3)

37. Bestimmen Sie für die folgenden Folgen jeweils alle Häufungspunkte (19(35)),und geben Sie Teilfolgen (19(32)) an, die gegen diese Häufungspunkte kon-vergieren.

(a) (an)n∈N mit an := (−1)n + 1

n2 +1für n ∈N.

(b) (bn)n∈N mit bn := min{(−1)n +n,1000} für n ∈N.

(c) (cn)n∈N mit cn := (−1)n(n+1)

2 für n ∈N.

(37.pdf A 5)

112

Documents

Vorkurs Skript