Beweis durch Noethersche Induktion

Question

Aufgabe:

Wir betrachten die aus der Vorlesung bekannte Ackermann-Funktion:
ack : ℕ × ℕ → ℕ

ack(n, m) = {    m + 1                                           if n = 0
                        ack(n − 1, 1)                                if n > 0, m = 0
                        ack(n − 1, ack(n, m − 1))             if n > 0, m > 0

Beweisen Sie durch Noethersche Induktion über die lexikographische Ordnung der Argumente:
∀ n,m ∈ N. m < ack(n, m)

Leider weiß ich nicht, wie ich hier vorgehen kann. Kann mir jemand weiterhelfen?

Comments

Noether Induktion:

zz wenn Aussage für alle (x,y) < (n,m) gilt dann gilt sie auch für (n,m)

Sei also (n,m) beliebig und die Aussage gelte für alle (x,y) < (n,m)

Falls n=0: Dann ist ack(0,m)=m+1>m. Passt.

Falls n > 0 und m=0: Dann ist ack(n,0) = ack(n-1,1)

Wegen (n-1,1) < (n,0) ist nach Voraussetzungen aber ack(n-1,1)>1>0. Passt also auch

Falls n>0 und m>0 ist ack(n,m)=ack(n-1,ack(n,m-1))

Nun ist (n-1,ack(n,m-1)) < (n,m) insbesondere also ack(n-1,ack(n,m-1)) > ack(n,m-1)

Und wegen (n,m-1)<(n,m) ist

ack(n,m-1)>m-1

Es folgt ack(n,m) = ack(n-1,ack(n,m-1)) > ack(n,m-1)≥m.