Proposition 1.1: Flächeninhalt unter der Parabel

Angenommen es gibt einen Begriff eines Flächeninhalts für Bereiche in [latex]\mathbb {R}^2[/latex], der folgende Eigenschaften erfüllt:

• Der Flächeninhalt des sogenannten abgeschlossenen Rechtecks
  [latex]
  \begin{aligned}[][a,b] \times [c,d] = \left \lbrace {(x,y) \in \mathbb {R}^2} \mid {a \leq x \leq b, \ c \leq y \leq d}\right \rbrace\end{aligned}
  [/latex]

  und des sogenannten offenen Rechtecks

  [latex]
  \begin{aligned}[](a,b) \times (c,d) = \left \lbrace {(x,y) \in \mathbb {R}^2} \mid {a[/latex]

  ist gleich [latex](b-a)(d-c)[/latex], wobei [latex]a,b,c,d[/latex] reelle Zahlen sind mit [latex]a \leq b, c \leq d[/latex].

• Falls [latex]G[/latex] ein Bereich in [latex]\mathbb {R}^2[/latex] ist und [latex]F[/latex] ein in [latex]G[/latex] enthaltener Bereich ist, dann ist der Flächeninhalt von [latex]F[/latex] kleiner oder gleich dem Flächeninhalt von [latex]G[/latex].
• Für Bereiche [latex]F,G[/latex] in [latex]\mathbb {R}^2[/latex] ohne gemeinsame Punkte ist der Flächeninhalt des vereinigten Bereiches [latex]F \cup G[/latex] die Summe der Flächeninhalte von [latex]F[/latex] und [latex]G[/latex].

Dann ist der Flächeninhalt von [latex]P[/latex] wie in Gleichung (1.1) (falls überhaupt definiert) gleich [latex]\frac {1}{3}[/latex].

Applet 1.2: Abschätzung eines Flächeninhaltes

Wir verwenden jeweils bis zu 1000 Rechtecke um den Flächeninhalt von unten und von oben abzuschätzen. Im Beweis unten werden wir aber unbegrenzt viele Rechtecke verwenden und können damit den Flächeninhalt ohne jegliche Unschärfe genau bestimmen.

Lemma 1.3: Summenformel mittels Induktion

Sei [latex]n \geq 1[/latex] eine natürliche Zahl. Dann gilt
[latex]
\begin{aligned}[]\label{eq:einf-beispiel vollst. Induktion} 1^2 + 2^2 + \cdots + (n-1)^2 + n^2 = \frac {n^3}{3} + \frac {n^2}{2} + \frac {n}{6}.\end{aligned}
[/latex]

Satz: Eine Version des Archimedischen Prinzips

Wenn [latex]x\in \mathbb {R}[/latex] die Ungleichung [latex]-\frac {1}{n}\leq x \leq \frac {1}{n}[/latex] für alle natürlichen Zahlen [latex]n[/latex] erfüllt, dann ist [latex]x=0[/latex].

Bemerkung

Wie schon erwähnt, haben wir die Frage, ob es einen Flächeninhalt für Bereiche im [latex]\mathbb {R}^2[/latex] gibt, nicht beantwortet. Wir haben auch nicht genau beschrieben, was denn eigentlich Bereiche im [latex]\mathbb {R}^2[/latex] sind; wir sind aber implizit davon ausgegangen, dass Bereiche jene Teilmengen des [latex]\mathbb {R}^2[/latex] sind, denen wir einen Flächeninhalt zuordnen können. Diese grundlegenden Fragen werden zum Teil in Analysis I und II mit den Begriffen des Riemann-Integrals und der Jordan-messbaren Mengen beantwortet. Des Weiteren werden diese Fragen in grösserer Allgemeinheit in der Vorlesung der Mass- und Integrationstheorie im vierten Semester und anderen weiterführenden Vorlesungen im dritten oder vierten Jahr des Mathematikstudiums besprochen.

Übung 1.4: Logische Implikationen und Tautologien

Seien A,B zwei Aussagen.

1. Bestimmen Sie die Wahrheitstabellen zu «A[latex]\implies[/latex]B» und zu «A[latex]\iff[/latex]B» .
2. Definieren Sie die logische Operation des auschliessenden Oder «A XOR B» mittels der obigen Operationen. Die Aussage «A XOR B» soll zutreffen, wenn A oder B zutrifft, aber nicht beide zutreffen.
3. Überprüfen Sie, dass die Aussagen «A[latex]\iff[/latex]([latex]\neg[/latex]([latex]\neg[/latex]A))» und «(A[latex]\wedge[/latex]B)[latex]\iff[/latex]([latex]\neg[/latex]([latex]\neg[/latex]A[latex]\vee \neg[/latex]B))» Tautologien sind.

Übung 1.5: Ritter und Knappen

Auf der Insel der Ritter und Knappen ist jeder Einwohner entweder ein Ritter oder ein Knappe (und jeder weiss den Status von allen anderen Einwohnern). Es ist wichtig zu wissen, dass

• Ritter immer die Wahrheit sagen.
• Knappen immer lügen.

Sie werden auf Einwohner der Insel treffen und Ihre Aufgabe ist bei jedem zu entscheiden, ob er ein Ritter oder ein Knappe ist.

1. Sie treffen Johannes und Willhelm auf der Insel. Johannes sagt «Willhelm und ich sind Ritter.» Willhelm sagt «Das ist eine Lüge, Johannes ist ein Knappe!» Was sind sie?
2. Sie treffen Gildas, Ergard und Telones auf der Insel. Gildas sagt «Seien Sie vorsichtig, wir sind nicht alle drei Ritter.» Ergard sagt: «Wir sind auch nicht alle drei Knappen.» Telones sagt «Hören Sie nicht auf sie, ich bin der einzige Ritter.» Was sind sie?
3. Sie treffen Heinrich und Arthur auf der Insel. Heinrich murmelt irgend etwas Unverständliches. Arthur sagt «Er sagte, er sei ein Knappe. Das ist er sicher – vertrauen Sie ihm nicht!» Was sind sie?

Dieses Beispiel entstammt aus ^[5], wo Sie noch viele andere Rätsel dieser Art finden können.

Bemerkung: Alternative Notation

Anstelle der Symbole [latex]\forall[/latex] respektive [latex]\exists[/latex] werden teilweise auch die weniger gebräuchlichen Symbole [latex]\bigwedge[/latex] respektive [latex]\bigvee[/latex] als Synonyme verwendet. Letztere haben den Vorteil, dass sie andeuten, dass [latex]\bigwedge[/latex] ein erwachsen gewordenes [latex]\wedge[/latex] und [latex]\bigvee[/latex] ein erwachsen gewordenes [latex]\vee[/latex] darstellt. Um diesen Kommentar besser zu verstehen, nehmen wir an, dass [latex]X= \left \lbrace {x_1,x_2,x_3,\ldots ,x_n} \right \rbrace[/latex] eine endliche Menge ist, die genau die Elemente [latex]x_1,\ldots ,x_n[/latex] enthält. Dann gilt

und

Später werden wir sehen, dass die Symbole [latex]\cap ,\bigcap[/latex] für den Durchschnitt von Mengen den Symbolen [latex]\wedge ,\forall[/latex] und die Symbole [latex]\cup ,\bigcup[/latex] für die Vereinigung von Mengen den Symbolen [latex]\vee , \exists[/latex] entsprechen.

Beispiel 1.6: Nicht-vertauschbare Quantoren

Angenommen [latex]X[/latex] steht für die Menge der Studienanfänger an der ETH, [latex]Y[/latex] für die Menge der Vorlesungen für Studienanfänger. Zu [latex]x \in X[/latex] und [latex]y \in Y[/latex] sei [latex]A(x,y)[/latex] die Aussage «Student [latex]x[/latex] interessiert sich für die Vorlesung [latex]y[/latex]» . Dann ist » [latex]\forall x\in X\ \exists y \in Y: A(x,y)[/latex]» hoffentlich wahr (oder es gibt Studenten, die sich für das völlig falsche Studium entschieden haben). Die Aussage » [latex]\exists y \in Y\ \forall x\in X : A(x,y)[/latex]» ist jedoch falsch, denn es gibt sicher zwei Studienanfänger, die keine gemeinsame Vorlesung besuchen und auch komplett verschiedene Interessen haben.

Beispiel 1.7: Nicht-vertauschbare Quantoren

Sei [latex]Y=X[/latex] eine beliebige Menge. Die Aussage » [latex]\forall x\in X\ \exists y \in Y: x=y[/latex]» ist dann sicher richtig, da wir für jedes [latex]x \in X[/latex] einfach [latex]y=x[/latex] wählen können. Die Aussage » [latex]\exists y \in X\ \forall x\in X : x=y[/latex]» hingegen ist nur für sehr spezielle Mengen richtig, welche?

Wichtige Übung 1.8: Vertauschbarkeit von Quantoren

Seien [latex]X,Y[/latex] zwei Mengen und für jedes [latex]x \in X[/latex] und [latex]y\in Y[/latex] sei «[latex]A(x,y)[/latex]» eine Aussage. Überzeugen Sie sich oder noch besser eine Mitstudentin/einen Mitstudenten davon, dass

wahre Aussagen sind.

Wichtige Übung 1.9: Negation und verknüpfte Quantoren

Sei [latex]X[/latex] eine Teilmenge der reellen Zahlen [latex]\mathbb {R}[/latex]. Bilden Sie die Negation folgender Aussagen und versuchen Sie die Negation so weit wie möglich nach «rechts» zu verschieben (obwohl die Aussagen geometrische Bedeutung haben, muss man diese weder kennen noch verstehen, um die Aufgabe zu lösen):

• «[latex]\forall y \in \mathbb {R}\ \forall \varepsilon > 0\ \exists x \in X: |x-y|
• «[latex]\forall y \in X\ \exists \varepsilon >0\ \forall x \in X: |x-y|
• «[latex]\forall \varepsilon >0\ \forall x\in X\ \exists y\in X: (y \neq x) \wedge |x-y|

Hier ist «[latex]\forall \varepsilon > 0:A(\varepsilon )[/latex]» eine gebräuchliche Kurzform für «[latex]\forall \varepsilon \in \mathbb {R}: \varepsilon >0 \implies A(\varepsilon )[/latex]» oder anders ausgedrückt für «[latex]\forall \varepsilon \in \left \lbrace {x \in \mathbb {R}} \mid {x>0}\right \rbrace : A(\varepsilon )[/latex]» . Die Aussage «[latex]\exists \varepsilon > 0:A(\varepsilon )[/latex]» steht für «[latex]\exists \varepsilon \in \mathbb {R}: \varepsilon >0 \wedge A(\varepsilon )[/latex]» oder äquivalenterweise für «[latex]\exists \varepsilon \in \left \lbrace {x \in \mathbb {R}} \mid {x>0}\right \rbrace : A(\varepsilon )[/latex]» . Sie können für die Negation von «[latex]|x-y|

Übung 1.10

Formulieren Sie ein konkretes Beispiel zu obigem. In anderen Worten: finden Sie eine Aussage über Elemente einer Menge, die von genau einem Element erfüllt wird.

Übung 1.11

Zum Spass: Betrachten Sie den Satz «Everybody loves my babe, but my babe loves no one but me» (leicht adaptiert nach Louis Armstrong) vom streng logischen Standpunkt. Handelt er von einem Liebespaar?

Definition 1.12: Inklusionen

Wir sagen, dass eine Menge [latex]P[/latex] Teilmenge einer Menge [latex]Q[/latex] ist und schreiben [latex]P \subseteq Q[/latex], falls für alle [latex]x \in P[/latex] auch [latex]x \in Q[/latex] gilt (in Prädikatenlogik [latex]\forall x \in P: x\in Q[/latex]). Wir sagen, dass [latex]P[/latex] eine echte Teilmenge von [latex]Q[/latex] ist und schreiben [latex]P \subsetneq Q[/latex], falls [latex]P[/latex] eine Teilmenge von [latex]Q[/latex] ist, aber nicht gleich [latex]Q[/latex] ist. Wir schreiben [latex]P \not \subseteq Q[/latex], falls [latex]P[/latex] keine Teilmenge von [latex]Q[/latex] ist (also [latex]\neg (P \subseteq Q)[/latex] gilt).

Äquivalente Formulierungen für «[latex]P[/latex] ist eine Teilmenge von [latex]Q[/latex]» sind «[latex]P[/latex] ist in [latex]Q[/latex] enthalten» und «[latex]Q[/latex] ist eine Obermenge von [latex]P[/latex]» , was wir auch als «[latex]Q \supseteq P[/latex]» schreiben. Die Bedeutung der Aussage «[latex]Q[/latex] ist eine echte Obermenge von [latex]P[/latex]» , geschrieben [latex]Q \supsetneq P[/latex], ergibt sich nun implizit.

Übung 1.13

Seien [latex]P,Q[/latex] Mengen. Formuliere die Aussagen «[latex]P[/latex] ist eine echte Teilmenge von [latex]Q[/latex]» und «[latex]P[/latex] ist keine Teilmenge von [latex]Q[/latex]» in Prädikatenlogik.

Definition 1.14: Mengenoperationen

Seien [latex]P,Q[/latex] zwei Mengen. Der Durchschnitt [latex]P \cap Q[/latex], die Vereinigung [latex]P \cup Q[/latex], das relative Komplement [latex]P \setminus Q[/latex] und die symmetrische Differenz [latex]P {\scriptstyle \triangle } Q[/latex] sind durch

definiert. Wenn aus dem Zusammenhang klar ist, dass alle betrachteten Mengen Teilmengen einer gegebenen (Ober-) Menge [latex]X[/latex] sind, dann ist das Komplement [latex]P^c[/latex] von [latex]P[/latex] (in [latex]X[/latex]) definiert durch [latex]P^c = X \setminus P[/latex]. Dies ist alles in den Bildern 1.4 und 1.5 veranschaulicht.

Übung 1.15: Distributivgesetze

Zeigen Sie die folgenden Distributivgesetze:

1. Seien [latex]A,B,C[/latex] Aussagen. Zeigen Sie
   [latex]
   \begin{aligned}[]&(A \vee B) \wedge C \iff (A \wedge C) \vee (B \wedge C)\\ &(A \wedge B) \vee C \iff (A \vee C) \wedge (B \vee C)\end{aligned}
   [/latex]
2. Seien [latex]P,Q,R[/latex] Mengen. Zeigen Sie
   [latex]
   \begin{aligned}[]&(P \cup Q) \cap R = (P \cap R) \cup (Q \cap R)\\ &(P \cap Q) \cup R = (P \cup R) \cap (Q \cup R)\end{aligned}
   [/latex]

Können Sie auch Kommutativ- und Assoziativgesetze formulieren?

Übung 1.16: Gesetze von De Morgan

Seien [latex]P,Q[/latex] Teilmengen einer Menge [latex]X[/latex]. Zeigen Sie den folgenden Spezialfall der De Morganschen Gesetze:

Erläutern Sie Ihr Vorgehen an einem Bild im Stile von Figuren 1.4 und 1.5.

Definition 1.17: Beliebige Vereinigungen und Schnitte

Sei [latex]\mathcal {A}[/latex] eine Kollektion von Mengen. Dann definieren wir die Vereinigung resp. den Schnitt der Mengen in [latex]\mathcal {A}[/latex] als

Vergewissern Sie sich an dieser Stelle, dass diese beiden Begriffe zu Definition 1.14 kompatibel sind. Falls wir die Vereinigung nicht über alle Mengen in [latex]\mathcal {A}[/latex] nehmen wollen, sondern nur über solche, die eine gewisse Eigenschaft [latex]E(A)[/latex] erfüllen, dann schreiben wir auch

und analog für den Durchschnitt. Falls [latex]\mathcal {A} = \left \lbrace {A_1,A_2,\ldots } \right \rbrace[/latex], dann schreiben wir auch

und

Wichtige Übung 1.18: De Morgansche Gesetze

Sei [latex]\mathcal {A}[/latex] eine Kollektion von Mengen. Zeigen Sie die allgemeine Form der De Morganschen Gesetze:

Übung 1.19

Was ist die Menge

wobei [latex]n[/latex] wie in Definition 1.17 über alle natürlichen Zahlen läuft, und wie nennen wir dies?

Definition 1.20: Disjunktheit

Zwei Mengen [latex]A,B[/latex] heissen disjunkt, falls [latex]A \cap B = \left \lbrace { } \right \rbrace[/latex]. In diesem Fall wird ihre Vereinigung [latex]A \cup B[/latex] disjunkte Vereinigung genannt und auch als [latex]A \sqcup B[/latex] geschrieben. Für eine Kollektion [latex]\mathcal {A}[/latex] von Mengen, sagen wir, dass die Mengen in [latex]\mathcal {A}[/latex] paarweise disjunkt sind, falls für alle [latex]A_1,A_2 \in \mathcal {A}[/latex] mit [latex]A_1 \neq A_2[/latex] gilt [latex]A_1 \cap A_2 = \left \lbrace { } \right \rbrace[/latex]. Die Vereinigung der Mengen in [latex]\mathcal {A}[/latex] wird dann auch disjunkte Vereinigung genannt und als [latex]\bigsqcup _{A \in \mathcal {A}} A[/latex] geschrieben.

Definition 1.21: Kartesisches Produkt

Für zwei Mengen [latex]X[/latex] und [latex]Y[/latex] ist das kartesische Produkt [latex]X \times Y[/latex] die Menge aller geordneten Paare [latex](x,y)[/latex] wobei [latex]x \in X[/latex] und [latex]y \in Y[/latex]. In Symbolen,

Allgemeiner ist das kartesische Produkt von [latex]n[/latex]-Mengen [latex]X_1,X_2,\ldots ,X_n[/latex] definiert als

Weiters definieren wir [latex]X^n[/latex], für eine natürliche Zahl [latex]n[/latex], als das [latex]n[/latex]-fache kartesische Produkt von [latex]X[/latex] mit sich selbst. Das heisst, [latex]X^2 = X \times X[/latex], [latex]X^3 = X\times X \times X[/latex] und so weiter.

Beispiel 1.22: Einige kartesische Produkte

Falls [latex]X = \left \lbrace {0,1} \right \rbrace[/latex] ist, dann ist

Falls [latex]X = \left \lbrace {a,b,c,\ldots ,z} \right \rbrace[/latex] die Menge der Buchstaben im Alphabet ist, so kann man [latex]X^n[/latex] mit der Menge aller möglichen (potenziell sinnfreien) Wörter der Länge [latex]n[/latex] identifizieren. Die Menge der deutschen Wörter der Länge [latex]n[/latex] bildet eine echte Teilmenge von [latex]X^n[/latex] unter dieser Identifikation.

Übung 1.23: Digitale Uhr

Die Menge der von einer digitalen Uhr angezeigten Uhrzeiten lässt sich als kartesisches Produkt zweier Mengen auffassen. Wie?

Übung 1.24: Schnitte von Rechtecken

Seien [latex]X,Y[/latex] Mengen und [latex]A, A'[/latex] Teilmengen von [latex]X[/latex], [latex]B,B'[/latex] Teilmengen von [latex]Y[/latex]. Zeigen Sie die Formel

Überzeugen Sie sich auch davon, dass es keine ähnliche Formel für die Vereinigung gibt.

Definition 1.25: Potenzmenge

Für eine Menge [latex]X[/latex] ist die Potenzmenge [latex]\mathcal {P}(X)[/latex] durch die Menge all ihrer Teilmengen gegeben, das heisst

Übung 1.26

Bestimmen Sie [latex]\mathcal {P}(\left \lbrace {} \right \rbrace )[/latex] und [latex]\mathcal {P}(\mathcal {P}(\left \lbrace {} \right \rbrace ))[/latex].

Beispiel 1.27: Russell 1903

Sei [latex]R[/latex] die Menge aller Mengen, die sich nicht selbst enthalten, also

Stellt man nun die Frage, ob [latex]R[/latex] selbst zu [latex]R[/latex] gehören kann, so erhält man «[latex]R \in R \iff R \notin R[/latex]» . Dies kann aber nicht gelten und ist also ein Widerspruch der naiven Mengenlehre (siehe ^[7]).

Übung 1.28: Der Barber aus Sevilla

Bart, der Barber in dem Dorf Sevilla, rasiert alle Männer von Sevilla, die sich nicht selbst rasieren. Sonst rasiert Bart aber niemanden. Rasiert Bart sich selbst?

Definition 1.29: Funktionen und erste dazugehörige Begriffe

In Worten ausgedrückt ist eine Funktion [latex]f[/latex] von der Menge [latex]X[/latex] nach der Menge [latex]Y[/latex] eine Zuordnung, die jedem [latex]x \in X[/latex] ein eindeutig bestimmtes [latex]y = f(x) \in Y[/latex] zuweist. Wir schreiben [latex]f : X \to Y[/latex] für eine Funktion von [latex]X[/latex] nach [latex]Y[/latex] und sprechen manchmal auch von einer Abbildung oder einer Transformation. Zu einer Funktion [latex]f: X \to Y[/latex] wird [latex]X[/latex] der Definitionsbereich von [latex]f[/latex] und [latex]Y[/latex] der Wertebereich (oder Zielbereich) von [latex]f[/latex] genannt. Im Zusammenhang mit der Funktion [latex]f[/latex] wird ein Element [latex]x[/latex] des Definitionsbereichs auch Argument und ein von der Funktion angenommenes Element [latex]y = f(x) \in Y[/latex] für ein [latex]x \in X[/latex] auch Wert der Funktion genannt.

Zwei Funktionen [latex]f_1:~X_1~\to ~Y_1[/latex] und [latex]f_2:X_2 \to Y_2[/latex] gelten als gleich, falls [latex]X_1 = X_2[/latex], [latex]Y_1 = Y_2[/latex] und [latex]f_1(x) = f_2(x)[/latex] für alle [latex]x \in X_1[/latex] gilt. Das Bild einer Funktion [latex]f: X \to Y[/latex] ist die Menge

Falls [latex]f:X \to Y[/latex] eine Funktion und [latex]A[/latex] eine Teilmenge von [latex]X[/latex] ist, dann definieren wir die Einschränkung [latex]f|_A:A \to Y[/latex] durch [latex]f|_A(x) = f(x)[/latex] für alle [latex]x \in A[/latex]. Umgekehrt wird die Abbildung [latex]f[/latex] auch als eine Fortsetzung der Funktion [latex]f|_A[/latex] bezeichnet. Des Weiteren definieren wir das Bild der Teilmenge [latex]A[/latex] unter [latex]f[/latex] als

Beispiel 1.30: Erste Funktionen

1. Sei [latex]X[/latex] eine Menge. Die Identitätsabbildung [latex]\operatorname {id}_X: X \to X[/latex] ist die Funktion definiert durch [latex]\operatorname {id}_X(x) = x[/latex] für alle [latex]x \in X[/latex].
2. Seien [latex]X,Y[/latex] Mengen und sei [latex]y_0 \in Y[/latex]. Dann ist [latex]f:X \to Y[/latex] definiert durch [latex]f(x) = y_0[/latex] für alle [latex]x \in X[/latex] eine Funktion. Solche Funktionen werden konstante Funktionen genannt.
3. Sei [latex]A \subseteq X[/latex] eine Teilmenge und [latex]Y[/latex] eine Menge, die [latex]\{ 0,1\}[/latex] enthält. Die Funktion
   [latex]
   \begin{aligned}[]\mathds {1}_A: X &\to Y\\ \mathds {1}_A(x) &= \left \lbrace \begin{array}{cc} 0 & \text {für } x \not \in A \\ 1 & \text {für } x \in A\end{array} \right .\end{aligned}
   [/latex]

   wird die charakteristische Funktion von [latex]A[/latex] genannt. Das Bild von [latex]\mathds {1}_A[/latex] ist genau dann ganz [latex]\left \lbrace {0,1} \right \rbrace[/latex], wenn die Menge [latex]A[/latex] weder leer noch ganz [latex]X[/latex] ist (wieso?).

4. Für zwei Mengen [latex]X_1,X_2[/latex] definieren wir die Projektionen
   [latex]
   \begin{aligned}[]\pi _1: X_1 \times X_2 \to X_1\\ \pi _1\big ((x_1,x_2)\big ) = x_1\end{aligned}
   [/latex]

   und

   [latex]
   \begin{aligned}[]\pi _2: X_1 \times X_2 \to X_2\\ \pi _2\big ((x_1,x_2)\big ) = x_2.\end{aligned}
   [/latex]

   Das Bild von [latex]\pi _1[/latex] ist [latex]X_1[/latex], falls [latex]X_2[/latex] nicht leer ist, und ebenso ist [latex]\pi _2(X_1 \times X_2) = X_2[/latex], falls [latex]X_1 \neq \left \lbrace { } \right \rbrace[/latex]. Wir schreiben manchmal auch [latex]\pi _{X_1}[/latex] anstelle von [latex]\pi _1[/latex] und [latex]\pi _{X_2}[/latex] anstelle von [latex]\pi _2[/latex].

   

Definition 1.31: Drei Eigenschaften von Funktionen

Sei [latex]f: X\to Y[/latex] eine Funktion.

• Die Funktion [latex]f[/latex] heisst injektiv oder eine Injektion falls für alle [latex]x_1,x_2 \in X[/latex] gilt, dass [latex]f(x_1) = f(x_2) \implies x_1 = x_2[/latex].
• Die Funktion [latex]f[/latex] ist surjektiv, eine Surjektion oder eine Funktion von [latex]X[/latex] auf [latex]Y[/latex], falls [latex]f(X) = Y[/latex].
• Die Funktion [latex]f[/latex] heisst bijektiv, eine Bijektion oder eine eineindeutige Abbildung, falls [latex]f[/latex] surjektiv und injektiv ist.

Applet 1.32: Funktionen auf Mengen mit höchstens drei Elementen

In diesem Applet kann man verschiedene Funktionen [latex]f[/latex] von einer Menge [latex]X[/latex] mit höchstens drei Elementen nach einer Menge [latex]Y[/latex] mit höchstens drei Elementen definieren. Hierbei kommt es zu verschiedenen Eigenschaften der Funktion.

Beispiel 1.33: Ist Quadrieren bijektiv?

Ist [latex]x \mapsto x^2[/latex] injektiv, surjektiv oder bijektiv? Diese Frage macht wie oben erklärt (noch) keinen Sinn, da weder Definitionsbereich noch Wertebereich festgelegt wurden und wir diese zur Beantwortung der Frage kennen müssen. Folgende Beobachtungen bestätigen, dass die Antwort zur Frage in der Tat von der Wahl des Definitionsbereichs und des Wertebereichs abhängt:

1. Die Funktion [latex]f: \mathbb {R}_{\geq 0} \to \mathbb {R},\ x \mapsto x^2[/latex] ist injektiv, denn falls [latex]x,y[/latex] zwei nicht-negative Zahlen mit [latex]x y[/latex], dass [latex]x^2> y^2[/latex] ist. Sie ist jedoch nicht surjektiv: [latex]-1[/latex] ist nicht Element des Bildes von [latex]f[/latex], da Quadrate von reellen Zahlen niemals negativ sind.
2. Die Funktion [latex]f: \mathbb {R} \to \mathbb {R}_{\geq 0},\ x \mapsto x^2[/latex] ist surjektiv (es existiert eine Wurzel), sie ist aber nicht injektiv, denn [latex]f(1) = 1 = (-1)^2 = f(-1)[/latex].
3. Die Funktion [latex]f: \mathbb {R}_{\geq 0} \to \mathbb {R}_{\geq 0},\ x \mapsto x^2[/latex] ist bijektiv.

Wir werden diese Aussagen später noch ausführlicher beweisen.

Definition 1.34: Umkehrabbildung

Sei [latex]f: X \to Y[/latex] eine Bijektion. Die Umkehrabbildung (Inverse Abbildung oder auch kurz [latex]\pmb {f}[/latex] invers) [latex]f^{-1}: Y \to X[/latex] von [latex]f[/latex] ist die Abbildung, welche jedem [latex]y\in Y[/latex] das eindeutig bestimmte Element [latex]x \in X[/latex] mit [latex]y = f(x)[/latex] zuweist.

Definition 1.35: Verknüpfung

Angenommen [latex]f:X \to Y[/latex] und [latex]g: Y \to Z[/latex] sind Funktionen. Dann ist die Verknüpfung [latex]g \circ f: X \to Z[/latex] (gesprochen [latex]g[/latex] nach [latex]f[/latex] oder [latex]g[/latex] Ring [latex]f[/latex]) für alle [latex]x \in X[/latex] durch [latex]g\circ f(x) = g(f(x))[/latex] definiert.

Beispiel 1.36: Assoziativgesetz für Verknüpfungen

Seien [latex]f:X_1\to X_2[/latex], [latex]g:X_2 \to X_3[/latex], [latex]h:X_3 \to X_4[/latex] Funktionen. Dann können wir sowohl die Funktion [latex]h \circ (g \circ f): X_1 \to X_4[/latex] als auch die Funktion [latex](h \circ g) \circ f: X_1 \to X_4[/latex] betrachten. Glücklicherweise sind die Klammern irrelevant, denn es gilt

für alle [latex]x \in X_1[/latex]. Deswegen schreiben wir einfach [latex]h\circ g \circ f: X_1 \to X_4[/latex].

Beispiel 1.37: Verknüpfung ist nicht kommutativ

Für zwei Funktionen [latex]f:X \to Y[/latex] und [latex]g:Y \to Z[/latex] macht zwischen [latex]g \circ f[/latex] und [latex]f \circ g[/latex] im Allgemeinen nur [latex]g \circ f[/latex] Sinn, da [latex]f[/latex] nicht auf [latex]Z[/latex] definiert sein muss. Dies kann man sich mit einer Analogie aus der Informatik illustrieren. Seien zwei Programme [latex]P_1,P_2[/latex] gegeben, so dass [latex]P_1[/latex] eine Zahl als Input und einen Zeichenkette als Output hat und [latex]P_2[/latex] eine Zeichenkette als Input und eine Zeichenkette als Output hat. In diesem Fall kann man [latex]P_2[/latex] den Output von [latex]P_1[/latex] als Input übergeben; umgekehrt jedoch kann man [latex]P_1[/latex] den Output von [latex]P_2[/latex] nicht übergeben, da [latex]P_1[/latex] nur mit einer Zahl etwas anzufangen weiss.

Nimmt man nun an, dass [latex]X=Y= Z[/latex], so dass sowohl [latex]g \circ f[/latex] als auch [latex]f \circ g[/latex] Sinn machen und beide Abbildungen auf [latex]X[/latex] definiert sind, dann gilt die Gleichheit [latex]g \circ f = f \circ g[/latex] im Allgemeinen trotzdem nicht. Wir nennen ein geometrisches Beispiel. Seien [latex]X=Y=Z= \mathbb {R}^2[/latex], [latex]f[/latex] die Spiegelung um die [latex]y[/latex]-Achse und [latex]g[/latex] die Verschiebung (Translation) um [latex]1[/latex] in positiver Richtung entlang der [latex]x[/latex]-Achse. Der Ursprung [latex](0,0)[/latex] wird unter [latex]g \circ f[/latex] auf [latex](1,0)[/latex] abgebildet und unter [latex]f \circ g[/latex] auf [latex](-1,0)[/latex] abgebildet, also gilt [latex]g \circ f \neq f \circ g[/latex].

Definition 1.38: Iterationen einer Funktion

Sei [latex]f: X \to X[/latex] eine Funktion von einer Menge [latex]X[/latex] auf sich selbst. Wir definieren die Iterationen der Funktion [latex]f[/latex] durch

und rekursiv auch

für alle natürlichen Zahlen [latex]n \in \mathbb {N}[/latex]. Wir sprechen [latex]f^{\, \circ \, {n} }[/latex] auch als «[latex]f[/latex] hoch [latex]n[/latex]» aus und setzen des Weiteren [latex]f^{\, \circ \, {0} } = \operatorname {id}_X[/latex].

Übung 1.39: Beispiele und eine Eigenschaft von Iterationen

1. Sei [latex]X= \left \lbrace {a,b,c} \right \rbrace[/latex] eine Menge mit [latex]3[/latex] verschiedenen Elementen und [latex]f: X \to X[/latex] die Funktion definiert durch [latex]f(a) = b,\ f(b) = c[/latex] und [latex]f(c) = a[/latex]. Zeigen Sie, dass [latex]f[/latex] bijektiv ist. Beschreiben Sie die Umkehrabbildung und alle Iterationen von [latex]f[/latex] explizit.
2. Iterieren Sie die Funktion [latex]g:x \in \mathbb {R} \to 3x \in \mathbb {R}[/latex] und beschreiben Sie intuitiv, wie sich [latex]f^{\, \circ \, {n} }(x)[/latex] für ein [latex]x \in \mathbb {R}[/latex] und verschiedene [latex]n\in \mathbb {N}[/latex] verhält.
3. Iterieren Sie die Funktion [latex]g:x \in \mathbb {R} \to x^2 \in \mathbb {R}[/latex] und beschreiben Sie intuitiv, wie sich [latex]f^{\, \circ \, {n} }(x)[/latex] für ein [latex]x \in \mathbb {R}[/latex] und verschiedene [latex]n\in \mathbb {N}[/latex] verhält.
4. Sei [latex]X[/latex] eine Menge und [latex]f:X \to X[/latex] eine Transformation auf [latex]X[/latex]. Zeigen Sie, dass für alle [latex]m,n\in \mathbb {N}_0[/latex] gilt [latex]f^{\, \circ \, {m} } \circ f^{\, \circ \, {n} } = f^{\, \circ \, {(m+n)} }[/latex].

Beispiel 1.40: Hilbert–Hotel

Die Abbildung

ist zwar injektiv aber nicht surjektiv, denn [latex]1 \not \in f(\mathbb {N})[/latex]. Dies kann man sich zur Veranschaulichung wie folgt vorstellen: Angenommen ein Hotel (das sogenannte Hilbert Hotel) ist voll belegt und hat für jede natürliche Zahl [latex]n[/latex] ein Hotelzimmer mit der Türnummer [latex]n[/latex] (entlang eines wirklich sehr langen Ganges der Reihe nach nummeriert). Dann kann man trotzdem noch einen Gast unterbringen. Dazu muss die Rezeption bloss dem Gast im ersten Zimmer einen Brief mit folgender Botschaft aushändigen:

Daraufhin wird das erste Zimmer frei sein, wo dann der neue Gast untergebracht werden kann. Ebenso bekommen alle alten Gäste jeweils ein neues Zimmer.

Genauso gibt es auch surjektive Abbildungen [latex]\mathbb {N} \to \mathbb {N}[/latex], die nicht injektiv sind, zum Beispiel

Das Gedankenspiel von Hilberts Hotel lässt sich durchaus erweiteren. Wir verweisen dazu auf die nächste Übung und diesen Kurzfilm, der folgende Übung auflöst und erweitert.

Übung 1.41: Hilberts Bus

Wir setzen das Gedankenspiel von Hilberts Hotel fort: Stellen Sie sich vor, dass ein sehr langer, voll besetzter Bus mit Gästen vor Hilberts vollem Hotel auffährt, der für jede natürliche Zahl einen entsprechend nummerierten Sitzplatz aufweist. Wie können Sie die neuen Gäste alle im Hotel unterbringen? Welche Abbildung [latex]h:\mathbb {N} \to \mathbb {N}[/latex] können Sie verwenden, um im Hotel Platz zu beschaffen?

Lemma 1.42: Eigenschaften von Verknüpfungen

Seien [latex]f:X \to Y[/latex] und [latex]g: Y \to Z[/latex] Funktionen.

1. Falls [latex]f[/latex] und [latex]g[/latex] injektiv sind, dann ist auch [latex]g \circ f[/latex] injektiv.
2. Falls [latex]f[/latex] und [latex]g[/latex] surjektiv sind, dann ist auch [latex]g \circ f[/latex] surjektiv.
3. Falls [latex]f[/latex] und [latex]g[/latex] bijektiv sind, dann ist auch [latex]g \circ f[/latex] bijektiv und es gilt [latex](g \circ f)^{-1} = f^{-1} \circ g^{-1}[/latex].

Wichtige Übung 1.43: Weitere Eigenschaften von Verknüpfungen

Seien [latex]f: X \to Y[/latex] und [latex]g: Y \to Z[/latex] Funktionen.

1. Zeigen Sie, dass [latex]g[/latex] surjektiv ist, falls [latex]g \circ f[/latex] surjektiv ist. Überzeugen Sie sich davon, dass in diesem Fall [latex]f[/latex] nicht unbedingt surjektiv sein muss.
2. Zeigen Sie, dass [latex]f[/latex] surjektiv ist, falls [latex]g \circ f[/latex] surjektiv und [latex]g[/latex] injektiv ist.
3. Zeigen Sie, dass [latex]f[/latex] injektiv ist, falls [latex]g \circ f[/latex] injektiv ist. Überzeugen Sie sich davon, dass in diesem Fall [latex]g[/latex] nicht unbedingt injektiv sein muss.
4. Zeigen Sie, dass [latex]g[/latex] injektiv ist, falls [latex]g \circ f[/latex] injektiv ist und [latex]f[/latex] surjektiv ist.

Wichtige Übung 1.44: Bijektivität und Existenz einer Umkehrabbildung

Sei [latex]f: X \to Y[/latex] eine Funktion. Wenn [latex]f[/latex] bijektiv ist, dann gelten [latex]f^{-1}\circ f = \operatorname {id}_X[/latex] und [latex]f \circ f^{-1}= \operatorname {id}_Y[/latex], wie schon bemerkt wurde. Wir zeigen hier die «Umkehrung» : Angenommen es existiert eine Funktion [latex]g: Y \to X[/latex], so dass [latex]g \circ f = \operatorname {id}_X[/latex] und [latex]f \circ g = \operatorname {id}_Y[/latex]. Zeigen Sie unter Verwendung der letzten Übung, dass [latex]f[/latex] bijektiv ist und dass [latex]g = f^{-1}[/latex] gilt. Des Weiteren, überprüfen Sie, dass [latex]f^{-1}: Y \to X[/latex] ebenfalls bijektiv ist. Was ist die Umkehrabbildung von [latex]f^{-1}[/latex]?

Definition 1.45: Urbilder einer Funktion

Für eine Funktion [latex]f: X \to Y[/latex] und eine Teilmenge [latex]B \subseteq Y[/latex] definieren wir das Urbild [latex]f^{-1}(B)[/latex] von [latex]B[/latex] unter [latex]f[/latex] als

Wichtige Übung 1.46: Verhalten von Bildern und Urbildern unter Mengenoperationen

Gegeben sei eine Funktion [latex]f: X \to Y[/latex] und Teilmengen [latex]A,A' \subseteq X[/latex] und [latex]B,B' \subseteq Y[/latex].

1. Zeigen Sie, dass [latex]f(f^{-1}(B)) \subseteq B[/latex] gilt. Unter welcher Bedingung an [latex]f[/latex] gilt auf jeden Fall Gleichheit?
2. Zeigen Sie, dass [latex]f^{-1}(f(A)) \supseteq A[/latex] gilt. Unter welcher Bedingung an [latex]f[/latex] gilt auf jeden Fall Gleichheit?
3. Zeigen Sie die Gleichungen
   [latex]
   \begin{aligned}[]f(A \cup A') = f(A) \cup f(A'), \quad f^{-1}(B \cup B') = f^{-1}(B) \cup f^{-1}(B').\end{aligned}
   [/latex]
4. Zeigen Sie, dass [latex]f(A \cap A') \subseteq f(A) \cap f(A')[/latex] und dass Gleichheit gilt, wenn [latex]f[/latex] injektiv ist. Verifzieren Sie, dass in diesem Fall auch [latex]f(A \setminus A') = f(A) \setminus f(A')[/latex] gilt.
5. Zeigen Sie, dass [latex]f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')[/latex] und [latex]f^{-1}(Y \setminus B) = X \setminus f^{-1}(B)[/latex] gelten.
6. Verallgemeinern Sie die Regeln [latex]f^{-1}(B \cup B') = f^{-1}(B) \cup f^{-1}(B')[/latex] und [latex]f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')[/latex] für beliebige Vereinigungen resp. Schnitte.

Zusammenfassend sollten Sie sich merken, dass die Urbildoperation mit allen von uns besprochenen mengentheoretischen Operationen (unter anderem Vereinigung, Durchschnitt und Komplement) verträglich ist, während dies die Bildoperation nur für die Vereinigung oder unter gewissen Bedingungen erfüllt.

Definition 1.47: Graph einer Funktion

Sei [latex]f:X \to Y[/latex] eine Funktion. Der Graph von [latex]f[/latex] ist

Übung 1.48: Graphen und Projektion auf den Definitionsbereich

1. Sei [latex]f: X \to Y[/latex] eine Funktion. Wie in Beispiel 1.30 bezeichnen wir mit [latex]\pi _1: X\times Y \to X[/latex] die Projektion auf [latex]X[/latex], die durch [latex](x,y) \mapsto x[/latex] definiert ist und mit [latex]\pi _2: X \times Y \to Y[/latex] die Projektion auf [latex]Y[/latex]. Zeigen Sie, dass [latex]\pi _1|_{\operatorname {graph}(f)}: \operatorname {graph}(f) \to X[/latex] bijektiv ist und finden Sie die Umkehrabbildung. Beweisen Sie des Weiteren die Identität
   [latex]
   \begin{aligned}[]\pi _2 \circ (\pi _1|_{\operatorname {graph}(f)})^{-1} = f,\end{aligned}
   [/latex]

   welche erklärt, wie man aus dem Graphen einer Funktion, die Funktion zurückerhalten kann.

2. Zeigen Sie, dass eine Teilmenge [latex]\Gamma \subseteq X\times Y[/latex] genau dann ein Graph einer Funktion [latex]f:X\to Y[/latex] ist, wenn [latex]\pi _1|_\Gamma : \Gamma \to X[/latex] bijektiv ist. Verifizieren Sie auch, dass in diesem Fall [latex]f[/latex] eindeutig bestimmt ist.

Applet 1.49: Einschränkungen einer Funktion

Wir betrachten eine Funktion [latex]f:I\to \mathbb {R}[/latex], die auf einem Intervall [latex]I[/latex] in [latex]\mathbb {R}[/latex] definiert ist. Durch Einschränken der Funktion auf Teilintervalle [latex][a,b]\subseteq I[/latex] des Definitionsbereichs oder durch Einschränken des Wertebereichs auf ein Intervall [latex][c,d]\subseteq \mathbb {R}[/latex] können wir mitunter Injektivität, Surjektivität, oder auch Bijektivität der neuen Funktion erreichen.

Wichtige Übung 1.50: Eigenschaften des Graphen unter Projektion auf den Wertebereich

Sei [latex]f: X \to Y[/latex] eine Funktion.

• Zeigen Sie, dass [latex]f[/latex] injektiv ist genau dann, wenn [latex]\pi _2|_{\operatorname {graph}(f)}[/latex] injektiv ist.
• Zeigen Sie, dass [latex]f[/latex] surjektiv ist genau dann, wenn [latex]\pi _2|_{\operatorname {graph}(f)}[/latex] surjektiv ist. Intuitiv bedeutet letzteres, dass die Projektion des Graphen [latex]\operatorname {graph}(f)[/latex] auf [latex]Y[/latex] jedes Element erreicht.
• Angenommen [latex]f[/latex] ist bijektiv. Wie findet man den Graphen von [latex]f^{-1}[/latex]?

Applet 1.51: Bilder und Urbilder

Wir betrachten eine Funktion [latex]f:I\to \mathbb {R}[/latex], die auf einem Intervall [latex]I[/latex] in [latex]\mathbb {R}[/latex] definiert ist. Je nach Einstellung des Applets wird entweder das Bild [latex]f(A)[/latex] eines Teilintervalls [latex]A=[x_1,x_2]\subseteq I[/latex] oder das Urbild [latex]f^{-1}([y_1,y_2])[/latex] eines Intervalls [latex][y_1,y_2]\subseteq \mathbb {R}[/latex] dargestellt.

Beispiel 1.52: Kanonische Abbildungen

Sei [latex]X[/latex] eine Menge und [latex]A \subseteq X[/latex] eine Teilmenge. Wir betrachten injektive Abbildungen [latex]A \to X[/latex] und versuchen darunter eine kanonische auszumachen. Da [latex]A \subseteq X[/latex] eine Teilmenge ist, ist die injektive Abbildung [latex]A \to X[/latex], die man am schnellsten hinschreiben kann, die Inklusionsabbildung

am natürlichsten. Denn wir mussten dazu weder spezifische Elemente von [latex]A[/latex] noch von [latex]X[/latex] wählen. Es gibt nun aber ganz viele andere injektive Abbildungen von [latex]A[/latex] nach [latex]X[/latex]. Diese involvieren jedoch alle eine (recht zufällige) Regel.

Wir untersuchen das konkrete Beispiel [latex]A = \left \lbrace {a} \right \rbrace[/latex] und [latex]X = \left \lbrace {a,b,c} \right \rbrace[/latex]. Dann gibt es [latex]3[/latex] verschiedene injektive Abbildungen [latex]A \to X[/latex]. Nebst der Inklusionsabbildung (die [latex]a[/latex] auf [latex]a[/latex] abbildet) sind dies

• die Funktion [latex]A \to X[/latex] mit [latex]a \mapsto b[/latex] und
• die Funktion [latex]A \to X[/latex] mit [latex]a \mapsto c[/latex].

Für diese beiden Abbildungen mussten wir jedoch die Menge [latex]X[/latex] kennen und spezifische Elemente von [latex]X[/latex] (das wären [latex]b,c[/latex]) auswählen, was bei der Inklusionsabbildung nicht der Fall war. In diesem Sinne ist die Inklusionsabbildung unter den injektiven Abbildungen [latex]A \to X[/latex] die natürliche, die kanonische.

Ein weiteres interessanteres Beispiel bilden die in Beispiel 1.30 definierten kanonischen Projektionen [latex]\pi _1: X_1\times X_2 \to X_1[/latex] und [latex]\pi _2: X_1 \times X_2 \to X_2[/latex] für zwei Mengen [latex]X_1,X_2[/latex].

Definition 1.53: Relationen

Seien [latex]X[/latex] und [latex]Y[/latex] Mengen. Eine Relation auf [latex]X \times Y[/latex] ist eine Teilmenge [latex]\mathcal {R} \subseteq X \times Y[/latex]. Wir schreiben auch [latex]x \mathcal {R} y[/latex] falls [latex](x,y) \in \mathcal {R}[/latex] und verwenden oft Symbole wie [latex]

Übung 1.54: Eine bekannte Relation

In einem gewissen Sinne haben wir schon Relationen betrachtet. Seien [latex]X,Y[/latex] Mengen und sei [latex]\mathcal {G}[/latex] eine Relation auf [latex]X\times Y[/latex], die die folgende Eigenschaft erfüllt:

Wie nennen wir eine solche Relation gemeinsam mit [latex]X[/latex] und [latex]Y[/latex]?

Definition 1.55: Äquivalenzrelationen

Eine Relation [latex]\sim[/latex] auf [latex]X[/latex] ist eine Äquivalenzrelation, falls folgende drei Eigenschaften erfüllt sind:

• Reflexivität: [latex]\forall x \in X: x \sim x[/latex].
• Symmetrie: [latex]\forall x,y \in X: x \sim y \implies y \sim x[/latex].
• Transitivität: [latex]\forall x,y,z \in X:((x \sim y) \wedge (y \sim z)) \implies x \sim z[/latex].

Beispiel 1.56: Beispiele von Äquivalenzrelationen

1. Das einfachste Beispiel einer Äquivalenzrelation auf einer beliebigen Menge [latex]X[/latex] ist die Gleichheit, also die Relation [latex]\mathcal {R} = \left \lbrace {(x,y) \in X^2} \mid {x=y}\right \rbrace[/latex].
2. Ein weiteres allgemeines Beispiel ist die sogenannte triviale Relation [latex]\mathcal {R} = X^2[/latex], bezüglich der je zwei Elemente in [latex]X[/latex] äquivalent sind.
3. Wir betrachten ein Beispiel in der ebenen (euklidschen) Geometrie. Sei [latex]X[/latex] die Menge der Geraden in der Ebene. Zu zwei Geraden [latex]G_1,G_2[/latex] schreiben wir
   [latex]
   \begin{aligned}[]G_1 \sim G_2 \iff G_1 \text { und } G_2 \text { sind parallel}.\end{aligned}
   [/latex]

   Dies definiert eine Äquivalenzrelation auf [latex]X[/latex] (wieso?).

4. Äquivalenzrelationen werden in anderen Wissenschaften oder auch im Alltag häufig verwendet. Beispielsweise kann man auf der Menge aller Lebewesen eine Äquivalenzrelation definieren, in dem man zwei Lebewesen für äquivalent erklärt, wenn sie zur selben Art (oder Gattung oder Familie) gehören.

Übung 1.57: Zwei weitere Beispiele

In dieser Übungen möchten wir weitere, allgemeine Beispiele von Äquivalenzrelationen besprechen. Sei [latex]X[/latex] eine Menge.

1. (Zerquetschen einer Teilmenge) Sei [latex]A \subseteq X[/latex] eine Teilmenge. Zeigen Sie, dass die Relation gegeben durch
   [latex]
   \begin{aligned}[]x \sim _A y :\iff (x,y \in A) \vee (x = y)\end{aligned}
   [/latex]

   für [latex]x,y \in X[/latex] eine Äquivalenzrelation auf [latex]X[/latex] definiert.

2. (Äquivalenz über eine Abbildung) Sei [latex]f: X \to Y[/latex] eine Abbildung in eine weitere Menge [latex]Y[/latex]. Wir definieren eine Relation auf [latex]X[/latex] durch
   [latex]
   \begin{aligned}[]x_1 \sim _f x_2 :\iff f(x_1) = f(x_2)\end{aligned}
   [/latex]

   für alle [latex]x_1,x_2 \in X[/latex]. Zeigen Sie, dass [latex]\sim[/latex] eine Äquivalenzrelation auf [latex]X[/latex] definiert.

Übung 1.58: Ein falscher Beweis

In dieser Aufgabe behaupten wir fälschlicherweise, dass jede symmetrische und transitive Relation [latex]\sim[/latex] auf einer Menge [latex]X[/latex] auch reflexiv ist (d.h. eine Äquivalenzrelation ist). Finden Sie den Fehler in folgendem «Beweis» :

Finden Sie ein Beispiel einer Relation, die symmetrisch und transitiv, aber nicht reflexiv ist.

Übung 1.59: Beispiele allgemeiner Relationen

Finden Sie eine Relation auf den natürlichen Zahlen [latex]\mathbb {N}[/latex], die von den Eigenschaften einer Äquivalenzrelation

• nur die Symmetrie,
• nur die Transitivität,
• die Reflexivität und die Transitivität, aber nicht die Symmetrie

erfüllt.

Definition 1.60: Äquivalenzklassen und die Quotientenmenge

Sei [latex]\sim[/latex] eine Äquivalenzrelation auf einer Menge [latex]X[/latex]. Dann wird für [latex]x \in X[/latex] die Menge

die Äquivalenzklasse von [latex]x[/latex] genannt. Weiters ist

der Quotient (oder die Quotientenmenge) von [latex]X[/latex] modulo [latex]\sim[/latex]. Ein Element [latex]x \in X[/latex] wird auch Repräsentant seiner Äquivalenzklasse [latex][x]_\sim[/latex] genannt.

Definition 1.61: Partition

Sei [latex]X[/latex] eine Menge und [latex]\mathcal {P}[/latex] eine Familie von nicht-leeren, paarweise disjunkten Teilmengen von [latex]X[/latex], so dass [latex]X = \bigsqcup _{P \in \mathcal {P}}P[/latex]. Dann wird [latex]\mathcal {P}[/latex] eine Partition von [latex]X[/latex] genannt.

Proposition 1.62: Korrespondenz zwischen Äquivalenzrelationen und Partitionen

Sei [latex]X[/latex] eine Menge. Dann entsprechen Äquivalenzrelationen auf [latex]X[/latex] und Partitionen von [latex]X[/latex] einander im folgenden Sinne: Für eine gegebene Äquivalenzrelation [latex]\sim[/latex] auf [latex]X[/latex] ist die Menge

eine Partition von [latex]X[/latex]. Umgekehrt definiert für eine Partition [latex]\mathcal {P}[/latex] von [latex]X[/latex]

für [latex]x,y \in X[/latex] eine Äquivalenzrelation auf [latex]X[/latex]. Des Weiteren sind die Konstruktion der Partition aus der Äquivalenzrelation und die Konstruktion der Äquivalenzrelation aus der Partition zueinander invers: Für jede Partition [latex]\mathcal {P}[/latex] von [latex]X[/latex] gilt [latex]\mathcal {P}_{\sim _\mathcal {P}} = \mathcal {P}[/latex] und für jede Äquivalenzrelation [latex]\sim[/latex] auf [latex]X[/latex] gilt [latex]\sim _{\mathcal {P}_\sim } = \sim[/latex].

Applet 1.63: Eine Äquivalenzrelation

Links wird eine Menge [latex]X[/latex] partitioniert, was einer Äquivalenzrelation [latex]\sim[/latex] auf [latex]X[/latex] entspricht. Rechts betrachten wir die Menge der Äquivalenzklassen, also den Quotienten von [latex]X[/latex] bzüglich [latex]\sim[/latex]. Die Menge links könnte eine abstrakte Menge darstellen oder den Einheitskreis. Im letzteren Fall muss klar definiert sein, zu welcher Menge die Punkte der Kanten, bei denen der Kreis unterteilt wird, gehören. Wir haben dies im Beispiel mit Farben angedeutet.

Übung 1.64: Zerquetschen einer Teilmenge

Charakterisieren Sie die Äquivalenzklassen der in Übung 1.57 (ii) definierten Äqui­valenzrelation [latex]\sim[/latex]. Zeigen Sie, dass [latex]\mathcal {P}_\sim[/latex] (wie in obiger Proposition definiert) eine Partition ist (ohne auf die noch nicht-bewiesene Proposition zurückzugreifen) und beschreiben Sie [latex]\mathchoice {\text {\raise 0.4ex\hbox {${X}$}\big /\lower 0.4ex\hbox {${\sim }$}}} {{X}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${\sim }$} } {{X}\, /{\sim } } {{X}\, /{\sim } }[/latex] intuitiv.

