Kurs:Vorkurs Mathematik (Osnabrück 2009)/Arbeitsblatt 6/kontrolle

Aufgaben zur Mächtigkeit

Aufgabe Referenznummer erstellen

Es seien ${}L$ und ${}M$ zwei Mengen und ${}\varphi \colon L\rightarrow M$ eine bijektive Abbildung zwischen diesen Mengen. Zeige, dass für jede Teilmenge ${}S\subseteq L$ eine Bijektion ${}S\rightarrow \varphi (S)$ vorliegt, und dass ebenso für jede Teilmenge ${}T\subseteq M$ eine Bijektion ${}\varphi ^{-1}(T)\rightarrow T$ vorliegt.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge davon. Zeige, dass durch die Gleichmächtigkeit von Mengen eine Äquivalenzrelation auf ${}{\mathfrak {P}}\,(M)$ definiert wird.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge davon. Zeige, dass durch

$S\preccurlyeq T,{\text{wenn es eine injektive Abbildung }}S\rightarrow T{\text{ gibt}},$

eine reflexive und transitive Relation auf ${}{\mathfrak {P}}\,(M)$ definiert wird, die in aller Regel weder symmetrisch noch antisymmetrisch ist.

Aufgabe Referenznummer erstellen

Definiere eine bijektive Abbildung zwischen den natürlichen Zahlen ${}\mathbb {N}$ und den rationalen Zahlen ${}\mathbb {Q}$.

Aufgabe Referenznummer erstellen

Man gebe ein Beispiel für eine surjektive Abbildung

$\varphi \colon \mathbb {R} \longrightarrow \mathbb {R}$

derart, dass jeder Wert ${}y\in \mathbb {R}$ unendlich oft angenommen wird.

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.

Aufgabe Referenznummer erstellen

Zeige, dass die Menge ${}\{1,\ldots ,n\}$ endlich mit ${}n$ Elementen ist. Zeige ferner, dass für jedes ${}k\in \mathbb {N}$ die Menge

${}\{k+1,\ldots ,k+n\}={\left\{x\in \mathbb {N} \mid x\geq k+1{\text{ und }}x\leq k+n\right\}}\,$

ebenfalls eine endliche Menge mit ${}n$ Elementen ist.

Aufgabe Referenznummer erstellen

Es sei ${}n\in \mathbb {N}$, ${}n\geq 1$ und ${}x\in \{1,\ldots ,n\}$. Zeige, dass die Menge

$\{1,\ldots ,n\}\setminus \{z\}$

die Anzahl ${}n-1$ besitzt.

Aufgabe Referenznummer erstellen

Es seien ${}m$ und ${}n$ natürliche Zahlen. Zeige durch Induktion über ${}m$, dass aus einer Bijektion

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

folgt, dass ${}m=n$ ist.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine endliche Menge. Zeige, dass die Anzahl von ${}M$ wohldefiniert ist.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und es sei ${}T\subseteq M$ eine Teilmenge. Zeige, dass ${}T$ ebenfalls eine endliche Menge ist, und dass für ihre Anzahl ${}k$ die Abschätzung

${}k\leq m\,$

gilt. Zeige ferner, dass ${}T$ genau dann eine echte Teilmenge ist, wenn

${}k<m\,$

ist.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und es sei

$M\longrightarrow N$

eine surjektive Abbildung in eine weitere Menge ${}N$. Zeige, dass dann auch ${}N$ endlich ist, und dass für ihre Anzahl ${}n$ die Abschätzung

${}n\leq m\,$

gilt.

Aufgabe Referenznummer erstellen

Es sei ${}T\subseteq \mathbb {N}$ eine nichtleere Teilmenge der natürlichen Zahlen. Zeige, dass ${}T$ genau dann endlich ist, wenn ${}T$ ein Maximum besitzt.

Aufgabe Referenznummer erstellen

Mit welcher Wahrscheinlichkeit gewinnt man im Lotto „Sechs aus Neunundvierzig“?

Aufgabe Referenznummer erstellen

Es seien ${}M$ und ${}N$ zwei disjunkte endliche Mengen. Zeige, dass die Anzahl der (disjunkten) Vereinigung ${}M\cup N$ gleich der Summe der beiden Anzahlen der beiden Mengen ist.

Aufgabe Referenznummer erstellen

Es seien ${}M$ und ${}N$ endliche Mengen. Zeige, dass die Produktmenge ${}M\times N$ ebenfalls endlich ist, und dass die Beziehung

${}{\#\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.

Aufgabe Referenznummer erstellen

Zeige, dass durch die Zuordnung

$S_{n}\times \{1,\ldots ,n+1\}\longrightarrow S_{n+1},\,(\varphi ,x)\longmapsto {\tilde {\varphi }},$

mit

${}{\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.

Aufgabe Referenznummer erstellen

Zeige, dass

${}{\#\left(S_{n}\right)}=n!\,$

gilt.

Aufgabe * Referenznummer erstellen

Es sei ${}M$ eine ${}n$-elementige Menge und sei

$B={\left\{F:M\rightarrow M{\text{ Abbildung}}\mid F{\text{ bijektiv}}\right\}}.$

Zeige, dass

${}{\#\left(B\right)}=n!\,$

ist.

Aufgabe Referenznummer erstellen

Es seien ${}M$ und ${}N$ zwei endliche Teilmengen einer Menge ${}G$. Zeige, dass die Formel

${}{\#\left(M\right)}+{\#\left(N\right)}={\#\left(M\cup N\right)}+{\#\left(M\cap N\right)}\,$

gilt.

Aufgabe Referenznummer erstellen

Es sei ${}G$ eine Menge und es seien ${}M_{i}\subseteq G$, ${}i=1,\ldots ,n$, endliche Teilmengen. Für eine Teilmenge ${}J\subseteq \{1,\ldots ,n\}$ sei

${}M_{J}=\bigcap _{i\in J}M_{i}\,.$

Finde eine Beziehung zwischen den Anzahlen der verschiedenen Schnittmengen ${}M_{J}$, ${}J\subseteq \{1,\ldots ,n\}$. Beweise diese Formel.

Aufgabe Referenznummer erstellen

Es sei ${}(I,\preccurlyeq )$ eine total geordnete Menge. Zeige durch Induktion, dass jede nichtleere endliche Teilmenge ${}T\subseteq I$ ein eindeutiges Maximum besitzt.