Mengenlehre und Abbildungen – Analysis I (Kap. 1-9)

1.4 Mengenlehre und Abbildungen

1.4.1 Naive Mengenlehre

Georg Cantor definierte 1895 in [Can95] den Begriff einer Menge wie folgt:

„Unter einer Menge verstehen wir jede Zusammenfassung $M$ von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denken (welche Elemente von $M$ genannt werden) zu einem Ganzen.“

Also sind die zentralen Annahmen der naiven Mengenlehre (oder Cantorschen Mengenlehre) die folgenden Punkte.

(1): Eine Menge besteht aus beliebigen unterscheidbaren Elementen. Etwaige Vielfachheiten werden ignoriert.
(2): Eine Menge ist unverwechselbar durch ihre Elemente bestimmt.
(3): Jede Eigenschaft $A (x)$ definiert die Menge der Objekte ${x ∣ A (x)}$ , die diese Eigenschaft besitzen (das heisst, die Aussage $A (x)$ erfüllen).

Manchmal beschreiben wir eine Menge durch eine konkrete Auflistung ihrer Elemente (zum Beispiel in der Form $M = {x_{1}, x_{2}, \dots, x_{n}}$ ). Die leere Menge, geschrieben als ${}$ oder auch $\emptyset$ , ist die Menge, die keine Elemente enthält. Mengen werden teilweise auch Familien (oder Kollektionen, Ansammlungen) genannt. Wir schreiben „ $x \in X$ “, falls $x$ ein Element der Menge $X$ ist. Je nach Zusammenhang nennen wir die Elemente mitunter auch Punkte, Zahlen oder Vektoren. Falls $x$ kein Element der Menge $X$ ist (also $\neg (x \in X)$ ), so schreiben wir auch $x \notin X$ .

Definition 1.14 (Inklusionen).

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

Äquivalente Formulierungen für „ $P$ ist eine Teilmenge von $Q$ “ sind „ $P$ ist in $Q$ enthalten“ und „ $Q$ ist eine Obermenge von $P$ “, was wir auch als „ $Q \supseteq P$ “ schreiben. Die Bedeutung der Aussage „ $Q$ ist eine echte Obermenge von $P$ “, geschrieben $Q ⊋ P$ , ergibt sich nun implizit.

Für eine Menge $X$ und eine Aussage „ $A (x)$ “ über Elemente $x \in X$ schreiben wir auch

\begin{align} {x \in X ∣ A (x)} = {x ∣ x \in X \land A (x)} & (1.8) \end{align}

für die Teilmenge aller $x \in X$ für die die Aussage „ $A (x)$ “ gilt.

Übung 1.15.

Seien $P, Q$ Mengen. Formuliere die Aussagen „ $P$ ist eine echte Teilmenge von $Q$ “ und „ $P$ ist keine Teilmenge von $Q$ “ in Prädikatenlogik.

Teillösung.

„ $P$ ist eine echte Teilmenge“ ist durch „ $(\forall x \in P : x \in Q) \land (\exists x \in Q : x \notin P)$ “ definiert.

Wegen der zweiten Annahme der naiven Mengenlehre sind zwei Mengen $P, Q$ genau dann gleich, wenn $P \subseteq Q$ und $Q \subseteq P$ gelten. Insbesondere könnte ${x, y} = {z}$ gelten, falls $x = y = z$ ist. Also gibt es für Elemente einer Menge keine Vielfachheiten, aber es ist prinzipiell erlaubt ein Element mehrmals als Element einer Menge aufzulisten. Im Folgenden führen wir geläufige Konstruktionen von Mengen aus gegebenen Mengen ein.

Definition 1.16 (Mengenoperationen).

Seien $P, Q$ zwei Mengen. Der Durchschnitt $P \cap Q$ , die Vereinigung $P \cup Q$ , das relative Komplement $P ∖ Q$ und die symmetrische Differenz $P △ Q$ sind durch

\begin{array}{l} P \cap Q & = {x ∣ x \in P \land x \in Q} \\ P \cup Q & = {x ∣ x \in P \lor x \in Q} \\ P ∖ Q & = {x ∣ x \in P \land x \notin Q} \\ P △ Q & = (P ∖ Q) \cup (Q ∖ P) = {x ∣ x \in P XOR x \in Q} \end{array}

definiert. Wenn aus dem Zusammenhang klar ist, dass alle betrachteten Mengen Teilmengen einer gegebenen (Grund-) Menge $X$ sind, dann ist das Komplement $P^{c}$ von $P$ (in $X$ ) definiert durch $P^{c} = X ∖ P$ . Dies ist alles in den Bildern 1.4 und 1.5 veranschaulicht.

Im Zusammenhang dieser Definitionen wollen wir noch erwähnen, dass man der Komplementbildung zu einer Grundmenge immer die höchste Priorität und der Vereinigungsoperation die geringste Priorität zuordnet. Also sollte man für Teilmengen $A, B, C, D, E$ einer Grundmenge $X$ zum Beispiel den Ausdruck $A^{c} \cup B ∖ C \cup D \cap E$ als $(A^{c}) \cup (B ∖ C) \cup (D \cap E)$ lesen. Im Zweifel schreibt man aber lieber eine Klammer zu viel um Verwirrungen zu vermeiden.

$PIC$

Figur 1.4: Schnitt, Vereinigung, Komplement beziehungsweise symmetrische Differenz von

P, Q

. Skizzen dieser Art nennen sich auch Venndiagramme.

$PIC$

Figur 1.5: Das Komplement

P^{c} = X ∖ P

von

P

X

Übung 1.17 (Distributivgesetze).

Zeigen Sie die folgenden Distributivgesetze:

(i): Seien $A, B, C$ Aussagen. Zeigen Sie $\begin{array}{l} (A \lor B) \land C \Leftrightarrow (A \land C) \lor (B \land C) \\ (A \land B) \lor C \Leftrightarrow (A \lor C) \land (B \lor C) \end{array}$
(ii): Seien $P, Q, R$ Mengen. Zeigen Sie $\begin{array}{l} (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{array}$

Können Sie auch Kommutativ- und Assoziativgesetze formulieren?

Eine Teillösung.

Als Illustration davon, wie man hier vorgehen kann, wollen wir den ersten Teil von (i) lösen. Angenommen die Aussage $(A \lor B) \land C$ ist wahr. Dann stimmt $C$ und es stimmt $A$ oder $B$ . Angenommen $A$ stimmt. Dann ist $A \land C$ wahr und somit auch die Aussage $(A \land C) \lor (B \land C)$ . Genauso geht man vor, wenn $B$ stimmt.

Angenommen die Aussage $(A \land C) \lor (B \land C)$ ist wahr. Dann gilt $A \land C$ oder $B \land C$ . In erstem Fall stimmen die Aussagen $A$ (und damit auch $A \lor B$ ) und $C$ und also folgt $(A \lor B) \land C$ . Der zweite Fall ist analog.

Die Kommutativgesetze der Aussagenlogik lauten

\begin{array}{l} A \land B & \Leftrightarrow B \land A, \\ A \lor B & \Leftrightarrow B \lor A . \end{array}

Die Assoziativgesetze lauten

\begin{array}{l} (A \land B) \land C & \Leftrightarrow A \land (B \land C), \\ (A \lor B) \lor C & \Leftrightarrow A \lor (B \lor C) . \end{array}

Übung 1.18 (Gesetze von De Morgan).

Seien $P, Q$ Teilmengen einer Grundmenge $X$ . Zeigen Sie den folgenden Spezialfall der De Morganschen Gesetze:

\begin{array}{l} {(P \cup Q)}^{c} = P^{c} \cap Q^{c}, \\ {(P \cap Q)}^{c} = P^{c} \cup Q^{c} . \end{array}

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

Wir verallgemeinern nun zwei Begriffe aus Definition 1.16:

Definition 1.19 (Beliebige Vereinigungen und Schnitte).

Sei $𝒜$ eine Kollektion von Mengen. Dann definieren wir die Vereinigung der Mengen in $𝒜$ als

\begin{array}{l} ⋃_{A \in 𝒜} A = {x ∣ \exists A \in 𝒜 : x \in A} . \end{array}

Falls $𝒜$ eine nicht-leere Kollektion von Mengen ist, so definieren wir auch den Durchschnitt über alle Mengen in $𝒜$ durch

\begin{array}{l} ⋂_{A \in 𝒜} A = {x ∣ \forall A \in 𝒜 : x \in A} \end{array}

Falls wir die Vereinigung nicht über alle Mengen in $𝒜$ nehmen wollen, sondern nur über solche, die eine gewisse Eigenschaft $E (A)$ erfüllen, dann schreiben wir dafür auch $⋃_{A \in 𝒜 : E (A)} A$ und analog für den Durchschnitt. Falls $𝒜 = {A_{1}, A_{2}, \dots}$ , dann schreiben wir auch

\begin{array}{l} ⋃_{n \geq 1} A_{n} = ⋃_{n = 1}^{\infty} A_{n} = ⋃_{A \in 𝒜} A = {x ∣ \exists n \in ℕ : x \in A_{n}} \end{array}

und

\begin{array}{l} ⋂_{n \geq 1} A_{n} = ⋂_{n = 1}^{\infty} A_{n} = ⋂_{A \in 𝒜} A = {x ∣ \forall n \in ℕ : x \in A_{n}} . \end{array}

Wir bemerken, dass wir den Durchschnitt $⋂_{A \in \emptyset} A$ nicht definieren wollen. Würden wir obige Definition in diesem Fall anwenden, so erhielten wir die „Zusammenfassung aller Objekte unserer Anschauung und unseres Denkes“ im Sinne des eingangs erwähnten Zitats von Georg Cantor. Wir wollen diese Zusammenfassung nicht betrachten und auch kein Symbol dafür einführen. Falls wir aber im Rahmen einer Diskussion nur Teilmengen einer bestimmten vorgegebenen Grundmenge $X$ betrachten, so werden wir den Durchschnitt $⋂_{A \in \emptyset} A$ als $X$ definieren. Dies ist mit den Aussagen in folgender Übung kompatibel.

Wichtige Übung 1.20 (De Morgansche Gesetze).

Sei $𝒜$ eine Kollektion von Teilmengen einer Grundmenge $X$ . Zeigen Sie die allgemeine Form der De Morganschen Gesetze:

\begin{array}{l} (⋃_{A \in 𝒜} A)^{c} & = ⋂_{A \in 𝒜} A^{c} \\ (⋂_{A \in 𝒜} A)^{c} & = ⋃_{A \in 𝒜} A^{c} . \end{array}

Hinweis.

Dieses Gesetz entspricht der Dualität der Quantoren $\forall$ und $\exists$ in (1.7).

Übung 1.21.

Was ist die Menge

\begin{array}{l} ⋂_{n = 1}^{\infty} {x \in ℝ | - \frac{1}{n} \leq x \leq \frac{1}{n}}, \end{array}

wobei $n$ wie in Definition 1.19 über alle natürlichen Zahlen läuft, und wie nennen wir dies?

Hinweis.

Wir haben dieses Prinzip bereits in Abschnitt 1.1 kurz besprochen.

Für unsere Zwecke wird folgende Definition ebenfalls nützlich sein:

Definition 1.22 (Disjunktheit).

Zwei Mengen $A, B$ heissen disjunkt, falls $A \cap B = {}$ . In diesem Fall wird ihre Vereinigung $A \cup B$ disjunkte Vereinigung genannt und auch als $A ⊔ B$ geschrieben. Für eine Kollektion $𝒜$ von Mengen, sagen wir, dass die Mengen in $𝒜$ paarweise disjunkt sind, falls für alle $A_{1}, A_{2} \in 𝒜$ mit $A_{1} \neq A_{2}$ gilt $A_{1} \cap A_{2} = {}$ . Die Vereinigung der Mengen in $𝒜$ wird dann auch disjunkte Vereinigung genannt und wird in diesem Fall auch oft als $⨆_{A \in 𝒜} A$ geschrieben.

Wir wenden uns nun einer weiteren, intuitiv vielleicht bekannten, Mengenkonstruktion zu:

Definition 1.23 (Kartesisches Produkt).

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

\begin{array}{l} X \times Y = {(x, y) ∣ x \in X und y \in Y} . \end{array}

Allgemeiner ist das kartesische Produkt von $n$ -Mengen $X_{1}, X_{2}, \dots, X_{n}$ definiert als

\begin{array}{l} X_{1} \times X_{2} \times \dots \times X_{n} = {(x_{1}, x_{2}, \dots, x_{n}) ∣ x_{1} \in X_{1}, x_{2} \in X_{2}, \dots, x_{n} \in X_{n}} . \end{array}

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

Graphisch (meist schematisch) wird das kartesische Produkt $X \times Y$ zweier Mengen $X$ , $Y$ wie in folgendem Bild dargestellt.

$PIC$

Figur 1.6: Zwei Darstellungen von

X \times Y

Wir wollen kurz ein paar Beispiele dieser Konstruktion erwähnen.

Beispiel 1.24 (Einige kartesische Produkte).

Falls $X = {0, 1}$ ist, dann ist

\begin{array}{l} X^{2} = {0, 1}^{2} = {(0, 1), (1, 0), (0, 0), (1, 1)} . \end{array}

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

Übung 1.25 (Digitale Uhr).

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

Übung 1.26 (Schnitte von Rechtecken).

Seien $X, Y$ Mengen und $A, A^{'}$ Teilmengen von $X$ , $B, B^{'}$ Teilmengen von $Y$ . Zeigen Sie die Formel

\begin{array}{l} (A \times B) \cap (A^{'} \times B^{'}) = (A \cap A^{'}) \times (B \cap B^{'}) . \end{array}

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

Unsere vorerst letzte Konstruktion von Mengen ist in der nächsten Definition gegeben:

Definition 1.27 (Potenzmenge).

Für eine Menge $X$ ist die Potenzmenge $𝒫 (X)$ durch die Menge all ihrer Teilmengen gegeben, das heisst

\begin{array}{l} 𝒫 (X) = {Q ∣ Q ist eine Menge und Q \subseteq X} . \end{array}

Übung 1.28.

Bestimmen Sie $𝒫 ({})$ und $𝒫 (𝒫 ({}))$ .

Eine Lösung zu Ersterem.

Ist $Q$ eine Teilmenge von ${}$ , so muss jedes Element, das in $Q$ liegt, auch in ${}$ liegen. Also muss $Q$ die leere Menge sein. Umgekehrt ist die leere Menge natürlich in der leeren Menge enthalten. Also besteht die Potenzmenge $𝒫 ({})$ der leeren Menge genau aus der Menge ${{}}$ , die ein Element enthält.

Wir empfehlen Ihnen, analog zu Abschnitt 1.3.3 eine Übersicht aller Abkürzungen in der Mengenlehre zusammenzustellen.

Der Grund, warum Obiges die naive Mengenlehre genannt wird, ist, dass sie Anfang des zwanzigsten Jahrhunderts durch die axiomatische Mengenlehre (ZF- oder ZFC-Mengenlehre abhängig von einem weiteren Axiom – ZF steht für Zermelo-Fraenkel) ersetzt wurde. Denn die naive Mengenlehre kann sehr schnell zu Widersprüchen geführt werden:

Beispiel 1.29 (Russell 1903).

Sei $R$ die Menge aller Mengen, die sich nicht selbst enthalten, also

\begin{array}{l} R = {X ∣ X ist eine Menge und X \notin X} . \end{array}

Stellt man nun die Frage, ob $R$ selbst zu $R$ gehören kann, so erhält man „ $R \in R \Leftrightarrow R \notin R$ “. Dies kann aber nicht gelten und ist also ein Widerspruch der naiven Mengenlehre (siehe [Rus03]).

Dieses Beispiel wird Russell-Paradox genannt (siehe auch diesen Link) und ist eine Version des sogenannten Lügner-Paradoxons („Dieser Satz ist falsch.“ oder „Ich lüge immer.“). Es entstand, da wir ohne vernünftige Einschränkungen das Bilden beliebiger neuer Mengen erlaubten. In der axiomatischen Mengenlehre werden nur gewisse Konstruktionen (wie zum Beispiel die Potenzmenge oder die Definition einer Teilmenge in (1.8) anstelle der dritten Annahme der naiven Mengenlehre) erlaubt, was dazu führt, dass die Menge $R$ aus dem Russell-Paradox keine Menge mehr ist. Dies löst den Widerspruch auf: $R$ kann sich somit nicht selbst enthalten, da $R$ ja nur Mengen enthält. $R$ wird in der axiomatischen Mengenlehre eine Klasse genannt. Weiters dürfen Klassen nicht als Elemente von Mengen oder Klassen auftreten.

Im folgenden bedienen wir uns der naiven Mengenlehre, da wir die Zeit nicht aufbringen können, die axiomatische Mengenlehre ausreichend zu besprechen und da wir auf jeden Fall nur “vernünftige” Mengenkonstruktionen verwenden werden. (Dies macht vom streng logischen Standpunkt wenig Sinn, ist aber ein notwendiger Kompromiss.)

Übung 1.30 (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?

Hinweis.

Die Aussage ist nicht paradox und der zu findende Ausweg ist analog zur obigen Auflösung des Russell-Paradoxes.

1.4.2 Abbildungen

Der Begriff der Funktion ist für die Analysis, die Lineare Algebra, die Mathematik allgemein und ihre Anwendungen unentbehrlich.

Definition 1.31 (Funktionen und erste dazugehörige Begriffe).

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

Zwei Funktionen $f_{1} : X_{1} \to Y_{1}$ und $f_{2} : X_{2} \to Y_{2}$ gelten nur dann als gleich, falls die Definitionsbereiche $X_{1} = X_{2}$ übereinstimmen, die Wertebereiche $Y_{1} = Y_{2}$ übereinstimmen, und natürlich auch $f_{1} (x) = f_{2} (x)$ für alle $x \in X_{1}$ gilt.

Das Bild einer Funktion $f : X \to Y$ ist die Menge

\begin{array}{l} f (X) = {y \in Y ∣ \exists x \in X : y = f (x)} . \end{array}

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

\begin{array}{l} f (A) = f |_{A} (A) = {y \in Y ∣ \exists x \in A : y = f (x)} . \end{array}

Oft, aber bei weitem nicht immer, wird eine Funktion durch eine Formel wie zum Beispiel $y = x^{2}$ definiert. Wir wollen aber betonen, dass ohne Angabe des Definitionsbereichs und des Wertebereichs die Definition der Funktion unvollständig wäre (siehe auch Beispiel 1.35). Wir diskutieren hier kurz geläufige Art und Weisen, diesen Mangel zu beheben. Ist $f : X \to Y$ eine Funktion, so schreibt man auch

\begin{array}{l} f : X \to Y, x \mapsto f (x) \end{array}

oder

\begin{array}{l} f : X & \to Y \\ x & \mapsto f (x), \end{array}

wobei $f (x)$ eine konkrete Formel sein könnte. Beispielsweise wäre $f : ℝ \to ℝ, x \mapsto x^{2}$ eine vollständig definierte Funktion in dieser Notation. Alternativ schreibt man auch

\begin{array}{l} x \in X \mapsto f (x) \in Y, \end{array}

also zum Beispiel $x \in ℝ \mapsto x^{2} \in ℝ$ , und hat auch hier Definitions- und Wertebereich angegeben. Wir sprechen „ $\mapsto$ “ unter anderem als „wird abgebildet auf“ aus.

Wir wollen auch noch kurz den Begriff „wohldefiniert“ erwähnen. Angenommen wir wollen $X$ als Definitionsbereich und $Y$ als Wertebereich verwenden und haben auch bereits ausgesprochen, wie wir jedem $x \in X$ ein $y \in Y$ zuordnen wollen. Aber vielleicht wissen wir noch nicht genau, ob oder warum diese Zuordnung für jedes $x$ auch wirklich ein zugeordnets $y \in Y$ findet. Oder vielleicht wissen wir noch nicht, warum dieses $y \in Y$ auch durch $x \in X$ eindeutig bestimmt wird. Beides sind aber fundamentale notwendige Forderung an einer Funktion $f : X \to Y$ . Also wird einer der nächsten Schritte der Diskussion der Beweis dieser Forderungen sein. In diesem Zusammenhang sagen wir, dass $f$ wohldefiniert ist, wenn wir eben zeigen konnten, dass die gewählte Zuordnung tatsächlich jedem $x \in X$ ein eindeutig bestimmtes $y \in Y$ zuordnet.

Also wenn wir von einer wohldefinierten Funktion $f : X \to Y$ sprechen, dann wollen wir damit die notwendige Eigenschaft einer Funktion, dass diese jedem $x \in X$ ein eindeutig bestimmtes $y \in Y$ zuordnet, betonen. Aber formal gesehen kann das Wort „wohldefiniert“ in der Aussage „ $f : X \to Y$ ist eine wohldefinierte Funktion.“ ersatzlos gestrichen werden, ohne dass sich der logische Inhalt der Aussage ändern würde.

Beispiel 1.32 (Erste Funktionen).

(a)

Sei

X

eine Menge. Die Identitätsabbildung

{id}_{X} : X \to X

ist die Funktion definiert durch

{id}_{X} (x) = x

für alle

x \in X

(b)

Seien

X, Y

Mengen und sei

y_{0} \in Y

. Dann ist

f : X \to Y

definiert durch

f (x) = y_{0}

für alle

x \in X

eine Funktion. Solche Funktionen werden konstante Funktionen genannt.

(c)

Sei

A \subseteq X

eine Teilmenge. Die Funktion

\begin{array}{l} 𝟙_{A} : X & \to {0, 1} \\ 𝟙_{A} (x) & = {\begin{matrix} 0 & für x \notin A \\ 1 & für x \in A \end{matrix} \end{array}

wird die charakteristische Funktion von $A$ genannt. Das Bild von $𝟙_{A}$ ist genau dann ganz ${0, 1}$ , wenn die Menge $A$ weder leer noch ganz $X$ ist In der Tat ist $0 \in 𝟙_{A} (X)$ genau dann falls es ein $x_{0} \in X ∖ A$ (wie in der ersten Zeile der Definition von $𝟙_{A}$ ) gibt, und $1 \in 𝟙_{A} (X)$ genau dann wenn es ein $x_{1} \in A$ (wie in der zweiten Zeile) gibt.. Eine zweite ebenso übliche Notation für eine characteristische Funktion ist $χ_{A} = 𝟙_{A}$ .

(d)

Für zwei Mengen

X_{1}, X_{2}

definieren wir die Projektionen

\begin{array}{l} π_{1} : X_{1} \times X_{2} \to X_{1} \\ π_{1} ((x_{1}, x_{2})) = x_{1} \end{array}

und

\begin{array}{l} π_{2} : X_{1} \times X_{2} \to X_{2} \\ π_{2} ((x_{1}, x_{2})) = x_{2} . \end{array}

Das Bild von $π_{1}$ ist $X_{1}$ , falls $X_{2}$ nicht leer ist, und ebenso ist $π_{2} (X_{1} \times X_{2}) = X_{2}$ , falls $X_{1} \neq {}$ . Wir schreiben manchmal auch $π_{X_{1}}$ anstelle von $π_{1}$ und $π_{X_{2}}$ anstelle von $π_{2}$ .

$PIC$

Definition 1.33 (Drei Eigenschaften von Funktionen).

Sei $f : X \to Y$ eine Funktion.

•

Die Funktion

f

heisst injektiv oder eine Injektion falls für alle

x_{1}, x_{2} \in X

gilt, dass

f (x_{1}) = f (x_{2}) \Rightarrow x_{1} = x_{2}

•

Die Funktion

f

ist surjektiv, eine Surjektion oder eine Funktion von

X

auf

Y

, falls es zu jedem

y \in Y

ein

x \in X

mit

f (x) = y

gibt.

•

Die Funktion

f

heisst bijektiv, eine Bijektion oder eine eineindeutige Abbildung, falls

f

surjektiv und injektiv ist.

Eine Funktion $f : X \to Y$ ist also nicht injektiv, falls zwei verschiedene Elemente $x_{1}, x_{2} \in X$ existieren mit $f (x_{1}) = f (x_{2})$ . Des Weiteren ist $f$ surjektiv genau dann wenn das Bild $f (X)$ der Funktion (siehe Definition 1.31) gleich $Y$ ist.

Applet 1.34 (Funktionen auf Mengen mit höchstens drei Elementen).

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

(*)

Die vielleicht eigenartigste Frage ist, welche Eigenschaften die Funktion von der leeren Menge zur leeren Menge besitzt. Folgt man stur der Definition der Begriffe (was sonst sollte man machen) so erkennt man, dass diese Funktion injektiv, surjektiv, und daher auch bijektiv ist. Doch ist diese Funktion auch konstant? Dies hängt davon ab, welche der beiden Aussagen man als die Definition für eine konstante Funktion ansieht:

\begin{array}{l} \forall x_{1}, x_{2} \in X : f (x_{1}) = f (x_{2}) \\ \exists y \in Y : \forall x \in X : f (x) = y \end{array}

Diese beiden Aussagen über eine Funktion $f : X \to Y$ sind äquivalent, sobald $Y$ nicht die leere Menge ist, und könnten beide als Definition des Begriffs „konstant“ angesehen werden. Doch für den eigenartigen Spezialfall der „leeren Funktion“, welche auf der leeren Menge definiert ist und Werte in der leeren Menge annimmt, sind diese beiden Aussagen unterschiedlich. Da wir ab nun diesen höchst eigenartigen Spezialfall einfach ignorieren und nur Funktionen auf nicht-leeren Mengen betrachten wollen, müssen wir uns nicht für eine der beiden Definitionen entscheiden.

Im folgenden Beispiel schreiben wir $ℝ_{\geq 0} = {x \in ℝ ∣ x \geq 0}$ für die Menge der nicht-negativen reellen Zahlen.

Beispiel 1.35 (Ist Quadrieren bijektiv?).

Ist $x \mapsto x^{2}$ 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:

(a): Die Funktion $f : ℝ_{\geq 0} \to ℝ, x \mapsto x^{2}$ ist injektiv, denn falls $x, y$ zwei nicht-negative Zahlen mit $x < y$ sind, so gilt auch $x^{2} < y^{2}$ . Genauso folgt aus $x > y$ , dass $x^{2} > y^{2}$ ist. Sie ist jedoch nicht surjektiv: $- 1$ ist nicht Element des Bildes von $f$ , da Quadrate von reellen Zahlen niemals negativ sind.
(b): Die Funktion $f : ℝ \to ℝ_{\geq 0}, x \mapsto x^{2}$ ist surjektiv (es existiert eine Wurzel), sie ist aber nicht injektiv, denn $f (1) = 1 = {(- 1)}^{2} = f (- 1)$ .
(c): Die Funktion $f : ℝ \to ℝ, x \mapsto x^{2}$ ist weder injektiv noch surjektiv.
(d): Die Funktion $f : ℝ_{\geq 0} \to ℝ_{\geq 0}, x \mapsto x^{2}$ ist bijektiv.

Wir werden diese Aussagen später noch ausführlicher beweisen (d.h. auf die noch einzuführenden Axiome der reellen Zahlen zurückführen).

Sei $f : X \to Y$ eine bijektive Funktion. Dann existiert zu jedem $y \in Y$ ein eindeutig bestimmtes $x \in X$ , so dass $y = f (x)$ : Da $f$ surjektiv ist, existiert ein solches $x$ und da $f$ injektiv ist, kann es höchstens ein solches $x$ geben. Daher rührt auch die Bezeichnung „eineindeutige Abbildung“ für eine Bijektion. Insbesondere kann man wie folgt eine Abbildung definieren.

Definition 1.36 (Umkehrabbildung).

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

An dieser Stelle sollte man noch erwähnen, dass $f^{- 1}$ nicht durch eine Formel gegeben sein muss, selbst wenn $f$ durch eine Formel definiert war. Des Weiteren wollen wir anmerken, dass sich allgemeiner für eine injektive Funktion $f : X \to Y$ eine Umkehrabbildung mit eingeschränktem Definitionsbereich $f^{- 1} : f (X) \to X$ definieren lässt. In der Tat ist die Funktion $x \in X \mapsto f (x) \in f (X)$ (also „ $f$ mit eingeschränktem Wertebereich“) bijektiv.

Definition 1.37 (Verknüpfung).

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

Wir bemerken, dass für eine bijektive Abbildung $f : X \to Y$ und ihre Umkehrabbildung $f^{- 1} : Y \to X$ die Identitäten

\begin{array}{l} f \circ f^{- 1} = {id}_{Y}, f^{- 1} \circ f = {id}_{X} \end{array}

erfüllt sind – eben per Konstruktion von $f^{- 1}$ (siehe auch Übung 1.42).

Beispiel 1.38 (Assoziativgesetz für Verknüpfungen).

Seien $f : X_{1} \to X_{2}$ , $g : X_{2} \to X_{3}$ , $h : X_{3} \to X_{4}$ Funktionen. Dann können wir sowohl die Funktion $h \circ (g \circ f) : X_{1} \to X_{4}$ als auch die Funktion $(h \circ g) \circ f : X_{1} \to X_{4}$ betrachten. Glücklicherweise sind die Klammern irrelevant, denn es gilt

\begin{array}{l} h \circ (g \circ f) (x) = h (g \circ f (x)) = h (g (f (x)) = h \circ g (f (x)) = (h \circ g) \circ f (x) \end{array}

für alle $x \in X_{1}$ . Deswegen schreiben wir einfach $h \circ g \circ f : X_{1} \to X_{4}$ .

Beispiel 1.39 (Verknüpfung ist nicht kommutativ).

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

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

Sowohl die Eigenschaften in Definition 1.33 als auch die Verknüpfung in Definition 1.37 sind so grundlegend, dass wir nicht umhin kommen, einige fundamentale Tatsachen zu beweisen:

Lemma 1.40 (Eigenschaften von Verknüpfungen).

Seien $f : X \to Y$ und $g : Y \to Z$ Funktionen.

(i): Falls $f$ und $g$ injektiv sind, dann ist auch $g \circ f$ injektiv.
(ii): Falls $f$ und $g$ surjektiv sind, dann ist auch $g \circ f$ surjektiv.
(iii): Falls $f$ und $g$ bijektiv sind, dann ist auch $g \circ f$ bijektiv und es gilt ${(g \circ f)}^{- 1} = f^{- 1} \circ g^{- 1}$ .

Beweis.

(i): Angenommen $f$ und $g$ sind injektiv und $g \circ f (x_{1}) = g \circ f (x_{2})$ für Elemente $x_{1}, x_{2} \in X$ . Wegen $g \circ f (x_{1}) = g (f (x_{1}))$ und $g \circ f (x_{2}) = g (f (x_{2}))$ muss $f (x_{1}) = f (x_{2})$ gelten, da $g$ injektiv ist. Da $f$ injektiv ist, folgt $x_{1} = x_{2}$ (aus $f (x_{1}) = f (x_{2})$ ). Wir haben also gesehen, dass $x_{1}, x_{2} \in X$ und $g \circ f (x_{1}) = g \circ f (x_{2})$ impliziert, dass $x_{1} = x_{2}$ . Dies bedeutet aber genau, dass $g \circ f$ injektiv ist.

(ii): Angenommen $f$ und $g$ sind surjektiv und $z \in Z$ ist ein beliebiges Element. Da $g$ surjektiv ist, können wir ein $y \in Y$ mit $g (y) = z$ wählen. Da auch $f$ surjektiv ist, gibt es ein $x \in X$ mit $f (x) = y$ und damit $g \circ f (x) = g (f (x)) = g (y) = z$ . Also existiert für jedes Element $z \in Z$ ein Element $x \in X$ mit $g \circ f (x) = z$ und daher ist $g \circ f$ surjektiv.

(iii): Angenommen $f$ und $g$ sind bijektiv. Der erste Teil von (iii) folgt direkt, denn nach (i) ist $g \circ f$ injektiv und nach (ii) surjektiv. Wir verifizieren nun die behauptete Formel. Sei $z \in Z$ . Wir müssen zeigen, dass $f^{- 1} (g^{- 1} (z)) \in X$ ein Punkt (und damit der Punkt) ist, der unter $g \circ f$ auf $z$ abgebildet wird. Tatsächlich erfüllen die Inversen $f^{- 1} : Y \to X$ and $g^{- 1} : Z \to Y$ die Aussagen $f (f^{- 1} (y)) = y$ für alle $y \in Y$ und $g (g^{- 1} (z)) = z$ für alle $z \in Z$ . Weswegen $f^{- 1} (g^{- 1} (z)) \in X$ und

\begin{array}{l} g \circ f (f^{- 1} (g^{- 1} (z)) = g (f (f^{- 1} (g^{- 1} (z)))) = g (g^{- 1} (z)) = z \end{array}

für alle $z \in Z$ gilt. Damit ist nun auch (iii) bewiesen.

■

Mit ein wenig Übung und dem aktiven Wissen, wie denn eigentlich Injektivität, Surjektivität, und Bijektivität (in Definition 1.33) definiert sind, schreibt sich obiger Beweis fast von selbst: Wenn wir zum Beispiel im Beweis von (i) zeigen wollen, dass $g \circ f$ injektiv ist, dann beginnen wir automatisch auf Grund der Definition (der zu zeigenden Aussage) mit der Annahme $g (f (x_{1})) = g (f (x_{2}))$ für $x_{1}, x_{2} \in X$ . Zu diesem Zeitpunkt können wir aber nur eine einzige Annahme, nämlich die Injektivität von $g$ verwenden, um $f (x_{1}) = f (x_{2})$ zu erhalten. Danach haben wir eine einzige Annahme noch nicht verwendet, nämlich die Injektivität von $f$ , und dies ist auch genau die Annahme aus der wir die gewünschte Aussage $x_{1} = x_{2}$ schliessen können. Der Beweis von (ii) ergibt sich auf ähnliche Weise. Gewissermassen sind die Definitionen für die Begriffe in derartigen Beweise einfach gebaute Bauteile oder Schichten, die eigentlich nur auf eine Art und Weise zu einem Ganzem – dem Beweis – zusammgengebaut werden können.

Wir werden klare Fälle (und nur ganz klare Fälle) von solchen Beweisen hier im eSkript mittels dem Emoji matrbeweis als „Matrjoschkabeweise“ kennzeichnen, sie sollten dies als Einladung sehen diese Beweise nach Wiederholung der Definitionen selbst zu schreiben.

In der folgenden Übung kombinieren wir die Begriffe aus den Definitionen 1.33 und 1.37 ein weiteres Mal:

Wichtige Übung 1.41 (Weitere Eigenschaften von Verknüpfungen).

Seien $f : X \to Y$ und $g : Y \to Z$ Funktionen.

(i): Zeigen Sie, dass $g$ surjektiv ist, falls $g \circ f$ surjektiv ist. Überzeugen Sie sich davon, dass in diesem Fall $f$ nicht unbedingt surjektiv sein muss.
(ii): Zeigen Sie, dass $f$ surjektiv ist, falls $g \circ f$ surjektiv und $g$ injektiv ist.
(iii): Zeigen Sie, dass $f$ injektiv ist, falls $g \circ f$ injektiv ist. Überzeugen Sie sich davon, dass in diesem Fall $g$ nicht unbedingt injektiv sein muss.
(iv): Zeigen Sie, dass $g$ injektiv ist, falls $g \circ f$ injektiv ist und $f$ surjektiv ist.

Teillösung.

Angenommen $g \circ f$ ist surjektiv wie in (i). Dann existiert für jedes $z \in Z$ ein $x \in X$ mit $g \circ f (x) = z$ , womit auch $g (y) = z$ für $y = f (x) \in Y$ gilt. Dies beweist die allgemeine Behauptung in (i). Falls nun zusätzlich $g$ injektiv ist wie in (ii), so ist $g$ bijektiv und Lemma 1.40 (ii) zeigt, dass $f = g^{- 1} \circ (g \circ f)$ surjektiv ist. Bei genauer Untersuchung von diesem Argument lässt sich auch ein einfaches Beispiel wie in (i) finden, wobei man sogar $X = Z = {1}$ und $Y = {1, 2}$ setzen kann.

Wichtige Übung 1.42 (Bijektivität und Existenz einer Umkehrabbildung).

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

Lösung.

Wir nehmen an, dass $f : X \to Y$ und $g : Y \to X$ sowohl $g \circ f = {id}_{X}$ als auch $f \circ g = {id}_{Y}$ erfüllen. Nach Übung 1.41 folgt, dass $f$ daher bijektiv ist. Des Weiteren gilt für $y \in Y$ und $x = g (y) \in X$ , dass $f (x) = f \circ g (y) = y$ und daher auch $x = f^{- 1} (y)$ . Da dies für alle $y \in Y$ gilt, erhalten wir $g = f^{- 1}$ . Vertauschen wir die Rollen von $f$ und $g$ , so erhalten wir, dass $g$ bijektiv ist und $f = g^{- 1} = {(f^{- 1})}^{- 1}$

Gewisse Objekte bezeichnet man als kanonisch oder natürlich, wenn sie unabhängig von jeglicher Wahl sind. Dieser Begriff drängt sich insbesondere in der Linearen Algebra auf. Wir möchten dies an einem Beispiel erläutern.

Beispiel 1.43 (Kanonische Abbildungen).

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

\begin{array}{l} ι : A \to X, x \mapsto x \end{array}

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

Wir untersuchen das konkrete Beispiel $A = {a}$ und $X = {a, b, c}$ . Dann gibt es $3$ verschiedene injektive Abbildungen $A \to X$ . Nebst der Inklusionsabbildung (die $a$ auf $a$ abbildet) sind dies

•

die Funktion

A \to X

mit

a \mapsto b

und

•

die Funktion

A \to X

mit

a \mapsto c

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

Ein weiteres interessanteres Beispiel bilden die in Beispiel 1.32 definierten kanonischen Projektionen $π_{1} : X_{1} \times X_{2} \to X_{1}$ und $π_{2} : X_{1} \times X_{2} \to X_{2}$ für zwei Mengen $X_{1}, X_{2}$ .

Für zwei Mengen $X, Y$ wird die Menge aller Abbildungen von $X$ nach $Y$ als $Y^{X}$ geschrieben, formaler

\begin{array}{l} Y^{X} = {f ∣ f : X \to Y ist eine Funktion} . \end{array}

Grund für die Notation ist unter anderem die folgende Behauptung: Falls $X$ und $Y$ endliche Mengen sind mit $m$ resp. $n$ Elementen für zwei natürliche Zahlen $m, n \in ℕ$ , so hat $Y^{X}$ genau $n^{m}$ Elemente (siehe auch Abschnitt 1.7).

1.4.3 Graph einer Abbildung

Mit Hilfe des folgenden Begriffs lässt sich der Funktionsbegriff, der in Definition 1.31 in Worten eingeführt wurde, formalisieren und auch besser visualisieren:

Definition 1.44 (Graph einer Funktion).

Sei $f : X \to Y$ eine Funktion. Der Graph von $f$ ist

\begin{array}{l} graph (f) = {(x, y) \in X \times Y ∣ y = f (x)} \subseteq X \times Y . \end{array}

Der Graph einer Funktion enthält viel Information über die Funktion selbst. Unter anderem lässt sich aus dem Graphen bereits erkennen, ob die Funktion wohldefiniert ist (das heisst in der Tat eine Funktion ist) oder nicht. Beispielsweise kann folgende Teilmenge von $X \times Y$ nicht der Graph einer Funktion von $X$ nach $Y$ sein:

$PIC$

Figur 1.7: Die hier dargestellte Teilmenge von

X \times Y

ist nicht der Graph einer Funktion von

X

nach

Y

. Denn man müsste dem grün markierten Punkt

x_{1}

X

vier verschiedene Punkte in

Y

zuweisen, was der Definition einer Funktion widerspricht. Genauso problematisch ist der Punkt

x_{2} \in X

, dem gar kein Punkt zugewiesen wird. Standardmässig nimmt man bei der Darstellung des Graphen einer Funktion den Definitionbereich als die Horizontale und den Wertebereich als die Vertikale.

Welche Teilmengen von $X \times Y$ Graphen einer Funktion sein können und welche nicht, wollen wir im Folgenden erklären. Wir beginnen damit, das in Figur 1.7 aufgetauchte Problem formal zu interpretieren:

Übung 1.45 (Graphen und Projektion auf den Definitionsbereich).

(i): Sei $f : X \to Y$ eine Funktion. Wie in Beispiel 1.32 bezeichnen wir mit $π_{1} : X \times Y \to X$ die Projektion auf $X$ , die durch $(x, y) \mapsto x$ definiert ist und mit $π_{2} : X \times Y \to Y$ die Projektion auf $Y$ . Zeigen Sie, dass $π_{1} |_{graph (f)} : graph (f) \to X$ bijektiv ist und finden Sie die Umkehrabbildung. Beweisen Sie des Weiteren die Identität $\begin{array}{l} π_{2} \circ {(π_{1} |_{graph (f)})}^{- 1} = f, \end{array}$
welche erklärt, wie man aus dem Graphen einer Funktion, die Funktion zurückerhalten kann.
(ii): Zeigen Sie, dass eine Teilmenge $Γ \subseteq X \times Y$ genau dann ein Graph einer Funktion $f : X \to Y$ ist, wenn $π_{1} |_{Γ} : Γ \to X$ bijektiv ist. Verifizieren Sie auch, dass in diesem Fall $f$ eindeutig bestimmt ist.

Hinweis.

Die Aussagen sind im Wesentlichen eine Umformulierung der Definition einer Funktion.

Auch die Eigenschaften aus Definition 1.33 lassen sich im Graphen erkennen. Unter anderem ist ersichtlich, ob eine Funktion injektiv ist oder nicht:

$PIC$

Figur 1.8: Dies ist der Graph einer nicht injektiven Funktion. Der grün markierte Punkt

y

Y

wird unter der Funktion von vier verschiedenen Elementen in

X

angenommen.

$PIC$

Figur 1.9: Dies ist der Graph einer injektiven Funktion. Der grün markierte Punkt

y \in Y

ist das Bild von nur einem Punkt in

X

. Dies ist immer noch der Fall, wenn

y

verschoben wird (bis auf die Tatsache, dass

y

dann vielleicht gar nicht mehr im Bild liegt). In anderen Worten: jede horizontale Linie schneidet den Graphen in höchstens einem Punkt.

Genauso lässt sich beurteilen, ob eine Funktion surjektiv ist oder nicht – siehe Figuren 1.10 und 1.11. Wir formalisieren dies in Übung 1.47.

$PIC$

Figur 1.10: Dies ist der Graph einer nicht-surjektiven Funktion. Der grün markierte Punkt

y

Y

wird unter der Funktion von keinem Element in

X

angenommen.

$PIC$

Figur 1.11: Dies ist der Graph einer surjektiven Funktion. Jede horizontale Linie (wie zum Beispiel jene durch

y_{1}

oder

y_{2}

) schneidet den Graphen in mindestens einem Punkt.

Applet 1.46 (Einschränkungen einer Funktion).

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

Wichtige Übung 1.47 (Eigenschaften des Graphen unter Projektion auf den Wertebereich).

Sei $f : X \to Y$ eine Funktion.

•

Zeigen Sie, dass

f

injektiv ist genau dann, wenn

π_{2} |_{graph (f)}

injektiv ist.

•

Zeigen Sie, dass

f

surjektiv ist genau dann, wenn

π_{2} |_{graph (f)}

surjektiv ist. Intuitiv bedeutet letzteres, dass die Projektion des Graphen

graph (f)

auf

Y

jedes Element erreicht.

•

Angenommen

f

ist bijektiv. Wie findet man den Graphen von

f^{- 1}

Hinweis.

Die Aufgabe lässt sich entweder direkt oder unter Verwendung von Übung 1.45(i) lösen. Den Graph von $f^{- 1}$ erhält man, indem man die Koordinaten jedes Punktes $(x, y) \in graph (f)$ vertauscht.

1.4.4 Bild- und Urbildmengen

Sei $f : X \to Y$ eine Funktion und $A \subseteq X$ eine Teilmenge. Wir verwenden manchmal auch die Notation ${f (x) ∣ x \in A}$ für das Bild $f (A)$ der Teilmenge $A$ wie in Definition 1.31. Ebenso schreiben wir auch

\begin{array}{l} {f (x) ∣ x \in X \land A (x)} = {y ∣ y \in Y \land \exists x \in X : (f (x) = y \land A (x))}, \end{array}

wobei $A (x)$ irgend eine Aussage über Elemente $x$ von $X$ sein kann. In dieser Gleichung haben wir rechts genau nach dem Schema in der dritten Annahme an die Mengenlehre (siehe Abschnitt 1.4.1) eine Menge definiert und verwenden dies, um den kürzeren (und übersichtlicheren) Ausdruck links zu definieren.

Folgende Definition der Urbildmengen ist auch für nicht bijektive Funktionen nützlich:

Definition 1.48 (Urbilder bezüglich einer Funktion).

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

\begin{array}{l} f^{- 1} (B) = {x \in X ∣ f (x) \in B} . \end{array}

Beispielsweise gilt für eine Funktion $f : X \to Y$ , dass $f^{- 1} ({}) = {}$ und $f^{- 1} (Y) = X$ . In der nächsten Übung prüfen wir einige Eigenschaften von Bildmengen und Urbildmengen.

Wichtige Übung 1.49 (Verhalten von Bildern und Urbildern unter Mengenoperationen).

Gegeben sei eine Funktion $f : X \to Y$ und Teilmengen $A, A^{'} \subseteq X$ und $B, B^{'} \subseteq Y$ .

(i): Zeigen Sie, dass $f (f^{- 1} (B)) \subseteq B$ gilt. Unter welcher Bedingung an $f$ gilt auf jeden Fall Gleichheit?
(ii): Zeigen Sie, dass $f^{- 1} (f (A)) \supseteq A$ gilt. Unter welcher Bedingung an $f$ gilt auf jeden Fall Gleichheit?
(iii): Zeigen Sie die Gleichungen $\begin{array}{l} f (A \cup A^{'}) = f (A) \cup f (A^{'}), f^{- 1} (B \cup B^{'}) = f^{- 1} (B) \cup f^{- 1} (B^{'}) . \end{array}$
(iv): Zeigen Sie, dass $f (A \cap A^{'}) \subseteq f (A) \cap f (A^{'})$ und dass Gleichheit gilt, wenn $f$ injektiv ist. Verifzieren Sie, dass in diesem Fall auch $f (A ∖ A^{'}) = f (A) ∖ f (A^{'})$ gilt.
(v): Zeigen Sie, dass $f^{- 1} (B \cap B^{'}) = f^{- 1} (B) \cap f^{- 1} (B^{'})$ und $f^{- 1} (Y ∖ B) = X ∖ f^{- 1} (B)$ gelten.
(vi): Verallgemeinern Sie die Regeln $f^{- 1} (B \cup B^{'}) = f^{- 1} (B) \cup f^{- 1} (B^{'})$ und $f^{- 1} (B \cap B^{'}) = f^{- 1} (B) \cap f^{- 1} (B^{'})$ 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.

Teillösung.

Wir beweisen Teil (iv). Sei $f : X \to Y$ eine Funktion, $A, A^{'} \subseteq X$ Teilmengen des Definitionsbereichs und $a \in A \cap A^{'}$ , dann gilt $f (a) \in f (A) \cap f (A^{'})$ . Dies beweist bereits $f (A \cap A^{'}) \subseteq f (A) \cap f (A^{'})$ . Wir nehmen nun zusätzlich an, dass $f$ injektiv ist. Angenommen $y = f (a) = f (a^{'}) \in f (A) \cap f (A^{'})$ für ein $a \in A$ und $a^{'} \in A^{'}$ . Da $f$ injektiv ist, impliziert dies $a = a^{'} \in A \cap A^{'}$ und damit $y \in f (A \cap A^{'})$ . Wir erhalten daher $f (A \cap A^{'}) = f (A) \cap f (A^{'})$ .

Wir nehmen weiterhin an, dass $f$ injektiv ist. Für $a \in A ∖ A^{'}$ gilt dann $f (a) \in f (A) ∖ f (A^{'})$ . In der Tat, da $f$ injektiv ist, folgt aus $f (a) = f (x)$ für ein $x \in X$ die Gleichheit $x = a$ . Da $a \notin A^{'}$ erhalten wir daraus $f (a) \notin f (A^{'})$ . Falls umgekehrt $y \in f (A) ∖ f (A^{'})$ , dann existiert ein $a \in A$ mit $y = f (a)$ und es muss des Weiteren $a \notin A^{'}$ gelten, was $y \in f (A ∖ A^{'})$ impliziert.

Applet 1.50 (Bilder und Urbilder).

Wir betrachten eine Funktion $f : I \to ℝ$ , die auf einem Intervall $I$ in $ℝ$ definiert ist. Je nach Einstellung des Applets wird entweder das Bild $f (A)$ eines Teilintervalls $A = [x_{1}, x_{2}] \subseteq I$ oder das Urbild $f^{- 1} ([y_{1}, y_{2}])$ eines Intervalls $[y_{1}, y_{2}] \subseteq ℝ$ dargestellt.

1.4.5 Partitionen

Der folgende Begriff kann für die Definition von Funktionen durch „Fallunterscheidung“ nützlich sein.

Definition 1.51 (Partition).

Sei $X$ eine Menge und $𝒫$ eine Familie von nicht-leeren, paarweise disjunkten Teilmengen von $X$ , so dass $X = ⨆_{P \in 𝒫} P$ . Dann wird $𝒫$ eine Partition von $X$ genannt.

Folgendes Lemma beschreibt, unter welchen Bedingungen man eine Funktion aus Funktionen auf Teilmengen „ zusammensetzen“ kann:

Lemma 1.52 (Funktionen durch Fallunterscheidungen).

Seien $X$ und $Y$ Mengen und sei $𝒫$ eine Partition von $X$ . Angenommen es ist für jedes $P \in 𝒫$ eine Funktion $f_{P} : P \to Y$ gegeben. Dann existiert eine eindeutige Funktion $f : X \to Y$ , so dass $f |_{P} = f_{P}$ für jedes $P \in 𝒫$ gilt.

Beweis.

Wir definieren die gewünschte Funktion $f : X \to Y$ wie folgt: Sei $x \in X$ . Dann existiert genau ein $P \in 𝒫$ mit $x \in P$ , da $𝒫$ eine Partition ist. Wir setzen nun $f (x) = f_{P} (x)$ und haben also eine Funktion $f : X \to Y$ definiert. Diese erfüllt $f |_{P} = f_{P}$ nach Konstruktion.

Wir zeigen noch die Eindeutigkeit von $f$ . Sei also $g : X \to Y$ eine weitere Funktion mit $g |_{P} = f_{P}$ für alle $P \in 𝒫$ . Sei $x \in X$ ein beliebiges Element und $P \in 𝒫$ das Partitionselement mit $x \in P$ . Dann gilt

\begin{array}{l} g (x) = g |_{P} (x) = f_{P} (x) = f (x) . \end{array}

Da dies für alle $x \in X$ gilt, erhalten wir $g = f$ .

■

Übung 1.53 (Funktionen durch Fallunterscheidungen).

Zeigen Sie, dass die Bedingung in Lemma 1.52, dass $𝒫$ eine Partition ist, notwendig ist, durch Auffinden geeigneter Beispiele:

•

Finden Sie Mengen

X, Y

, eine Kollektion

𝒫

nicht paarweise disjunkter Teilmengen mit

X = ⋃_{P \in 𝒫} P

und Funktionen

f_{P} : P \to Y

für jedes

P \in 𝒫

, so dass keine Funktion

f : X \to Y

mit

f |_{P} = f_{P}

für jedes

P \in 𝒫

existiert.

•

Seien

X

und

Y

Mengen,

𝒫

eine Kollektion paarweise disjunkter Teilmengen mit

X \neq ⋃_{P \in 𝒫} P

und Funktionen

f_{P} : P \to Y

für jedes

P \in 𝒫

gegeben. Zeigen Sie, dass mehrere Funktionen

f : X \to Y

mit

f |_{P} = f_{P}

für jedes

P \in 𝒫

existieren, falls

Y

mehr als ein Element enthält.

1.4.6 Iterationen

Eine Funktion, für die Wertebereich gleich dem Definitionsbereich ist, lässt sich auch mit sich selbst verknüpfen.

Definition 1.54 (Iterationen einer Funktion).

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

\begin{array}{l} f^{\circ 1} = f : X \to X, f^{\circ 2} = f \circ f : X \to X, f^{\circ 3} = f \circ f \circ f : X \to X \end{array}

und rekursiv auch

\begin{array}{l} f^{\circ (n + 1)} = f \circ f^{\circ n} : X \to X \end{array}

für alle natürlichen Zahlen $n \in ℕ$ . Wir sprechen $f^{\circ n}$ auch als „ $f$ hoch $n$ “ aus und setzen des Weiteren $f^{\circ 0} = {id}_{X}$ .

Wir bemerken, dass man die Iteration einer Funktion $f : X \to X$ oft einfach auch durch $f^{n} = f^{\circ n}$ bezeichnet.† Wir wollen zumindest anfangs die Notation $f^{\circ n}$ verwenden, um Verwirrungen mit der $n$ -ten Potenz einer reellwertigen Funktion zu vermeiden.

Übung 1.55 (Beispiele und eine Eigenschaft von Iterationen).

(i): Sei $X = {a, b, c}$ eine Menge mit $3$ verschiedenen Elementen und $f : X \to X$ die Funktion definiert durch $f (a) = b, f (b) = c$ und $f (c) = a$ . Zeigen Sie, dass $f$ bijektiv ist. Beschreiben Sie die Umkehrabbildung und alle Iterationen von $f$ explizit.
(ii): Iterieren Sie die Funktion $f : x \in ℝ \to 3 x \in ℝ$ und beschreiben Sie intuitiv, wie sich $f^{\circ n} (x)$ für ein $x \in ℝ$ und verschiedene $n \in ℕ$ verhält.
(iii): Iterieren Sie die Funktion $f : x \in ℝ \to x^{2} \in ℝ$ und beschreiben Sie intuitiv, wie sich $f^{\circ n} (x)$ für ein $x \in ℝ$ und verschiedene $n \in ℕ$ verhält.
(iv): Sei $X$ eine Menge und $f : X \to X$ eine Transformation auf $X$ . Zeigen Sie, dass für alle $m, n \in ℕ_{0}$ gilt $f^{\circ m} \circ f^{\circ n} = f^{\circ (m + n)}$ .

Eine Teillösung.

Wir erklären hier die Lösung zum letzten Teil. Falls $m = 0$ oder $n = 0$ gilt, gibt es nichts zu zeigen, da $f^{\circ 0} = {id}_{X}$ definiert wurde. Wir verwenden zuerst das Assoziativgesetz in Beispiel 1.38 und die Definition der Iteration um

f^{\circ (m + 1)} = f \circ f^{\circ m} = f^{\circ m} \circ f

(1.9)

zu zeigen. Die erste Gleichung ist bloss unsere Definition der Iteration. Die zweite Gleichung wollen wir mittels vollständiger Induktion beweisen und gilt für $m = 1$ , was den Induktionsanfang darstellt. Falls nun (1.9) bereits für ein $m \in ℕ$ gilt, so erhalten wir gemeinsam mit der Definition

f^{\circ (m + 2)} = f \circ f^{\circ (m + 1)} = f \circ f^{\circ m} \circ f = f^{\circ (m + 1)} \circ f .

Dies beweist (1.9) für alle $m \in ℕ$ mittels vollständiger Induktion.

Wir behaupten nun

f^{\circ (m + n)} = f^{\circ m} \circ f^{\circ n}

(1.10)

für alle $m, n \in ℕ$ und wollen wiederum vollständige Induktion verwenden. Genauer formuliert, wollen wir vollständige Induktion nach $n$ für die Aussage

\forall m \in ℕ : f^{\circ (m + n)} = f^{\circ m} \circ f^{\circ n} .

verwenden.

Nach (1.9) gilt (1.10) für alle $m \in ℕ$ und $n = 1$ , was den Induktionsanfang darstellt. Angenommen (1.10) gilt bereits für alle $m \in ℕ$ und ein $n \in ℕ$ . Dann erhalten wir

\begin{array}{l} f^{\circ (m + n + 1)} = f^{\circ (m + 1)} \circ f^{\circ n} = f^{\circ m} \circ f \circ f^{\circ n} = f^{\circ m} \circ f^{\circ (n + 1)} \end{array}

für alle $m \in ℕ$ , womit der Induktionsschritt und damit auch (1.10) für alle $m, n \in ℕ$ bewiesen ist.

1.4.7 Das Hilbert Hotel

Für eine Abbildung $f : X \to X$ auf einer endlichen Menge $X$ sind Injektivität und Surjektivität äquivalent (siehe Abschnitt 1.7). Für unendliche Mengen ergeben sich jedoch weitere Möglichkeiten, die auf den ersten Blick ungewöhnlich erscheinen könnten.

Beispiel 1.56 (Hilbert Hotel).

Die Abbildung

\begin{array}{l} f : n \in ℕ \mapsto n + 1 \in ℕ \end{array}

ist zwar injektiv aber nicht surjektiv, denn $1 \notin f (ℕ)$ . 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 $n$ ein Hotelzimmer mit der Türnummer $n$ (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:

„Wir bedauern, Ihnen mitzuteilen, dass wir Ihnen ein neues Zimmer zuweisen müssen. Bitte packen Sie ihre Sachen, übergeben Sie diesen Brief dem Gast im nächsten Zimmer und übernehmen Sie dieses Zimmer, sobald es frei ist.“

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 $ℕ \to ℕ$ , die nicht injektiv sind, zum Beispiel

\begin{array}{l} g : ℕ \to ℕ, n \mapsto {\begin{matrix} 1 & falls n = 1 \\ n - 1 & falls n \neq 1 \end{matrix} . \end{array}

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.57 (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 $h : ℕ \to ℕ$ können Sie verwenden, um im Hotel Platz zu beschaffen?

1.4 Mengenlehre und Abbildungen

1.4.1 Naive Mengenlehre

Definition 1.14 (Inklusionen).

Übung 1.15.

Definition 1.16 (Mengenoperationen).

Übung 1.17 (Distributivgesetze).

Übung 1.18 (Gesetze von De Morgan).

Definition 1.19 (Beliebige Vereinigungen und Schnitte).

Wichtige Übung 1.20 (De Morgansche Gesetze).

Übung 1.21.

Definition 1.22 (Disjunktheit).

Definition 1.23 (Kartesisches Produkt).

Beispiel 1.24 (Einige kartesische Produkte).

Übung 1.25 (Digitale Uhr).

Übung 1.26 (Schnitte von Rechtecken).

Definition 1.27 (Potenzmenge).

Übung 1.28.

Beispiel 1.29 (Russell 1903).

Übung 1.30 (Der Barber aus Sevilla).

1.4.2 Abbildungen

Definition 1.31 (Funktionen und erste dazugehörige Begriffe).

Beispiel 1.32 (Erste Funktionen).

Definition 1.33 (Drei Eigenschaften von Funktionen).

Applet 1.34 (Funktionen auf Mengen mit höchstens drei Elementen).

Beispiel 1.35 (Ist Quadrieren bijektiv?).

Definition 1.36 (Umkehrabbildung).

Definition 1.37 (Verknüpfung).

Beispiel 1.38 (Assoziativgesetz für Verknüpfungen).

Beispiel 1.39 (Verknüpfung ist nicht kommutativ).

Lemma 1.40 (Eigenschaften von Verknüpfungen).

Wichtige Übung 1.41 (Weitere Eigenschaften von Verknüpfungen).

Wichtige Übung 1.42 (Bijektivität und Existenz einer Umkehrabbildung).

Beispiel 1.43 (Kanonische Abbildungen).

1.4.3 Graph einer Abbildung

Definition 1.44 (Graph einer Funktion).

Übung 1.45 (Graphen und Projektion auf den Definitionsbereich).

Applet 1.46 (Einschränkungen einer Funktion).

Wichtige Übung 1.47 (Eigenschaften des Graphen unter Projektion auf den Wertebereich).

1.4.4 Bild- und Urbildmengen

Definition 1.48 (Urbilder bezüglich einer Funktion).

Wichtige Übung 1.49 (Verhalten von Bildern und Urbildern unter Mengenoperationen).

Applet 1.50 (Bilder und Urbilder).

1.4.5 Partitionen

Definition 1.51 (Partition).

Lemma 1.52 (Funktionen durch Fallunterscheidungen).

Übung 1.53 (Funktionen durch Fallunterscheidungen).

1.4.6 Iterationen

Definition 1.54 (Iterationen einer Funktion).

Übung 1.55 (Beispiele und eine Eigenschaft von Iterationen).

1.4.7 Das Hilbert Hotel

Beispiel 1.56 (Hilbert Hotel).

Übung 1.57 (Hilberts Bus).

License