Behauptung

Sei [latex]\sim[/latex] eine Äquivalenzrelation auf [latex]X[/latex]. Dann sind folgende drei Aussagen für alle [latex]x, y\in X[/latex] (paarweise) äquivalent:

1. [latex]x \sim y[/latex]
2. [latex][x]_\sim = [y]_\sim[/latex]
3. [latex][x]_\sim \cap [y]_\sim \neq \left \lbrace { } \right \rbrace[/latex]

Beispiel 1.65: Konstruktion der rationalen Zahlen

Wir nehmen an, dass wir bereits die ganzen Zahlen [latex]\mathbb {Z}[/latex] und die Addition und Multiplikation auf [latex]\mathbb {Z}[/latex] mit allen üblichen Eigenschaften kennen und wollen damit die rationalen Zahlen [latex]\mathbb {Q}[/latex] definieren. Zu diesem Zwecke betrachten wir die Relation [latex]\sim[/latex] auf [latex]\mathbb {Z} \times (\mathbb {Z}\setminus \left \lbrace {0} \right \rbrace )[/latex] definiert durch

für [latex](m_1,m_2), (n_1,n_2) \in \mathbb {Z} \times (\mathbb {Z}\setminus \left \lbrace {0} \right \rbrace )[/latex]. Diese Definition rührt daher, dass wir rationale Zahlen als Brüche von ganzen Zahlen auffassen möchten. Dabei müssen wir allerdings solche identifizieren, die «nach Kürzen» gleich sind; zum Beispiel sollte gelten [latex]\frac {10}{6} = \frac {5}{3}[/latex]. Allerdings wollen wir hier davon ausgehen, dass wir die rationalen Zahlen noch nicht kennen, weswegen wir anstatt Gleichungen der Form [latex]\frac {m_1}{m_2}=\frac {n_1}{n_2}[/latex] Gleichungen der Form [latex]m_1n_2 = n_1m_2[/latex] mit Ausdrücken innerhalb von [latex]\mathbb {Z}[/latex] betrachten (im Beispiel [latex]10 \cdot 3 = 5 \cdot 6[/latex]).

