Mengen, Relationen und Funktionen

Die Sprache des Kurses

Die nächste Lektion definiert die natürlichen Zahlen mithilfe einer Funktion, des Nachfolgers, die injektiv ist und die $1$ nicht erreicht. Die nächste Einheit konstruiert die ganzen und die rationalen Zahlen als Klassen einer Äquivalenzrelation; die Lektion über Kombinatorik definiert die Anzahl der Elemente mithilfe von Bijektionen; die Ordnung der natürlichen Zahlen ist eine Ordnungsrelation; und die dritte Einheit verkettet und invertiert reelle Funktionen. Alle diese Wörter gehören zu einer einzigen Sprache, die man festlegen sollte, bevor man sie verwendet, zusammen mit den ersten Sätzen, auf die sich der Kurs später berufen wird.

Es ist angebracht zu sagen, was vorweggenommen wird. Die Beispiele verwenden kleine natürliche Zahlen mit ihrer Ordnung, ihrer Addition, ihrer Multiplikation, der Teilbarkeit und dem Rest einer Division, so wie man sie in der Schule lernt. Die nächste Lektion definiert die natürlichen Zahlen durch die Peano-Axiome, und die Lektionen der Einheit definieren diese Operationen und beweisen ihre Eigenschaften, ohne irgendein Beispiel aus dieser Lektion zu verwenden, sodass kein Zirkel entsteht. Kein Satz dieser Lektion hängt von den Beispielen ab: Die Zahlen dienen nur dazu, die Sätze in Aktion zu sehen.

Was vorausgesetzt wird

Eine Menge ist eine Zusammenfassung von Objekten, ihren Elementen; man schreibt $a \in A$, um zu sagen, dass $a$ zu $A$ gehört, und $a \notin A$, um es zu verneinen. Menge und Elementbeziehung werden nicht definiert: Sie sind Grundbegriffe, wie die $1$ und der Nachfolger in der Arithmetik. Allerdings definiert nicht jede Eigenschaft eine Menge. Gäbe es die Menge $R$ aller Mengen, die sich nicht selbst als Element enthalten, so hätte die Frage, ob $R$ zu $R$ gehört, keine Antwort, denn nach der Definition von $R$ hätte man $R \in R \leftrightarrow R \notin R$. Dieser Widerspruch, den Russell 1901 entdeckte, zwingt dazu, die Bildung von Mengen einzuschränken: Eine Eigenschaft wählt nur Elemente einer schon gegebenen Menge aus.

Vorausgesetzte Tatsache (Regeln der naiven Mengenlehre). Ohne Beweis vorausgesetzt werden die Regeln der naiven Mengenlehre, die diese Lektion verwendet: Zwei Mengen mit denselben Elementen sind gleich; aus einer gegebenen Menge $A$ und einer Eigenschaft $P$ bildet man die Menge $\{ x \in A : P(x) \}$ der Elemente von $A$, die sie erfüllen; und es existieren die leere Menge, die Menge $\{a, b\}$, deren einzige Elemente $a$ und $b$ sind, die Vereinigung der Elemente einer Menge von Mengen und die Menge der Teilmengen einer Menge. Die Existenz einer Menge mit den Eigenschaften der Menge der natürlichen Zahlen wird in der nächsten Lektion vorausgesetzt.

Diese Regeln gehören zu den Axiomen von Zermelo und Fraenkel, deren Untersuchung Sache der Mengenlehre ist und über diesen Kurs hinausgeht; deshalb werden sie vorausgesetzt, und sie werden ausdrücklich genannt, damit man genau weiß, was verwendet wird.

Logik der Quantoren

Die Beweise verknüpfen Aussagen mit den Junktoren $\neg$, $\wedge$, $\vee$, $\rightarrow$ und $\leftrightarrow$, deren Gesetze im ergänzenden Kurs Mathematische Logik I: Aussagenlogik untersucht werden, ausgehend von ihrer Sprache; hier genügt es, daran zu erinnern, dass die Implikation $p \rightarrow q$ nur dann falsch ist, wenn $p$ wahr und $q$ falsch ist, dass sie zu ihrer Kontraposition $\neg q \rightarrow \neg p$ äquivalent ist und dass die De Morganschen Gesetze eine Konjunktion oder eine Disjunktion verneinen:

Um über Mengen zu sprechen, braucht man außerdem Aussagen über alle Elemente oder über einige. Ist $P(x)$ eine Eigenschaft der Elemente von $A$, so behauptet die Aussage $(\forall x \in A)\,P(x)$, die man „für jedes $x$ aus $A$ gilt $P(x)$“ liest, dass alle Elemente von $A$ sie erfüllen; die Aussage $(\exists x \in A)\,P(x)$, „es gibt ein $x$ aus $A$, sodass $P(x)$“, behauptet, dass mindestens eines sie erfüllt; und $(\exists! x \in A)\,P(x)$ behauptet, dass genau eines sie erfüllt. Die Zeichen $\forall$ und $\exists$ heißen Quantoren, All- und Existenzquantor.

Vorausgesetzte Tatsache (Verneinung der Quantoren). Zu verneinen, dass alle Elemente eine Eigenschaft erfüllen, heißt zu behaupten, dass irgendeines sie nicht erfüllt, und zu verneinen, dass irgendeines sie erfüllt, heißt zu behaupten, dass keines sie erfüllt:

Diese Regeln, die der Prädikatenlogik erster Stufe angehören, werden vorausgesetzt; sie erweitern die De Morganschen Gesetze, denn ist $A = \{a, b\}$, so ist die Allaussage $P(a) \wedge P(b)$ und die Existenzaussage $P(a) \vee P(b)$. Die Reihenfolge der Quantoren spielt eine Rolle: Die Aussage $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ besagt, dass es zu jeder natürlichen Zahl eine größere gibt, und sie ist wahr; die Aussage $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ besagt, dass es eine natürliche Zahl gibt, die größer als alle ist, auch größer als sie selbst, und sie ist falsch.

Die logische Form einer Aussage bestimmt die Art, sie zu beweisen. Die Strategien, die diese Lektion verwendet, sind die folgenden; ihre logische Begründung wird in der Lektion über die Ableitungstechniken untersucht.

• Um $(\forall x \in A)\,P(x)$ zu beweisen, nimmt man ein beliebiges Element $x$ von $A$, ohne über es mehr vorauszusetzen als seine Zugehörigkeit zu $A$, und beweist $P(x)$.
• Um $(\exists x \in A)\,P(x)$ zu beweisen, gibt man ein konkretes Element von $A$ an, das $P$ erfüllt; um $(\forall x \in A)\,P(x)$ zu widerlegen, genügt ein Gegenbeispiel, ein Element, das sie nicht erfüllt.
• Um $p \rightarrow q$ zu beweisen, nimmt man $p$ an und folgert $q$; oder man beweist die Kontraposition $\neg q \rightarrow \neg p$; oder man nimmt $p \wedge \neg q$ an und gelangt zu einem Widerspruch.
• Um $p \leftrightarrow q$ zu beweisen, beweist man die beiden Implikationen $p \rightarrow q$ und $q \rightarrow p$.

Mengen

Elementbeziehung, Gleichheit und Inklusion

Eine Menge wird durch Aufzählung beschrieben, indem man ihre Elemente zwischen geschweiften Klammern aufzählt, wie $\{1, 2, 3\}$, oder durch Aussonderung, mithilfe einer Eigenschaft, wie $\{ n \in \mathbb{N} : n \leq 3 \}$, was dieselbe Menge ist. Die Regel der Extensionalität besagt, dass eine Menge durch ihre Elemente bestimmt ist:

Daraus folgt, dass es bei einer Beschreibung durch Aufzählung weder auf die Reihenfolge noch auf Wiederholungen ankommt: $\{1, 2, 2\}$ und $\{2, 1\}$ sind dieselbe Menge, weil sie dieselben Elemente haben. Es folgt auch, dass es nur eine Menge ohne Elemente gibt, die leere Menge $\emptyset$: Zwei Mengen ohne Elemente haben dieselben Elemente, nämlich keine.

Definition (Inklusion). Eine Menge $A$ ist in einer Menge $B$ enthalten, oder ist eine Teilmenge von $B$, wenn jedes Element von $A$ ein Element von $B$ ist:

Ist außerdem $A \neq B$, so sagt man, $A$ sei eine echte Teilmenge von $B$.

Die leere Menge ist in jeder Menge $A$ enthalten, weil die Implikation $x \in \emptyset \rightarrow x \in A$ stets ein falsches Antezedens hat und daher wahr ist. Man muss die Elementbeziehung von der Inklusion unterscheiden: $1 \in \{1, 2\}$ und $\{1\} \subseteq \{1, 2\}$ sind wahr, während $\{1\} \in \{1, 2\}$ falsch ist, weil die einzigen Elemente von $\{1, 2\}$ die Zahlen $1$ und $2$ sind und die Menge $\{1\}$ keiner von ihnen gleich ist: $\{1\} \neq 1$, weil die Menge, deren einziges Element die $1$ ist, nicht mit der $1$ verwechselt werden darf, und $\{1\} \neq 2$.

