Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 6

Darstellungsmöglichkeiten für Abbildungen

Wir modellieren das Abzählen einer Menge ${}M$ mathematisch als eine bijektive Abbildung zwischen einer Menge der Form ${}\{1,\ldots ,n\}$ und ${}M$. Wir wollen zeigen, dass dabei das ${}n$ unabhängig von der gewählten Abbildung ist. Um dies klar begründen zu können, müssen wir uns etwas genauer mit Abbildungen beschäftigen. Abbildungen können auf recht unterschiedliche Arten dargestellt werden. Zu nennen sind (vollständige oder unvollständige) Wertetabellen, der Graph einer Abbildung, Säulen- und Kuchendiagramme, Pfeildiagramme, Höhenlinien, Animationen. Eine besondere Rolle spielen funktionale Vorschriften, mit denen häufig Abbildungen festgelegt werden, das sind Ausdrücke der Form ${}x^{2},{\sqrt {x}},\exp x,\sin x$.

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$
${}\pi (x)$	${}2$	${}4$	${}6$	${}5$	${}3$	${}1$

${}\cdot$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$
${}0$	${}0$	${}0$	${}0$	${}0$	${}0$	${}0$	${}0$
${}1$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$
${}2$	${}0$	${}2$	${}4$	${}6$	${}1$	${}3$	${}5$
${}3$	${}0$	${}3$	${}6$	${}2$	${}5$	${}1$	${}4$
${}4$	${}0$	${}4$	${}1$	${}5$	${}2$	${}6$	${}3$
${}5$	${}0$	${}5$	${}3$	${}1$	${}6$	${}4$	${}2$
${}6$	${}0$	${}6$	${}5$	${}4$	${}3$	${}2$	${}1$

Wir wollen zu zwei gegebenen Nummerierungen einer Menge ${}M$, also zu zwei bijektiven Abbildungen ${}\varphi \colon {\{1,\ldots ,n\}}\rightarrow M$ und ${}\psi \colon \{1,\ldots ,k\}\rightarrow M$ zeigen, dass ${}n=k$ ist. Da bei einer Bijektion sich die Elemente der beiden Mengen eindeutig entsprechen, führt dies zu einer eindeutigen Entsprechung zwischen ${}{\{1,\ldots ,n\}}$ und ${}\{1,\ldots ,k\}$. Mit diesem Trick, dem die Hintereinanderschaltung von Abbildungen und die Umkehrabbildung einer bijektiven Abbildung zugrunde liegt, kann man also unter Umgehung der Menge ${}M$ direkt diese Teilmengen der natürlichen Zahlen untereinander vergleichen.

Die Hintereinanderschaltung von Abbildungen

Definition

Es seien ${}L,\,M$ und ${}N$ Mengen und

$F\colon L\longrightarrow M,\,x\longmapsto F(x),$

und

$G\colon M\longrightarrow N,\,y\longmapsto G(y),$

Abbildungen. Dann heißt die Abbildung

$G\circ F\colon L\longrightarrow N,\,x\longmapsto G(F(x)),$

die Hintereinanderschaltung der Abbildungen ${}F$ und ${}G$.

Eine Hintereinanderschaltung kann man sich durch ein Diagramm der Form

$L{\stackrel {F}{\longrightarrow }}M{\stackrel {G}{\longrightarrow }}N$

gut veranschaulichen.

Beispiel

Die Wertetabelle

${}n$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}10$
${}\varphi (n)$	${}A$	${}A$	${}B$	${}C$	${}C$	${}B$	${}E$	${}D$	${}D$	${}B$

beschreibt, welche Person der Bearbeitungsgruppe ${}G=\{A,B,C,D,E\}$ welche Aufgabe federführend macht und die Wertetabelle

${}P$	${}A$	${}B$	${}C$	${}D$	${}E$
${}\psi (P)$	${}S$	${}L$	${}M$	${}M$	${}W$

mit den möglichen Werten ${}\{M,S,L,W,U\}$ beschreibt, wie viel Lust die Personen in dieser Woche haben (${}M$: hat Megalust, ${}S$: hat Superlust, ${}L$ hat Lust, ${}W$ hat wenig Lust, ${}U$ hat Unlust). Die zusammengesetzte Abbildung ${}\psi \circ \varphi$ beschreibt dann, mit wie viel Lust die verschiedenen Aufgaben bearbeitet werden, die zugehörige Wertetabelle ist