Nun verifzieren wir, dass obige Relation tatsächlich eine Äquivalenzrelation ist. Seien dazu [latex](m_1,m_2),(n_1,n_2),(q_1,q_2) \in \mathbb {Z} \times (\mathbb {Z}\setminus \left \lbrace {0} \right \rbrace )[/latex].

• Reflexivität: [latex](m_1,m_2)\sim (m_1,m_2)[/latex], denn [latex]m_1m_2 = m_1m_2[/latex].
• Symmetrie: Angenommen es gilt [latex](m_1,m_2) \sim (n_1,n_2)[/latex]. Dann ist per Definition also [latex]m_1 n_2 = n_1 m_2[/latex], was [latex]n_1 m_2 = m_1n_2[/latex] und daher auch [latex](n_1,n_2) \sim (m_1,m_2)[/latex] impliziert.
• Transitivität: [latex](m_1,m_2) \sim (n_1,n_2)[/latex] und [latex](n_1,n_2) \sim (q_1,q_2)[/latex] ergibt [latex]m_1 n_2 = n_1 m_2[/latex] und [latex]n_1 q_2 = q_1 n_2[/latex]. Durch Multiplikation der ersten Gleichungen mit [latex]q_2[/latex] und der zweiten Gleichung mit [latex]m_2[/latex] erhalten wir
  [latex]
  \begin{aligned}[]m_1 n_2 q_2 = n_1 m_2 q_2 = q_1n_2m_2.\end{aligned}
  [/latex]

  Da [latex]n_2[/latex] nicht Null ist, können wir in obiger Gleichung [latex]n_2[/latex] Wegstreichen (was eine der Eigenschaften von [latex]\mathbb {Z}[/latex] ist und [latex]\mathbb {Q}[/latex] nicht verwendet), womit sich [latex]m_1q_2 = q_1 m_2[/latex] und damit [latex](m_1,m_2) \sim (q_1,q_2)[/latex] ergibt.

