Kurs:Analysis (Osnabrück 2013-2015)/Teil I/Endliche Mengen/latex
\inputdefinition
{}
{
Eine Menge $M$ heißt \definitionswort {endlich}{} mit $n$ Elementen, wenn es eine \definitionsverweis {Bijektion}{}{} \maabbdisp {} {\{ 1 , \ldots , n \}} {M} {} gibt.
}
Die natürliche Zahl $n$ ist dabei nach
Aufgabe 2.5
eindeutig bestimmt und heißt die \stichwort {Anzahl} {}
\zusatzklammer {oder die \stichwort {Kardinalität} {}} {} {}
der Menge. Sie wird mit
\mathl{{ \# \left( M \right) }}{} oder mit
\mathl{\betrag { M }}{} bezeichnet. Die bijektive Abbildung
\maabbdisp {} {\{1 , \ldots , n \}} {M
} {}
kann man eine \stichwort {Nummerierung} {} der Menge $M$ nennen. Eine Menge besitzt also $n$ Elemente, wenn man sie mit den natürlichen Zahlen von $1$ bis $n$ durchnummerieren kann. Zwei endliche Mengen
\mathkor {} {M} {und} {N} {,}
für die es eine Bijektion
\maabbdisp {} {M} {N
} {}
gibt, besitzen die gleiche Anzahl. Dies beruht einfach darauf, dass diese Bijektion verknüpft mit der bijektiven Nummerierung wieder eine Bijektion ist. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit
\mathl{{ \{ 1 , \ldots , n \} }}{} für kein $n$ gibt, heißt \stichwort {unendlich} {.}
\inputfaktbeweis
{Endliche Menge/Schubfachprinzip/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $M$ eine
\definitionsverweis {endliche Menge}{}{}
mit $m$ Elementen und $N$ eine endliche Menge mit $n$ Elementen.}
\faktvoraussetzung {Es sei
\mavergleichskette
{\vergleichskette
{m
}
{ > }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann gibt es keine
\definitionsverweis {injektive Abbildung}{}{}
\maabbdisp {} {M} {N
} {.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir nehmen an, dass es eine injektive Abbildung
\maabbdisp {\varphi} {M} {N
} {}
gibt. Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ = }{\varphi(M)
}
{ \subseteq }{ N
}
{ }{
}
{ }{
}
}
{}{}{}
das
\definitionsverweis {Bild}{}{}
von $M$ unter der Abbildung $\varphi$. Dann ergibt sich eine Bijektion
\maabbdisp {\tilde{\varphi}} {M} {T
} {,}
da sich die Injektivität überträgt und da eine Abbildung immer surjektiv auf ihr Bild ist. Daher haben
\mathkor {} {M} {und} {T} {}
gleich viele Elemente. Nach
Aufgabe 10.1
ist die Anzahl einer Teilmenge stets kleiner oder gleich der Anzahl der Menge. Also ist
\mavergleichskette
{\vergleichskette
{m
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
im Widerspruch zur Voraussetzung.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {TooManyPigeons.jpg} }
\end{center}
\bildtext {} }
\bildlizenz { TooManyPigeons.jpg } {} {McKay} {en Wikipedia} {CC-by-sa 3.0} {}
Die vorstehende Aussage heißt \stichwort {Schubfachprinzip} {}
\zusatzklammer {oder \stichwort {Taubenschlagprinzip} {}} {} {.}
Es besagt, dass wenn man $m$ Tauben auf $n$ Plätze verteilt mit
\mavergleichskette
{\vergleichskette
{m
}
{ > }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
dass dann in mindestens einem Platz mindestens zwei Tauben landen.
\inputfaktbeweis
{Endliche Menge/Gleiche Anzahl/Injektiv ist surjektiv/Fakt}
{Lemma}
{}
{
Seien \mathkor {} {M} {und} {N} {} \definitionsverweis {endliche Mengen}{}{} mit $n$ Elementen. Dann sind für eine Abbildung \maabbdisp {F} {M} {N } {} die Begriffe \definitionsverweis {injektiv}{}{,} \definitionsverweis {surjektiv}{}{} und \definitionsverweis {bijektiv}{}{} äquivalent.
}
{
Wir führen Induktion über die Anzahl $n$ der beiden Mengen
\mathkor {} {M} {und} {N} {.} Bei
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es nur die leere Abbildung
\zusatzklammer {von der leeren Menge in die leere Menge} {} {,}
und diese erfüllt alle drei Eigenschaften. Es sei nun
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Aussage für alle endlichen Mengen $M$ mit einer Anzahl $<n$ bewiesen. Es muss lediglich die Äquivalenz von injektiv und surjektiv gezeigt werden. Es sei zunächst $F$ injektiv. Wir wählen ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und setzen
\mavergleichskette
{\vergleichskette
{y
}
{ = }{F(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir setzen
\mathdisp {M' =M \setminus \{x \} \text{ und } N' =N \setminus \{y\}} { . }
Beide Mengen haben
nach Fakt *****
\mathl{n-1}{} Elemente, und somit kann man darauf die Induktionsvoraussetzung anwenden. Es sei
\maabbeledisp {F'} {M'} {N'
} {x} {F(x)
} {.}
Diese Abbildung ist wohldefiniert, da wegen der Injektivität nur das Element $x$ auf $y$ abgebildet wird, alle anderen Elemente aus $M'$ werden auf andere Elemente abgebildet, d.h. sie landen in $N'$. Die Injektivität von $F$ überträgt sich auf die Teilmenge $M'$. Nach der Induktionsvoraussetzung ist also $F'$ surjektiv. Damit ist aber insgesamt $F$ surjektiv, da einerseits $y$ im Bild liegt
\zusatzklammer {mit $x$ als Urbild} {} {}
und da andererseits jedes Element
\mavergleichskette
{\vergleichskette
{z
}
{ \neq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zu $N'$ gehört und damit ein Urbild in $M'$ besitzt.
Es sei nun $F$ surjektiv. Sei
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beliebig und
\mavergleichskette
{\vergleichskette
{y
}
{ = }{F(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir betrachten die
\definitionsverweis {Einschränkung}{}{}
\maabbdisp {F'} {M' = M \setminus \{x\}} {N
} {.}
Diese Abbildung kann nicht surjektiv sein. Andernfalls würde sich nämlich der Widerspruch \zusatzklammer {hier geht auch
Aufgabe *****
ein} {} {}
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { { \# \left( M \right) }
}
{ >} {{ \# \left( M \setminus \{x\} \right) }
}
{ \geq} {{ \# \left( F( M \setminus \{x\} ) \right) }
}
{ =} { { \# \left( N \right) }
}
}
{
\vergleichskettefortsetzung
{ =} {n
}
{ } {}
{ } {}
{ } {}
}{}{}
ergeben. Daher muss $y$ im Bild von $F'$ fehlen, und das heißt, dass eine surjektive Abbildung
\maabbdisp {} {M \setminus \{x\} } { N \setminus \{y\}
} {}
vorliegt. Beide Mengen besitzen
\mathl{n-1}{} Elemente, sodass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.