Kurs:Vorkurs Mathematik (Osnabrück 2009)/Arbeitsblatt 6/latex
\zwischenueberschrift{Aufgaben zur Mächtigkeit}
\inputaufgabe
{}
{
Es seien \mathkor {} {L} {und} {M} {} zwei Mengen und \maabb {\varphi} {L} {M } {} eine \definitionsverweis {bijektive Abbildung}{}{} zwischen diesen Mengen. Zeige, dass für jede Teilmenge $S \subseteq L$ eine Bijektion \maabb {} {S} {\varphi(S) } {} vorliegt, und dass ebenso für jede Teilmenge $T\subseteq M$ eine Bijektion \maabb {} {\varphi^{-1}(T)} {T } {} vorliegt.
}
{} {}
\inputaufgabe
{}
{
Es sei $M$ eine Menge und $\mathfrak {P} \, (M )$ die \definitionsverweis {Potenzmenge}{}{} davon. Zeige, dass durch die \definitionsverweis {Gleichmächtigkeit}{}{} von Mengen eine \definitionsverweis {Äquivalenzrelation}{}{} auf $\mathfrak {P} \, (M )$ definiert wird.
}
{} {}
\inputaufgabe
{}
{
Es sei $M$ eine Menge und $\mathfrak {P} \, (M )$ die
\definitionsverweis {Potenzmenge}{}{} davon. Zeige, dass durch
\mathdisp {S \preccurlyeq T, \text{wenn es eine injektive Abbildung } S \rightarrow T \text{ gibt}} { , }
eine \definitionsverweis {reflexive}{}{} und \definitionsverweis {transitive}{}{} \definitionsverweis {Relation}{}{} auf $\mathfrak {P} \, (M )$ definiert wird, die in aller Regel weder \definitionsverweis {symmetrisch}{}{} noch \definitionsverweis {antisymmetrisch}{}{} ist.
}
{} {}
\inputaufgabe
{}
{
Definiere eine \definitionsverweis {bijektive Abbildung}{}{} zwischen den natürlichen Zahlen $\N$ und den rationalen Zahlen $\Q$.
}
{} {}
\inputaufgabe
{}
{
Man gebe ein Beispiel für eine \definitionsverweis {surjektive Abbildung}{}{} \maabbdisp {\varphi} {\R} {\R} {} derart, dass jeder Wert $y \in \R$ unendlich oft angenommen wird.
}
{} {}
\zwischenueberschrift{Aufgaben zu endlichen Mengen}
Die folgenden Aufgaben über endliche Mengen sind intuitiv klar. Es geht aber darum, sie unter Bezug auf die Definitionen mit Hilfe von bijektiven Abbildungen zu beweisen.
\inputaufgabe
{}
{
Zeige, dass die Menge $\{1 , \ldots , n \}$ endlich mit $n$ Elementen ist. Zeige ferner, dass für jedes $k \in \N$ die Menge
\mavergleichskettedisp
{\vergleichskette
{ \{k+1 , \ldots , k+n \}
}
{ =} { { \left\{ x \in \N \mid x \geq k+1 \text{ und } x \leq k+n \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ebenfalls eine endliche Menge mit $n$ Elementen ist.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathbed {n \in \N} {}
{n \geq 1} {}
{} {} {} {}
und $x \in \{1 , \ldots , n \}$. Zeige, dass die Menge
\mathdisp {\{1 , \ldots , n \} \setminus \{z \}} { }
die Anzahl $n-1$ besitzt.
}
{} {}
\inputaufgabe
{}
{
Es seien
\mathkor {} {m} {und} {n} {} natürliche Zahlen. Zeige durch Induktion über $m$, dass aus einer
\definitionsverweis {Bijektion}{}{}
\maabbdisp {\varphi} {\{ 1, \ldots , m\}} {\{ 1, \ldots , n\}
} {}
folgt, dass
\mavergleichskette
{\vergleichskette
{ m
}
{ = }{ n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $M$ eine \definitionsverweis {endliche Menge}{}{.} Zeige, dass die Anzahl von $M$ wohldefiniert ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $M$ eine
\definitionsverweis {endliche Menge}{}{}
mit $m$ Elementen und es sei
\mavergleichskette
{\vergleichskette
{ T
}
{ \subseteq }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge. Zeige, dass $T$ ebenfalls eine endliche Menge ist, und dass für ihre Anzahl $k$ die Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ k
}
{ \leq} { m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt. Zeige ferner, dass $T$ genau dann eine echte Teilmenge ist, wenn
\mavergleichskettedisp
{\vergleichskette
{ k
}
{ <} { m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $M$ eine
\definitionsverweis {endliche Menge}{}{}
mit $m$ Elementen und es sei
\maabbdisp {} {M} {N
} {}
eine
\definitionsverweis {surjektive Abbildung}{}{}
in eine weitere Menge $N$. Zeige, dass dann auch $N$ endlich ist, und dass für ihre Anzahl $n$ die Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ n
}
{ \leq} { m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabe
{}
{
Es sei $T \subseteq \N$ eine nichtleere Teilmenge der natürlichen Zahlen. Zeige, dass $T$ genau dann \definitionsverweis {endlich}{}{} ist, wenn $T$ ein \definitionsverweis {Maximum}{}{} besitzt.
}
{} {}
\inputaufgabe
{}
{
Mit welcher Wahrscheinlichkeit gewinnt man im Lotto \anfuehrung{Sechs aus Neunundvierzig}{?}
}
{} {}
\inputaufgabe
{}
{
Es seien \mathkor {} {M} {und} {N} {} zwei disjunkte \definitionsverweis {endliche Mengen}{}{.} Zeige, dass die Anzahl der \zusatzklammer {disjunkten} {} {} Vereinigung $M \cup N$ gleich der Summe der beiden Anzahlen der beiden Mengen ist.
}
{} {}
\inputaufgabe
{}
{
Es seien
\mathkor {} {M} {und} {N} {} endliche Mengen. Zeige, dass die
\definitionsverweis {Produktmenge}{}{}
$M \times N$ ebenfalls endlich ist, und dass die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( M \times N \right) }
}
{ =} { { \# \left( M \right) } \cdot { \# \left( N \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
In den drei folgenden Aufgaben bezeichen wir mit $S_n$ die Menge der bijektiven Abbildungen von $\{1, \ldots , n\}$ in sich selbst\zusatzfussnote {In diesen drei Aufgaben beweisen wir, dass man eine $n$-elementige Menge auf $n!$ verschiedene Weisen anordnen kann. Der Aufwand mag angesichts der simplen Idee, dass es für das erste Element $n$ Möglichkeiten gibt, für das zweite $n-1$ Möglichkeiten usw. unangemessen hoch erscheinen. Dies beruht eben darauf, dass wir einen präzisen Beweis geben, der auf einer präzisen Definition der Anzahl aufbaut. Es sei aber hier schon ausdrücklich erwähnt, dass allgemein in der höheren Mathematik dieses Missverhältnis zwischen einer
\zusatzklammer {detaillierten} {} {}
Beweisidee und deren Übersetzung in einen korrekten Beweis nicht herrscht} {.} {.}
\inputaufgabe
{}
{
Zeige, dass durch die Zuordnung
\maabbeledisp {} { S_n \times \{1 , \ldots , n+1\} } { S_{n+1}
} { (\varphi,x) } { \tilde{ \varphi}
} {,}
mit
\mavergleichskettedisp
{\vergleichskette
{ \tilde{\varphi} (k)
}
{ =} { \begin{cases} \varphi(k) \text{ für } k \leq n \text{ und } \varphi(k) < x \, , \\
\varphi(k)+1 \text{ für } k \leq n \text{ und } \varphi(k) \geq x \, , \\
x \text{ für } k = n+1 \, , \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine wohldefinierte bijektive Abbildung gegeben ist.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( S_n \right) }
}
{ =} { n!
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei $M$ eine $n$-elementige Menge und sei
\mathdisp {B={ \left\{ F:M \rightarrow M \text{ Abbildung} \mid F \text{ bijektiv} \right\} }} { . }
Zeige, dass
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( B \right) }
}
{ =} {n!
}
{ } {
}
{ } {
}
{ } {}
}
{}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Es seien
\mathkor {} {M} {und} {N} {} zwei
\definitionsverweis {endliche Teilmengen}{}{}
einer Menge $G$. Zeige, dass die Formel
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( M \right) } + { \# \left( N \right) }
}
{ =} { { \# \left( M \cup N \right) } + { \# \left( M \cap N \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabe
{}
{
Es sei $G$ eine Menge und es seien
\mathbed {M_i \subseteq G} {}
{i =1 , \ldots , n} {}
{} {} {} {,}
\definitionsverweis {endliche Teilmengen}{}{.}
Für eine Teilmenge $J \subseteq \{1 , \ldots , n\}$ sei
\mavergleichskettedisp
{\vergleichskette
{ M_J
}
{ =} { \bigcap_{i \in J} M_i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Finde eine Beziehung zwischen den Anzahlen der verschiedenen Schnittmengen
\mathbed {M_J} {}
{J \subseteq \{1 , \ldots , n\}} {}
{} {} {} {.}
Beweise diese Formel.
}
{} {}
\inputaufgabe
{}
{
Es sei $(I, \preccurlyeq)$ eine \definitionsverweis {total geordnete}{}{} Menge. Zeige durch Induktion, dass jede nichtleere endliche Teilmenge $T \subseteq I$ ein eindeutiges \definitionsverweis {Maximum}{}{} besitzt.
}
{} {}