Vereinigung, Schnittmenge und Differenz

Definition (Mengenoperationen). Die Vereinigung von $A$ und $B$ ist die Menge der Elemente, die zu mindestens einer von ihnen gehören; die Schnittmenge die Menge derer, die zu beiden gehören; und die Differenz $A \setminus B$ die Menge derer, die zu $A$ und nicht zu $B$ gehören:

Ist $B \subseteq A$, so heißt die Differenz $A \setminus B$ das Komplement von $B$ bezüglich $A$. Zwei Mengen sind disjunkt, wenn ihre Schnittmenge leer ist.

Jede Operation übersetzt einen Junktor: die Vereinigung die Disjunktion, die Schnittmenge die Konjunktion, die Differenz die Konjunktion mit einer Verneinung. Wenn dem so ist, liefert jedes logische Gesetz ein Gesetz der Mengen: Vereinigung und Schnittmenge sind kommutativ, assoziativ und distributiv zueinander, weil die Junktoren es sind, und alle diese Gesetze werden wie der folgende Satz bewiesen. Das Komplement wird stets bezüglich einer Grundmenge gebildet, denn eine Menge von allem, was nicht in $B$ liegt, würde die Russellsche Antinomie wiederherstellen.

Die Potenzmenge

Die Teilmengen einer Menge bilden ihrerseits eine Menge, deren Existenz zu Beginn vorausgesetzt wurde. Die Potenzmenge von $A$, die man mit $\mathcal{P}(A)$ bezeichnet, ist die Menge, deren Elemente die Teilmengen von $A$ sind:

Zum Beispiel hat die Potenzmenge von $\{1, 2, 3\}$ acht Elemente: die leere Menge, drei Mengen mit einem Element, drei mit zwei Elementen und $\{1, 2, 3\}$ selbst.

Für jede Menge $A$ sind die leere Menge und $A$ selbst Elemente von $\mathcal{P}(A)$, und für jedes $a$ aus $A$ gilt $\{a\} \in \mathcal{P}(A)$, während $a$ im Allgemeinen kein Element von $\mathcal{P}(A)$ ist. In der Lektion über Kombinatorik wird bewiesen, dass eine Menge mit $n$ Elementen $2^n$ Teilmengen hat.

Geordnete Paare und kartesisches Produkt

Ein Punkt der Ebene, ein Bruch oder eine noch auszuführende Subtraktion werden durch zwei Objekte in einer bestimmten Reihenfolge beschrieben: Das Paar $(3, 5)$ ist nicht das Paar $(5, 3)$. Die Menge $\{3, 5\}$ eignet sich nicht, um es darzustellen, weil sie gleich $\{5, 3\}$ ist. Das Einzige, was man von einem geordneten Paar verlangt, ist seine charakteristische Eigenschaft: Zwei Paare sind genau dann gleich, wenn sie dieselbe erste und dieselbe zweite Komponente haben. Kuratowski bemerkte 1921, dass der Begriff der Menge genügt, um ein Objekt mit dieser Eigenschaft zu konstruieren.

Definition (geordnetes Paar). Das geordnete Paar mit erster Komponente $a$ und zweiter Komponente $b$ ist die Menge

Ist die charakteristische Eigenschaft bewiesen, so kann man die Konstruktion von Kuratowski vergessen: Alles, was der Kurs über Paare sagt, folgt aus ihr.

Definition (kartesisches Produkt). Das kartesische Produkt von $A$ und $B$ ist die Menge der Paare, deren erste Komponente zu $A$ und deren zweite Komponente zu $B$ gehört:

Die Schreibweise $\{ (a, b) : a \in A \wedge b \in B \}$ ist für sich genommen keine der vorausgesetzten Regeln, die nur erlauben, Elemente aus einer schon gebildeten Menge auszusondern. Allerdings existiert diese Menge: Ist $a \in A$ und $b \in B$, so sind die Mengen $\{a\}$ und $\{a, b\}$ in $A \cup B$ enthalten und daher Elemente von $\mathcal{P}(A \cup B)$; daraus folgt, dass das Paar $(a, b) = \{ \{a\}, \{a, b\} \}$ in $\mathcal{P}(A \cup B)$ enthalten ist, also ein Element von $\mathcal{P}(\mathcal{P}(A \cup B))$ ist. Also wird das kartesische Produkt durch Aussonderung innerhalb dieser Menge gebildet, die nach den vorausgesetzten Regeln existiert: $A \cup B$ ist die Vereinigung der Elemente von $\{A, B\}$, und man bildet zweimal die Potenzmenge.

Der Name erinnert an Descartes: Die Ebene der analytischen Geometrie ist $\mathbb{R} \times \mathbb{R}$. Das Produkt ist nicht kommutativ: $\{1\} \times \{2\}$ enthält nur $(1, 2)$, und $\{2\} \times \{1\}$ nur $(2, 1)$, das nach der charakteristischen Eigenschaft verschieden ist.

Relationen

Zu sagen, dass $2$ die Zahl $6$ teilt, dass $3$ kleiner als $5$ ist oder dass zwei Tage auf denselben Wochentag fallen, heißt zu behaupten, dass gewisse Paare von Objekten in Relation stehen. Wenn dem so ist, ist eine Relation durch die Paare bestimmt, die sie in Beziehung setzt, und kann als eine Menge von Paaren definiert werden.

Definition (Relation). Eine Relation von $A$ nach $B$ ist eine Teilmenge $R$ des Produkts $A \times B$; eine Relation auf $A$ ist eine Relation von $A$ nach $A$. Ist $(a, b) \in R$, so sagt man, $a$ stehe mit $b$ in der Relation $R$.

Zum Beispiel ist die Relation „kleiner oder gleich“ auf $\{1, 2, 3\}$ die Menge der Paare $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. Für häufig verwendete Relationen schreibt man ein Zeichen zwischen die Terme, wie $a \leq b$ oder $a \mid b$, statt $(a, b) \in R$. Vier Eigenschaften einer Relation auf einer Menge kehren im ganzen Kurs wieder.

Definition (Eigenschaften von Relationen). Eine Relation $R$ auf $A$ ist reflexiv, symmetrisch, antisymmetrisch oder transitiv, wenn sie jeweils die folgenden Bedingungen erfüllt.

• Sie ist reflexiv, wenn jedes Element mit sich selbst in Relation steht: $(\forall a \in A)\,((a, a) \in R)$;
• Sie ist symmetrisch, wenn die Relation von $a$ zu $b$ die von $b$ zu $a$ nach sich zieht: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$;
• Sie ist antisymmetrisch, wenn zwei in beiden Richtungen in Relation stehende Elemente gleich sind: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$;
• Sie ist transitiv, wenn die Relation von $a$ zu $b$ und die von $b$ zu $c$ die von $a$ zu $c$ nach sich ziehen: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

Im Gitter von $A \times A$ ist eine Relation eine Menge von Punkten. Sie ist reflexiv, wenn sie die ganze Diagonale enthält, die der Paare $(a, a)$; sie ist symmetrisch, wenn ihr Bild symmetrisch zur Diagonale ist; und sie ist antisymmetrisch, wenn kein Punkt außerhalb der Diagonale seinen Spiegelpunkt in der Relation hat. Antisymmetrisch bedeutet nicht „nicht symmetrisch“: Die Gleichheit ist beides, und Übungsaufgabe 1 verlangt eine Relation, die keines von beiden ist.

Äquivalenzrelationen

Die Relation „dieselbe Parität haben“ verhält sich wie eine teilweise Gleichheit: Sie identifiziert die Zahlen, die in einer Hinsicht übereinstimmen, ihrer Parität, und vergisst alles Übrige. Die drei Eigenschaften, die sie sich so verhalten lassen, erhalten einen Namen.

Definition (Äquivalenzrelation). Eine Relation auf $A$ ist eine Äquivalenzrelation, wenn sie reflexiv, symmetrisch und transitiv ist. Man schreibt dann $a \sim b$ und sagt, $a$ sei äquivalent zu $b$. Die Klasse von $a$ ist die Menge der zu $a$ äquivalenten Elemente, und jedes von ihnen ist ein Repräsentant der Klasse:

Die Menge aller Klassen heißt Quotientenmenge und wird mit $A/{\sim}$ bezeichnet.

