Functions « sjochim.com

Archive for ‘Functions’

Übung Äquivalenzrelation

Saturday, February 13th, 2010

Seien M eine endliche Menge und ~ eine Äquivalenzrelation auf M, sodass alle Äquivalenzklassen die gleiche Kardinalität k haben. Wie viele Äquivalenzklassen gibt es? Wie viele solche Äquivalenzrelationen kann man auf der Menge $M = \{ 1, \dots , p \}$ geben, wenn p eine Primzahl ist? Gibt es eine Äquivalenzrelation auf $\{ k \in \mathbb{N} : k \leq 78 \}$ , bei der alle Äquivalenzklassen genau sieben Elemente haben?
Sei k die (immer gleich) Kardinalität der Äquivalenzklassen, dann gilt für $v = [x], w = [y] : v = w \ oder \ v \wedge w = \emptyset$ . Denn sei $\alpha \in v \wedge w \Rightarrow x \sim \alpha \sim y \Rightarrow x \sim y \Rightarrow v = w$ . Damit ist $M = \bigcup_{w \in M/ \sim} w$ eine disjunkte Zerlegung von M. Seien $m = \mid M \mid, q = \mid M/ \sim \mid$ sowie $\varphi : \{ 1, \dots , q \} \rightarrow M/ \sim \ bijektiv$ :
$\Rightarrow m = \mid M \mid = \mid \bigcup_{w \in M/ \sim} w \mid = \sum_{w \in M/ \sim}{\mid w \mid} = \sum_{j=1}^q{k} = qk$
$\Rightarrow q = \frac{m}{k}$
Für $M = \{ 1, \dots , p \}$ und die Äquivalenzrelation ~ mit $\mid [x] \mid = \mid [y] \mid = k \ \forall x, y \leq p$ gilt:
$\mid M/ \sim \mid = \frac{p}{k} \in \mathbb{N} \Rightarrow k \mid p \Rightarrow k = 1 \vee k = p$ (da p Primzahl)
Für k = 1 gilt wegen $j \in [j]: (j, k) \in \sim \Leftrightarrow j = k$ , dann ist ~ gerade die Identität.
Für k = p gilt $k \in [j] \ \forall 1 \leq k, j \leq p \Rightarrow \sim = \{ 1, \dots , p \} \times \{ 1, \dots , p \}$
Eine Äquivalenzrelation auf $\{ k \in \mathbb{N} : k \leq 78 \}$ , bei der alle Äquivalenzklassen genau sieben Elemente haben, existiert nicht, da $\frac{78}{7} = 11 \ Rest \ 1$ und daher eine Klasse 8 oder 1 Element haben müsste.

Tags: Äquivalenzrelation, Übung
Posted in Analysis, Functions, Mathematics, Practices | No Comments »

Übung Kardinalität

Saturday, February 13th, 2010

