Theory of Sets « sjochim.com

Archive for ‘Theory of Sets’

Übung Abzählbarkeit

Friday, February 12th, 2010

1. Zu zeigen ist, dass die Menge $\mathbb{P}_e(\mathbb{N}) = \{ M \subseteq \mathbb{N} : M \ endlich \}$ aller endlichen Teilmengen von den natürlichen Zahlen abzählbar ist.
Es muss also gezeigt werden, dass eine injektive Abbildung $\mathbb{P}_e(\mathbb{N}) \rightarrow \mathbb{N}$ existiert. Es gilt:
$\mathbb{P}_e ( \mathbb{N} ) = \bigcup \mathbb{P}_j ( \mathbb{N} ) : \mathbb{P}_j ( \mathbb{N} ) = \{ A \subseteq \mathbb{N} : \mid A \mid = j \}$ (also die Vereinigung der Mengensysteme mit den Mengen mit j Elementen für alle j aus $\mathbb{N}$ )
Für eine Teilmenge A mit j Elementen $\{ k_1, \dots , k_j \} , k_1 < k_2 < \dots < k_j$ kann man die folgende Abbildung definieren:
$F : \mathbb{P}_j(\mathbb{N}) \rightarrow \mathbb{N}^j = \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \dots \times \mathbb{N}$ (j-mal), $f(\{ k_1, \dots , k_j \} ) \mapsto (k_1, \dots , k_j)$
F ist injektiv, was leicht nachgerechnet werden kann. $\mathbb{N}^j$ ist als kartesisches Produkt abzählbarer Mengen abzählbar. Dies kann z.B. durch Induktion gezeigt werden, da $\mathbb{N}^j = \mathbb{N}^{j-1} \mathbb{N}$ .
Sei g eine injektive Abbildung $\mathbb{N}^j \rightarrow \mathbb{N}$ , dann existiert:
$g \circ f : \mathbb{P}_j(\mathbb{N}) \rightarrow \mathbb{N} \ injektiv$
$\Rightarrow$ Alle $\mathbb{P}_j$ sind abzählbar und damit $\mathbb{P}_e$ als Vereinigung abzählbarer Mengen ebenso.

2. Zu zeigen ist, dass die Menge $\mathbb{P}_{ \infty }(\mathbb{N}) = \{ M \subseteq \mathbb{N} : M \ unendlich \}$ aller unendlichen Teilmengen von den natürlichen Zahlen nicht abzählbar ist.
Angenommen $\mathbb{P}_{ \infty }$ wäre abzählbar, dann würde $\mathbb{P}(\mathbb{N}) = \mathbb{P}_e(\mathbb{N}) \cup \mathbb{P}_{ \infty }(\mathbb{N})$ als Vereinigung abzählbarer Mengen abzählbar sein – Widerspruch zu $\mathbb{P}(\mathbb{N})$ ist überabzählbar.

Tags: Abzählbarkeit, Übung
Posted in Mathematics, Practices, Theory of Sets | No Comments »

Übungen Endliche Mengen

Friday, February 12th, 2010

1. Seien A, B zwei endliche Mengen. Es ist zu zeigen:
$\mid A \cup B \mid = \mid A \mid + \mid B \mid - \mid A \cap B \mid$
Wie lautet die Formel zur Berechnung von $\mid A \cup B \cup C \mid$ für drei endliche Mengen?

