Abbildungen und Relationen

Eine Abbildung $f:A\to B$ ordnet jedem Element der Menge $A$ genau ein Element der Menge $B$ zu. Aus der Schule kennst du das als Funktion, wie $x\mapsto x^2$. An der Universität steht der Begriff viel allgemeiner da: $A$ und $B$ sind beliebige Mengen, nicht nur Zahlen. Eine Relation ist die Verallgemeinerung: Sie sagt nur, welche Elemente zueinander „in Beziehung stehen“, ohne dass die Zuordnung eindeutig sein muss.

Diese Seite führt die Begriffe der ersten Vorlesungswochen zusammen. Du lernst, wann eine Abbildung injektiv, surjektiv und bijektiv ist, wie man Abbildungen verkettet und umkehrt, was eine Äquivalenzrelation und eine Ordnung ist und wie man mit Bijektionen die Größe unendlicher Mengen vergleicht. Die Grundlagen zu Mengen stehen auf der Seite Mengenlehre, die Beweisformen auf Beweisverfahren. Zum Üben gibt es einen Aufgabengenerator.

Was eine Abbildung ist

Eine Abbildung besteht aus drei Dingen: der Definitionsmenge $A$, der Zielmenge $B$ und der Vorschrift $f$. Zwei Abbildungen sind nur gleich, wenn alle drei übereinstimmen. Mit der Vorschrift $x\mapsto x^2$ ergeben sich also ganz verschiedene Abbildungen, je nachdem, ob die Zielmenge $ℝ$ oder $[0,\infty )$ ist.

Zu jeder Abbildung gehören außerdem Bild und Urbild von Teilmengen. Das Bild einer Teilmenge $S\subseteq A$ ist $f(S)=\{f(x)\mid x\in S\}$. Das Urbild einer Teilmenge $T\subseteq B$ ist $f^{-1}(T)=\{x\in A\mid f(x)\in T\}$. Die Bezeichnung $f^{-1}(T)$ gibt es immer, auch wenn es keine Umkehrabbildung gibt.

Injektiv, surjektiv, bijektiv

Zum Nachweis nimmst du die Definition wörtlich. Injektiv zeigst du, indem du $f(x)=f(y)$ annimmst und daraus $x=y$ schließt. Nicht injektiv zeigst du mit einem Gegenbeispiel: zwei verschiedene Elemente mit gleichem Bild. Surjektiv zeigst du, indem du zu einem beliebigen $b$ ein Urbild angibst, am besten durch Auflösen der Gleichung $f(x)=b$ nach $x$.

Abbildungen zwischen endlichen Mengen

Haben $A$ und $B$ endlich viele Elemente, $\left|A\right|=m$ und $\left|B\right|=n$, kannst du zählen. Es gibt $n^m$ Abbildungen, denn jedes der $m$ Elemente hat $n$ mögliche Bilder. Injektiv sind $n·(n-1)\cdots (n-m+1)$ davon (für $m\le n$), bijektiv sind es $n!$ für $m=n$. Für $m=4$ und $n=6$ gibt es $6^4=1296$ Abbildungen, davon $6·5·4·3=360$ injektive. Für $m=3$, $n=2$ gibt es $2^3=8$ Abbildungen, davon $8-2=6$ surjektive (nur die zwei konstanten Abbildungen sind es nicht).

Daraus folgt das Schubfachprinzip (siehe Kombinatorik): Ist $m>n$, kann keine Abbildung $A\to B$ injektiv sein. Bei endlichen Mengen gleicher Größe sind injektiv, surjektiv und bijektiv sogar dasselbe. Bei unendlichen Mengen stimmt das nicht, wie $n\mapsto n+1$ auf $\mathbb{N}=\{0,1,2,\dots \}$ zeigt: injektiv, aber die $0$ wird nicht getroffen.

Verkettung und Umkehrabbildung

Sind $f:A\to B$ und $g:B\to C$ Abbildungen, ist die Verkettung (Komposition) $g\circ f:A\to C$ durch $(g\circ f)(x)=g(f(x))$ erklärt. Man liest „$g$ nach $f$“: erst $f$, dann $g$. Die Verkettung ist assoziativ, $h\circ (g\circ f)=(h\circ g)\circ f$, aber nicht kommutativ. Mit $f(x)=x+1$ und $g(x)=x^2$ ist $(g\circ f)(x)={(x+1)}^2$, aber $(f\circ g)(x)=x^2+1$.

