1

I'm looking at a proof and failing to understand a step.

1) Base case:

$ss(0) + 0 = ss(0)$,

by the axiom for 0 addition which states that 0+n=n.

2) We want to prove that for all n,

$ss(0) + s(n) = sss(n)$.

By definition / axioms, we get the following:

2.1) $ss(0) + s(n) = s(ss(0)+n)$

But what axiom or rule allows us to go from that to the conclusion that

2.2) $ss(0) + s(n) = sss(n)$ ?

IgnorantCuriosity
  • 1,423
  • We are aiming for induction. So you are now assuming ss(0)+s(n)=sss(n), and then you want to prove the same with n replaced by s(n). So 2.2) should be assumed. – Wojowu Jan 08 '17 at 21:11
  • Sorry, I should have stated that we had already assumed ss(0)+n=sss(n). 2.2 involves s(n) though, not n. – IgnorantCuriosity Jan 08 '17 at 21:13
  • Ah, sorry, from the title I have misunderstood that ss(0)+s(n)=sss(n) is the statement to be proven by induction – Wojowu Jan 08 '17 at 21:18
  • Did I understand correctly that the statement to be proven by induction is $ss(0) + n = ss(n)$? If so, consider to make it explicit in your question. – Ennar Jan 08 '17 at 21:26
  • Also, $0 + n = n$ is not an axiom. It is definition + commutativity. – Ennar Jan 08 '17 at 21:29

1 Answers1

0

Assume $ss(0) + n = ss(n)$. Then we have

$$s(ss(0)+n) = sss(n)\implies ss(0) + s(n) = sss(n)$$ by definition $m+s(n) = s(m+n)$.

Ennar
  • 23,082