Seien f und g injektive Funktionen, dann existiert eine Bijektion

Question

Zu zeigen ist:

Gibt es für beliebige Mengen A und B injektive Funktionen $$f: A \to B$$ und $$g: B \to A$$ dann existiert eine bijektive Funktion $$h: A \to B$$

Intuitiv macht das Sinn, weil A und B gleichmächtig sein müssen damit eine Injektion von A nach B und von B nach A existiert. Daraus folgt dann auch sofort die Existenz der Bijektion. Aber weil die Mengen beliebig gewählt werden können, können sie auch unendlich sein, und das erschwert mir den Beweis. Wie löst man das?

Answer 1

Hi.

Ich würde bei dieser Aufgabe folgende zwei Punkte zeigen:

(1) Die Mengen $A$ und $B$ sind gleichmächtig, d.h. $|A| = |B|$, unabhängig davon ob $A$, $B$ endlich oder unendlich sind, und

(2) die Existenz einer bijektiven Abbildung $h:A\to B$.

Lösungsvorschlag:

Seien $A$ und $B$ beliebige Mengen.

(1) Zeige $|A| = |B|$:

Da $f:\,A\to B$ injektiv ist:
$\Rightarrow\;$ $|A| = |f(A)|$, wobei $f(A) \subseteq B$ die Bildmenge von $f$ ist.
$\Rightarrow\;$ $|A| = |f(A)| = |B| - |M_B|$, wobei $M_B \, := \lbrace b \in B \;|\; b \neq f(a) \,,\;\forall a\in A \rbrace$ die Menge der Elemente $b \in B$ ist, die aufgrund der Injektivität von $f$ gar keinen Partner $a \in A$ haben.
$\Rightarrow\;$ $|A| \leq |B|$ $\;\; (\star)$

Da $g:\,B \to A$ injektiv ist:
$\Rightarrow\;$ $|B| = |g(B)|$, wobei $g(B) \subseteq A$ die Bildmenge von $g$ ist.
$\Rightarrow\;$ $|B| = |g(B)| = |A| - |M_A|$, wobei $M_A \,:= \lbrace a \in A \;|\; a \neq g(b) \,,\;\forall b\in B \rbrace$ die Menge der Elemente $a \in A$ ist, die aufgrund der Injektivität von $g$ gar keinen Partner $b \in B$ haben.
$\Rightarrow\;$ $|B| \leq |A|$ $\;\; (\star\star)$

Aus $(\star)$ und $(\star\star)$ folgt $|B| \leq |A| \leq |B|$ bzw. $|A| = |B|$, und mithin $M_A = M_B = \emptyset$.

(2) Zeige $f:\,A\to B$ ist surjektiv:

Wir wissen, dass $|A| = |B|$ und $f:\,A\to B$ injektiv ist. Widerspruchsbeweis: wir nehmen an, dass $f$ nicht surjektiv sei. Dann:

$f :\, A \to B$ nicht surjektiv
$\;\Rightarrow\; \exists\, b \in B \,:\, \forall\, a\in A \,:\, b \neq f(a)$
$\;\Rightarrow\; M_B := \lbrace b \in B \;|\; b \neq f(a) \,,\;\forall a\in A \rbrace \neq \emptyset$
$\;\Rightarrow\; |A| = |B| - |M_B|$
$\;\Rightarrow\; |B| > |A| = |B|$
$\;\Rightarrow\; |B| > |B|$
$\;\Rightarrow\;$ Widerspruch!

Also muss $f$ surjektiv sein. Somit ist $f$ bijektiv. Wir wählen anschließend $h \, := f$. Dadurch ist $h :\,A\to B$ automatisch bijektiv. Und wir haben die Existenz einer bijektiven Funktion von zwischen A und B bewiesen.

$\blacksquare$

Ich hoffe, es hilft.

MfG

Comments

$|A| = |f(A)| = |B| - |M_B|$

Ist dabei ∞-∞ = 0 oder ∞-∞ = ∞ oder ∞-∞ = 77  ?

Ich hoffe, es hilft.

Mich verwirrt es leider eher, da ich mir die identische Abbildung f von ℕ nach ℤ nicht wirklich so recht bijektiv vorstellen kann.

---

Hi Gasthj2166. Vielen Dank für deinen Kommentar. Ich habe die Formulierung im Beweis angepasst.

Seien $A$ und $B$ beliebige Mengen.

(1) Zeige $|A| = |B|$:

Da $f\,:\,A\to B$ ist injektiv:

$\Rightarrow\;$ $|A| = |f(A)|$ und $f:A\to f(A)$ bijektiv, wobei $f(A) \subseteq B$ die Bildmenge von $f$ ist.
$\Rightarrow\;$ $|M_B| \geq 0$, wobei $M_B := B\setminus f(A) = \lbrace b \in B \;|\; b \neq f(a) \,,\;\forall a\in A \rbrace$ die Menge der Elemente $b \in B$ ist, die aufgrund der Injektivität von $f$ gar keinen Partner $a \in A$ haben.
$\Rightarrow\;$ $|A| = |f(A)| = |B\setminus M_B|$
$\Rightarrow\;$ $|A| \leq |B|$$\;\;(\star)\;$, d.h. $A$ ist weniger mächtig wie $B$.

Da $g\,:\,B\to A$ ist injektiv:

$\Rightarrow\;$ $|B| = |g(B)|$ und $g:B\to g(B)$ bijektiv, wobei $g(B) \subseteq A$ die Bildmenge von $g$ ist.
$\Rightarrow\;$ $|M_A| \geq 0$, wobei $M_A := A\setminus g(B) = \lbrace a \in A \;|\; a \neq g(b) \,,\;\forall b\in B \rbrace$ die Menge der Elemente $a \in A$ ist, die aufgrund der Injektivität von $g$ gar keinen Partner $b \in B$ haben.
$\Rightarrow\;$ $|B| = |g(B)| = |A\setminus M_A|$
$\Rightarrow\;$ $|B| \leq |A|$$\;\;(\star\star)\;$, d.h. $B$ ist weniger mächtig wie $A$.

Aus $(\star)$ und $(\star\star)$ folgt $|B| \leq |A| \leq |B|$ bzw. $|A| = |B|$, mithin $M_A = M_B = \emptyset$.

(2) Zeige $f\,:\,A\to B$ ist surjektiv:

Wir wissen, dass $f \;\text{injektiv}$ und $|A|=|B|$ ist.
Wir nehmen nun an: $f$ sei nicht surjektiv. Dann:

$f : A \to B$ nicht surjektiv
$\;\Rightarrow\; \exists\, b \in B \,:\, \forall\, a\in A \,:\, b \neq f(a)$
$\;\Rightarrow\; M_B = \lbrace b \in B \;|\; b \neq f(a) \,,\;\forall a\in A \rbrace \neq \emptyset$
$\;\Rightarrow\; |A| = |f(A)| = |B\setminus M_B|$
$\;\Rightarrow\; |B| > |A| = |B|$
$\;\Rightarrow\; |B| > |B|$
$\;\Rightarrow\;$ Widerspruch!

Also $f$ muss surjektiv sein. Somit ist $f\,:\, A \to B$ bijektiv. Wir wählen anschließend $h\,:= f$. Es ist offensichtlich, dass $h\,:\,A\to B$ bijektiv ist. Damit haben wir die Existenz einer Bijektion zwischen $A$ und $B$ gezeigt.