Der Quotient [latex]\mathchoice {\text {\raise 0.4ex\hbox {${(\mathbb {Z} \times (\mathbb {Z} \setminus \left \lbrace {0} \right \rbrace ))}$}\big /\lower 0.4ex\hbox {${\sim }$}}} {{(\mathbb {Z} \times (\mathbb {Z} \setminus \left \lbrace {0} \right \rbrace ))}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${\sim }$} } {{(\mathbb {Z} \times (\mathbb {Z} \setminus \left \lbrace {0} \right \rbrace ))}\, /{\sim } } {{(\mathbb {Z} \times (\mathbb {Z} \setminus \left \lbrace {0} \right \rbrace ))}\, /{\sim } }[/latex] kann nun als Definition der rationalen Zahlen [latex]\mathbb {Q}[/latex] angesehen werden. Für eine Äquivalenzklasse [latex][(m_1,m_2)]_\sim \in \mathbb {Q}[/latex] schreibt man wie üblich [latex]\frac {m_1}{m_2}[/latex]. Damit gilt nun die Gleichung

für [latex]m_1\in \mathbb {Z}[/latex] und [latex]q,m_2\in \mathbb {Z}\setminus \{ 0\}[/latex]. In der Tat bezeichnen nach Definition beide Seiten Äquivalenzklassen und die Gleichung gilt genau wenn

