ich weiß leider nicht, wie ich auf die Lösung bei folgender Aufgabe komme:
Sei dC: ℕ × ℕ → ℕ die bekannte Funktion zum ersten Cantorschen Diagonalverfahren:
dC(m, n) =df \( \frac{1}{2} \)(m + n + 1) (m + n) + m.
Beweisen Sie, dass dC surjektiv ist. Zeigen Sie dazu die Aussage
∀ k ∈ ℕ. ∃ m, n ∈ ℕ. dC (m, n) = k
durch vollständige Induktion nach k.
Hinweis: Unterscheiden Sie im Induktionsschluss die Fälle, dass die Nummerierung entlang einer
Nebendiagonalen fortgesetzt wird (n > 0), und den „Sprung“ in eine neue Nebendiagonale (n = 0).
,
MfG
