Kardinalitätsvergleich von unendlichen Mengen

Question

Aufgabe:

Beweise, dass die Mengen M und N gleichmächtig sind.

M = ℕ×ℕ

N = {k²+k|k ∈ ℕ}

…

Problem/Ansatz:

Ich weiß, dass |ℕ×ℕ| = |ℕ| gilt

komme aber bei N nicht weiter

Answer 1

Das |ℕ×ℕ| = |ℕ| ist, hilft dir schon einmal weiter.

Sei Mengen M und N sind gleichmächtig, wenn es eine bijektive Abbildungen von M nach N gibt (bzw. nach Satz von Schröder–Bernstein reicht es, wenn es eine injektive Abb von M nach N und eine injektive Abbildung von N nach M gibt).

Sei P = ℕ, musst also zeigen, dass es eine injektive Abb von N nach P gibt und eine von P nach N.

P nach N ist einfach (jeder natürlichen Zahl k wird ihr k²+k zugeordnet, dabei gilt, dass wenn k_1² + k_1 = k_2² + k_2 gilt, k_1 = k_2 ist (Nachweis MUSS geführt werden, sollte aber gehen)).

N nach P ist bisschen schwieriger. Du musst sozusagen die Elemente von P "durchnummerieren", oder du findest eine Umkehrabbildung, die ebenfalls injektiv ist.

Alternativ kannst du natürlich zeigen, dass die Abbildung vob P nach N bijektiv ist, also zusätzlich auch noch surjektiv. Dies ist aber im allgemeinen schwerer.

Comments

Danke, das hat mir geholfen!

---

@Erdbeere Die Verwendung des Cantor-Bernstein-Schröder Theorems ist vielleicht ein bisschen hochgegriffen für eine solche Aufgabe

---

@Liszt das Theorem haben wie schon eigeführt und kann ddeshalb auch benutzt werden

---

Ja, ich wollte eben nur sagen, dass es nicht absolute notwendig ist.

Answer 2

Wegen \( |\mathbb{N}|=|\mathbb{N} \times \mathbb{N}| \) gibt es eine Bijektion \( \varphi: \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N} \). Wir müssen also lediglich eien Bijektion von \( \mathbb{N} \) nach \( N \) finden. Die Funktion \( k^{2}+k \) ist auf dem Interval \( [0, \infty) \) streng monoton wachsend und somit bijektiv, da sie unbeschränkt und stetig ist. Dementsprechend ist
\( \gamma: \mathbb{N}\rightarrow N, \quad \gamma(x)=x^{2}+x \)
eine Bijektion und daher
\( \gamma \circ \varphi: \mathbb{N} \times \mathbb{N} \rightarrow N \)
eine Bijektion.

Die Umkehrfunktion von \(\gamma\) von \( \gamma \) auf \( [0, \infty) \) ist gegeben durch
\( \begin{aligned} y=x^{2}+x & \Longleftrightarrow x^{2}+x+\frac{1}{4}=y+\frac{1}{4} \\ & \Longleftrightarrow\left(x+\frac{1}{2}\right)^{2}=y+\frac{1}{4} \\ & \Longleftrightarrow x=\sqrt{y+\frac{1}{4}}-\frac{1}{2}, \quad \text { da } x \geq 0\\ &\Longrightarrow \gamma^{-1}(x) = \sqrt{x+\frac{1}{4}}-\frac{1}{2}\end{aligned}\)

Comments

Dass strenge Monotonie Bijektivität impilziert kann ich nicht verwenden, da wir das noch nicht eingeführt haben, bisher gilt für uns nur, dass strenge Monotonie Injektivität impliziert

---

Strenge Monotonie impliziert auch nicht im Allgemeinen Bijektivität.

---

Passt es jetzt für dich? Ich habe nichts verwendet ausser zu zeigen, dass die Funktion eine Umkehrfunktion hat.

---

Vielen Dank, das ist eine große Hilfe!