# How to prove that $+$ is commutative on the natural numbers?

Let $N$ be a non empty set. Let $s:N\to N$ a function satisfying:

1. there is only one element in $N-s(N)$ (denoted by $1$);

2. $s$ is injective;

3. for any subset $X\subset N$, if $1\in X$ and $(n\in N \Rightarrow s(n)\in N)$ then $X=N$.

We define a binary operation '$+$' on $N$ by $$m+n=s^n(m)$$ where $s^n$ is the iterated function. So $$m+1=s(m) \quad \text{and}\quad m+s(n)=s(m+n).$$

My problem is: how to prove (probably using the induction) that $$m+n=n+m.$$

-
"We define a binary operation '+' on $N$ by $m+n = s^n(m)$" : it seems like this can't be right as written, because I don't know how to compute $s^n$ unless $n$ is a natural number, and $N$ (the set which $n$ is a member of) hasn't been necessarily defined as a set of naturals at this point. –  Steven Stadnicki Feb 8 '13 at 0:03
$s^n$ is defined recursively by induction. After this we can define the operation $+$. –  Sigur Feb 8 '13 at 0:07
But the point is that the exponent $n$ in $s^n$ is of necessity a number - something like '5' or '17'. You haven't shown how those numbers relate to elements in $N$ yet. If there's an inductive definition of $s^n$ for $n\in N$ (something like $s^{s(n)}(m) = s(s^n(m))$), then that should probably be part of your problem statement. –  Steven Stadnicki Feb 8 '13 at 0:13
@StevenStadnicki, OK, sorry. There are many things that I didn't write. I only focused on the commutative property. So, I can assume that $s^n$ is well defined. Thanks. –  Sigur Feb 8 '13 at 0:17

Hint: Let $X_m:=\{n\in N\mid m+n=n+m\}$ for a fixed $m\in N$ and show that it satisfies 3, by induction on $m$.

For $X_1$, $1\in X_1$ by definition, and so on.

-
I tried but how to show that $1\in X$? –  Sigur Feb 8 '13 at 0:00
$1\in X_m$ for all $m$ iff $X_1=N$. –  Berci Feb 8 '13 at 0:06

Hint: Show that the set $X=\{n\mid\forall m\leq n: m+n=n+m\}$ is inductive.

(Recall that $\leq$ is definable from $+$, $n\leq m\iff\exists k.n+k=m\lor n=m$)

-