oder äquivalenterweise [latex]qm_1m_2=m_1qm_2[/latex] erfüllt ist. Da letzteres gilt, erfüllen damit die so definierten rationalen Zahlen die üblichen Erweiterungs- und Kürzungsregeln.

Des Weiteren lässt sich [latex]\mathbb {Z}[/latex] als Teilmenge von [latex]\mathbb {Q}[/latex] auffassen. In der Tat ist die Abbildung

injektiv, denn die Gleichung [latex]\frac {m}{1} = \frac {n}{1}[/latex] ist für [latex]m,n \in \mathbb {Z}[/latex] per Definition genau dann erfüllt, wenn [latex]m= n[/latex] ist. Wir identifizieren [latex]\mathbb {Z}[/latex] mit dem Bild obiger Abbildung und schreiben insbesondere [latex]\frac {m}{1} = m[/latex] für [latex]m \in \mathbb {Z}[/latex].

Übung 1.66: Addition und Multiplikation auf den rationalen Zahlen

Wir definieren nun zusätzliche Strukturen auf [latex]\mathbb {Q}[/latex]. Zeigen Sie, dass die Abbildungen

und

wohldefiniert sind. Verifizieren Sie des Weiteren die Rechenregeln

für [latex]m,n,b \in \mathbb {Z}\setminus \left \lbrace {0} \right \rbrace[/latex] und [latex]a \in \mathbb {Z}[/latex]. Sie dürfen in dieser Aufgabe zwar alle üblichen Rechenregeln und Eigenschaften von [latex]\mathbb {Z}[/latex] verwenden, aber nicht jene von [latex]\mathbb {Q}[/latex] (da wir letztere ja definieren wollen).

Lemma 1.67: Funktionen durch Fallunterscheidungen

Seien [latex]X[/latex] und [latex]Y[/latex] Mengen und sei [latex]\mathcal {P}[/latex] eine Partition von [latex]X[/latex]. Angenommen es ist für jedes [latex]P \in \mathcal {P}[/latex] eine Funktion [latex]f_P: P \to Y[/latex] gegeben. Dann existiert eine eindeutige Funktion [latex]f: X \to Y[/latex], so dass [latex]f|_P = f_P[/latex] für jedes [latex]P \in \mathcal {P}[/latex] gilt.

Übung 1.68: Funktionen durch Fallunterscheidungen

Zeigen Sie, dass die Bedingung in Lemma 1.67, dass [latex]\mathcal {P}[/latex] eine Partition ist, notwendig ist, durch Auffinden geeigneter Beispiele:

• Finden Sie Mengen [latex]X,Y[/latex], eine Kollektion [latex]\mathcal {P}[/latex] nicht paarweise disjunkter Teilmengen mit [latex]X = \bigcup _{P \in \mathcal {P}}P[/latex] und Funktionen [latex]f_P: P \to Y[/latex] für jedes [latex]P \in \mathcal {P}[/latex], so dass keine Funktion [latex]f:X \to Y[/latex] mit [latex]f|_P = f_P[/latex] für jedes [latex]P \in \mathcal {P}[/latex] existiert.
• Seien [latex]X[/latex] und [latex]Y[/latex] Mengen, [latex]\mathcal {P}[/latex] eine Kollektion paarweise disjunkter Teilmengen mit [latex]X \neq \bigcup _{P \in \mathcal {P}}P[/latex] und Funktionen [latex]f_P: P \to Y[/latex] für jedes [latex]P \in \mathcal {P}[/latex] gegeben. Zeigen Sie, dass mehrere Funktionen [latex]f: X \to Y[/latex] mit [latex]f|_P = f_P[/latex] für jedes [latex]P \in \mathcal {P}[/latex] existieren, falls [latex]Y[/latex] mehr als ein Element enthält.

Definition 1.69: Gleichmächtigkeit

Zwei Mengen [latex]X,Y[/latex] sind gleichmächtig, geschrieben [latex]X \sim Y[/latex], falls es eine Bijektion [latex]f:X \to Y[/latex] gibt.

Definition 1.70: Endliche Mengen

Wir sagen, dass die Kardinalität der leeren Menge [latex]\emptyset[/latex] Null ist und schreiben [latex]|\emptyset | = \# \emptyset = 0[/latex]. Sei nun [latex]X[/latex] eine beliebige Menge und [latex]n \geq 1[/latex] eine natürliche Zahl. Die Menge [latex]X[/latex] hat Kardinalität [latex]n[/latex], falls [latex]X[/latex] gleichmächtig zu [latex]\left \lbrace {1,\ldots ,n} \right \rbrace[/latex] ist. In diesem Fall schreiben wir [latex]|X| = \# X = n[/latex]. Des Weiteren ist [latex]X[/latex] eine endliche Menge, falls [latex]|X| = n[/latex] für eine nicht-negative ganze Zahl [latex]n \in \mathbb {N}_0 = \left \lbrace {0,1,2,\ldots } \right \rbrace[/latex]. In diesem Fall sagen wir auch, dass [latex]X[/latex] endliche Kardinalität hat und wir schreiben [latex]|X|unendliche Menge (oder sagen, dass [latex]X[/latex] unendliche Kardinalität hat) und schreiben [latex]|X| = \infty[/latex].

Proposition 1.71: Schubfachprinzip

Seien [latex]m > n \geq 1[/latex] natürliche Zahlen. Dann gibt es keine injektive Abbildung von [latex]\left \lbrace {1,\ldots ,m} \right \rbrace[/latex] nach [latex]\left \lbrace {1,\ldots ,n} \right \rbrace[/latex]. Insbesondere sind zwei endliche Mengen [latex]X[/latex] und [latex]Y[/latex] genau dann gleichmächtig, wenn [latex]|X| = |Y|[/latex] ist.

Übung 1.72: Schubfachprinzip mittels surjektiven Funktionen

Seien [latex]m > n \geq 1[/latex] natürliche Zahlen. Zeigen Sie, dass es keine surjektive Abbildung von [latex]\left \lbrace {1,\ldots ,n} \right \rbrace[/latex] nach [latex]\left \lbrace {1,\ldots ,m} \right \rbrace[/latex] geben kann.

Übung 1.73

Sei [latex]X[/latex] eine endliche Menge und [latex]f:X \to X[/latex] eine Abbildung.

1. Beweisen Sie, dass Injektivität, Surjektivität und Bijektivität von [latex]f[/latex] äquivalent sind.
2. Sei nun [latex]f[/latex] bijektiv. Zeigen Sie, dass es eine natürliche Zahl [latex]n \geq 1[/latex] gibt mit [latex]f^{\, \circ \, {n} } = \operatorname {id}_X[/latex].

Theorem 1.74: Cantors Diagonalargument

Sei [latex]X[/latex] eine Menge. Dann ist [latex]X[/latex] nicht zu seiner Potenzmenge [latex]\mathcal {P}(X)[/latex] gleichmächtig. Insbesondere ist die Menge [latex]\mathbb {N} = \left \lbrace {1,2,3,\ldots } \right \rbrace[/latex] der natürlichen Zahlen nicht gleichmächtig zu [latex]\mathcal {P}(\mathbb {N})[/latex].

Übung 1.75: Potenzmengen endlicher Mengen

Sei [latex]n[/latex] eine natürliche Zahl und sei [latex]X[/latex] eine Menge mit genau [latex]n[/latex] verschiedenen Elementen. Zeigen Sie, dass [latex]|\mathcal {P}(X)| = 2^n[/latex] gilt. Verwenden Sie dazu vollständige Induktion und schliessen Sie daraus Theorem 1.74 für den Fall, dass [latex]X[/latex] eine endliche Menge ist.

Übung 1.76

Sei [latex]X[/latex] eine Menge und sei [latex]Y[/latex] die Menge der Funktionen [latex]X \to \left \lbrace {0,1} \right \rbrace[/latex]. Zeigen Sie, dass [latex]Y[/latex] und [latex]\mathcal {P}(X)[/latex] gleichmächtig sind.

Übung 1.77: Die Diagonale in Cantors Diagonalargument