Seien $n \in \mathbb{N}, k_1, \dots , k_r \in \mathbb{N}_0$ mit $\sum_{j=1}^r{k_j} = n$ . Zu zeigen ist, dass die Menge
$A = \{ f : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid f^{-1}(\{ l \} ) \mid = k_l, l = \{ 1, \dots , r \}$
die Kardinalität $\mid A \mid = \frac{n!}{k_1! \cdots k_r!}$ hat.

Die Aufgabe ist vergleichbar mit folgendem Szenario:
Sei $S = \{ 1, \dots , n \}$ eine Schule mit n Kindern und r Klassen. Jede Klasse j darf nur (und muss) $k_j$ Kinder haben.
$A = \{ f : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid \{ x : f(x) = j \} \mid = k_j \}$ ist die Menge der verschiedenen Klassenzusammenstellungen. Zum Beispiel für r=2 gilt $k_1 + k_2 = n$ und damit $k_2 = n - k_1$ . Dann gilt $\mid A \mid = \mid \mathbb{P}_{k_1}( \{ 1, \dots , n \} ) \mid$ (denn es gibt genau diese Anzahl an Möglichkeiten, die Kinder der ersten Klasse (und somit gleichzeitig alle anderen Kinder) zu verteilen).
$\Rightarrow \mid A \mid = {n \choose k_1} = \frac{n!}{k_1! \cdot (n - k_1)!} = \frac{n!}{k_1! \cdot k_2!}$
Induktionsanfang: n = 1:
$\exists 1 \leq j_0 \leq r : k_{j_0} = 1$ und A enthält nur die Abbildung $f(1) = j_0$
$\Rightarrow \mid A \mid = 1 = \frac{1!}{(1 \cdots 1)} = \frac{n!}{k_1! \cdots k_r!}$
Induktionshypothese:
$\mid A \mid = \mid \{ f : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid f^{-1}( \{ j \} ) \mid = k_j \} \mid = \frac{n!}{k_1! \cdots k_r!}$
Induktionsschritt: $n \mapsto n + 1$ :
Seien nun $k_1, \dots , k_r \in \mathbb{N}_0, \sum_{k=1}^r{k_j} = n + 1$ , dann ist:
$A = \{ f : \{ 1, \dots , n + 1 \} \rightarrow \{ 1, \dots , r \} : \mid f^{-1}( \{ j \} ) \mid = k_j \} = \bigcup_{j=1}^r \{ f \in A : f(n+1) = j \}$
Mit $A_j := \{ f \in A : f(n+1) = j \}$ ist $A = \bigcup_{j=1}^r A_j$ .
Für $j \not= l$ ist $A_j \cap A_l = \emptyset$ , weil für $f \in A_j \cap A_l$ gilt $j = f(n+1) = 1$ – Widerspruch
$\Rightarrow \mid A \mid = \mid \bigcup_{j=1}^r A_j \mid = \sum_{j=1}^r{ \mid A_j \mid}$
Falls $k_j = 0$ , dann ist $A_j \not= 0$ :
Angenommen $f \in A_j \Rightarrow \mid f^{-1}( \{ j \} ) \mid = k_j = 0, f(n+1) = j \Rightarrow n+1 \in f^{-1}( \{ j \} ) = \emptyset$ – Widerspruch
Also gilt: $\mid A_j \mid = 0 = k_j \frac{n!}{k_1! \cdots k_r!}$
Falls $k_j \geq 1$ , dann ist:
$\lambda_l = \{ {k_l \ falls \ l \not= j \atop k_{j-1} \ falls \ l = j}$
$f^{-1}( \{ l \} ) = f \mid_{ \{ 1, \dots , n \} }$ von $A_j$ in $\{ \lambda : \{ 1, \dots , n \} \rightarrow \{ 1, \dots , r \} : \mid \lambda^{-1}( \{ l \} ) \mid = \lambda_l \}$
$\Rightarrow \mid A_j \mid = \frac{n!}{\lambda_1! \cdots \lambda_r!} = k_j \cdot \frac{n!}{k_1! \cdots k_r!}$
Somit erhält man:
$\mid A \mid = \sum_{j=1}^r{\mid A_j \mid} = \sum_{j=1}^r{(k_j \cdot \frac{n!}{k_1! \cdots k_r!})} = (\sum_{j=1}^r{k_j}) \cdot \frac{n!}{k_1! \cdots k_r!} = \frac{(n + 1)n!}{k_1! \cdots k_r!} = \frac{(n + 1)!}{k_1! \cdots k_r!}$

Tags: Funktionen, Kardinalität, Mengen, Übung
Posted in Analysis, Functions, Mathematics, Practices | No Comments »

Übungen Ringschluss

Friday, February 12th, 2010

1. Seien X eine nicht-leere Menge und $f : X \rightarrow Y$ eine Abbildung. Es ist zu zeigen, dass die folgenden Aussagen äquivalent sind:

(i) f ist injektiv
(ii) $\exists j : Y \rightarrow X$ , so dass $j \circ f = id, id : X \rightarrow X, x \mapsto x$
(iii) Für alle Mengen Z und Funktionen $g, h : Z \rightarrow X$ folgt aus $f \circ g = f \circ h$ bereits g = h
(iv) $\forall A, B \subseteq X$ gilt $f(A) \cap f(B) = f(A \cap B)$

Hierzu wird das Ringschlussverfahren genutzt, um nicht jede Äquivalenz zweier Aussagen in beiden Richtungen zu beweisen. Stattdessen wird aus (i) (ii) gefolgert, aus (ii) (iii), aus (iii) (iv) und um einen Ring zu bilden schließlich aus (iv) (i).

(i) $\rightarrow$ (ii):
Sei $f : X \rightarrow Y$ injektiv. Sei $Z = \{ y \in Y : f(x) = y \}$ , dann ist $f' : X \rightarrow Z$ bijektiv und es existiert:
$f'^{-1} : Z \rightarrow X$ , so dass $f'^{-1} \circ f : X \rightarrow X : x \mapsto f'^{-1}(f(x))$
$\forall z \in X$ gilt dann $(f'^{-1} \circ f)(x) = f'^{-1}(f(x)) = x$
$\Rightarrow f'^{-1} \circ f = id_X$

(ii) $\rightarrow$ (iii):
Sei Z eine Menge und $g, h \in X^Z, f \circ g = f \circ h$ , dann gilt wegen $id_X \circ g = g, id_X \circ h = h$ :
$g = id_X \circ g = (j \circ f) \circ g = j \circ (f \circ g) = j \circ (f \circ h) = (j \circ f) \circ h = id_X \circ h = h$

(iii) $\rightarrow$ (iv):
Sei $y \in f(A) \cap f(B)$ , dann existiert $a \in A \wedge b \in B : f(a) = f(b) = y$ . Durch Definition von:
$g : X \rightarrow X, x \mapsto a$
$h : X \rightarrow X, x \mapsto b$
folgt $(f \circ h)(x) = f(b) = y = f(a) = (f \circ g)(x)$
$\Rightarrow f \circ h = f \circ g \Rightarrow h = g$
Sei nun $z \in X, X \not= \emptyset$ , dann folgt
$a = g(z) = h(z) = b \Rightarrow a \in A \cap B \Rightarrow y = f(a) \in f(A \cap B)$

(iv) $\rightarrow$ (i):
Seien $a, b \in X : f(a) = f(b)$ . Durch Definition von:
$A = \{ a \}, B = \{ b \}$
erhält man $f(A) \cap f(B) = f( \{ a \} ) \cap f( \{ b \} ) = \{ f(a) \} \cap \{ f(b) \} = \{ f(a) \}$ , weil f(a) = f(b).
$\Rightarrow f(a) \in f(A) \cap f(B) = f(A \cap B) \Rightarrow f(A \cap B) \not= \emptyset \Rightarrow A \cap B \not= \emptyset$
$\Rightarrow \{ a \} \cap \{ b \} \not= \emptyset \Rightarrow a = b$