Es ist |2N| ≤ |NN| weil jeder Teilmenge T von N eine unterschiedliche Folge (an)n∈N über N zugeordnet werden kann, nämlich
an := 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 (an)n∈N aus NN die Menge
{p(n)an | n ∈ N}
zuordnet. Dann ist f injektiv und somit |NN| ≤ |2N|.
Also ist |NN| = |2N|.