Äquivalenzrelationen sind die Gleichheit, deren Klassen ein einziges Element haben; dieselbe Parität, mit zwei Klassen; denselben Rest bei der Division durch $3$ haben, mit drei; und auf denselben Wochentag fallen, mit sieben, was die gelöste Aufgabe 3 behandelt. Allgemein gilt: Ist $g$ eine auf $A$ definierte Funktion, so erbt die Relation $g(x) = g(y)$ von der Gleichheit die drei Eigenschaften, und die gelöste Aufgabe 5 zeigt, dass jede Äquivalenz von dieser Form ist.

Die Klassen zerlegen also die Menge in Blöcke, die sich nicht überlappen. Diese Art, eine Menge zu zerlegen, verdient eine eigene Definition.

Definition (Partition). Eine Partition einer Menge $A$ ist eine Menge von Teilmengen von $A$, Blöcke genannt, die nicht leer und paarweise disjunkt sind und deren Vereinigung $A$ ist; gleichwertig: Jedes Element von $A$ gehört zu genau einem Block.

Eine Äquivalenz auf $A$ anzugeben und eine Partition von $A$ anzugeben sind also zwei Arten, dasselbe zu sagen; die gelöste Aufgabe 4 nutzt das, um Äquivalenzen zu zählen. Die Quotientenmenge ist die Partition, als neue Menge betrachtet: Beim Übergang von $A$ zu $A/{\sim}$ verschmelzen äquivalente Elemente zu einem einzigen.

Ebenso sind in der Lektion über die rationalen Zahlen zwei Brüche $(p, q)$ und $(r, s)$ äquivalent, wenn $ps = qr$ gilt, und eine rationale Zahl ist eine Klasse; und in der Lektion über die Kongruenzen sind die Reste modulo $n$ die Klassen einer Äquivalenz zwischen ganzen Zahlen.

Ordnungsrelationen

Die Teilbarkeit aus dem vorigen Beispiel ist nicht symmetrisch, sondern antisymmetrisch: Statt Elemente zu identifizieren, ordnet sie sie. Relationen dieser Art erhalten einen eigenen Namen.

Definition (Ordnung). Eine Relation auf $A$ ist eine Ordnungsrelation oder Halbordnung, wenn sie reflexiv, antisymmetrisch und transitiv ist; man schreibt dann $a \preceq b$ und sagt, $a$ gehe $b$ voran. Die Ordnung ist eine Totalordnung, wenn je zwei Elemente vergleichbar sind, das heißt, wenn für alle $a$ und $b$ gilt: $a \preceq b$ oder $b \preceq a$.

Ordnungen sind die Relation $\leq$ zwischen natürlichen Zahlen, die nach der in der Lektion über die Grundrechenarten mit natürlichen Zahlen bewiesenen Trichotomie total ist; die Inklusion, nach dem Satz über ihre Eigenschaften, die nicht total ist, weil $\{1\}$ und $\{2\}$ nicht vergleichbar sind; und die Teilbarkeit zwischen natürlichen Zahlen, deren Antisymmetrie in der Lektion über die Teilbarkeit bewiesen wird und die nicht total ist, weil weder $2 \mid 3$ noch $3 \mid 2$ gilt. Eine endliche Ordnung zeichnet man mit einem Hasse-Diagramm: ein Punkt je Element, mit $b$ höher als $a$, wenn $a$ dem Element $b$ vorangeht, und eine Strecke, wenn zwischen beiden kein anderes Element liegt; die Transitivität erlaubt es, die übrigen Strecken wegzulassen.

Definition (Schranken und extremale Elemente). Seien $\preceq$ eine Ordnung auf $A$ und $X$ eine Teilmenge von $A$. Die Schranken und die extremalen Elemente von $X$ werden wie folgt definiert.

• Ein Element $c$ von $A$ ist eine untere Schranke von $X$, wenn es allen Elementen von $X$ vorangeht, und eine obere Schranke, wenn alle Elemente von $X$ ihm vorangehen.
• Ein Minimum von $X$ ist eine untere Schranke von $X$, die zu $X$ gehört, und ein Maximum ist eine obere Schranke, die zu $X$ gehört.
• Ein Element $m$ von $X$ ist minimal, wenn ihm kein von ihm verschiedenes Element von $X$ vorangeht, und maximal, wenn es keinem von ihm verschiedenen Element von $X$ vorangeht.
• Das Infimum von $X$ ist das Maximum der Menge seiner unteren Schranken, und das Supremum ist das Minimum der Menge seiner oberen Schranken, sofern sie existieren.