Betrachten Sie den Spezialfall [latex]X = \mathbb {N}[/latex] in Theorem 1.74 und nehmen Sie an, dass [latex]\mathcal {P}(\mathbb {N}) \sim \mathbb {N}[/latex], also [latex]\mathcal {P}(\mathbb {N}) = \left \lbrace {A_1,A_2,A_3,\ldots } \right \rbrace[/latex] für Teilmengen [latex]A_n \subseteq \mathbb {N}[/latex] für jede natürliche Zahl [latex]n[/latex]. Für jedes solche [latex]n[/latex] lässt sich die Menge [latex]A_n[/latex] als die Folge in [latex]0,1[/latex] auffassen, für welche die [latex]m[/latex]-te Zahl genau dann [latex]1[/latex] ist, wenn [latex]m \in A_n[/latex] (vergleiche auch Übung 1.76 und Beispiel 1.30). Wir schreiben nun die Folgen in eine Tabelle der Art

wobei die [latex]n[/latex]-te Zeile der Menge [latex]A_n[/latex] entspricht. Dann lässt sich mit Hilfe der (in rot markierten) Diagonalen eine Folge konstruieren, deren zugehörige Menge nicht in der Liste [latex]A_1,A_2,A_3,\ldots[/latex] ist. Wie? Was hat das mit dem Beweis von Theorem 1.74 zu tun?

Übung 1.78: Verschärfung von Cantors Diagonalargument

Formulieren Sie den Beweis von Theorem 1.74 so um, dass keine indirekte Annahme notwendig ist und zeigen Sie, dass eine Abbildung [latex]f: X \to \mathcal {P}(X)[/latex] nicht surjektiv sein kann.

Definition 1.79: Schmächtiger

Seien [latex]X[/latex] und [latex]Y[/latex] zwei Mengen. Dann sagen wir, dass [latex]X[/latex] schmächtiger als (oder genau formuliert höchstens so mächtig wie) [latex]Y[/latex] ist und schreiben [latex]X \lesssim Y[/latex], falls es eine Injektion [latex]f:X \to Y[/latex] gibt. Wir sagen, dass [latex]X[/latex] echt schmächtiger (oder weniger mächtig) als [latex]Y[/latex] ist, falls [latex]X[/latex] schmächtiger als [latex]Y[/latex] ist und [latex]Y[/latex] nicht schmächtiger als [latex]X[/latex] ist ([latex]X \lesssim Y[/latex] und [latex]Y \not \lesssim X[/latex]).

Übung 1.80: Schmächtiger als Relation

Untersuchen Sie die Relation [latex]\lesssim[/latex] auf der Klasse aller Mengen auf ihre Eigenschaften (siehe auch Definition 1.55).

Theorem 1.81: Cantor, Schröder, Bernstein

Seien [latex]X[/latex] und [latex]Y[/latex] Mengen, so dass [latex]X \lesssim Y[/latex] und [latex]Y \lesssim X[/latex]. Dann gilt [latex]X \sim Y[/latex].

Übung 1.82: Verbindung zu Hilberts Hotel

Erklären Sie intuitiv, wo die Parallelen in obigem Beweis von Theorem 1.81 zu Hilberts Hotel sind. Fassen Sie dazu den Beweis in einigen wenigen Sätzen anhand des Bildes 1.12 oder dem folgenden Applet zusammen.

Applet 1.83: Beweis des Satzes von Cantor-Schröder-Bernstein

Im Beweis von Theorem 1.81 wird die Menge [latex]X[/latex] in zwei Typen von Teilmengen zerlegt. Die konstruierte Funktion wird angedeutet, indem Bild (und Urbilder) von einem bewegbaren Punkt [latex]x\in X[/latex] eingezeichnet werden.

Definition 1.84: Kardinalität einer Menge

Die zu einer Menge [latex]X[/latex] gehörenden Äquivalenzklasse bezüglich Gleichmächtigkeit wird die Kardinalität der Menge [latex]X[/latex] genannt und als [latex]|X|[/latex] geschrieben. Falls [latex]X[/latex] endlich ist und genau [latex]n[/latex] verschiedene Elemente hat, dann schreiben wir [latex]|X| = n[/latex]. Eine Menge heisst abzählbar unendlich, falls sie die Kardinalität [latex]|\mathbb {N}|[/latex] hat oder in anderen Worten gleichmächtig zu [latex]\mathbb {N}[/latex] ist. Die Kardinalität von [latex]\mathbb {N}[/latex] wird auch [latex]\aleph _0[/latex], gesprochen Aleph-[latex]0[/latex], genannt.

Übung 1.85: Gitterpunkte in der Ebene

Zeigen Sie, dass [latex]\mathbb {N} \times \mathbb {N}[/latex] abzählbar unendlich ist. Sie können hierzu Theorem 1.81 verwenden: Eine Injektion [latex]\mathbb {N} \times \mathbb {N} \to \mathbb {N}[/latex] finden Sie unter Verwendung der Tatsache, dass unendlich viele Primzahlen existieren. Alternativ lässt sich mit Hilfe eines Bildes tatsächlich eine explizite Bijektion [latex]\mathbb {N} \to \mathbb {N} \times \mathbb {N}[/latex] finden, wie? Zeigen Sie auch, dass das Produkt [latex]\mathbb {Z} \times \mathbb {Z}[/latex] abzählbar unendlich ist.

Definition 1.86: Das Kontinuum

Eine Menge [latex]X[/latex] heisst überabzählbar, falls [latex]\mathbb {N}[/latex] schmächtiger ist als [latex]X[/latex], aber [latex]\mathbb {N}[/latex] nicht gleichmächtig zu [latex]X[/latex] ist. Nach Theorem 1.74 ist [latex]\mathcal {P}(\mathbb {N})[/latex] überabzählbar. Die Kardinalität von [latex]\mathcal {P}(\mathbb {N})[/latex] wird auch mit [latex]\mathfrak {c}[/latex] bezeichnet und das Kontinuum genannt.

Übung 1.87: Trichotomie der Kardinalitäten

1. Zeigen Sie, dass jede Menge entweder endlich, abzählbar unendlich oder überabzählbar ist. Gehen Sie dazu davon aus, dass [latex]X[/latex] eine nicht-endliche Menge ist und finden Sie eine injektive Abbildung [latex]\mathbb {N} \to X[/latex].
2. Zeigen Sie, dass es unendlich viele überabzählbare Kardinalitäten gibt.

Bemerkung

Im Beweis von Übung 1.87 werden Sie wahrscheinlich abzählbar oft eine Wahl treffen müssen. Formal verwendet dies das sogenannte Auswahlaxiom der Mengenlehre (Axiom of Choice), welches wir implizit erlauben werden.

Peano Axiome

Die natürlichen Zahlen [latex]\mathbb {N}[/latex] sind (in einem gewissen Sinne eindeutig) durch die folgenden Eigenschaften charakterisiert:

1. Es existiert ein ausgezeichnetes Element [latex]1 \in \mathbb {N}[/latex] und eine injektive Abbildung [latex]\nu : \mathbb {N} \to \mathbb {N}[/latex], auch Nachfolgerfunktion genannt, so dass [latex]1 \not \in \nu (\mathbb {N})[/latex].
2. [latex]\mathbb {N}[/latex] erfüllt das Induktionsaxiom: Ist [latex]A[/latex] eine Teilmenge von [latex]\mathbb {N}[/latex], die [latex]1[/latex] enthält und für alle [latex]n\in \mathbb {N}[/latex] die Eigenschaft » [latex]n \in A \implies \nu (n) \in A[/latex]» erfüllt, dann gilt [latex]A = \mathbb {N}[/latex].

Behauptung: Nachfolgerzahlen

Sei [latex]n \in \mathbb {N}[/latex] eine natürliche Zahl verschieden von [latex]1[/latex]. Dann ist [latex]n \in \nu (\mathbb {N})[/latex].

Bemerkung

Eigentlich lautet das Zitat (siehe Seite 15 in ^[12]) von Kronecker zu Beginn dieses Abschnitts

Es kann jedoch sein, dass Kronecker eigentlich die natürlichen Zahlen gemeint hat. Auf jeden Fall wollen wir hier den Mönch und Historiker William of Malmesbury (ca. 1095-1143), der die ganze Zahl [latex]0[/latex] als «dangerous Saracen magic» bezeichnet hat, als grössere Autorität in dieser Frage ansehen. Scherz beiseite, die Menschheit hat in der Tat sehr lange gebraucht, um mit der Null und den negativen Zahlen zurecht zu kommen. Für einen geschichtlichen Exkurs zur «Zahl [latex]0[/latex]» verweisen wir auf diesen Podcast der BBC, und zum Thema «Negative Zahlen» auf die ersten [latex]10[/latex]–[latex]20[/latex] Minuten eines weiteren Podcasts der BBC.

Beispiel 1.88: Konstruktion der Menge der ganzen Zahlen

Wir nehmen an, dass wir bereits die Menge der nicht-negativen ganzen Zahlen [latex]\mathbb {N}_0 = \left \lbrace {0,1,2,3,4,\ldots } \right \rbrace[/latex] und die Addition auf [latex]\mathbb {N}_0[/latex] mit allen üblichen Eigenschaften kennen und wollen daraus die ganzen Zahlen definieren. Dazu betrachten wir eine Äquivalenzrelation auf [latex]\mathbb {N}_0^2[/latex]: für [latex](m_1,m_2),(n_1,n_2)\in \mathbb {N}_0^2[/latex] definieren wir
[latex]
\begin{aligned}[]\label{eq:einf-Z aus N 1} (m_1,m_2) \sim (n_1,n_2) \iff m_1+n_2 = n_1 + m_2\end{aligned}
[/latex]
Motiviert ist das ganze dadurch, dass man eine ganze Zahl als Differenz von zwei nicht-negativen ganzen Zahlen auffassen kann. Diese sind aber nicht eindeutig gegeben; deswegen führt man auf Tupeln von natürlichen Zahlen obige Äquivalenzrelation ein. In der Tat hat man bei Definition (1.10) eigentlich [latex](m_1,m_2) \sim (n_1,n_2) \iff m_1-m_2 = n_1 -n_2[/latex] im Hinterkopf, darf dies aber formal nicht verwenden, da die Subtraktion (noch) nicht erlaubt ist. Wenn wir über [latex][(m_1,m_2)]_\sim[/latex] sprechen, werden wir leicht schizophren an [latex]m_1-m_2[/latex] denken, dies aber nicht verwenden.

Informell können wir uns das Tupel [latex](m_1,m_2)[/latex] als einen Vektor mit Anfangspunkt [latex]m_1 \in \mathbb {N}_0[/latex] und Endpunkt [latex]m_2 \in \mathbb {N}_0[/latex] vorstellen, womit die Äquivalenzklassen allen Vektoren mit gleicher Länge und Richtung entspricht. Alternativ könnte [latex]m_1[/latex] der Kontostand vor und [latex]m_2[/latex] der Kontostand nach einer Transaktion darstellen und die Äquivalenzklasse entspricht dann dem Nettogewinn/-verlust.

Wir verifizieren nun, dass es sich bei [latex]\sim[/latex] effektiv um eine Äquivalenzrelation handelt. Es gilt für alle [latex](m_1,m_2),(n_1,n_2),(q_1,q_2) \in \mathbb {N}_0^2[/latex]

• Reflexivität: [latex](m_1,m_2)\sim (m_1,m_2)[/latex], denn [latex]m_1+m_2 = m_1+m_2[/latex].
• Symmetrie: [latex](m_1,m_2) \sim (n_1,n_2)[/latex] denn [latex]m_1+n_2 = n_1+m_2[/latex] impliziert [latex]n_1+m_2 = m_1+n_2[/latex] und daher auch [latex](n_1,n_2) \sim (m_1,m_2)[/latex].
• Transitivität: [latex](m_1,m_2) \sim (n_1,n_2)[/latex] und [latex](n_1,n_2) \sim (q_1,q_2)[/latex] impliziert [latex]m_1+n_2 = n_1 + m_2[/latex] und [latex]n_1+q_2 = q_1 + n_2[/latex]. Durch Summieren dieser Gleichungen ergibt sich
  [latex]
  \begin{aligned}[]m_1+n_2 + n_1+q_2 = n_1 + m_2 + q_1 + n_2\end{aligned}
  [/latex]

  und durch Wegstreichen von [latex]n_1+n_2[/latex] (was eine der Eigenschaften von [latex]\mathbb {N}_0[/latex] ist und nicht die Subtraktion verwendet) erhalten wir [latex]m_1+q_2 = q_1+m_2[/latex], also [latex](m_1,m_2) \sim (q_1,q_2)[/latex]

Der Quotient [latex]\mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {N}_0^2}$}\big /\lower 0.4ex\hbox {${\sim }$}}} {{\mathbb {N}_0^2}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${\sim }$} } {{\mathbb {N}_0^2}\, /{\sim } } {{\mathbb {N}_0^2}\, /{\sim } }[/latex] kann als Definition von [latex]\mathbb {Z}[/latex] angesehen werden, wobei wir die Äquivalenz­kla­sse auch als [latex][(m_1,m_2)]_\sim = m_2-m_1[/latex] schreiben. Insbesondere identifizieren wir [latex]n \in \mathbb {N}_0[/latex] mit [latex][(n,0)]_\sim[/latex] und schreiben [latex][(0,n)]_\sim[/latex] auch als [latex]0-n = -n[/latex] für [latex]n \in \mathbb {N}[/latex]. Dies macht nach folgender Übung Sinn.

Übung 1.89: Eine Partition der ganzen Zahlen

1. Zeigen Sie, dass die Abbildungen
   [latex]
   \begin{aligned}[]\iota _+: n \in \mathbb {N}_0 &\mapsto [(n,0)]_\sim \in \mathbb {Z} \\ \iota _-: n \in \mathbb {N} &\mapsto -n = [(0,n)]_\sim \in \mathbb {Z}\end{aligned}
   [/latex]

   injektiv sind und disjunkte Bilder [latex]\iota _+(\mathbb {N}_0),\iota _-(\mathbb {N})[/latex] haben, welche wir mit [latex]\mathbb {N}_0=\iota _+(\mathbb {N}_0)[/latex] und [latex]-\mathbb {N}=\iota _-(\mathbb {N})[/latex] bezeichnen werden.

