1
$\begingroup$

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}$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ancientmathematician Mar 27 at 16:24
  • 1
    $\begingroup$ You'll find it much easier to root the inductions at $0$. $\endgroup$ – ancientmathematician Mar 27 at 16:29
  • 1
    $\begingroup$ OK, but as I said, that's not what you have written, is it? $\endgroup$ – ancientmathematician Mar 27 at 17:36
  • 1
    $\begingroup$ 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. $\endgroup$ – ancientmathematician Mar 27 at 17:52
  • 1
    $\begingroup$ 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. $\endgroup$ – ancientmathematician Mar 28 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.