Posts Tagged ‘Endlich’

Endliche Summen und Produkte

Saturday, February 13th, 2010

Für abelsche Gruppen (K, +) spielt die Summationsreihenfolge bei der Summation endlich vieler Elemente x_k keine Rolle. Sei M also eine endlich Menge mit |M| = m, dann gibt es eine Bijektion:
\varphi : \{ 1, \dots , m \} \rightarrow M
Für k \in M gilt dann:
\sum_{k \in M}{x_k} = x_{\varphi(1)} + \dots + x_{\varphi(m)}
Oftmals sind die Elemente aus M eine Spanne von Zahlen a bis b mit a, b \in \mathbb{N}_0. Dann gilt:
\sum_{k \in M}{x_k} = \sum_{n=a}^b{x_n}
Für M = \emptyset gilt \sum_{x \in \emptyset}{x} = 0.

Für abelsche Gruppen (K, ∙) spielt die Produktreihenfolge beim Produkt endlich vieler Elemente x_k keine Rolle. Sei M also eine endlich Menge mit |M| = m, dann gibt es eine Bijektion:
\varphi : \{ 1, \dots , m \} \rightarrow M
Für k \in M gilt dann:
\prod_{k \in M}{x_k} = x_{\varphi(1)} \cdot \dots \cdot x_{\varphi(m)}
Oftmals sind die Elemente aus M eine Spanne von Zahlen a bis b mit a, b \in \mathbb{N}_0. Dann gilt:
\prod_{k \in M}{x_k} = \prod_{n=a}^b{x_n}
Für M = \emptyset gilt \prod_{x \in \emptyset}{x} = 1.

Für Summen und Produkte gilt wegen den Assoziativ- und Kommutativgesetzen:
\sum_{k \in M}{x_k + y_k} = (\sum_{k \in M}{x_k}) + (\sum_{k \in M}{y_k})
\prod_{k \in M}{x_k + y_k} = (\prod_{k \in M}{x_k}) \cdot (\prod_{k \in M}{y_k})
Für einen Körper K und a \in K ergeben sich darüber hinaus:
\sum_{k \in M}{ax_k} = a \sum_{k \in M}{x_k}
\prod_{k \in M}{ax_k} = a \prod_{k \in M}{x_k}

Für Summen gibt es zwei Tricks, die zur einfacheren Berechnung beitragen können:
1. Summationsreihenfolge ändern
2. Teleskopsumme bilden

1. \sum_{n=1}^m{n} = 1 + 2 + 3 + \dots + n = m + (m - 1) + (m - 2) + \dots + 1 = \sum_{n=1}^m{m - (n + 1)}
\Rightarrow 2\sum_{n=1}^m{n} = \sum_{n=1}^m{n} + \sum_{n=1}^m{m - (n + 1)} = \sum_{n=1}^m{m + 1} = m(m + 1)
\Rightarrow \sum_{n=1}^m{n} = \frac{m(m + 1)}{2}

2. Kann man \sum_{n=1}^m{x_n} als \sum_{n=1}^m{(y_n - y_{n+1})} schreiben, nennt man die zweite Summe Teleskopsumme:
\sum_{n=1}^m{x_n} = \sum_{n=1}^m{(y_n - y_{n+1})} = y_1 - y_2 + y_2 - y_3 + \dots + y_n - y_{n+1} = y_1 - y_{n+1}
Zum Beispiel gilt:
\sum_{n=1}^m{\frac{1}{n(n + 1)}} = \sum_{n=1}^m{\frac{1}{n} - \frac{1}{n + 1}} = 1 - \frac{1}{m + 1} = \frac{m}{m + 1}

Eine weitere sehr wichtige Summe ist die geometrische Summe. In einem Körper K mit q \in K, n \in \mathbb{N}_0 gilt:
(1 - q) \sum_{k=0}^n{q^k} = (\sum_{k=0}^n{q^k}) - q^k + 1 = 1 - q^{n + 1}
Für q ≠ 1 folgt daraus:
\sum_{k=0}^n{q^k} = \frac{1 - q^{n+1}}{1 - q}
Für q = 1 gilt offensichtlich: \sum_{k=0}^n{q^k} = n + 1 (da die Summe n+1-Summanden umfasst und jedes q^k = 1 ist)

