Primzahlen und |ℕ × ℕ| = |ℕ|

 Primzahlen liefern Zerlegungen von ℕ in unendlich viele unendliche Teile, und hieraus erhält man weitere Beweise von |ℕ × ℕ| = |ℕ|. Für n  ∈  ℕ sei

p_n  =  „die (n + 1)-te Primzahl“,

also

p₀  =  2,  p₁  =  3,  p₂  =  5,  p₃  =  7,  p₄  =  11,  … 

 Dann sind für n  ∈  ℕ die Mengen P_n = { p^k + 1_n | k  ∈  ℕ } paarweise disjunkte unendliche Teilmengen von ℕ [Eindeutigkeit der Primfaktorzerlegung!]. Setzen wir

f(n, k)  =  p^k + 1_n  für n, k  ∈  ℕ,

so ist f : ℕ × ℕ → ℕ injektiv, also |ℕ × ℕ| ≤ |ℕ|, und damit nach Cantor-Bernstein |ℕ × ℕ| = |ℕ| (denn i : ℕ → ℕ × ℕ mit i(n) = (n, 0) für n  ∈  ℕ ist injektiv, also |ℕ| ≤ |ℕ × ℕ|).

 Ebenso ist die Abbildung g : ℕ × ℕ → ℕ injektiv mit

g(a, b)  =  p^a + 1₀ p^b + 1₁  =  2^a + 1 3^b + 1  für a, b  ∈  ℕ.

 Analog erhält man für beliebige n ≥ 2 injektive Funktionen g_n : ℕ^n + 1 → ℕ. Wir setzen

g_n(a₀, … , a_n)  =  p^a₀ + 1₀ … p^a_n + 1_n  für a₀, … , a_n  ∈  ℕ.

 Bijektionen g : ℕⁿ → ℕ werden auch als Kodierungen bezeichnet. Die natürliche Zahl g(a₁, …, a_n) ist dann der Kode für das „Wort“ (a₁, …, a_n), und die Umkehrfunktion liefert die Dekodierung. Es gibt auch konkrete Kodierungen, die auf Worten variabler Länge operieren (siehe hierzu die Übung unten). In der Logik spielen sie eine große Rolle, da man mit ihrer Hilfe innerhalb der Zahlentheorie über Zeichenketten, und damit in der Zahlentheorie über eine formalisierte Mathematik reden kann.