$A \cup B = A \cup (B \backslash A) \Rightarrow \mid A \cup B \mid = \mid A \cup (B \backslash A) \mid$
Da A und B \ A disjunkt sind, ergibt sich:
$\mid A \cup B \mid = \mid A \mid + \mid (B \backslash A) \mid$
$B = (B \backslash A) \cup (B \cap A)$
Da $(B \backslash A), (B \cap A)$ disjunkt sind, ergibt sich:
$\mid B \mid = \mid B \backslash A \mid + \mid B \cap A \mid \Rightarrow \mid B \backslash A \mid = \mid B \mid - \mid B \cap A \mid$
$\Rightarrow \mid A \cup B \mid = \mid A \mid + \mid B \mid - \mid B \cap A \mid$
Für drei endliche Mengen A, B, C folgt daraus:
$\mid A \cup B \cup C \mid = \mid A \cup B \mid + \mid C \mid - \mid (A \cup B) \cap C \mid = \mid A \mid + \mid B \mid + \mid C \mid - \mid A \cap B \mid - \mid (A \cup B) \cap C \mid$
$= \mid A \mid + \mid B \mid + \mid C \mid - \mid A \cap B \mid - \mid (A \cap B) \cup (A \cap C) \mid$
$= \mid A \mid + \mid B \mid + \mid C \mid - \mid A \cap B \mid - \mid A \cap B \mid - \mid A \cap C \mid + \mid (A \cap B) \cap (A \cap C) \mid$
$= \mid A \mid + \mid B \mid + \mid C \mid - \mid A \cap B \mid - \mid A \cap B \mid - \mid A \cap C \mid + \mid A \cap B \cap C \mid$
Für n endliche Mengen $A_1 \dots A_n$ gilt die sogenannte Siebformel:
$\mid \bigcup A_i \mid = \sum{(-1)^{ \mid j \mid + 1} \mid \bigcap A_i \mid }$ ,
wobei $\bigcup A_i : i = 1 \dots n, \ J \subseteq \{ 1, \dots, n \} , \bigcap A_i : i \in J$ .
Für n = 2:
$\mid \bigcup A_i \mid = \mid A_1 \cup A_2 \mid$
J kann als Teilmengen von {1, 2} entweder {1}, {2} oder {1, 2} sein:
Für J = {1} folgt: $(-1)^2 \mid A_1 \mid = \mid A_1 \mid$
Für J = {2} folgt: $(-1)^2 \mid A_2 \mid = \mid A_2 \mid$
Für J = {1, 2} folgt: $(-1)^3 \mid A_1 \mid \cap A_2 \mid$
Also: $\mid \bigcup A_i \mid = \mid A_1 \mid + \mid A_2 \mid - \mid A_1 \cap A_2 \mid$

2. Seien N, M zwei endliche Mengen mit |N| = n und |M| = m. Es soll die Kardinalität der injektiven bzw. bijektiven Funktionen von N nach M berechnet werden.