Tags: , , , ,
Posted in Analysis, Linear Algebra, Mathematics | 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: , , , ,
Posted in Mathematics, Practices, Theory of Sets | No Comments »

Endliche Mengen & Kardinalität

Thursday, February 11th, 2010

Eine Menge M = \{ 1, \dots , n \} ist für n \in \mathbb{N}_0 genau dann leer, falls n = 0:
M = \{ 1, \dots , 0 \} = \emptyset
In diesem Fall besitzt die Menge die sogenannte Kardinalität \mid M \mid = 0. Die Kardinalität beschreibt die Anzahl von Elementen in einer Menge. Man unterscheidet endliche und unendliche Mengen. Die Menge der natürlichen Zahlen beispielsweise ist unendlich. Man schreibt dann auch \mid \mathbb{N} \mid = \infty. Eine Menge M wird genau dann als endlich bezeichnet, wenn es eine injektive Abbildung f : M \rightarrow \{ 1, \dots , n \} , n \in \mathbb{N}_0 gibt. Die Kardinalität dieser Menge ist dann:
\mid M \mid = min \{ n \in \mathbb{N}_0 : \exists M \rightarrow \{ 1, \dots , n \} \ injektiv \}
Das heißt also, dass quasi jedes Element von M abgezählt und so die Anzahl der Elemente festgestellt wird.

Für zwei Mengen A und B und m \in \mathbb{N}_0 gilt:
1. \mid A \mid = m \Leftrightarrow \exists A \rightarrow \{ 1, \dots , m \} \ bijektiv (d.h. es werden alle Elemente von A durch {1, … , m} abgezählt und keines wird doppelt zugewiesen)
2. Falls es eine Bijektion A \rightarrow B gibt, dann gilt offensichtlich \mid A \mid = \mid B \mid
3. Gilt \mid A \mid = \mid B \mid und ist A oder B endlich, dann gibt es eine Bijektion A \rightarrow B
4. Falls A \cap B = \emptyset, dann ist \mid A \cup B \mid = \mid A \mid + \mid B \mid

Sind M und N zwei endliche Mengen mit \mid M \mid = m, \mid N \mid = n, dann gilt:
1. \mid M \times N \mid = \mid M \mid \mid N \mid
2. \mid \{ f : M \rightarrow N : f \ ist \ Abbildung \} \mid = \mid N \mid^{\mid M \mid} = \mid N^M \mid, wobei n^0 = 1 \ \forall n \in \mathbb{N}_0
3. \mid \mathbb{P} (M) \mid = 2^{\mid M \mid}
4. \mid \mathbb{P}_k(M) \mid = {m \choose k}, wobei \mathbb{P}_k(M) = \{ A \in \mathbb{P}(M) : \mid A \mid = k \}

Beweise:
1. Ist f : N \rightarrow \{ 1, \dots , n \} eine Bijektion, dann ist auch M \times N \rightarrow M \times \{ 1, \dots , n \} eine Bijektion.
Induktionsanfang: n = 0:
\Rightarrow M \times \emptyset = \emptyset \Rightarrow \mid M \times \emptyset \mid = \mid M \mid \mid \emptyset \mid = m0 = 0
Induktionshypothese: \mid M \times N \mid = \mid M \mid \mid N \mid
Induktionsschritt: n - 1 \mapsto n:
M \times N = M \times \{ 1, \dots , n - 1 \} \cup M \times \{ n \}
\Rightarrow M \times \{ 1, \dots , n - 1 \} \cap M \times \{ n \} = \emptyset
\Rightarrow \mid M \times N \mid = \mid M \times \{ 1, \dots , n \} \mid + \mid M \times \{ n \} \mid = \mid M \mid \mid \{ 1, \dots , n \} \mid + \mid M \mid \mid \{ n \} \mid =
= m(n - 1) + m(1) = mn

2. Für die Menge aller Abbildungen von M \rightarrow N schreibt man auch N^M.
Für M = \emptyset existiert genau eine Funktion M \rightarrow N, da jede Relation von der leeren Menge nach N leer ist und damit Teilmenge von \emptyset \times N. Diese leere Relation ist eine Funktion. Für M \not= \emptyset \exists x \in M. Dadurch ist folgende Abbildung eine Bijektion, wodurch die Mengen, dieselben Kardinalitäten haben:
F : N^M \rightarrow N^{M \backslash \{ x \} } \times N, f \mapsto (f(M \backslash \{ x \} ), f(x))
\Rightarrow per Induktion \mid N^M \mid = \mid N^{M \backslash \{ x \} } \times N \mid = \mid N^{M \backslash \{ x \} } \mid \mid N \mid = n^{m - 1}n = n^m

