Vollständige Induktion Cantorsche Diagonalverfahren

Question

Sei dC: N x N -> N die bekannte Funktion zum ersten Cantorschen Diagonalverfahren:

dC(m,n) = df 1/2(m+n+1)(m+n)+m.

Beweisen Sie, dass dC surjektiv ist. Zeigen Sie dazu die Aussage

Für mindestens ein Element k E N. existiert m,n E 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).

Answer 1

dC(m,n) =  1/2(m+n+1)(m+n)+m.

Ind. anfang:  Für  k=0 erfüllt, weil dC(0,0)=0

Sei k∈ℕ und dC(m,n)=k , also   1/2(m+n+1)(m+n)+m = k

1. Fall:  n>0 ==>   n-1∈ℕ und es ist

              dC(m+1,n-1) =  1/2(m+1+n-1+1)(m+1+n-1)+m+1

                                   =  1/2(m+n+1)(m+n)+m+1  =  k+1

denn das rote ist gleich k.

Also gibt es auch ein Paar , nämlich (m+1,n-1) , dessen Bild k+1 ist.

2. Fall  n=0 ==>    1/2(m+1)*m+m = k <=> 1/2*m^2 + 1/2*m + m = k

                              <=> 1/2*m^2 + 3/2*m = k

                              <=> 1/2*(m^2 + 3m) = k

==>  dC(0, m+1) =  1/2(0+m+1+1)(0+m+1)+0

                  =  1/2(m+2)(m+1) = 1/2(m^2+3m+2)

                 = 1/2(m^2+3m)  +1/2 * 2   =  k+1 .

Also gibt es auch in diesem Fall ein Paar , nämlich (0,m+1) , dessen Bild k+1 ist.

Also ist dC surjektiv.