# Proving that addition in $\mathbb{N}$ is associative and commutative

I would like to prove the associative and commutative property of the natural numbers by using Peanos axioms only. Did I justify every step in my proofs correctly?

Definition. $$\forall n,m \in \mathbb{N}\ , \ n+m = \underbrace{s(s(...s}_\text{m} (n)...)) = s^{[m]}(n)\$$ where $$s(n)$$ is the successor function.

a) $$\forall n,m,k \in \mathbb{N} , n+(m+k)=(n+m)+k$$

Proof: Let $$S\subset\mathbb{N}$$ be the set for which a) holds.

1. Case $$k=1 \ , \ \forall n,m \in \mathbb{N}$$

$$n +(m+1) =$$ (definition of $$+$$) $$= s^{[m+1]}(n) = (*) = s(s^{[m]}(n)) = s(m + n) = (m+n) + 1$$

I am not sure how to justify $$(*)$$. I have:

$$s^{[m+1]}(n) = \underbrace{s(s(....s}_\text{m}(\underbrace{s}_\text{1}(n))...))=\underbrace{s}_\text{1}(\underbrace{s(s(...s}_\text{m}(n)...)))=s(s^{[m]}(n))$$

The composition of functions is associative but am I implicitly assuming the commutative property of the natural numbers i.e. $$m+1 = 1+m$$ ?

1. Let $$k\in S$$ be arbitrary $$\implies n+(m+k)=(n+m)+k$$

$$n+(m+(k+1))=$$ (From 1. for $$m+(k+1)$$) = $$n +((m+k)+1) =$$ (From 1. for $$n+(t+1)$$ and $$t=m+k\in\mathbb{N}$$) $$=(n+t)+1 = (n + (m+k))+1 = (k\in S) = ((n+m)+k)+1=s^{[k]}(n+m)+1=s^{[k+1]}(n+m) = (n+m)+(k+1)$$

From 1. we have $$1\in S$$ and from 2. we have $$k\in S \implies s(k)=k+1\in S$$ and by the axiom of mathematical induction it follows that $$S = \mathbb{N}$$.

b) $$\forall n,m \in \mathbb{N}\ ,\ n+m=m+n$$

Proof:

First we will show that $$s(n) = s^{[n]}(1)$$

$$n=1 \implies s(1) = 1+1 = s^{[1]}(1)$$

Let $$n\in\mathbb{N}$$ be an arbitrary number for which the claim holds:

$$s(n+1) = (n+1) + 1 = s(n) + 1 = s^{[n]}(1) + 1 = s^{[n+1]}(1)$$

By the axiom of mathematical induction, the claim holds for all natural numbers.

Now let $$S\subset\mathbb{N}$$ be the set of all numbers for which the original claim holds.

1. Case $$m=1$$

$$n+1 = s(n) = s^{[n]}(1) = 1 + n$$

1. Let $$m\in S$$ be arbitrary $$\implies n + m = m + n$$

$$n + (m+1) = s^{[m+1]}(n) = s(s^{[m]}(n)) =s(n+m) =$$ ( $$m\in S$$ ) $$= s(m+n) = s(s^{[n]}(m)) = s^{[n+1]}(m) = m + (n+1) =$$ (Case 1.) $$=m+(1+n)=$$ (associative) $$=(m+1)+n$$.

From 1. we have $$1\in S$$ and from 2. we have $$m\in S \implies s(m)=m+1\in S$$ and by the axiom of mathematical induction it follows that $$S = \mathbb{N}$$.

• You'll have to clarify lines like "Let $S\subset\mathbb{N}$ be the set for which a) holds." I suspect you mean that you are looking at the $k$ which make it true foe all $m,n$ but since (a) has no free variables what you say is meaningless. – ancientmathematician Mar 27 at 16:24
• You'll find it much easier to root the inductions at $0$. – ancientmathematician Mar 27 at 16:29
• OK, but as I said, that's not what you have written, is it? – ancientmathematician Mar 27 at 17:36
• I'd also recommend not using $\dots$ in such proofs/definitions. I think that's where you're getting confused. If you insist in excluding $0$ from $\mathbb{N}$ then the definition of $+$ in terms of $s$ is: $m+1=s(m)$, $m+s(n)=s(m+n)$. It's then pretty straightforward to prove associativity. – ancientmathematician Mar 27 at 17:52
• I'm sorry, it just seems to me not to be a good enough definition as it leads to exactly this doubt. I think you are right when you say you've used $m+1=1+m$ at $(*)$; the problem is that the Peano arithmetic is escaping into the mathematical language describing it. In most standard formulations one proves associativity, then $1+m=m+1$ then full commutativity. – ancientmathematician Mar 28 at 7:48