Beide Teilaussagen können wegen des ersten Peano-Axioms nicht zugleich wahr sein. Es geht also um die Aussage

${\displaystyle \forall x{\left({\left(x=0\right)}\vee {\left(\exists ux=u+1\right)}\right)},}$

die wir durch Induktion beweisen. Der Induktionsanfang für ${\displaystyle {}x=0}$ ist durch den linken Bestandteil gesichert. Sei also die Aussage für ein gewisses ${\displaystyle {}x}$ schon bewiesen, und sie ist für ${\displaystyle {}x+1}$ zu beweisen. Bei ${\displaystyle {}x=0}$ ist ${\displaystyle {}x+1=0+1}$, so dass man ${\displaystyle {}u=0}$ nehmen kann. Bei ${\displaystyle {}x=u+1}$ ist

${\displaystyle {}x+1=(u+1)+1\,}$

${\displaystyle {}u+1}$