Existenz einer Bijektion zeigen

28.09.2015, 17:18

Joefish

Existenz einer Bijektion zeigen

$\begin{align*} \text{Sei } X \neq \emptyset. \text{ Zeige dass eine Bijektion } f: \mathfrak{P}(X) \to \{0,1\}^X, A \mapsto \chi_{A} \text{existiert.} \end{align*}$
$\begin{align*} \mathfrak{P} \text{ bezeichnet die Potenzmenge von X, } \{0,1\}^X \text{bezeichnet die Menge aller Abbildungen von } X \text{ auf } \{0,1\} \text{ und } \chi_A \text{ bezeichnet die charakterische Funktion.} \end{align*}$

$\begin{align*} \underline{Injektivitaet}: A \neq B \Rightarrow f(A) \neq f(B),\ A,B \subset X. \end{align*}$
$\begin{align*} \text{Dann sind die char. Funktionen } \chi_A \text{ und } \chi_B \text{ von einander verschieden,} \end{align*}$
$\begin{align*} \text{da nach Vorraussetzung ein } x \in X \text{ existiert, fuer welches } x \in A \wedge x \in B^C \text{ bzw. } x \in A^C \wedge x \in B. \end{align*}$

$\begin{align*} \underline{Surjektivitaet}: \end{align*}$
$\begin{align*} \text{Angenommen, es existiert eine char. Funktion } \varphi \in \{0,1\}^X, \text{ sodass fuer alle } A \in \mathfrak{P}(X)\quad f(A) \neq \varphi \text{ gilt.} \end{align*}$
$\begin{align*} \text{Mein Gedanke ist, dass } \left\{ \chi_A\ \vert \ \forall A \in \mathfrak{P}(X) \right\} = \{0,1\}^X \text{ entspricht, da fuer jedes } A \in \mathfrak{P}(X) \text{ auch } X \setminus A \in \mathfrak{P}(X) \end{align*}$
$\begin{align*} \text{ und somit kein } \varphi \text{ existieren kann, welches nicht Element der Permutation ist.} \end{align*}$
$\begin{align*} \text{Mit Permutation meine ich die Zuweisung von } x \in X \text{ auf 0 oder 1 in der Menge der charakterischen Funktionen auf die f abbildet.} \end{align*}$
$\begin{align*} \text{Betrachte man die Vereinigung aller x, welche auf 0 und der Vereinigung aller x welche auf 1 in den char. Funktionen } \chi_A, \forall A \in \mathfrak{P}(X) \text{ abgebildet werden,} \end{align*}$
$\begin{align*} \text{dann entsprechen diese gerade X. Daher kann es kein }\varphi \in \{0,1\}^X\text{ geben, welches nicht in der Bildmenge von f ist.} \end{align*}$

$\begin{align*} \text{ Falls mein Gedankengang ueberhaupt richtig ist, wie kann ich das praezise schreiben?} \end{align*}$

28.09.2015, 17:33

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Joefish
$\begin{align*} \text{da nach Vorraussetzung ein } x \in X \text{ existiert, fuer welches } x \in A \wedge x \in B^C \text{ bzw. } x \in A^C \wedge x \in B. \end{align*}$

Das würde ich etwas klarer formulieren, und das "bzw." durch "oder" ersetzen - denn das ist hier gemeint! Also:

Es existiert ein $\begin{align*} x\in ((A\setminus B)\cup (B\setminus A)) \end{align*}$ , d.h., $\begin{align*} x \in A \wedge x \in B^c \end{align*}$ oder $\begin{align*} x \in A^c \wedge x \in B \end{align*}$ , und für dieses x ist dann offenbar $\begin{align*} \chi_A(x)\neq \chi_B(x) \end{align*}$ .

Zur Surjektivität: Warum so kompliziert? Für $\begin{align*} \varphi\in\{0,1\}^X \end{align*}$ kannst du doch die Urbildmenge $\begin{align*} A:=\varphi^{-1}(\{1\}) \end{align*}$ definieren, und dann ist es einfach zu zeigen, dass $\begin{align*} \varphi=\chi_A \end{align*}$ ist.

28.09.2015, 17:34

bijektion

Auf diesen Beitrag antworten »

Willst du zeigen das $\begin{eqnarray*} f \end{eqnarray*}$ eine Bijektion ist?

Bei der Surjektivität musst du zeigen, dass es zu jedem $\begin{eqnarray*} \varphi\in \left\{0,1\right\}^X \end{eqnarray*}$ eine Menge $\begin{eqnarray*} A\subseteq X \end{eqnarray*}$ gibt, sodass $\begin{eqnarray*} \chi_A=\varphi \end{eqnarray*}$ . Dazu passt deine Überlegung schon, die Idee, dass $\begin{eqnarray*} \left\{0,1\right\}^X = \left\{ \chi_A ~|~ A\in \mathcal{P}(X)\right\} \end{eqnarray*}$ gilt, ist nämlich gerade die Surjektivitätsbedingung.

Du kannst zu $\begin{eqnarray*} \varphi\in \left\{0,1\right\}^X \end{eqnarray*}$ einmal $\begin{eqnarray*} \varphi^{-1}(0)\subseteq X \end{eqnarray*}$ bzw. $\begin{eqnarray*} \varphi^{-1}(1)\subseteq X \end{eqnarray*}$ bestimmen.

28.09.2015, 19:17

Joefish

Auf diesen Beitrag antworten »

Vorweg muss ich sagen ich tue mir immer schwer die Surjektivitaet zu zeigen, falls ich diese nicht mit einem Gegenbeispiel widerlegen kann.
Also, naechster Versuch:

Sei $\begin{eqnarray*} \varphi \in \{0,1\}^X \end{eqnarray*}$ und $\begin{eqnarray*} A := \varphi^{-1}\left(\{1\}\right) \in \mathfrak{P}(X) \end{eqnarray*}$ .
Man definiere ein $\begin{eqnarray*} \chi_A : X \to \{0,1\}, x \mapsto \left\{\begin{matrix} 0, & x \in \varphi^{-1}\left(\{0\}\right), \\<br /> 1, & x \in \varphi^{-1}\left(\{1\}\right). \end{matrix} \right. \end{eqnarray*}$

Da $\begin{eqnarray*} f(A) = \chi_A \end{eqnarray*}$ und $\begin{eqnarray*} f \end{eqnarray*}$ injektiv, folgt $\begin{eqnarray*} \varphi = \chi_A \end{eqnarray*}$ .

Edit: Wuerde mich freuen, wenn jemand mir sagen koennte ob das okay ist.

29.09.2015, 19:32

Joefish

Auf diesen Beitrag antworten »

Sorry fuer den Bump aber waere klasse, wenn jemand mir ein okay geben koennte smile

Neue Frage »

Antworten »

Existenz einer Bijektion zeigen

Verwandte Themen