Potenzmenge ist gleich Selbstabbildung

Question

Aufgabe:

Zeigen Sie: Es gilt |N^N| = |2^N|

N = Natürliche Zahlen

Problem/Ansatz:

2^N ist ja die Potenzmenge von N und N^N wäre eine Selbstabbildung f: N->N wenn ich mich nicht irre.

aber wie verknüpfe ich das ganze?

Answer 1

Es ist |2^N| ≤ |N^N| weil jeder Teilmenge T von N eine unterschiedliche Folge (a_n)_n∈N über N zugeordnet werden kann, nämlich

        a_n := 1 + |{m ∈ T | m ≤ n}| für alle n ∈ N.

Sei p: N → P die Abbildung von N in die Menge P der Primzahlen mit

        p(n) = die Primzahl, so dass es nur n-1 kleinere Primzahlen gibt.

Beispielsweise ist p(5) = 11, weil 5-1=4 Primzahlen kleiner als 11 sind, nähmlich 2, 3, 5 und 7. Die Abbildung p ist bijektiv.

Sei f: N→N die Abbildung, die jeder Folge (a_n)_n∈N aus N^N die Menge

        {p(n)^a_n | n ∈ N}

zuordnet. Dann ist f injektiv und somit |N^N| ≤ |2^N|.

Also ist |N^N| = |2^N|.