ich habe folgende Frage:
Begründen Sie, warum die Funktion Q : ℕ0 x ℕ → ℕ0 durch die folgende rekursive Definition eindeutig bestimmt ist.
Q((a,b)) = { 0 für a < b Q(a - b, b) + 1 für a ≥ b
Ich hab hier leider nicht mal einen Ansatz an dem ich mich orientieren könnte.
versuch mal Induktion über a: Für a=0 hast du also Q (0 ; b) mit b aus IN zu
betrachten, also den Fall a<b also ist das 0
Wenn nun für alle Paare (a,b) bis zu einem festen a aus INo alles eindeutig bestimmtist,
musst du den Fall (a+1,b) betrachten .
Fall a+1 < b ist Q(a+1 ; b) = 0 also alles klar.
falls a+1 >= b ist, ist Q(a+1,b) = Q ( a+1-b, b )+1 und
a+1-b < a+1 also <=a
Für diese Fälle ist lt. Ind.annahme alles eindeutig bestimmt, also
auch Q(a+1, b). q.e.d.