2. Zeigen Sie, dass [latex]\mathbb {Z} = \mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {N}_0^2}$}\big /\lower 0.4ex\hbox {${\sim }$}}} {{\mathbb {N}_0^2}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${\sim }$} } {{\mathbb {N}_0^2}\, /{\sim } } {{\mathbb {N}_0^2}\, /{\sim } } = \iota _+(\mathbb {N}_0) \sqcup \iota _-(\mathbb {N})[/latex] gilt.

Übung 1.90: Addition von ganzen Zahlen

1. Zeigen Sie, dass die Funktion [latex]f_{\text {neg}}: \mathbb {Z} = \mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {N}_0^2}$}\big /\lower 0.4ex\hbox {${\sim }$}}} {{\mathbb {N}_0^2}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${\sim }$} } {{\mathbb {N}_0^2}\, /{\sim } } {{\mathbb {N}_0^2}\, /{\sim } } \to \mathbb {Z}[/latex] definiert durch
   [latex]
   \begin{aligned}[]f_{\text {neg}}([(m_1,m_2)]_\sim ) = [(m_2,m_1)]_\sim\end{aligned}
   [/latex]

   für [latex](m_1,m_2) \in \mathbb {N}_0^2[/latex] wohldefiniert und bijektiv ist. Was ist das Bild von [latex]\iota _+(\mathbb {N}_0)[/latex] und von [latex]\iota _-(\mathbb {N})[/latex] unter dieser Abbildung?

2. Zeigen Sie, dass die Funktion
   [latex]
   \begin{aligned}[]f_{\text {add}}: \mathbb {Z}^2 \to \mathbb {Z},\quad ( [(m_1,m_2)]_\sim , [(n_1,n_2)]_\sim ) \mapsto [(m_1+ n_1,m_2+ n_2)]_\sim\end{aligned}
   [/latex]

   wohldefiniert ist. Verifizieren Sie, dass für jedes [latex]z \in \mathbb {Z}[/latex] gilt [latex]f_{\text {add}}(z,f_{\text {neg}}(z)) = [(0,0)]_\sim[/latex].

3. Finden und definieren Sie weitere natürliche Abbildungen [latex]\mathbb {Z} \to \mathbb {Z}[/latex] oder [latex]\mathbb {Z}^2 \to \mathbb {Z}[/latex].

Definition 1.91: Teilbarkeit und Kongruenz

Seien [latex]a,b\in \mathbb {Z}[/latex]. Wir sagen, dass [latex]b[/latex] durch [latex]a[/latex] teilbar ist, und schreiben [latex]a|b[/latex], falls ein [latex]k \in \mathbb {Z}[/latex] existiert mit [latex]ak = b[/latex]. Des Weiteren sind [latex]a[/latex] und [latex]b[/latex] kongruent modulo [latex]q\in \mathbb {N}[/latex], falls [latex]b-a[/latex] durch [latex]q[/latex] teilbar ist. In diesem Fall schreiben wir

Applet 1.92: Darstellung des Quotienten modulo Kongruenz

Wir stellen in diesem Applet den Quotienten [latex]\mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {Z}}$}\big /\lower 0.4ex\hbox {${q \mathbb {Z}}$}}} {{\mathbb {Z}}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${q \mathbb {Z}}$} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } {{\mathbb {Z}}\, /{q \mathbb {Z}} }[/latex] (für verschiedene Werte von [latex]q[/latex]) dar. Es macht Sinn sich die Punkte [latex]\mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {Z}}$}\big /\lower 0.4ex\hbox {${q \mathbb {Z}}$}}} {{\mathbb {Z}}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${q \mathbb {Z}}$} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } {{\mathbb {Z}}\, /{q \mathbb {Z}} }[/latex] entlang eines Kreises vorzustellen, doch hat dies formal (vorerst) keine Bedeutung.

Übung 1.93: Eigenschaften der Kongruenz

1. Zeigen Sie, dass Kongruenz modulo [latex]q[/latex] eine Äquivalenzrelation [latex]\equiv[/latex] auf [latex]\mathbb {Z}[/latex] darstellt.
2. Zeigen Sie, dass die Abbildungen
   [latex]
   \begin{aligned}[](a+ q \mathbb {Z}, b+ q \mathbb {Z}) \in \big ( \mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {Z}}$}\big /\lower 0.4ex\hbox {${q \mathbb {Z}}$}}} {{\mathbb {Z}}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${q \mathbb {Z}}$} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } \big )^2 &\mapsto (a+b)+ q \mathbb {Z} \in \mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {Z}}$}\big /\lower 0.4ex\hbox {${q \mathbb {Z}}$}}} {{\mathbb {Z}}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${q \mathbb {Z}}$} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } \\ (a+ q \mathbb {Z}, b+ q \mathbb {Z}) \in \big ( \mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {Z}}$}\big /\lower 0.4ex\hbox {${q \mathbb {Z}}$}}} {{\mathbb {Z}}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${q \mathbb {Z}}$} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } \big )^2 &\mapsto (a\cdot b)+ q \mathbb {Z} \in \mathchoice {\text {\raise 0.4ex\hbox {${\mathbb {Z}}$}\big /\lower 0.4ex\hbox {${q \mathbb {Z}}$}}} {{\mathbb {Z}}/\text {\hspace {-0.3ex}\vspace {-0.5ex}${q \mathbb {Z}}$} } {{\mathbb {Z}}\, /{q \mathbb {Z}} } {{\mathbb {Z}}\, /{q \mathbb {Z}} }\end{aligned}
   [/latex]

   wohldefiniert sind (man vergleiche auch mit Übung 1.90).

Beispiel 1.94: Überdeckungen mit Dreiecken

Folgendes Beispiel entstammt dem Buch von Blatter ^[14](Kapitel 1, Seite 6).

Sei [latex]D[/latex] das gleichseitige Dreieck mit Kantenlänge [latex]2[/latex] und sei [latex]a[/latex] eine Zahl kleiner als [latex]2[/latex]. Wir betrachten folgende Aussagen:

Bei einer Überdeckung durch Dreiecke sind auch Überlappungen erlaubt. Wir behaupten nun, dass

gilt. Auf Grund deren Definitionen impliziert die Aussage [latex]A(a)[/latex] die Aussage [latex]B(a)[/latex]; in Symbolen [latex]A(a) \implies B(a)[/latex]. Wir fixieren [latex]a>0[/latex] und beweisen nun die Implikation [latex]B(a) \implies A(a)[/latex], in dem wir die Kontraposition [latex]\neg A(a) \implies \neg B(a)[/latex] beweisen. Wir nehmen [latex]\neg A(a)[/latex] an, also dass sich [latex]D[/latex] nicht mit [latex]4[/latex] gleichseitigen Dreiecken überdecken lässt. Dann muss [latex]a

Gegeben eine Überdeckung von [latex]D[/latex] durch Dreiecke der Seitenlänge [latex]a[/latex], dann müssen die in obiger Grafik erhaltenen [latex]6[/latex] Punkte (unten in rot markiert)

in jeweils verschiedenen gleichseitigen Dreiecken der Kantenlänge [latex]a[/latex] enthalten sein, da wir bereits erkannt haben, dass die Kantenlänge [latex]a[/latex] kleiner als [latex]1[/latex] ist. Insbesondere sind mindestens [latex]6[/latex] solche Dreiecke notwendig, um [latex]D[/latex] zu überdecken; also gilt [latex]\neg B(a)[/latex].

Übung 1.95: Gauss’sche Summationsformel

Zeigen Sie mittels vollständiger Induktion, dass für jede natürliche Zahl [latex]n \geq 1[/latex] gilt

Beispiel 1.96: Eine geometrische Induktion

Sei [latex]n[/latex] eine natürliche Zahl. Wir betrachten das Quadrat mit Kantenlänge [latex]2^n[/latex], aus dem ein kleines Quadrat der Kantenlänge [latex]1[/latex] entfernt wurde.

Bei diesen beiden Quadraten und auch bei allen noch zu erscheinenden Konstrukten möchten wir nur Ecken an ganzzahligen Stellen (d.h. in [latex]\mathbb {Z}^2[/latex]) zulassen. Wir behaupten nun, dass sich das obige «Quadrat mit Loch» durch Objekte der Art (rotieren ist erlaubt)

abdecken lässt und beweisen dies per Induktion über [latex]n[/latex]. Zum Induktionsanfang [latex]n=1[/latex]: Das grössere Quadrat hat Kantenlänge [latex]2[/latex], also ist das Bild

und die Aussage stimmt. Angenommen wir wissen, dass die Behauptung für [latex]n[/latex] korrekt ist. Wir zerlegen das Quadrat mit Kantenlänge [latex]2^{n+1}[/latex] in [latex]4[/latex] Quadrate der Kantenlänge [latex]2^n[/latex] und entfernen aus einem dieser Quadrate ein kleines Quadrat der Kantenlänge [latex]1[/latex]. Zusätzlich entfernen wir aus den anderen Quadraten je ein kleines Quadrat wie in folgendem Bild

Die [latex]4[/latex] so entstandenen Objekte (Quadrate mit Loch) lassen sich aber jeweils abdecken nach dem Induktionsschritt, also folgt die Behauptung.

Beispiel 1.97

Wir betrachten die Abfolge von Zahlen

und behaupten, dass es eine davon geben muss, welche durch [latex]17[/latex] teilbar ist. Dazu definieren wir die Menge [latex]R = \left \lbrace {0,\ldots ,16} \right \rbrace[/latex] (die Reste mod [latex]17[/latex]) und die Schubfächer

für [latex]r \in R[/latex]. Nach Division mit Rest muss jede der Zahlen [latex]1,\ 11,\ 111,\ 1111,\ 11111,\ \ldots[/latex] in einem der Schubfächer [latex]S_r[/latex] enthalten sein und es gibt jeweils genau ein solches Schubfach. Da wir aber genau [latex]17[/latex] Schubfächer haben und unendlich viele Zahlen darin verstauen wollen, müssen sicherlich zwei dieser Zahlen im gleichen Schubfach liegen. Formaler betrachtet man die Abbildung

wobei [latex]r_x \in R[/latex] die eindeutig bestimmte Zahl mit [latex]x \in S_{r_x}[/latex] ist. Wie erwähnt kann diese Abbildung aber nicht injektiv sein. Es gibt also einen Rest [latex]r\in R[/latex] und zwei Zahlen [latex]x,y \in \mathbb {N}[/latex] von der Form [latex]111\ldots 1[/latex] mit [latex]x,y \in S_r[/latex] und [latex]y>x[/latex]. Die Differenz von [latex]x[/latex] und [latex]y[/latex] ist von der Form

wobei [latex]a[/latex] in unserer Liste vorkommt und [latex]n\in \mathbb {N}[/latex]. Des Weiteren ist [latex]y-x[/latex] wegen

durch [latex]17[/latex] teilbar. Da aber [latex]17[/latex] eine Primzahl ist und weder [latex]10[/latex] noch [latex]10^n[/latex] durch [latex]17[/latex] teilbar ist, ist [latex]a[/latex] durch [latex]17[/latex] teilbar.

Beispiel 1.98: o.B.d.A

Sei [latex]A(n)[/latex] die Aussage [latex]2^{n^2} > n^2[/latex] über ganze Zahlen [latex]n[/latex], die die Eigenschaft [latex]A(n) \iff A(-n)[/latex] für jede ganze Zahl [latex]n[/latex] erfüllt. Wollen wir die Wahrheit der Aussage [latex]A(n)[/latex] nachweisen, so reicht es anzunehmen, dass [latex]n \geq 0[/latex] ist, denn ein mögliches Vorzeichen von [latex]n[/latex] wird von der Funktion [latex]n \in \mathbb {Z} \mapsto n^2 \in \mathbb {Z}[/latex] absorbiert. Wir schreiben zu Beginn des Beweises also «Sei o.B.d.A. [latex]n \geq 0[/latex]» .

Bemerkung

Eigentlich beschäftigt sich obiger Podcast mit Gödel’s Unvollständigkeitssatz, welcher Teil der mathematischen Logik ist. Dieses Teilgebiet der Mathematik beschäftigt sich mit der Theorie des Beweisens und Fragen wie «ist die Aussage … aus den Axiomen … beweisbar?» . Interessanterweise gibt es in dieser Theorie nicht bloss einen Unvollständigkeitssatz, sondern auch einen Vollständigkeitssatz. Die Auflösung dieses scheinbaren Paradox würde uns jedoch zu weit vom Thema abbringen.

Übung: Allgemeinere Bereiche unter der Parabel

Berechnen Sie in Analogie zu obigem die Fläche unter der Parabel

wobei [latex]a,b\in \mathbb {R}[/latex] zwei gegebene reelle Zahlen mit [latex]a

Übung

In dieser Übung möchten wir eine Variante illustrieren, wie man auf Lemma 1.3 schliessen kann ohne zuerst im Besitz der richtigen Formel zu sein. Wir schreiben dazu für [latex]n \in \mathbb {N}[/latex]

Gehen Sie nun wie folgt vor.

• Zeigen Sie für [latex]a,b \in \mathbb {R}[/latex]
  [latex]
  \begin{aligned}[](a+b)^3 = a^3 + 3a^2 b + 3ab^2 + b^3\end{aligned}
  [/latex]

  und erklären Sie, welche Rechenregeln Sie dabei verwenden.

