Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 6/latex
\setcounter{section}{6}
\zwischenueberschrift{Darstellungsmöglichkeiten für Abbildungen}
Wir modellieren das Abzählen einer Menge $M$ mathematisch als eine bijektive Abbildung zwischen einer Menge der Form
\mathl{{ \{ 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
\zusatzklammer {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
\mathl{x^2, \sqrt{x}, \exp x, \sin x}{.}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Aplicacion_2.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Aplicación_2.svg } {} {HiTe} {Commons} {PD} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Beliebteste_Eissorten_in_Deutschland.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Beliebteste Eissorten in Deutschland.svg } {} {Doofi} {Commons} {PD} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Tiefkühlkonsum.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Tiefkühlkonsum.svg } {} {SInner1} {Commons} {CC-by-sa 3.0} {}
\wertetabellesechsausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{ {6
} }
{ $\pi(x)$ }
{\mazeileundfuenf {2} {4} {6} {5} {3} }
{ {1} }
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Exp.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Exp.svg } {Peter John Acklam} {} {Commons} {CC-by-sa 3.0} {}
%Daten für folgende Tabelle
\renewcommand{\leitzeilenull}{ $\cdot$ }
\renewcommand{\leitzeileeins}{ $0$ }
\renewcommand{\leitzeilezwei}{ $1$ }
\renewcommand{\leitzeiledrei}{ $2$ }
\renewcommand{\leitzeilevier}{ $3$ }
\renewcommand{\leitzeilefuenf}{ $4$ }
\renewcommand{\leitzeilesechs}{ $5$ }
\renewcommand{\leitzeilesieben}{ $6$ }
\renewcommand{\leitzeileacht}{ }
\renewcommand{\leitzeileneun}{ }
\renewcommand{\leitzeilezehn}{ }
\renewcommand{\leitzeileelf}{ }
\renewcommand{\leitzeilezwoelf}{ }
\renewcommand{\leitspaltenull}{ $\cdot$ }
\renewcommand{\leitspalteeins}{ $0$ }
\renewcommand{\leitspaltezwei}{ $1$ }
\renewcommand{\leitspaltedrei}{ $2$ }
\renewcommand{\leitspaltevier}{ $3$ }
\renewcommand{\leitspaltefuenf}{ $4$ }
\renewcommand{\leitspaltesechs}{ $5$ }
\renewcommand{\leitspaltesieben}{ $6$ }
\renewcommand{\leitspalteacht}{ }
\renewcommand{\leitspalteneun}{ }
\renewcommand{\leitspaltezehn}{ }
\renewcommand{\leitspalteelf}{ }
\renewcommand{\leitspaltezwoelf}{ }
\renewcommand{\leitspaltedreizehn}{ }
\renewcommand{\leitspaltevierzehn}{ }
\renewcommand{\leitspaltefuenfzehn}{ }
\renewcommand{\leitspaltesechzehn}{ }
\renewcommand{\leitspaltesiebzehn}{ }
\renewcommand{\leitspalteachtzehn}{ }
\renewcommand{\leitspalteneunzehn}{ }
\renewcommand{\leitspaltezwanzig}{ }
\renewcommand{\aeinsxeins}{ 0 }
\renewcommand{\aeinsxzwei}{ 0 }
\renewcommand{\aeinsxdrei}{ 0 }
\renewcommand{\aeinsxvier}{ 0 }
\renewcommand{\aeinsxfuenf}{ 0 }
\renewcommand{\aeinsxsechs}{ 0 }
\renewcommand{\aeinsxsieben}{ 0 }
\renewcommand{\aeinsxacht}{ }
\renewcommand{\aeinsxneun}{ }
\renewcommand{\aeinsxzehn}{ }
\renewcommand{\aeinsxelf}{ }
\renewcommand{\aeinsxzwoelf}{ }
\renewcommand{\azweixeins}{ 0 }
\renewcommand{\azweixzwei}{ 1 }
\renewcommand{\azweixdrei}{ 2 }
\renewcommand{\azweixvier}{ 3 }
\renewcommand{\azweixfuenf}{ 4 }
\renewcommand{\azweixsechs}{ 5 }
\renewcommand{\azweixsieben}{ 6 }
\renewcommand{\azweixacht}{ }
\renewcommand{\azweixneun}{ }
\renewcommand{\azweixzehn}{ }
\renewcommand{\azweixelf}{ }
\renewcommand{\azweixzwoelf}{ }
\renewcommand{\adreixeins}{ 0 }
\renewcommand{\adreixzwei}{ 2 }
\renewcommand{\adreixdrei}{ 4 }
\renewcommand{\adreixvier}{ 6 }
\renewcommand{\adreixfuenf}{ 1 }
\renewcommand{\adreixsechs}{ 3 }
\renewcommand{\adreixsieben}{ 5 }
\renewcommand{\adreixacht}{ }
\renewcommand{\adreixneun}{ }
\renewcommand{\adreixzehn}{ }
\renewcommand{\adreixelf}{ }
\renewcommand{\adreixzwoelf}{ }
\renewcommand{\avierxeins}{ 0 }
\renewcommand{\avierxzwei}{ 3 }
\renewcommand{\avierxdrei}{ 6 }
\renewcommand{\avierxvier}{ 2 }
\renewcommand{\avierxfuenf}{ 5 }
\renewcommand{\avierxsechs}{ 1 }
\renewcommand{\avierxsieben}{ 4 }
\renewcommand{\avierxacht}{ }
\renewcommand{\avierxneun}{ }
\renewcommand{\avierxzehn}{ }
\renewcommand{\avierxelf}{ }
\renewcommand{\avierxzwoelf}{ }
\renewcommand{\afuenfxeins}{ 0 }
\renewcommand{\afuenfxzwei}{ 4 }
\renewcommand{\afuenfxdrei}{ 1 }
\renewcommand{\afuenfxvier}{ 5 }
\renewcommand{\afuenfxfuenf}{ 2 }
\renewcommand{\afuenfxsechs}{ 6 }
\renewcommand{\afuenfxsieben}{ 3 }
\renewcommand{\afuenfxacht}{ }
\renewcommand{\afuenfxneun}{ }
\renewcommand{\afuenfxzehn}{ }
\renewcommand{\afuenfxelf}{ }
\renewcommand{\afuenfxzwoelf}{ }
\renewcommand{\asechsxeins}{ 0 }
\renewcommand{\asechsxzwei}{ 5 }
\renewcommand{\asechsxdrei}{ 3 }
\renewcommand{\asechsxvier}{ 1 }
\renewcommand{\asechsxfuenf}{ 6 }
\renewcommand{\asechsxsechs}{ 4 }
\renewcommand{\asechsxsieben}{ 2 }
\renewcommand{\asechsxacht}{ }
\renewcommand{\asechsxneun}{ }
\renewcommand{\asechsxzehn}{ }
\renewcommand{\asechsxelf}{ }
\renewcommand{\asechsxzwoelf}{ }
\renewcommand{\asiebenxeins}{ 0 }
\renewcommand{\asiebenxzwei}{ 6 }
\renewcommand{\asiebenxdrei}{ 5 }
\renewcommand{\asiebenxvier}{ 4 }
\renewcommand{\asiebenxfuenf}{ 3 }
\renewcommand{\asiebenxsechs}{ 2 }
\renewcommand{\asiebenxsieben}{ 1 }
\renewcommand{\asiebenxacht}{ }
\renewcommand{\asiebenxneun}{ }
\renewcommand{\asiebenxzehn}{ }
\renewcommand{\asiebenxelf}{ }
\renewcommand{\asiebenxzwoelf}{ }
\renewcommand{\aachtxeins}{ }
\renewcommand{\aachtxzwei}{ }
\renewcommand{\aachtxdrei}{ }
\renewcommand{\aachtxvier}{ }
\renewcommand{\aachtxfuenf}{ }
\renewcommand{\aachtxsechs}{ }
\renewcommand{\aachtxsieben}{ }
\renewcommand{\aachtxacht}{ }
\renewcommand{\aachtxneun}{ }
\renewcommand{\aachtxzehn}{ }
\renewcommand{\aachtxelf}{ }
\renewcommand{\aachtxzwoelf}{ }
\renewcommand{\aneunxeins}{ }
\renewcommand{\aneunxzwei}{ }
\renewcommand{\aneunxdrei}{ }
\renewcommand{\aneunxvier}{ }
\renewcommand{\aneunxfuenf}{ }
\renewcommand{\aneunxsechs}{ }
\renewcommand{\aneunxsieben}{ }
\renewcommand{\aneunxacht}{ }
\renewcommand{\aneunxneun}{ }
\renewcommand{\aneunxzehn}{ }
\renewcommand{\aneunxelf}{ }
\renewcommand{\aneunxzwoelf}{ }
\renewcommand{\azehnxeins}{ }
\renewcommand{\azehnxzwei}{ }
\renewcommand{\azehnxdrei}{ }
\renewcommand{\azehnxvier}{ }
\renewcommand{\azehnxfuenf}{ }
\renewcommand{\azehnxsechs}{ }
\renewcommand{\azehnxsieben}{ }
\renewcommand{\azehnxacht}{ }
\renewcommand{\azehnxneun}{ }
\renewcommand{\azehnxzehn}{ }
\renewcommand{\azehnxelf}{ }
\renewcommand{\azehnxzwoelf}{ }
\renewcommand{\aelfxeins}{ }
\renewcommand{\aelfxzwei}{ }
\renewcommand{\aelfxdrei}{ }
\renewcommand{\aelfxvier}{ }
\renewcommand{\aelfxfuenf}{ }
\renewcommand{\aelfxsechs}{ }
\renewcommand{\aelfxsieben}{ }
\renewcommand{\aelfxacht}{ }
\renewcommand{\aelfxneun}{ }
\renewcommand{\aelfxzehn}{ }
\renewcommand{\aelfxelf}{ }
\renewcommand{\aelfxzwoelf}{ }
\renewcommand{\azwoelfxeins}{ }
\renewcommand{\azwoelfxzwei}{ }
\renewcommand{\azwoelfxdrei}{ }
\renewcommand{\azwoelfxvier}{ }
\renewcommand{\azwoelfxfuenf}{ }
\renewcommand{\azwoelfxsechs}{ }
\renewcommand{\azwoelfxsieben}{ }
\renewcommand{\azwoelfxacht}{ }
\renewcommand{\azwoelfxneun}{ }
\renewcommand{\azwoelfxzehn}{ }
\renewcommand{\azwoelfxelf}{ }
\renewcommand{\azwoelfxzwoelf}{ }
\renewcommand{\adreizehnxeins}{ }
\renewcommand{\adreizehnxzwei}{ }
\renewcommand{\adreizehnxdrei}{ }
\renewcommand{\adreizehnxvier}{ }
\renewcommand{\adreizehnxfuenf}{ }
\renewcommand{\adreizehnxsechs}{ }
\renewcommand{\adreizehnxsieben}{ }
\renewcommand{\adreizehnxacht}{ }
\renewcommand{\adreizehnxneun}{ }
\renewcommand{\adreizehnxzehn}{ }
\renewcommand{\adreizehnxelf}{ }
\renewcommand{\adreizehnxzwoelf}{ }
\renewcommand{\avierzehnxeins}{ }
\renewcommand{\avierzehnxzwei}{ }
\renewcommand{\avierzehnxdrei}{ }
\renewcommand{\avierzehnxvier}{ }
\renewcommand{\avierzehnxfuenf}{ }
\renewcommand{\avierzehnxsechs}{ }
\renewcommand{\avierzehnxsieben}{ }
\renewcommand{\avierzehnxacht}{ }
\renewcommand{\avierzehnxneun}{ }
\renewcommand{\avierzehnxzehn}{ }
\renewcommand{\avierzehnxelf}{ }
\renewcommand{\avierzehnxzwoelf}{ }
\renewcommand{\afuenfzehnxeins}{ }
\renewcommand{\afuenfzehnxzwei}{ }
\renewcommand{\afuenfzehnxdrei}{ }
\renewcommand{\afuenfzehnxvier}{ }
\renewcommand{\afuenfzehnxfuenf}{ }
\renewcommand{\afuenfzehnxsechs}{ }
\renewcommand{\afuenfzehnxsieben}{ }
\renewcommand{\afuenfzehnxacht}{ }
\renewcommand{\afuenfzehnxneun}{ }
\renewcommand{\afuenfzehnxzehn}{ }
\renewcommand{\afuenfzehnxelf}{ }
\renewcommand{\afuenfzehnxzwoelf}{ }
\renewcommand{\asechzehnxeins}{ }
\renewcommand{\asechzehnxzwei}{ }
\renewcommand{\asechzehnxdrei}{ }
\renewcommand{\asechzehnxvier}{ }
\renewcommand{\asechzehnxfuenf}{ }
\renewcommand{\asechzehnxsechs}{ }
\renewcommand{\asechzehnxsieben}{ }
\renewcommand{\asechzehnxacht}{ }
\renewcommand{\asechzehnxneun}{ }
\renewcommand{\asechzehnxzehn}{ }
\renewcommand{\asechzehnxelf}{ }
\renewcommand{\asechzehnxzwoelf}{ }
\renewcommand{\asiebzehnxeins}{ }
\renewcommand{\asiebzehnxzwei}{ }
\renewcommand{\asiebzehnxdrei}{ }
\renewcommand{\asiebzehnxvier}{ }
\renewcommand{\asiebzehnxfuenf}{ }
\renewcommand{\asiebzehnxsechs}{ }
\renewcommand{\asiebzehnxsieben}{ }
\renewcommand{\asiebzehnxacht}{ }
\renewcommand{\asiebzehnxneun}{ }
\renewcommand{\asiebzehnxzehn}{ }
\renewcommand{\asiebzehnxelf}{ }
\renewcommand{\asiebzehnxzwoelf}{ }
\renewcommand{\aachtzehnxeins}{ }
\renewcommand{\aachtzehnxzwei}{ }
\renewcommand{\aachtzehnxdrei}{ }
\renewcommand{\aachtzehnxvier}{ }
\renewcommand{\aachtzehnxfuenf}{ }
\renewcommand{\aachtzehnxsechs}{ }
\renewcommand{\aachtzehnxsieben}{ }
\renewcommand{\aachtzehnxacht}{ }
\renewcommand{\aachtzehnxneun}{ }
\renewcommand{\aachtzehnxzehn}{ }
\renewcommand{\aachtzehnxelf}{ }
\renewcommand{\aachtzehnxzwoelf}{ }
\tabelleleitsiebenxsieben
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Monkey_Saddle_Surface_(Shaded).png} }
\end{center}
\bildtext {} }
\bildlizenz { Monkey Saddle Surface (Shaded).png } {} {Inductiveload} {Commons} {PD} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Schoenberg-ebringen-isohypsen.png} }
\end{center}
\bildtext {} }
\bildlizenz { Schoenberg-ebringen-isohypsen.png } {} {W-j-s} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Elliptic_orbit.gif} }
\end{center}
\bildtext {} }
\bildlizenz { Elliptic orbit.gif } {} {Brandir} {Commons} {CC-BY-SA 2.5} {}
Wir wollen zu zwei gegebenen Nummerierungen einer Menge $M$, also zu zwei bijektiven Abbildungen
\maabb {\varphi} { { \{ 1 , \ldots , n \} } } { M
} {}
und
\maabb {\psi} { \{ 1 , \ldots , k \} } { M
} {}
zeigen, dass
\mavergleichskette
{\vergleichskette
{n
}
{ = }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Da bei einer Bijektion sich die Elemente der beiden Mengen eindeutig entsprechen, führt dies zu einer eindeutigen Entsprechung zwischen
\mathkor {} {{ \{ 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.
\zwischenueberschrift{Die Hintereinanderschaltung von Abbildungen}
\inputdefinition
{}
{
Es seien $L,\, M$ und $N$ Mengen und \maabbeledisp {F} {L} {M } {x} {F(x) } {,} und \maabbeledisp {G} {M} {N } {y} {G(y) } {,} \definitionsverweis {Abbildungen}{}{.} Dann heißt die Abbildung \maabbeledisp {G \circ F} {L} {N } {x} {G(F(x)) } {,} die \definitionswort {Hintereinanderschaltung}{} der Abbildungen \mathkor {} {F} {und} {G} {.}
}
Eine Hintereinanderschaltung kann man sich durch ein Diagramm der Form
\mathdisp {L \stackrel{F}{\longrightarrow} M \stackrel{G}{\longrightarrow} N} { }
gut veranschaulichen.
\inputbeispiel{}
{
Die Wertetabelle
\wertetabellezehnausteilzeilen { $n$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileundfuenf {6} {7} {8} {9} {10} }
{ $\varphi(n)$ }
{\mazeileundfuenf {A} {A} {B} {C} {C} }
{\mazeileundfuenf {B} {E} {D} {D} {B} }
beschreibt, welche Person der Bearbeitungsgruppe
\mavergleichskette
{\vergleichskette
{G
}
{ = }{\{A,B,C,D,E\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
welche Aufgabe federführend macht und die Wertetabelle
\wertetabellefuenfausteilzeilen { $P$ }
{\mazeileundfuenf {A} {B} {C} {D} {E} }
{ $\psi(P)$ }
{\mazeileundfuenf {S} {L} {M} {M} {W} }
mit den möglichen Werten
\mathl{\{M,S,L,W,U\}}{} beschreibt, wie viel Lust die Personen in dieser Woche haben
\zusatzklammer {$M$
- hat Megalust, $S$
- hat Superlust, $L$ hat Lust, $W$ hat wenig Lust, $U$ hat Unlust} {} {.}
Die zusammengesetzte Abbildung
\mathl{\psi \circ \varphi}{} beschreibt dann, mit wie viel Lust die verschiedenen Aufgaben bearbeitet werden, die zugehörige Wertetabelle ist
\wertetabellezehnausteilzeilen { $n$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileundfuenf {6} {7} {8} {9} {10} }
{ $\psi(\varphi(n))$ }
{\mazeileundfuenf {S} {S} {L} {M} {M} }
{\mazeileundfuenf {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
\maabbdisp {\varphi , \psi} {\R_{\geq 0} } {\R_{\geq 0}
} {}
Funktionen sind, die durch
\mathkor {} {\varphi(x) = x^2 +5} {und} {\psi (y) = \sqrt{ y}} {}
gegeben sind, so besitzt die zusammengesetzte Funktion
\mathl{\psi \circ \varphi}{}
\zusatzklammer {also in der Ausführung zuerst $\varphi$} {!} {}
die Vorschrift
\mavergleichskettedisp
{\vergleichskette
{ ( \psi \circ \varphi ) (x)
}
{ =} { \psi (\varphi(x))
}
{ =} { \sqrt{ x^2+5 }
}
{ } {
}
{ } {
}
}
{}{}{.}
In der anderen Reihenfolge ergibt sich
\mavergleichskettedisp
{\vergleichskette
{ ( \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.
\inputfaktbeweis
{Abbildung/Hintereinanderschaltung/Assoziativ/Fakt}
{Lemma}
{}
{
\faktsituation {Es seien
$L, M, N$ und $P$
Mengen und es seien
\maabbeledisp {F} {L} {M
} {x} {F(x)
} {,} \maabbeledisp {G} {M} {N
} {y} {G(y)
} {,}
und
\maabbeledisp {H} {N} {P
} {z} {H(z)
} {,}
\definitionsverweis {Abbildungen}{}{.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{ H \circ (G \circ F)
}
{ =} { (H \circ G) \circ F
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Zwei Abbildungen
\maabb {\alpha, \beta} {L} {P
} {}
sind genau dann gleich, wenn für jedes
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Gleichheit
\mavergleichskette
{\vergleichskette
{ \alpha(x)
}
{ = }{\beta(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt. Es sei also
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskettealign
{\vergleichskettealign
{ ( 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)
}
}
{}
{}{.}
\inputfaktbeweis
{Abbildung/Hintereinanderschaltung/Injektiv surjektiv bijektiv/Fakt}
{Lemma}
{}
{
\faktsituation {Es seien
$L,\, M$ und $N$
Mengen und
\maabbeledisp {F} {L} {M
} {x} {F(x)
} {,}
und
\maabbeledisp {G} {M} {N
} {y} {G(y)
} {,}
\definitionsverweis {Abbildungen}{}{}
mit der
\definitionsverweis {Hintereinanderschaltung}{}{}
\maabbdisp {G \circ F} {L} {N
} {.}}
\faktuebergang {Dann gelten folgende Eigenschaften.}
\faktfolgerung {\aufzaehlungdrei{Wenn
\mathkor {} {F} {und} {G} {}
\definitionsverweis {injektiv}{}{}
sind, so ist auch
\mathl{G \circ F}{} injektiv.
}{Wenn
\mathkor {} {F} {und} {G} {}
\definitionsverweis {surjektiv}{}{}
sind, so ist auch
\mathl{G \circ F}{} surjektiv.
}{Wenn
\mathkor {} {F} {und} {G} {}
\definitionsverweis {bijektiv}{}{}
sind, so ist auch
\mathl{G \circ F}{} bijektiv.
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungdrei{Es seien
\mavergleichskette
{\vergleichskette
{ x,x'
}
{ \in }{ L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{ G(F(x))
}
{ =} { G(F(x'))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben. Aufgrund der Injektivität von $G$ folgt
\mavergleichskettedisp
{\vergleichskette
{F(x)
}
{ =} {F(x')
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und aufgrund der Injektivität von $F$ folgt
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} {x'
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
was die Injektivität von
\mathl{G \circ F}{} bedeutet.
}{Sei
\mavergleichskette
{\vergleichskette
{ z
}
{ \in }{ N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben. Aufgrund der Surjektivität von $G$ gibt es ein
\mavergleichskette
{\vergleichskette
{ y
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{G(y)
}
{ =} {z
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Aufgrund der Surjektivität von $F$ gibt es ein
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{F(x)
}
{ =} {y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Insgesamt ist
\mavergleichskettedisp
{\vergleichskette
{ (G \circ F ) (x)
}
{ =} { G(F(x))
}
{ =} { G(y)
}
{ =} { z
}
{ } {
}
}
{}{}{,}
es gibt also ein Urbild von $z$ und somit ist die Gesamtabbildung surjektiv.
}{Folgt aus (1) und (2).
}
\zwischenueberschrift{Die Umkehrabbildung}
\inputdefinition
{}
{
Es sei $M$ eine Menge. Dann heißt die
\definitionsverweis {Abbildung}{}{}
\maabbeledisp {} {M} {M
} {x} {x
} {,}
die also jedes Element
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ M
}
{ }{}
{ }{}
{ }{}
}
{}{}{}
auf sich selbst schickt, die \definitionswort {identische Abbildung}{} oder \definitionswort {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.
\inputdefinition
{}
{
Es sei
\maabb {F} {L} {M} {}
eine
\definitionsverweis {bijektive Abbildung}{}{.}
Dann heißt die Abbildung
\maabbdisp {G} {M} {L} {,}
die jedes Element
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf das eindeutig bestimmte Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{F(x)
}
{ = }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
abbildet, die \definitionswort {Umkehrabbildung}{} zu $F$.
}
Die Umkehrabbildung zu $F$ wird mit $F^{-1}$ bezeichnet. Es gilt die charakteristische Eigenschaft, dass sowohl
\mathl{F \circ F^{-1}}{} als auch
\mathl{F^{-1} \circ F}{} die Identität
\zusatzklammer {auf den jeweiligen Mengen} {} {}
sind.
\inputbeispiel{}
{
Die Nummerierung der Schüler durch Heino,
\wertetabellezehnausteilzeilen { $n$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileundfuenf {6} {7} {8} {9} {10} }
{ $\varphi(n)$ }
{\mazeileundfuenf {M} {T} {A} {L} {S} }
{\mazeileundfuenf {B} {G} {R} {H} {C} }
ist bijektiv und hat daher eine eindeutig bestimmte
\definitionsverweis {Umkehrabbildung}{}{.}
Die Wertetabelle dieser Umkehrabbildung ist
\wertetabellezehnausteilzeilen { $P$ }
{\mazeileundfuenf {A} {B } {C } {G} {H} }
{\mazeileundfuenf { L} {M} {R} {S} {T } }
{ $\varphi^{-1} (P)$ }
{\mazeileundfuenf {3} {6} {10} {7} {9} }
{\mazeileundfuenf {4} {1} {8} {5} {2} }
Bei einem natürlichen Zählvorgang kann man sich darüber streiten, ob die Zahlen \anfuehrung{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.
\inputdefinition
{}
{
Es seien
\mathkor {} {L} {und} {M} {}
Mengen und es sei
\mavergleichskette
{\vergleichskette
{ c
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Element. Dann heißt die
\definitionsverweis {Abbildung}{}{}
\maabbeledisp {} {L} {M
} {x} {c
} {,}
die also jedes Element
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf $c$ abbildet, die \definitionswort {konstante Abbildung}{} zum Wert $c$.
}
\zwischenueberschrift{Die Wohldefiniertheit der Anzahl}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {VerschiedeneNummerierungen.png} }
\end{center}
\bildtext {} }
\bildlizenz { VerschiedeneNummerierungen.png } {Bocardodarapti} {} {Commons} {CC-by-sa 4.0} {}
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.
\inputfaktbeweis
{Endliche Menge/1 bis k/Eins heraus/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{k
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine natürliche Zahl mit dem Vorgänger $\ell$, es sei also
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ \ell^\prime
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{z
}
{ \in }{ \{ 1 , \ldots , k \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein fixiertes Element.}
\faktfolgerung {Dann gibt es eine bijektive Abbildung zwischen
\mathl{\{1 , \ldots , \ell \}}{} und
\mathl{\{ 1 , \ldots , k \} \setminus \{z\}}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir definieren eine Abbildung
\maabbdisp {\varphi} { \{1 , \ldots , \ell \} } { \{ 1 , \ldots , k \} \setminus \{z\}
} {}
durch
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ \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 \mathkor {} {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 \zusatzklammer {dies ist die Eigenschaft, dass der Vorgänger eindeutig bestimmt ist} {} {.} Wenn $x$ unterhalb von $z$ und $y$ oberhalb von $z$ \zusatzklammer {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$
\zusatzklammer {und unterhalb von $k$ einschließlich $k$} {} {}
kann man als
\mavergleichskettedisp
{\vergleichskette
{u
}
{ =} {v^\prime
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit $v$ oberhalb von $z$
\zusatzklammer {einschließlich $z$} {} {}
und echt unterhalb von $k$, also maximal gleich $\ell$ schreiben. Insgesamt ist $\varphi$ also eine Bijektion.
\inputfaktbeweis
{Endliche Mengen/Anzahl/Wohldefiniert/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Wenn $M$ eine Menge ist und wenn
\maabbdisp {\varphi} { { \{ 1 , \ldots , n \} } } {M
} {}
und
\maabbdisp {\psi} { \{ 1 , \ldots , k \} } {M
} {}
\definitionsverweis {bijektive Abbildungen}{}{}
sind,}
\faktfolgerung {so ist
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {Die Anzahl einer endlichen Menge ist also wohldefiniert.}
\faktzusatz {}
}
{
Es seien die bijektiven Abbildungen
\maabbdisp {\varphi} { { \{ 1 , \ldots , n \} } } {M
} {}
und
\maabbdisp {\psi} { \{ 1 , \ldots , k \} } {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
\maabbdisp {\psi^{-1} \circ \varphi} { { \{ 1 , \ldots , n \} } } { \{ 1 , \ldots , k \}
} {}
bijektiv. Wir müssen also nur die endlichen Standardmengen
\mathl{{ \{ 1 , \ldots , n \} }}{} untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung
\maabbdisp {\theta} { { \{ 1 , \ldots , n \} } } { \{ 1 , \ldots , k \}
} {}
vorliegt, dass dann
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist. Dies zeigen wir durch Induktion\zusatzfussnote {Dies ist ein Induktionsbeweis, ein Prinzip, das für die natürlichen Zahlen gilt und das wir später begründen werden} {.} {} nach $n$. Wenn
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es seien nun
\mathl{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
\mavergleichskettedisp
{\vergleichskette
{ z
}
{ =} {\theta (n)
}
{ \in} { \{ 1 , \ldots , k \}
}
{ } {
}
{ } {
}
}
{}{}{.}
Dann gibt es nach der Herausnahme von $n$ bzw. $z$ eine bijektive Abbildung
\maabbdisp {} { \{ 1 , \ldots , m \} = { \{ 1 , \ldots , n \} } \setminus \{n\} } { \{ 1 , \ldots , k \} \setminus \{z\}
} {.}
Nach
Lemma 6.9
gibt es eine bijektive Abbildung zwischen
\mathkor {} {\{1 , \ldots , \ell \}} {und} {\{ 1 , \ldots , k \} \setminus \{z\}} {.}
Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen
\mathkor {} {\{ 1 , \ldots , m \}} {und} {\{1 , \ldots , \ell \}} {.}
Nach Induktionsvoraussetzung ist
\mavergleichskette
{\vergleichskette
{m
}
{ = }{\ell
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also auch
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {m'
}
{ =} {\ell'
}
{ =} {k
}
{ } {
}
}
{}{}{.}
\zwischenueberschrift{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\zusatzfussnote {Es ist bei diesen wichtigen Operationen nicht einheitlich festgelegt, welche der beiden beteiligten Zahlen die Anzahl der Prozesse angibt und welche angibt, dass mit ihr der Prozess durchgeführt werden soll. Ferner kommt beispielsweise bei
\mathl{5 \cdot 3=3+3+3+3+3=0+3+3+3+3+3}{} der Summand $3$ fünfmal vor, in der ersten Darstellung kommt aber nur viermal das Pluszeichen vor, sodass hier Präzisierungen nötig sind. Auch Formulierungen wie \anfuehrung{mit sich selbst addieren}{} sind problematisch, es wird ja jeweils zu dem Teilergebnis hinzuaddiert} {.} {}
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
\zusatzklammer {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
\zusatzklammer {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
\mathl{(n-1)}{-}mal umschlägt.