Sei $I(N, M) = \{ f : N \rightarrow M : f \ injektiv \}$ , dann gilt für m < n, dass es keine surjektive Funktion von $M \rightarrow N$ geben kann. Somit gibt es auch keine injektive von $N \rightarrow M$ , woraus folgt, dass $I(N, M) = \emptyset$ und somit $\mid I(N, M) \mid = \mid \emptyset \mid = 0$ .
Für m ≥ n wird eine Induktion nach n durchgeführt:
Induktionsanfang: n = 0:
$\Rightarrow N = \emptyset \Rightarrow M^N = \{ \emptyset \}$ und jede Abbildung $f : \emptyset \rightarrow M$ ist injektiv. Es gibt ja keine Elemente in $\emptyset$ , deshalb können auch die Funktionswerte für verschiedene Elemente nicht gleich sein.
$\Rightarrow \mid I(N, M) \mid = \mid M^N \mid = \mid M \mid ^ \mid N \mid = m^0 = 1$
Induktionsannahme: Für $n \in \mathbb{N}$ fest und |N| = n ≤ m = |M| gilt:
$\mid I(N, M) \mid = \prod{j=0}^{n-1}{m - j}$
Induktionsschritt: $n \mapsto n + 1$ :
Seien $\mid \tilde N \mid = n + 1 \leq m = \mid M \mid, x \in \tilde N$ , dann kann man die folgende Abbildung definieren:
$\phi : I( \tilde N, M) \rightarrow \bigcup I( \tilde N \backslash \{ x \}, M \backslash \{ \alpha \} ) \times \{ \alpha \}, \phi (f) = (f \mid_ { \tilde N \backslash \{ x \} }, f(x)), \alpha \in M$
Diese Abbildung ist eine Bijektion:
a) Seien $\phi (f) = \phi (g) \Rightarrow (f \mid { \tilde N \backslash \{ x \} }, f(x)) = (g \mid { \tilde N \backslash \{ x \} }, g(x)$
$\Rightarrow \forall y \in \tilde N \backslash \{ x \}$ gilt f(y) = g(y) sowie f(x) = g(x) $\Rightarrow f = g$ und somit Injektivität
b) Sei $\alpha \in M, h \in I( \tilde N \backslash \{ x \}, M \backslash \{ \alpha \} )$ , dann kann man die folgende Abbildung definieren:
$H : \tilde N \rightarrow M, H(y) = \{ { \alpha \ falls \ y = x \atop h(y) \ falls \ y \not= x }$
H ist injektiv, denn sei H(v) = H(w) gilt, falls
$H(v) = H(w) = \alpha \Rightarrow v = x, w = x \Rightarrow v = w$
$H(v) = H(w) \not= \alpha \Rightarrow h(v) = h(w) \Rightarrow v = w$ (da h injektiv)
Somit gilt gerade $\phi (H) = (h, \alpha ), \phi surjektiv$ .
Damit gilt: $\mid I( \tilde N, M) \mid = \mid \bigcup I( \tilde N \backslash \{ x \} , M \backslash \{ \alpha \} ) \times \{ \alpha \} \mid = \sum{\mid I( \tilde N \backslash \{ x \}, M \backslash \{ \alpha \} ) \times \{ \alpha \} \mid }$
Das ist mit der Induktionshypothese aber nichts anderes als:
$\sum{\prod_{j=0}^{n-1}{m - 1 - j}} = m(\prod_{j=0}^{n-1}{m - 1 - j}) = (m-0)(\prod_{j=1}^{(n+1)-1}{m - 1 - j}) = \prod_{j=0}^{n}{m - j}$
Im letzten Schritt wurde das Produkt von j=0 bis n-1 auf j=1 bis (n+1)-1 gewechselt und der Faktor (m-0) als j=0 wieder hinzugefügt, so dass insgesamt das Produkt von j=0 bis (n+1)-1 geht, was die Induktion abschließt.

Für den Teil mit der Anzahl an Bijektionen gilt analog zu den Injektionen, wenn m < n, dann ist $B(N, M) = \{ f : N \rightarrow M : f \ bijektiv \} = \emptyset$ . Wegen $B(N, M) \subseteq I(N, M)$ folgt daraus $\mid B(N, M) \mid = \mid \emptyset \mid = 0$ .
Für m > n ist $B(N, M) = \emptyset$ , da es keine Surjektion von N nach M gibt. Ansonsten würde es Injektion von M nach N geben, was im ersten Teil widerlegt wurde.
Für m = n ist $\{ f : N \rightarrow M : f \ injektiv \}$ äquivalent zu $\{ f : N \rightarrow M : f \ bijektiv \}$ . Somit gilt:
$\mid B(N, M) \mid = \mid I(N, M) \mid = \prod_{j=0}^{n-1}{m - j} = m!$

3. Das Hotel Hilbert hat unendliche viele durchnummerierte Zimmer. Wegen einer Mathe-Konferenz sind alle Zimmer belegt. Am frühen Abend kommt ein unerwarteter Gast. Wie können er und alle Mathematiker in einem eigenen Zimmer untergebracht werden? Mitten in der Nacht trifft ein Reisebus mit unendlich vilen Physikern ein. Auch die können in Einzelzimmern untergebracht werden. Wie?
Sei $M_j$ der Mathematiker in Zimmer j und G der Gast, die Funktion f soll jedem ein Einzelzimmer zuordnen und tut dies mit: $f(M_j) = j + 1, f(G) = 1$ . Sei P der Physiker, dann wird f wie folgt umgestellt: $f(M_j) = 2j, f(P_j) = 2j + 1, f(G) = 1$ . Die Mathematiker werden also in den Zimmern mit geraden Nummern untergebracht, während die Physiker in die mit den ungeraden kommen.

Tags: Endlich, Hotel Hilbert, Induktion, Mengen, Übung
Posted in Mathematics, Practices, Theory of Sets | No Comments »

Abzählbarkeit

Thursday, February 11th, 2010

Bei der Kardinalität hat man Elemente abgezählt. Dieses Abzählen geschieht über die natürlichen Zahlen, denn es macht wenig Sinn, dass ein Element als das 1,34343235-te anzusehen, sondern eben als das zum Beispiel zweite. Der Begriff der Abzählbarkeit geht nun noch einen Schritt weiter und ist wie folgt definiert:
Eine Menge M heißt abzählbar, wenn es eine Injektion $f : M \rightarrow \mathbb{N}$ gibt. Also nicht mehr, wie bei der Endlichkeit nach {1, … , n} sondern in die gesamten (unendlichen) natürlichen Zahlen. Gibt es keine solche Injektion, dann wird die Menge M überabzählbar genannt.
Es existiert, wie in den Eigenschaften von Funktionen nachgelesen werden kann, eine injektive Abbildung genau dann, wenn es eine surjektive Abbildung von dem Ziel in die Quelle gibt, also in diesem Fall von N nach M.
Da Kompositionen injektiver bzw. surjektiver Abbildung wiederum injektiv bzw. surjektiv sind, ergeben sich folgende sogenannte Stabilitätseigenschaften:
1. Ist M eine abzählbare Menge, die Funktion $f : N \rightarrow M$ injektiv und $g : M \rightarrow K$ surjektiv, dann sind N und K offensichtlich auch abzählbar.
2. $\mathbb{N} \times \mathbb{N}$ ist abzählbar
3. Abzählbare Vereinigungen abzählbarer Mengen sind abzählbar
4. Produkte ( $M \times N$ ) abzählbarer Mengen sind abzählbar
5. $\mathbb{Z}, \mathbb{Q}, \mathbb{Q} \times \mathbb{Q}$ sind abzählbar
6. $\mathbb{P}(\mathbb{N}) \ und \ \{ 0, 1 \} ^\mathbb{N}$ sind überabzählbar
7. Es gibt eine Bijektion zwischen $\mathbb{P}(\mathbb{N}) \ und \ \mathbb{R}$ (Die reellen Zahlen sind also auch überabzählbar)

Beweise:
1. Es gibt, da M abzählbar ist, eine injektive Funktion $h : M \rightarrow \mathbb{N}$ . Dadurch ist die Komposition $h \circ f : N \rightarrow \mathbb{N}$ eine injektive Abbildung. Da es eine injektive Abbildung $g' : K \rightarrow M$ gibt, weil eine surjektive von M nach K existiert, ist die Komposition $h \circ g' : K \rightarrow \mathbb{N}$ eine injektive Abbildung.

2. $\mathbb{N} \times \mathbb{N}$ kann man sich als Matrix mit unendlich langen Zeilen und Spalten vorstellen. Die Diagonalen $D_n = \{ (j, k) \in \mathbb{N} \times \mathbb{N} : j + k = n + 1 \}$ können abgezählt werden. Die Kardinalität, also die Anzahl an Elementen einer Diagonalen entspricht $\mid D_n \mid = n$ und alle Diagonalen sind disjunkt zueinander, enthalten also keine gemeinsamen Elemente. Die Vereinigung aller Diagonalen (im unendlichen) ist gleich dem kartesischen Produkt. Die ersten n Mengen $D_1$ bis $D_n$ haben zusammen $N(n) = \frac{n(n + 1)}{2}$ Elemente (siehe Thema Induktion). Für die Diagonale $D_{n+1}$ werden dann logischerweise die Zahlen N(n)+1 bis N(n)+n+1 zur Nummerierung benötigt. Schreibt man $D_n = \{ x_{n, 1} \dots x_{n, n} \}$ dann ist die Funktion:
$f : \mathbb{N} \rightarrow \bigcup D_n, k \mapsto x_{n+1, k}, k = N(n) + l, l \in \{ 1, \dots , n + 1 \}$ eine surjektive Abbildung von $\mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ . Damit existiert umgedreht eine injektive und somit ist $\mathbb{N} \times \mathbb{N}$ abzählbar.

3. Genauer heißt die Aussage, wenn MS ein abzählbares Mengensystem ist, ist auch $\bigcup MS$ abzählbar.
Es kann angenommen werden, dass $MS \not= \emptyset, \emptyset \not\in MS$ . Da MS abzählbar ist, gibt es eine injektive Abbildung von MS in die natürlichen Zahlen. Daher gibt es auch eine surjektive Abbildung
$F : \mathbb{N} \rightarrow MS$ . Jede Teilmenge F(n) von MS ist abzählbar. Daher gibt es eine injektive Funktion von F(n) in die natürlichen Zahlen und damit auch eine surjektive Abbildung:
$G_n : \mathbb{N} \rightarrow F(n)$ . Die Funktion $H : \mathbb{N} \times \mathbb{N} \rightarrow \bigcup MS, (n, m) \mapsto G_n(m)$ ist surjektiv. Daher gibt es eine Injektion in die andere Richtung. Da $\mathbb{N} \times \mathbb{N}$ abzählbar ist, gibt es eine injektive Komposition in die natürlichen Zahlen.

4. Für Surjektionen $f: \mathbb{N} \rightarrow M, g: \mathbb{N} \rightarrow N$ ist $h : \mathbb{N} \times \mathbb{N} \rightarrow M \times N, (n, m) \mapsto (f(n), g(m))$ surjektiv. Dann gilt das selbe Argument wie am Ende von 3.

6. $f : M \rightarrow \mathbb{P}(M)$ ist nicht surjektiv. Andernfalls wäre die Menge $R = \{ x \in M : x \not\in f(x) \} = f(y) : y \in M$ (mit Auswahlaxiom). Für dieses y wäre dann, wegen $R = f(y): y \in R \Leftrightarrow y \not\in f(y) \Leftrightarrow y \not\in R$ – Widerspruch.
Die zweite Aussage folgt aus der ersten, da $\mathbb{P}(N) \rightarrow \{ 0, 1 \} ^N, A \mapsto I_A$ eine Bijektion ist:
Sei N eine Menge, dann definiert man für $A \subseteq N$ :
$I_A(x) = \{ {1 \ falls \ x \in A \atop 0 \ falls \ x \not\in A}, I_A \in \{ 0, 1 \} ^N$
Für $X : \mathbb{P}(N) \rightarrow \{ 0, 1 \} ^N, A \mapsto I_A$ gilt:
a) Χ ist injektiv: Seien $A, B \subseteq N : X_A = X_B$ (was quasi zwei Funktionen entspricht), dann gilt:
$A = \{ x \in N : I_A = 1 \} = \{ x \in N : X_A(x) = 1 \} = \{ x \in N : X_B(x) = 1 \} = \{ x \in N : I_B = 1 \} = B$
b) X ist surjektiv: Sei $f \in \{ 0, 1 \} ^N$ , dann definiert man $F = f^{-1}(\{ 1 \} )$ . Dies entspricht dem Input A der Funktion f, weil $A = X_A^{-1}(\{ 1 \} )$ und erhält mit X(F), $f : X \rightarrow \{ 0, 1 \} : X(F)(x) = f(x) \ \forall x \in X$ .
b1) $x \in F \Leftrightarrow x \in f^{-1}( \{ 1 \} ) \Leftrightarrow f(x) \in \{ 1 \} \Leftrightarrow f(x) = 1$ , daraus folgt $X(F)(x) = I_F(x) = 1$
b2) $x \not\in F \Leftrightarrow x \not\in f^{-1}( \{ 1 \} ) \Leftrightarrow f(x) \not\in \{ 1 \} \Leftrightarrow f(x) \not = 1 \Leftrightarrow f(x) = 0$ , daraus folgt $f(x) = 0 = I_F(x) = X(F)(x)$ . Also gilt f = X(F).