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)

(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\left(x\right)$ definiert die Menge der Objekte $\left\{x\mid A\left(x\right)\right\}$, die diese Eigenschaft besitzen (das heisst, die Aussage $A\left(x\right)$ erfüllen).

Manchmal beschreiben wir eine Menge durch eine konkrete Auflistung ihrer Elemente (zum Beispiel in der Form $M=\left\{x_1,x_2,\dots ,x_n\right\}$). Die leere Menge, geschrieben als $\left\{\right\}$ oder auch $\varnothing$, 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$.

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

für die Teilmenge aller $x\in X$ für die die Aussage „$A\left(x\right)$“ 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.

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 $\left\{x,y\right\}=\left\{z\right\}$ 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.

Übung 1.17 (Distributivgesetze).

Zeigen Sie die folgenden Distributivgesetze:

(i)

Seien $A,B,C$ Aussagen. Zeigen Sie $$\begin{array}{llll}\hfill & (A\vee B)\wedge C\iff (A\wedge C)\vee (B\wedge C)& \hfill & \\ \hfill & (A\wedge B)\vee C\iff (A\vee C)\wedge (B\vee C)& \hfill & \end{array}$$

(ii)

Seien $P,Q,R$ Mengen. Zeigen Sie $$\begin{array}{llll}\hfill & (P\cup Q)\cap R=(P\cap R)\cup (Q\cap R)& \hfill & \\ \hfill & (P\cap Q)\cup R=(P\cup R)\cap (Q\cup R)& \hfill & \end{array}$$

Können Sie auch Kommutativ- und Assoziativgesetze formulieren?

Übung 1.18 (Gesetze von De Morgan).

Seien $P,Q$ Teilmengen einer Menge $X$. 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.

Wir verallgemeinern nun zwei Begriffe aus Definition 1.16:

Übung 1.21.

Was ist die Menge

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

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

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

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

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

Beispiel 1.24 (Einige kartesische Produkte).

Falls $X=\left\{0,1\right\}$ ist, dann ist

Falls $X=\left\{a,b,c,\dots ,z\right\}$ 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^{\prime }$ Teilmengen von $X$, $B,B^{\prime }$ Teilmengen von $Y$. Zeigen Sie die Formel

Ü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:

Übung 1.28.

Bestimmen Sie $\mathcal{𝒫}\left(\left\{\right\}\right)$ und $\mathcal{𝒫}\left(\mathcal{𝒫}\right(\left\{\right\}\left)\right)$.

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

Stellt man nun die Frage, ob $R$ selbst zu $R$ gehören kann, so erhält man „$R\in R\iff 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 Definition einer Teilmenge in (1.8) anstelle der dritten Annahme der naiven Mengenlehre, das kartesische Produkt oder die Potenzmenge) 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?

1.4.2 Abbildungen

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

Beispiel 1.32 (Erste Funktionen).

(a)