${}n$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}10$
${}\psi (\varphi (n))$	${}S$	${}S$	${}L$	${}M$	${}M$	${}L$	${}W$	${}M$	${}M$	${}L$

Wenn die Abbildungen durch funktionale Ausdrücke gegeben sind, so erhält man die zusammengesetzte Abbildung, in den man den einen funktionalen Ausdruck in den anderen funktionalen Ausdruck einsetzt. Damit ist folgendes gemeint: Wenn

$\varphi ,\psi \colon \mathbb {R} _{\geq 0}\longrightarrow \mathbb {R} _{\geq 0}$

Funktionen sind, die durch ${}\varphi (x)=x^{2}+5$ und ${}\psi (y)={\sqrt {y}}$ gegeben sind, so besitzt die zusammengesetzte Funktion ${}\psi \circ \varphi$ (also in der Ausführung zuerst ${}\varphi$!) die Vorschrift

${}(\psi \circ \varphi )(x)=\psi (\varphi (x))={\sqrt {x^{2}+5}}\,.$

In der anderen Reihenfolge ergibt sich

${}(\varphi \circ \psi )(y)=\varphi (\psi (y))={\sqrt {y}}^{2}+5=y+5\,.$

Hier haben wir die beiden Funktionen mit unterschiedlichen Variablen geschrieben, was die Einsetzung dann erleichtert hat. Häufig muss man zuerst eine sinnvolle Umbenennung durchführen.

Lemma

Es seien ${}L,M,N$ und ${}P$ Mengen und es seien

$F\colon L\longrightarrow M,\,x\longmapsto F(x),$

$G\colon M\longrightarrow N,\,y\longmapsto G(y),$

und

$H\colon N\longrightarrow P,\,z\longmapsto H(z),$

Abbildungen.

Dann ist

${}H\circ (G\circ F)=(H\circ G)\circ F\,.$

Beweis

Zwei Abbildungen ${}\alpha ,\beta \colon L\rightarrow P$ sind genau dann gleich, wenn für jedes ${}x\in L$ die Gleichheit ${}\alpha (x)=\beta (x)$ gilt. Es sei also ${}x\in L$. Dann ist

