Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
"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.

share|cite|improve this answer
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$)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.