Induktionsbeweis

Guten Tag liebe Coder,

heute wende ich mich an euch weil ich einfach nicht mehr weiter weiß. :confused:

Ich studiere Informatik und habe gerade ein paar Schwierigkeiten mit einem Induktionsbeweis.

Vorgegeben ist folgende endrekursive Definition von Addition:

plus(x,0) = 0
plus(x,S(y)) = plus(S(x),y) dabei sei gesagt, dass S(x) der Nachfolger von x ist also x+1

Nun soll ich durch Induktion zeigen, dass:

plus(x,y) = x+y


Mein Problem liegt darin, dass ich nicht weiß wie ich in dem Induktionsschritt von der Funktion plus auf x+y kommen soll. Jedoch bin ich gerade auf eine Lösung gestoßen, jedoch weiß ich nicht ob diese erlaubt ist:

Induktion über x

IA: plus(x,0) = x = x+0

IS: Sei y=1

plus(x,y) = plus(x,1) = plus(S(x), 0) = S(x) = x+1 = x+y


Nun ist meine Frage, ob ich in dem Induktionsschritt einfach sagen darf, dass y=1 ist. Und falls nicht habe ich einfach überhaupt keine Ahnung was ich noch machen soll. :(

Ich hoffe einfach jemand kennt sich gut damit aus und kann mir weiterhelfen!

Du musst doch für den Induktionsstart mindestens eine Variable setzen und dann alles für n+1 (n Element |N) einsetzen und rauskürzen. Demnach müsste es erlaubt sein, ansonsten hast du ja keinen Induktionsanfang.

Wenn plus(x,0) = 0 für beliebige x, dann ist auch plus(S(x), 0) = 0.

Sollst du nun eine Induktion über x oder y machen? Werde nicht ganz schlau draus.