Beweis der zweiten Aussage. Sei $g\circ f$ injektiv und $f(x)=f(y)$. Wende $g$ an: $g(f(x))=g(f(y))$, also $(g\circ f)(x)=(g\circ f)(y)$. Wegen der Injektivität von $g\circ f$ folgt $x=y$. Also ist $f$ injektiv. Die Surjektivität zeigst du genauso: Jedes $c\in C$ hat ein Urbild $x$ unter $g\circ f$, und dann ist $f(x)$ ein Urbild von $c$ unter $g$.

Eine Abbildung $f:A\to B$ besitzt genau dann eine Umkehrabbildung $f^{-1}:B\to A$ mit $f^{-1}\circ f={\text{id}}_A$ und $f\circ f^{-1}={\text{id}}_B$, wenn sie bijektiv ist. Sind $f:A\to B$ und $g:B\to C$ bijektiv, so ist auch $g\circ f$ bijektiv, und es gilt ${(g\circ f)}^{-1}=f^{-1}\circ g^{-1}$, die Reihenfolge dreht sich um, wie beim Ausziehen von Socken und Schuhen. Für $f(x)=2x+3$ ist $f^{-1}(y)=\frac{y-3}{2}$. Die Schulversion steht bei der Umkehrfunktion.

Relationen und ihre Eigenschaften

Eine Relation zwischen $A$ und $B$ ist eine Teilmenge $R\subseteq A\times B$ des kartesischen Produkts. Man schreibt $aRb$ statt $(a,b)\in R$. Eine Abbildung ist der Spezialfall, in dem jedes $a$ in genau einem Paar vorkommt. Bekannte Relationen sind $\le$ auf den reellen Zahlen, „teilt“ auf den natürlichen Zahlen oder „ist Geschwister von“.

Wichtig sind Relationen auf einer Menge, $R\subseteq A\times A$. Dafür gibt es vier Eigenschaften:

Bei „$|a-b|\le 1$“ siehst du, warum die Transitivität einen eigenen Beweis braucht: $0R1$ und $1R2$, aber $0R2$ gilt nicht. Antisymmetrisch ist nicht das Gegenteil von symmetrisch. Die Gleichheit ist beides zugleich.

Äquivalenzrelationen und Klassen

Die Idee: Du fasst Dinge zusammen, die „im Wesentlichen gleich“ sind. Der Hauptsatz sagt, dass das lückenlos und ohne Überlappung geht.

Beweis. Wegen der Reflexivität gilt $a\in [a]$. Angenommen, $[a]$ und $[b]$ haben ein gemeinsames Element $c$. Dann gilt $c\sim a$ und $c\sim b$, wegen der Symmetrie $a\sim c$ und mit der Transitivität $a\sim b$. Jedes $x\in [a]$ erfüllt dann $x\sim a\sim b$, also $x\in [b]$. Umgekehrt genauso, also $[a]=[b]$. Zur Umkehrung: Eine Zerlegung liefert die Relation „$a\sim b$, wenn $a$ und $b$ im selben Teil liegen“. Sie ist reflexiv, symmetrisch und transitiv, weil „im selben Teil liegen“ diese drei Eigenschaften hat.

Ordnungsrelationen

Eine Halbordnung ist eine Relation $\preccurlyeq$, die reflexiv, antisymmetrisch und transitiv ist. Gilt zusätzlich für je zwei Elemente $a\preccurlyeq b$ oder $b\preccurlyeq a$, heißt sie Totalordnung oder lineare Ordnung. Die gewöhnliche Ordnung $\le$ auf $ℝ$ ist total. Die Teilbarkeit auf den natürlichen Zahlen ist nur eine Halbordnung, denn $2$ und $3$ sind nicht vergleichbar. Auch die Inklusion $\subseteq$ auf der Potenzmenge ist eine Halbordnung: $\left\{1\right\}$ und $\left\{2\right\}$ sind unvergleichbar.

Halbordnungen zeichnet man als Hasse-Diagramm: Jedes Element ist ein Punkt, und ein Strich nach oben verbindet ein Element mit seinen direkten Nachfolgern. Transitive Striche lässt man weg.