3. Für eine Teilmenge A von M existiert die sogenannte Indikatorfunktion:
I_A : M \rightarrow \{ 0, 1 \} , x \mapsto \{ {1 falls \ x \in A \atop 0 falls \ x \not\in A}
Für die Funktion, welche alle Teilmengen der Potenzmenge auf die Indikatorfunktion abbildet ergibt sich eine Bijektion:
F : \mathbb{P}(M) \rightarrow \{ 0, 1 \} ^M, A \mapsto I_A
\Rightarrow \mid \mathbb{P}(M) \mid = \mid \{ 0, 1 \} ^M \mid = 2^{ \mid M \mid } = 2^m

4. {n \choose k} beschreibt den sogenannten Binomialkoeffizienten. Dieser benutzt die Fakultät n!. Die Fakultät ist definiert durch 0! = 1, \ n! = 1 \cdot 2 \cdot 3 \cdots n. Daraus folgt offensichtlich, dass n! = (n - 1)!n. Der Binomialkoeffizient ist definiert für n \in \mathbb{N}_0, k \in \mathbb{N} durch:
{n \choose k} = \frac{n(n - 1)(n - 2)(n - 3) \cdots (n - (k - 2))(n - (k - 1))}{k!}
Per Definition gilt ausserdem {n \choose 0} = 1 \ \forall n \in \mathbb{N}_0. Offensichtlich ist {0 \choose k} = 0 \ \forall k \in \mathbb{N}.
Für n = 0 = \mid M \mid \Rightarrow M = \emptyset gilt:
Sei k \in \mathbb{N}, dann ist \mathbb{P}_k( \emptyset ) = \emptyset = 0 = {0 \choose k}, \mathbb{P}_0( \emptyset ) = \{ \emptyset \} = 1 = {n \choose 0}.
Für n \not= 0 = \mid M \mid \Rightarrow M \not= \emptyset gilt:
Sei x \in M, dann ist
\mathbb{P}_k(M) = \mathbb{P}_k(M \backslash \{ x \} ) \times \{ A \in \mathbb{P}_k(M) : x \in A \}
die Menge der Potenzmengen ohne das x vereinigt mit den Potenzmengen mit dem x.
\Rightarrow da \ A \mapsto A \backslash \{ x \} eine Bijektion mit \mathbb{P}_{k-1}(N \backslash \{ x \} ) ist, folgt induktiv:
\mid \mathbb{P}_k(N) \mid = \mid \mathbb{P}_k(N \backslash \{ x \} ) \mid + \mid \mathbb{P}_{k-1}(N \backslash \{ x \} ) (der zweite Summand entspricht genau der Anzahl an Teilmengen der Potenzmenge, die durch den Ausschluss von x im ersten Summanden nicht berücksichtigt werden)
Die vorangegangene Gleichung ist dasselbe wie:
{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}
Für n = n + 1 ergibt sich daraus:
{n+1 \choose k} = {n \choose k} + {n \choose k-1}
Dies ist die Formel für das Pascalsche Dreieck, die sich direkt aus dem Binomialkoeffizienten ergibt:
{n+1 \choose k} = \frac{n+1(n) \cdots (n-k+2)}{k!} = \frac{n(n-1) \cdots (n-k+2)}{k!} \cdot (n+1) =
= \frac{n(n-1) \cdots (n-k+2)}{k!} \cdot ((n-k+1)+k) =
= \frac{n(n-1) \cdots (n-k+1)}{k!} + \frac{nk(n-1) \cdots (n-k+2)}{k!} =
= \frac{n(n-1) \cdots (n-k+1)}{k!} + \frac{n(n-1) \cdots (n-k-1+1)}{(k-1)!} = {n \choose k} + {n \choose k-1}

Tags: , , , , , , , , ,
Posted in Analysis, Functions, Linear Algebra, Theory of Sets | No Comments »