Are my proofs correct for basic addition properties for natural numbers?

70 Views Asked by At

Are my proofs correct?


Additive Identity: $a + 0 = a$

Definition of Addition: $a + S(b) = S(a + b)$

where $S(a)$ is the successor of $a$.


Claim: $0 + a = a$.

Base Case: When $a=0$, we have $0 + 0 = 0$ which is true by the additive identity definition.

Inductive Step: Suppose $0 + a = a$. We wish to show that $0 + S(a) = S(a)$. By definition of addition, $0 + S(a) = S(0 + a)$. Then $S(0 + a) = S(a)$ by the inductive hypothesis, and we are done.


Claim: $S(a) + b = S(a+b)$.

Base Case: $S(a) + 0 = S(a + 0) = S(a)$ by additive identity and definition of addition.

Inductive Step: Suppose $S(a) + b = S(a+b)$. We want to show that $S(a) + S(b) = S(a + S(b))$. By definition of addition, $S(a) + S(b) = S(S(a) + b)$ which is also equal to $S(S(a+b))$ by inductive hypothesis. Then $S(S(a+b)) = S(a + S(b))$ by definition of addition, and we are done.


Claim: $a + b = b + a$

Base Case: $a + 0 = 0 + a = a$ which is true by our additive identities.

Inductive Step: Suppose $a + b = b + a$. We need to show that $a + S(b) = S(b) + a$. By definition of addition, $a + S(b) = S(a+b)$. Our new addition definition also gives us $S(b) + a = S(b+a)$, which by inductive hypothesis is equal to $S(a+b)$. Therefore both sides are equal and we are done.


Claim: $a + c = b + c$ implies $a = b$.

Base Case: If $c=0$ then we have $a + 0 = b + 0$ which reduces to $a = b$ by our additive identities.

Inductive Step: Suppose that $a + c = b + c$ implies $a=b$. We need to show that $a + S(c) = b + S(c)$ implies $a=b$. By definition of addition, $a + S(c) = S(a+c)$, and $b + S(c) = S(b+c)$. By Peano's axiom stating that S is injective, we have $a+c=b+c$. By inductive hypothesis, $a=b$, so we are done.


Claim: $(a+b)+c = a+(b+c)$.

Base Case: Setting $c=0$, by additive identities the equivalence $(a+b)+0 = a+(b+0)$ reduces to $a+b = a+b$ which is true.

Inductive Step: Suppose $(a+b)+c = a+(b+c)$. We need to show that $(a+b)+S(c) = a+(b+S(c))$. By definition of addition, $(a+b)+S(c) = S((a+b)+c)$, and $a+(b+S(c)) = a + S(b+c) = S(a+(b+c))$. By inductive hypothesis, $S(a+(b+c)) = S((a+b)+c)$. Now both sides are equal, so we are done. What this also suggests is that parentheses can be omitted since they have no impact on the end result, so $(a+b)+c = a+(b+c) = a+b+c$ can be considered equivalent.

1

There are 1 best solutions below

2
On BEST ANSWER

They all look OK to me except this one:

If $a + c = b + c$, then $a = b$.

Note that this is the only theorem that invokes the phrasing "if ... then."

Given the statement $P\implies Q,$ one cannot immediately infer $P.$ The correct inductive hypothesis would be that for some $c,$ $a + c = b + c \implies a = b.$ Instead, you assumed $a + c = b + c,$ which is a different statement.

You end up showing that $a + c = b + c \implies a + S(c) = b + S(c),$ but even if you combine this with the correct inductive hypothesis, it is not correct to infer from $P\implies Q$ and $P\implies R$ that $R\implies Q.$ You need your inductive step to conclude that $a + S(c) = b + S(c) \implies a = b.$