Ein Element $m$ heißt maximal, wenn kein anderes Element über ihm liegt, und Maximum, wenn alle anderen darunter liegen. Im Diagramm oben ist die 12 beides. Entfernst du die 12, sind 4 und 6 maximal, aber es gibt kein Maximum. Bei Totalordnungen fallen beide Begriffe zusammen. Mit der Ordnung auf den reellen Zahlen geht es auf der Seite Reelle Zahlen und Vollständigkeit weiter: Dort geht es um die kleinste obere Schranke.

Mächtigkeit und Bijektionen

Wie vergleichst du die Größe zweier Mengen, ohne zu zählen? Du paarst die Elemente. Zwei Mengen $A$ und $B$ heißen gleichmächtig, wenn es eine Bijektion $A\to B$ gibt, und man schreibt $\left|A\right|=\left|B\right|$. Es gilt $\left|A\right|\le \left|B\right|$, wenn es eine Injektion $A\to B$ gibt. Für endliche Mengen ist das die gewohnte Anzahl. Bei unendlichen Mengen kommt Überraschendes heraus.

Ein Bild dazu ist das Hotel mit unendlich vielen Zimmern, das David Hilbert zugeschrieben wird: Auch wenn alle Zimmer belegt sind, kann der Wirt einen neuen Gast aufnehmen, indem jeder Gast in das nächste Zimmer zieht. Das ist die Bijektion $n\mapsto n+1$ von $\mathbb{N}$ auf ${\mathbb{N}}_{>0}$.

Beweis (Diagonalargument). Angenommen, $g:A\to 𝒫(A)$ wäre surjektiv. Betrachte $D=\{x\in A\mid x\notin g(x)\}$. Das ist eine Teilmenge von $A$, also gibt es wegen der Surjektivität ein $d\in A$ mit $g(d)=D$. Liegt $d$ in $D$? Nach Definition von $D$ gilt $d\in D$ genau dann, wenn $d\notin g(d)$, und das ist $d\notin D$. Beides zugleich ist ein Widerspruch. Also gibt es keine solche Abbildung.

Das erzeugt eine endlose Treppe immer größerer Unendlichkeiten: $\mathbb{N}$, $𝒫(\mathbb{N})$, $𝒫(𝒫(\mathbb{N}))$, und so weiter. Weiter gilt der Satz von Cantor, Schröder und Bernstein: Gibt es Injektionen $A\to B$ und $B\to A$, so gibt es eine Bijektion $A\to B$. Damit ist $\le$ auf den Mächtigkeiten antisymmetrisch. Wie man $ℝ$ als überabzählbar erkennt, steht in Abzählbar und überabzählbar.

Typische Fehler

Übungen

Geschichte: vom Funktionsbegriff zur Mengenlehre

Der heutige Abbildungsbegriff ist das Ergebnis einer langen Verallgemeinerung. Leibniz und Euler dachten an Funktionen als Rechenausdrücke, Dirichlet erklärte 1837 die Zuordnung beliebiger Werte. Georg Cantor verglich ab 1874 die Größe unendlicher Mengen mit Hilfe von Zuordnungen und bewies 1891 mit dem Diagonalverfahren, dass es mehr als eine Unendlichkeit gibt. Dedekind fasste in Was sind und was sollen die Zahlen? (1888) die Abbildung als Grundbegriff auf und baute darauf die natürlichen Zahlen. Äquivalenzrelationen und ihre Klassen wurden danach zum Standardmittel, neue Objekte aus alten zu bauen: ganze Zahlen aus Paaren natürlicher Zahlen, rationale Zahlen aus Paaren ganzer Zahlen, reelle Zahlen aus Folgen.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Abbildung (Mathematik)
• Wikipedia: Äquivalenzrelation
• Albrecht Beutelspacher: Das ist o.B.d.A. trivial! Tipps und Tricks zur Formulierung mathematischer Gedanken, Vieweg+Teubner, Wiesbaden.
• Daniel Grieser: Mathematisches Problemlösen und Beweisen. Eine Entdeckungsreise in die Mathematik, Springer Spektrum, Wiesbaden.
• Richard Dedekind: Was sind und was sollen die Zahlen?, Vieweg, Braunschweig 1888.
• Georg Cantor: Über eine elementare Frage der Mannigfaltigkeitslehre, Jahresbericht der Deutschen Mathematiker-Vereinigung 1 (1891).