${}{\begin{aligned}(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{aligned}}$

$\Box$

Lemma

Es seien ${}L,\,M$ und ${}N$ Mengen und

$F\colon L\longrightarrow M,\,x\longmapsto F(x),$

und

$G\colon M\longrightarrow N,\,y\longmapsto G(y),$

Abbildungen mit der Hintereinanderschaltung

$G\circ F\colon L\longrightarrow N.$

Dann gelten folgende Eigenschaften.

1. Wenn ${}F$ und ${}G$ injektiv sind, so ist auch ${}G\circ F$ injektiv.
2. Wenn ${}F$ und ${}G$ surjektiv sind, so ist auch ${}G\circ F$ surjektiv.
3. Wenn ${}F$ und ${}G$ bijektiv sind, so ist auch ${}G\circ F$ bijektiv.

Beweis

1. Es seien ${}x,x'\in L$ mit

   ${}G(F(x))=G(F(x'))\,$

   gegeben. Aufgrund der Injektivität von ${}G$ folgt

   ${}F(x)=F(x')\,$

   und aufgrund der Injektivität von ${}F$ folgt

   ${}x=x'\,,$

   was die Injektivität von ${}G\circ F$ bedeutet.

2. Sei ${}z\in N$ gegeben. Aufgrund der Surjektivität von ${}G$ gibt es ein ${}y\in M$ mit

   ${}G(y)=z\,.$

   Aufgrund der Surjektivität von ${}F$ gibt es ein ${}x\in L$ mit

   ${}F(x)=y\,.$

   Insgesamt ist

   ${}(G\circ F)(x)=G(F(x))=G(y)=z\,,$

   es gibt also ein Urbild von ${}z$ und somit ist die Gesamtabbildung surjektiv.

3. Folgt aus (1) und (2).

$\Box$

Die Umkehrabbildung

Definition

Es sei ${}M$ eine Menge. Dann heißt die Abbildung

$M\longrightarrow M,\,x\longmapsto x,$

die also jedes Element ${}x\in M$ auf sich selbst schickt, die identische Abbildung oder Identität auf ${}M$. Sie wird mit ${}\operatorname {Id}$ oder ${}\operatorname {Id} _{M}$ bezeichnet.

Die Identität ist natürlich bijektiv. Umgekehrt kann man zu einer bijektiven Abbildung eine Abbildung derart angeben, dass die Verknüpfung die Identität ergibt.

Definition

Es sei ${}F\colon L\rightarrow M$ eine bijektive Abbildung. Dann heißt die Abbildung

$G\colon M\longrightarrow L,$

die jedes Element ${}y\in M$ auf das eindeutig bestimmte Element ${}x\in L$ mit ${}F(x)=y$ abbildet, die Umkehrabbildung zu ${}F$.

Die Umkehrabbildung zu ${}F$ wird mit ${}F^{-1}$ bezeichnet. Es gilt die charakteristische Eigenschaft, dass sowohl ${}F\circ F^{-1}$ als auch ${}F^{-1}\circ F$ die Identität (auf den jeweiligen Mengen) sind.

Beispiel

Die Nummerierung der Schüler durch Heino,

${}n$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}10$
${}\varphi (n)$	${}M$	${}T$	${}A$	${}L$	${}S$	${}B$	${}G$	${}R$	${}H$	${}C$

ist bijektiv und hat daher eine eindeutig bestimmte Umkehrabbildung. Die Wertetabelle dieser Umkehrabbildung ist

${}P$	${}A$	${}B$	${}C$	${}G$	${}H$	${}L$	${}M$	${}R$	${}S$	${}T$
${}\varphi ^{-1}(P)$	${}3$	${}6$	${}10$	${}7$	${}9$	${}4$	${}1$	${}8$	${}5$	${}2$

Bei einem natürlichen Zählvorgang kann man sich darüber streiten, ob die Zahlen „eher“ den Personen oder die Personen eher den Zahlen zugeordnet wird. Bei einer bijektiven Abbildung liegt eine Entsprechung vor.

Wir erwähnen noch die konstanten Abbildungen.

Definition

Es seien ${}L$ und ${}M$ Mengen und es sei ${}c\in M$ ein Element. Dann heißt die Abbildung

$L\longrightarrow M,\,x\longmapsto c,$

die also jedes Element ${}x\in L$ auf ${}c$ abbildet, die konstante Abbildung zum Wert ${}c$.

Die Wohldefiniertheit der Anzahl

Wir kehren zu dem Problem zurück, warum die Anzahl einer endlichen Menge wohldefiniert ist, warum es also egal ist, in welcher Reihenfolge man zählt.

Lemma

Es sei ${}k\neq 0$ eine natürliche Zahl mit dem Vorgänger ${}\ell$, es sei also ${}k=\ell ^{\prime }$. Es sei ${}z\in \{1,\ldots ,k\}$ ein fixiertes Element.

Dann gibt es eine bijektive Abbildung zwischen ${}\{1,\ldots ,\ell \}$ und ${}\{1,\ldots ,k\}\setminus \{z\}$.

Beweis

Wir definieren eine Abbildung

$\varphi \colon \{1,\ldots ,\ell \}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}$

durch

$\varphi (x)={\begin{cases}x\,,{\text{ falls }}x{\text{ in der Durchzählung von }}1{\text{ bis }}k{\text{ vor }}z{\text{ kommt}}\,,\\x^{\prime }\,,{\text{ falls }}x{\text{ gleich }}z{\text{ ist oder in der Durchzählung nach }}z{\text{ kommt}}\,.\end{cases}}\,$

Dies ist eine wohldefinierte Abbildung, da die Bilder echt unterhalb von ${}z$ oder echt oberhalb von ${}z$ liegen, niemals aber gleich ${}z$ sind, und da maximal der Nachfolger von ${}\ell$, also ${}k$ erreicht wird.

Die Abbildung ist injektiv: Wenn ${}x$ und ${}y$ beide unterhalb von ${}z$ liegen, so werden beide Elemente auf sich selbst abgebildet. Wenn beide oberhalb von ${}z$ liegen, so werden beide auf ihren Nachfolger abgebildet, und das Nachfolgernehmen ist injektiv (dies ist die Eigenschaft, dass der Vorgänger eindeutig bestimmt ist). Wenn ${}x$ unterhalb von ${}z$ und ${}y$ oberhalb von ${}z$ (oder umgekehrt) liegt, so ist erst recht ${}y^{\prime }$ oberhalb von ${}z$ und somit von ${}x$ verschieden.

Die Abbildung ist auch surjektiv. Die Zahlen echt unterhalb von ${}z$ werden durch sich selbst erreicht und die Zahlen ${}u$ echt oberhalb von ${}z$ (und unterhalb von ${}k$ einschließlich ${}k$) kann man als

${}u=v^{\prime }\,$

mit ${}v$ oberhalb von ${}z$ (einschließlich ${}z$) und echt unterhalb von ${}k$, also maximal gleich ${}\ell$ schreiben. Insgesamt ist ${}\varphi$ also eine Bijektion.

$\Box$

Satz

Wenn ${}M$ eine Menge ist und wenn

$\varphi \colon {\{1,\ldots ,n\}}\longrightarrow M$

und

$\psi \colon \{1,\ldots ,k\}\longrightarrow M$

bijektive Abbildungen sind,

so ist

${}n=k\,.$

Die Anzahl einer endlichen Menge ist also wohldefiniert.

Beweis

Es seien die bijektiven Abbildungen

$\varphi \colon {\{1,\ldots ,n\}}\longrightarrow M$

und

$\psi \colon \{1,\ldots ,k\}\longrightarrow M$

gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Lemma 6.4  (3) wieder bijektiv ist, ist auch

$\psi ^{-1}\circ \varphi \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$

bijektiv. Wir müssen also nur die endlichen Standardmengen ${}{\{1,\ldots ,n\}}$ untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung

$\theta \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$

vorliegt, dass dann

${}n=k\,$

ist. Dies zeigen wir durch Induktion nach ${}n$. Wenn ${}n=0$ ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch ${}k=0$. Es seien nun ${}n,k$ nicht ${}0$, sodass sie also jeweils einen Vorgänger haben. Es sei ${}m$ der Vorgänger von ${}n$ und ${}\ell$ der Vorgänger von ${}k$. Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen

${}z=\theta (n)\in \{1,\ldots ,k\}\,.$

Dann gibt es nach der Herausnahme von ${}n$ bzw. ${}z$ eine bijektive Abbildung

$\{1,\ldots ,m\}={\{1,\ldots ,n\}}\setminus \{n\}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}.$

Nach Lemma 6.9 gibt es eine bijektive Abbildung zwischen ${}\{1,\ldots ,\ell \}$ und ${}\{1,\ldots ,k\}\setminus \{z\}$. Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen ${}\{1,\ldots ,m\}$ und ${}\{1,\ldots ,\ell \}$. Nach Induktionsvoraussetzung ist ${}m=\ell$, also auch

${}n=m'=\ell '=k\,.$

$\Box$

Zählen von Prozessen

Mit natürlichen Zahlen kann man nicht nur endliche Mengen zählen, sondern auch Prozesse. Wenn ein Einzelprozess wohldefiniert ist, wie beispielsweise das Nachfolgernehmen in einem Modell der natürlichen Zahlen, oder das Umlegen eines Apfel von einem Haufen auf einen anderen Haufen, oder auf einer Leiter eine Sprosse nach oben steigen, so kann man mit den natürlichen Zahlen angeben, wie oft der Prozess durchgeführt wird oder werden soll. Dies eröffnet eine Vielzahl von Möglichkeiten, komplexere mathematische Konzepte dadurch festzulegen, dass gesagt wird, wie oft ein gewisser grundlegenderer Prozess durchgeführt werden soll. In diesem Sinne kann die Addition von zwei natürlichen Zahlen dadurch eingeführt werden, dass die eine Zahl angibt, wie oft von der anderen Zahl ausgehend der Nachfolger genommen werden soll, die Multiplikation von zwei natürlichen Zahlen kann dadurch eingeführt werden, dass die eine Zahl angibt, wie oft die andere Zahl zur ${}0$ addiert werden soll (die Anzahl der Summanden ist durch die erste Zahl festgelegt), die Potenzierung von zwei natürlichen Zahlen kann dadurch eingeführt werden, dass die eine Zahl angibt, wie oft die andere Zahl mit sich selbst multipliziert werden soll (Anzahl der Faktoren). Wenn eine Strecke ${}s$ und eine natürliche Zahl ${}n$ gegeben ist, so kann man die Strecke ${}n$-fach Hintereinanderlegen. Dabei entsteht eine Strecke, die ${}n$-mal so lang wie die Ausgangsstrecke ist. Geometrisch kann man dies dadurch durchführen, dass man die Stecke zu einer Geraden verlängert und dann mit Hilfe eines Zirkels die Strecke ${}(n-1)$-mal umschlägt.

Fußnoten

<< | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)