Sei $X$ eine Menge. Die Identitätsabbildung ${\mathrm{id}}_X:X\to X$ ist die Funktion definiert durch ${\mathrm{id}}_X\left(x\right)=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\left(x\right)=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}{llll}\hfill {𝟙}_A:X& \to \left\{0,1\right\}& \hfill & \\ \hfill {𝟙}_A\left(x\right)& =\{\begin{array}{cc}\hfill 0\hfill & \hfill \text{für }x\notin A\hfill \\ \hfill 1\hfill & \hfill \text{für }x\in A\hfill \end{array}& \hfill & \end{array}$$

wird die charakteristische Funktion von $A$ genannt. Das Bild von ${𝟙}_A$ ist genau dann ganz $\left\{0,1\right\}$, wenn die Menge $A$ weder leer noch ganz $X$ ist (wieso?).

(d)

Für zwei Mengen $X_1,X_2$ definieren wir die Projektionen $$\begin{array}{lll}\hfill {\pi }_1:X_1\times X_2\to X_1& & \hfill \\ \hfill {\pi }_1((x_1,x_2))=x_1& & \hfill \end{array}$$

und

$$\begin{array}{lll}\hfill {\pi }_2:X_1\times X_2\to X_2& & \hfill \\ \hfill {\pi }_2((x_1,x_2))=x_2.& & \hfill \end{array}$$

Das Bild von ${\pi }_1$ ist $X_1$, falls $X_2$ nicht leer ist, und ebenso ist ${\pi }_2(X_1\times X_2)=X_2$, falls $X_1\ne \left\{\right\}$. Wir schreiben manchmal auch ${\pi }_{X_1}$ anstelle von ${\pi }_1$ und ${\pi }_{X_2}$ anstelle von ${\pi }_2$.

Oft, aber bei weitem nicht immer, wird eine Funktion durch eine Formel wie zum Beispiel $y=x^2$ definiert, doch ohne Angabe des Definitionsbereichs und des Wertebereichs wäre die Definition der Funktion unvollständig (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

oder

wobei $f\left(x\right)$ 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

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.

Eine Funktion $f:X\to Y$ ist also nicht injektiv, falls zwei verschiedene Elemente $x_1,x_2\in X$ existieren mit $f\left(x_1\right)=f\left(x_2\right)$. Des Weiteren ist $f$ surjektiv genau dann wenn das Bild $f\left(X\right)$ 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.

Im folgenden Beispiel schreiben wir ${ℝ}_{\ge 0}=\left\{x\in ℝ\mid x\ge 0\right\}$ 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:{ℝ}_{\ge 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 {ℝ}_{\ge 0},x\mapsto x^2$ ist surjektiv (es existiert eine Wurzel), sie ist aber nicht injektiv, denn $f\left(1\right)=1={(-1)}^2=f(-1)$.

(c)

Die Funktion $f:ℝ\to ℝ,x\mapsto x^2$ ist weder injektiv noch surjektiv.

(d)

Die Funktion $f:{ℝ}_{\ge 0}\to {ℝ}_{\ge 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\left(x\right)$: 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.

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\left(X\right)\to X$ definieren lässt. In der Tat ist die Funktion $x\in X\mapsto f\left(x\right)\in f\left(X\right)$ (also „ $f$ mit eingeschränktem Wertebereich“) bijektiv.

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

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

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 $P_1,P_2$ gegeben, so dass $P_1$ eine Zahl als Input und einen Zeichenkette als Output hat und $P_2$ eine Zeichenkette als Input und eine Zeichenkette als Output hat. In diesem Fall kann man $P_2$ den Output von $P_1$ als Input übergeben; umgekehrt jedoch kann man $P_1$ den Output von $P_2$ nicht übergeben, da $P_1$ 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\ne 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:

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\left(f\right(x_1\left)\right)=g\left(f\right(x_2\left)\right)$ 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\left(x_1\right)=f\left(x_2\right)$ 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.

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

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

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=\left\{a\right\}$ und $X=\left\{a,b,c\right\}$. Dann gibt es $3$ verschiedene injektive Abbildungen $A\to X$. Nebst der Inklusionsabbildung (die $a$ auf $a$ abbildet) sind dies

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 ${\pi }_1:X_1\times X_2\to X_1$ und ${\pi }_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

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 \mathbb{N}$, so hat $Y^X$ genau $n^m$ Elemente (siehe 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:

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:

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 ${\pi }_1:X\times Y\to X$ die Projektion auf $X$, die durch $(x,y)\mapsto x$ definiert ist und mit ${\pi }_2:X\times Y\to Y$ die Projektion auf $Y$. Zeigen Sie, dass ${\pi }_1{|}_{\mathrm{graph}\left(f\right)}:\mathrm{graph}\left(f\right)\to X$ bijektiv ist und finden Sie die Umkehrabbildung. Beweisen Sie des Weiteren die Identität $$\begin{array}{lll}\hfill {\pi }_2\circ {\left({\pi }_1{|}_{\mathrm{graph}\left(f\right)}\right)}^{-1}=f,& & \hfill \end{array}$$

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

(ii)

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

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

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.

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.

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 $\left\{f\left(x\right)\mid x\in A\right\}$ für das Bild $f\left(A\right)$ der Teilmenge $A$ wie in Definition 1.31. Ebenso schreiben wir auch

wobei $A\left(x\right)$ 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:

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

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\left(A\right)$ eines Teilintervalls $A=[x_1,x_2]\subseteq I$ oder das Urbild $f^{-1}\left(\right[y_1,y_2\left]\right)$ 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.

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

Übung 1.53 (Funktionen durch Fallunterscheidungen).

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

1.4.6 Iterationen

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

Wir bemerken, dass man die Iteration einer Funktion $f:X\to X$ oft einfach auch durch $f^n=f^{\circ n}$ bezeichnet.²

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

(i)

Sei $X=\left\{a,b,c\right\}$ eine Menge mit $3$ verschiedenen Elementen und $f:X\to X$ die Funktion definiert durch $f\left(a\right)=b,f\left(b\right)=c$ und $f\left(c\right)=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 3x\in ℝ$ und beschreiben Sie intuitiv, wie sich $f^{\circ n}\left(x\right)$ für ein $x\in ℝ$ und verschiedene $n\in \mathbb{N}$ verhält.

(iii)

Iterieren Sie die Funktion $f:x\in ℝ\to x^2\in ℝ$ und beschreiben Sie intuitiv, wie sich $f^{\circ n}\left(x\right)$ für ein $x\in ℝ$ und verschiedene $n\in \mathbb{N}$ 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 {\mathbb{N}}_0$ gilt $f^{\circ m}\circ f^{\circ n}=f^{\circ (m+n)}$.

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

ist zwar injektiv aber nicht surjektiv, denn $1\notin f\left(\mathbb{N}\right)$. 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 $\mathbb{N}\to \mathbb{N}$, 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.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:\mathbb{N}\to \mathbb{N}$ können Sie verwenden, um im Hotel Platz zu beschaffen?