A question on the proof of commutativity of the sum of natural numbers?

Question

I made this question yesterday and today I've been thinking about another aspect of it. But this question is totally related to the previous one: I am trying to make a clarification about a proof of the commutativity of the sum on the natural numbers, having only:

• $S:\mathbb{N}\to\mathbb{N}$ is an injection; $0\in\mathbb{N}\setminus S(\mathbb{N})$ and the principle of finite induction.

• $m+0:=m \quad\quad\quad m+S(n):=S(m+n)$

Take the sentence

$$\text{If $0+n=n$, then $0+S(n)=S(0+n)=S(n)$.}$$

This sentence says:

$$\text{If $P$ is true, then $1$ happens.}$$

And I guess it also says:

$$\text{If $P$ is not true, then $2$ happens.}$$

With $1\neq 2$, I guess. In this case, it seems that we're only collecting the cases in which the commutativity happens and leaving out the cases in which it doesn't happens. It seems that the only point of interest is to select the cases in which it happens, but the given axioms do not guarantee that there is only commutativity. Is that correct?

Sorry If I'm being annoying, but I really want to understand this and after years, I've finally being able to express my concerns. The sentence "If $P$ is true, then $Q$" doesn't seems to make the commutativity legitimate. After all, "if $P$ is true, then $Q$" means that in the ocasion that $P$ holds, then $Q$ holds, but what about when $P$ doesn't hold?

Answer 1

Hint

Not a trivial exercise.

First prove associativity:

Suppose $x,y \in \mathbb{N}$. Prove by induction that, for all $k\in \mathbb{N}$, we have $x+y+k=x+(y+k)$.

Then prove commutativity:

(1) Prove by induction that, for all $k\in \mathbb{N}$, we have $k+0=0+k$.

(2) Prove by induction that, for all $k\in \mathbb{N}$, we have $k+1=1+k$.

(3) Suppose $x\in\mathbb{N}$. Prove by induction that, for all $k\in\mathbb{N}$, we have $x+k=k+x$.

Answer 2

Comments

The first-order axioms for sum are :

$m+0=m$

and :

$m+S(n)=S(m+n)$.

Thus, we have to prove :

$m=0+m$

and so, by property of equality, we conclude with :

$m+0=0+m$.

The proof of : $m=0+m$ is by induction, where the induction formula $P(m)$ is $(0+m)=m$ :

• basis step :

from axiom : $m+0=m$, that we have to read as universally quantified, i.e. as : $\forall x(x+0=x)$, by $\forall$-introduction, we get $P(0)$ :

$0+0=0$.

• induction step :

we have to prove : $\forall x(P(x) \to P(S(x)))$, where $P(S(m))$ is $0+S(m)=S(m)$.

1) $0+m=m$ --- assumed

2) $S(0+m)=S(m)$ --- from 1) by property of equality with the function $S$

3) $0+S(m)=S(m)$ --- from 2) and axiom : $S(n+m)=n+S(m)$ and properties of equality

4) $(0+m=m) \to (0+S(m)=S(m))$ --- from 1) and 3) by $\to$-introduction.

In conclusion, we have proved $P(0)$ and $\forall x(P(x) \to P(S(x)))$; we can apply the induction axiom to conclude with :

$\forall xP(x)$

i.e. : $(0+m)=m$, for all $m$.

---

We have proved the formula for commutativity :

$m+0=0+m$, for all $m$

by induction.

The induction axiom schema is :

$P(0) \to (\forall x(P(x) \to P(S(x))) \to \forall xP(x))$;

thus, the conclusion : $\forall xP(x)$ follows from the two steps of the induction proof by a "double" modus ponens ($\to$-elimination).

Your concern is about the "general form" of the conditional $p \to q$ : what if $p$ is not true ?

Of course, in this case we cannot apply modus ponens.

To be more specific, consider the silly example with $n>0$ as induction formula $P(n)$ : we have that $P(0)$ does not hold (because it is not true that $0 > 0$) and thus we cannot apply the induction axiom to conclude with (the false) : $n > 0$, for all $n$.