# How to prove the following statement regarding the successor function and addition of natural numbers?

Natural numbers (including 0) and the successor function are defined as per the Peano Axioms (you can check them on wikipedia). Addition is defined recursively as follows:

$$a+0=a$$

$$a+S(b)=S(a)+b$$

With these definitions in mind, I need to prove that $$a+S(b)=S(a+b)$$

I tried using induction on b, and while proving the base case was trivial, I only end up with a circular argument when I try to prove the inductive step.

• You should prove $\forall a (a + S(b) = S(a + b))$ by induction on $b$. May 23, 2022 at 23:15
• @MauroALLEGRANZA I intenionally used a different (hopefully equivalent, though I have yet it prove this) definition for addition, which is why I am trying to prove all of additions's properties from scratch, i.e. I am not allowed to use any "preliminary lemmas" and similar things. At the end of your proof, you state that $Sb+Sa=S(Sb+a)$... Which is exactly what I am trying to prove, so I can't use this statement in the proof. Also, I am not allowes to consider addition commutative yet either. May 24, 2022 at 7:51
• You should probably show your failed attempt. It might turn out to be correct, and anyway we can better see where exactly your confusion is. May 24, 2022 at 9:44

Hint: try to prove the stronger claim: $$\forall x(a + S(x) = S(a+x))$$
• This is exactly what I am trying to prove, essentially that $\forall a\forall b(a+S(b)=S(a+b))$ May 24, 2022 at 7:34
• No it isn't. You don't have the $\forall$, which is vital as you need to apply the inductive hypothesis with $S(b)$ in place of $b$.. @MauroALLEGRANZA leaves this implicit in his answer, but that is a sleight of hand. May 24, 2022 at 17:34