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.
- 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$ ?
- 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.
- Case $m=1$
$n+1 = s(n) = s^{[n]}(1) = 1 + n$
- 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}$.