• Verifizieren Sie die Gleichung
  [latex]
  \begin{aligned}[](n+1)^3 = (n+1) + 3 (1^2 + 2^2 + \ldots + n^2) + 3 (1+2+\ldots +n).\end{aligned}
  [/latex]
• Schliessen Sie auf Lemma 1.3.

Übung: Draculas Bücher

In der Bibliothek des Grafen Dracula gibt es keine zwei Bücher, deren Inhalt aus gleich vielen Wörtern besteht. Die Anzahl der Bücher ist die Summe der Anzahl der Wörter jedes einzelnen Buches. Des Weiteren genügen diese Aussagen, um den Inhalt mindestens eines Buches aus Draculas Bibliothek genau zu beschreiben. Was steht in diesem Buch? Diese Übung enstammt dem Buch ^[17].

Übung: Vier Aussagen in Prädikatenlogik

Wir sagen [latex]m\in \mathbb {N}[/latex] teilt [latex]n\in \mathbb {N}[/latex] falls es ein [latex]d\in \mathbb {N}[/latex] gibt mit [latex]n=dm[/latex]. Beschreiben Sie die Bedeutung folgender Aussagen und bestimmen Sie, ob diese zutreffen.

• [latex]\forall n\in \mathbb {N}\ \exists m\in \mathbb {N}:\ m[/latex] teilt [latex]n[/latex].
• [latex]\exists m\in \mathbb {N}\ \forall n\in \mathbb {N}:\ m[/latex] teilt [latex]n[/latex].
• [latex]\forall m\in \mathbb {N}\ \exists n\in \mathbb {N}:\ m[/latex] teilt [latex]n[/latex].
• [latex]\exists n\in \mathbb {N}\ \forall m\in \mathbb {N}:\ m[/latex] teilt [latex]n[/latex].

Übung: Allgemeinere Existenzquantoren

Sei [latex]X[/latex] eine Menge. In dieser Übung wollen wir Quantoren für die Aussage, dass mehrere Elemente mit einer Eigenschaft [latex]A(x)[/latex] in [latex]X[/latex] existieren, definieren.

1. Definieren Sie unter Verwendung des Existenzquantors einen neuen Quantor [latex]\exists ^{\geq 2}[/latex], so dass die Aussage «[latex]\exists ^{\geq 2} x\in X: A(x)[/latex]» bedeutet, dass es mindestens zwei Elemente [latex]x[/latex] in [latex]X[/latex] gibt, die die Eigenschaft [latex]A(x)[/latex] haben.
2. Verallgemeinern Sie (i) zu dem Quantor [latex]\exists ^{\geq n}[/latex] für eine natürliche Zahl [latex]n[/latex], und verwenden Sie diese um auch den Quantor [latex]\exists ^{=n}[/latex] zu definieren, der besagen soll, dass es genau [latex]n[/latex] Elemente in [latex]X[/latex] gibt, die die Eigenschaft [latex]A(x)[/latex] besitzen. (Sie dürfen entweder informell Punkte verwenden, oder formal korrekter den Funktionsbegriff, Eigenschaften von Funktionen, und die Menge [latex]\left \lbrace {k\in \mathbb {N}} \mid { k\leq n}\right \rbrace[/latex], die genau [latex]n[/latex] Elemente hat.)
3. Definieren Sie unter Verwendung des Existenzquantors, des Funktionsbegriffes, einer Eigenschaft von Funktionen und der natürlichen Zahlen [latex]\mathbb {N}[/latex] einen neuen Quantor [latex]\exists ^\infty[/latex], der besagt, dass es unendlich viele Elemente in [latex]X[/latex] gibt, die die Eigenschaft [latex]A(x)[/latex] besitzen.

Übung: Injektive Funktionen durch Fallunterscheidungen

Zeigen Sie folgende Behauptung: Seien [latex]X[/latex] und [latex]Y[/latex] Mengen und sei [latex]\mathcal {P}[/latex] eine Partition von [latex]X[/latex]. Angenommen es ist für jedes [latex]P \in \mathcal {P}[/latex] eine injektive Funktion [latex]f_P: P \to Y[/latex] gegeben und sei [latex]f: X \to Y[/latex] die eindeutige Funktion mit [latex]f|_P = f_P[/latex] für jedes [latex]P \in \mathcal {P}[/latex] nach Lemma 1.67. Zeigen Sie, dass [latex]f[/latex] genau dann injektiv ist, falls die Mengen [latex]f(P)[/latex] für [latex]P \in \mathcal {P}[/latex] paarweise disjunkt sind.

Übung: Eine Äquivalenzrelation auf dem kartesischen Produkt

Seien [latex]X, Y[/latex] zwei nicht-leere Mengen, sei [latex]\sim _X[/latex] eine Relation auf [latex]X[/latex] und sei [latex]\sim _Y[/latex] eine Relation auf [latex]Y[/latex]. Wir definieren damit eine Relation [latex]\sim[/latex] auf [latex]X \times Y[/latex] durch

für [latex](x,y),(x',y') \in X \times Y[/latex]. Zeigen Sie, dass [latex]\sim[/latex] genau dann eine Äquivalenzrelation auf [latex]X \times Y[/latex] ist, wenn [latex]\sim _X[/latex] eine Äquivalenzrelation auf [latex]X[/latex] ist und [latex]\sim _Y[/latex] eine Äquivalenzrelation auf [latex]Y[/latex] ist. Gilt dies auch, wenn eine der beiden Mengen [latex]X,Y[/latex] leer ist? Diese Übung enstammt dem Buch ^[18].

Applet: Nichtvertauschbarkeit der Verknüpfung

Wir betrachten zwei Funktionen [latex]f,g:\mathbb {R}\to \mathbb {R}[/latex], wobei [latex]f[/latex] nur durch den Graphen beschrieben ist und [latex]g:x\in \mathbb {R}\mapsto g(x)=ax+b[/latex] eine affine Funktion ist, die durch zwei Konstanten [latex]a,b\in \mathbb {R}[/latex] definiert wird. Durch Bewegen zweier Punkte am Graph von [latex]g[/latex] lassen sich [latex]a[/latex] und [latex]b[/latex] definieren. Experimentieren Sie damit um sich an die geometrische Bedeutung von den Zahlen [latex]a[/latex] und [latex]b[/latex] zu errinnern, und beobachten Sie, wie sich die beiden Funktionen [latex]g\circ f[/latex] und [latex]f\circ g[/latex] im rechten Fenster unterschiedlich verändern. Es ist nützlich sich diese Phänomene vollständig zu erklären, denn wir werden ähnlichen Verknüpfungen in unseren weiteren Überlegungen begegnen.

Übung

Sei [latex]n[/latex] eine natürliche Zahl. Zeigen Sie, dass die Implikation

gilt.

Übung: Türme von Hanoi

Es seien [latex]3[/latex] Ablageflächen gegeben. Angenommen auf der linken Ablagefläche seien [latex]n[/latex] Blöcke für eine natürliche Zahl [latex]n[/latex] aufgetürmt, wobei nie ein kleinerer Block unter einem grösseren Block liegt.

Zeigen Sie, dass Sie den Turm von links nach rechts umschichten können, ohne dass je ein kleinerer Block unter einem grösseren Block zu liegen kommt.

Übung

Zeigen Sie mittels vollständiger Induktion, dass für alle natürliche Zahlen [latex]n \geq 5[/latex] gilt [latex]4n

Übung

Zeigen Sie mittels vollständiger Induktion, dass die Ungleichung [latex]n^2

Übung

Wir färben jeden Punkt im Gitter [latex]\mathbb {Z}^2[/latex] mit einer von [latex]17[/latex] verschiedenen Farben ein. Zeigen Sie, dass es ein achsenparalleles Rechteck [latex]R[/latex] in diesem Gitter gibt, dessen Ecken alle dieselbe Farbe besitzen.

Übung

Sei [latex]n \in \mathbb {N}[/latex] und sei [latex]S[/latex] eine Teilmenge von [latex]\left \lbrace {1,\ldots ,2n} \right \rbrace[/latex] mit Kardinalität [latex]n+1[/latex]. Zeigen Sie, dass es Elemente [latex]a,b\in S[/latex] gibt mit [latex]a|b[/latex].

Übung

Sei [latex]T[/latex] eine endliche Menge und seien [latex]S_1,\ldots ,S_n[/latex] Teilmengen von [latex]T[/latex] mit

Zeigen Sie, dass es ein Element [latex]t \in T[/latex] gibt, welches in mindestens [latex]k+1[/latex] der Mengen [latex]S_1,\ldots ,S_n[/latex] liegt.

Übung: Satz von Pythagoras

In dieser Übung möchten wir (auf Ihnen vielleicht bereits bekannte Weise den Satz von Pythagoras) beweisen. Wir betrachten ein rechtwinkliges Dreieck mit Katheten der Länge [latex]a[/latex] und [latex]b[/latex] und Hypotenuse der Länge [latex]c[/latex]. Zeigen Sie, dass

Hinweis: Betrachten Sie folgende Bilder

und gehen Sie dabei davon aus, dass gewisse geometrische Begriffe wie Winkel, Länge und Fläche für elementare Bereiche und intuitiv anschauliche Eigenschaften wie Invarianz der Fläche unter Verschiebung und Drehung bekannt sind.

Übung: Primzahlen sind irreduzibel

Zeigen Sie, dass jede Primzahl in [latex]\mathbb {N}[/latex] auch irreduzibel ist.

Übung: Primfaktorzerlegung

Zeigen Sie mittels vollständiger Induktion, dass jede natürliche Zahl grösser als [latex]1[/latex] als Produkt von Primzahlen geschrieben werden kann.

Übung: Unendlich viele Primzahlen

Zeigen Sie, dass es unendliche viele Primzahlen gibt.

Übung: Summen von Quadraten

In dieser Übung möchten wir (mit einer detaillierten Anleitung) zeigen, dass für jede ungerade Primzahl [latex]p \in \mathbb {N}[/latex] mit [latex]p \equiv 1 \mod 4[/latex] Zahlen [latex]x,y \in \mathbb {N}[/latex] mit [latex]x^2+y^2 = p[/latex] existieren. Dabei folgen wir dem Artikel «A one-sentence proof that every prime [latex]p \equiv 1 \mod 4[/latex] is a sum of two squares.» von Don Zagier ^[19]. Wir zitieren:

Im Folgenden möchten wir die Details in obigem kryptischen aber auch eleganten Beweis ausarbeiten. Aber zuerst möchten wir einen Grund lieferen, wieso man obige Aussage überhaupt glauben sollte.

1. Sei also [latex]p \in \mathbb {N}[/latex] eine ungerade Zahl, für die [latex]x,y \in \mathbb {N}[/latex] mit [latex]x^2+y^2 = p[/latex] existieren. Zeigen Sie, dass dann [latex]p \equiv 1 \mod 4[/latex] ist.
2. Versuchen Sie [latex]5[/latex], [latex]9[/latex], [latex]13[/latex], [latex]17[/latex], [latex]21[/latex] als Summe [latex]x^2+y^2[/latex] von zwei Quadraten natürlicher Zahlen [latex]x,y\in \mathbb {N}[/latex] zu schreiben und bemerken sie, dass unter diesen Zahlen dies nur für die Primzahlen möglich ist.
3. Zeigen Sie nun, dass die obige Menge [latex]S[/latex] endlich ist und dass die Abbildung
   [latex]
   \begin{aligned}[]\tau : S \to S,\ (x,y,z) \mapsto (x,z,y)\end{aligned}
   [/latex]

   wohldefiniert ist.

4. Beweisen Sie, dass [latex]p[/latex] als Summe von zwei Quadraten geschrieben werden kann, wenn es für die Abbildung [latex]\tau[/latex] einen Punkt [latex]a= (x,y,z) \in S[/latex] mit [latex]\tau (a) = a[/latex] gibt. Ein solcher Punkt [latex]a \in S[/latex] nennt sich ein Fixpunkt von [latex]\tau[/latex].

Die Abbildung [latex]\tau[/latex] ist eine Involution, was bedeutet, dass [latex]\tau ^{\, \circ \, {2} } = \operatorname {id}_S[/latex] ist.

3. Zeigen Sie, dass eine Involution auf [latex]S[/latex] einen Fixpunkt besitzt, wenn [latex]|S|[/latex] ungerade ist. Verifizieren Sie auch, dass [latex]|S|[/latex] ungerade ist, wenn es eine Involution [latex]S \to S[/latex] mit einem eindeutig bestimmten Fixpunkt gibt.
4. Betrachten Sie die Abbildung [latex]\sigma[/latex] aus () und verifizieren Sie folgende Behauptungen:
   • Die Abbildung [latex]\sigma[/latex] ist wohldefiniert: Einerseits gilt für [latex](x,y,z) \in S[/latex], dass die Fälle [latex]x = y-z[/latex] und [latex]x = 2y[/latex] nicht eintreten können, womit [latex]\sigma[/latex] für jedes Element in [latex]S[/latex] definiert ist. Andererseits ist für jedes [latex](x,y,z) \in S[/latex] das Bild [latex]\sigma ((x,y,z))[/latex] (wie oben definiert) tatsächlich ein Element von [latex]S[/latex].
   • [latex]\sigma :S \to S[/latex] ist eine Involution.
5. Zeigen Sie, dass der einzige Fixpunkt von [latex]\sigma[/latex] durch [latex](1,1,k)[/latex] gegeben ist, wobei [latex]k \in \mathbb {N}_0[/latex] die Gleichung [latex]p = 4k+1[/latex] erfüllt.
6. Kombinieren Sie obige Argumente, um die gewünschte Aussage zu zeigen.

Wo haben Sie verwendet, dass [latex]p[/latex] eine Primzahl (oder irreduzibel) ist?