In the book Notes on Mathematical Analysis the set $\mathbb{N}$ of natural numbers was defined using the classical Peano's axioms. Then $<$ was defined as if exist $k\in \mathbb{N}$ such that $b=S^k(a)$ then we say $a<b$. Then it was asked to prove the transitivity of $<$ relation.

I proceed as follows: if $a<b$ then by definition there is a $k$, $b=S^k(a)$. Same for $b<c$, $c=S^l(b)$. Then it will comes that $c=S^{k+l}(a)$, which means $a<c$.

I can't find errors in my proof but in the book's hint this transitivity should be proved by the associativity which proved before. I can't find the required proof either. Any help will be greatly appreciated.

ps. Moreover, in the next section another definition of $\mathbb{N}$ appears as:

Given a set $N$ and a map $S:N\rightarrow N$, such that

a) $1\notin S(N)$;

b) $S$ is injective;

c) The set $N$ is well-ordered, that is, for any non-empty subset $E$ of $N$, there exists $m\in E$, $\forall n\in E(m\le n)$. The $<$ definition is the same as above.

In this case it is also asked to prove the transitivity of $<$, as well as $N=\mathbb{N}$. This also confuse me since I can't tell the difference between this two definitions, and I think the prove to things like "among $a<b, b<a, a=b$ exactly one is correct" and "1 is the minimal number in $N$" is the same as before. Please help. Thanks in advance.

  • $\begingroup$ Nitpicking... I assume that "your" $\mathbb N$ will start from $1$; otherwise, the def $a < b$ iff $b=S^k(a)$ for some $k$ will amounts to defining $\le$. $\endgroup$ – Mauro ALLEGRANZA Sep 29 '16 at 13:27
  • $\begingroup$ Have you proved (or already available) the fact that $S^k(a)=a + k$ ? $\endgroup$ – Mauro ALLEGRANZA Sep 29 '16 at 13:28
  • $\begingroup$ @MauroALLEGRANZA yes $\mathbb{N}$ start from 1 and $S^k(a)=a+k$ has not proved yet; only the definition of addition and the associativity, commutivity is available. $\endgroup$ – Yiyi Rao Sep 29 '16 at 13:32
  • $\begingroup$ If so, you can use it in the step from $c=S^l(b)=S^l[S^k(a)]$ to $S^{l+k}(a)$. $\endgroup$ – Mauro ALLEGRANZA Sep 29 '16 at 13:33
  • $\begingroup$ @MauroALLEGRANZA addition defined as a map $\mathbb{N}^2 \rightarrow \mathbb{N}$ with $n+1=S(n)$ and $n+S(m)=S(n+m)$. $\endgroup$ – Yiyi Rao Sep 29 '16 at 13:39

Long comment

From : $a < b$ and $b < c$, we have :

$b=S^k(a)$ and $c=S^l(b)$.

By substitution : $c=S^l[S^k(a)]$.

Now we need addition; $S(a)=a+1$, form first axiom for addition and from the hypotheses : $S^n(a)=a+n$ we have : $S^{n+1}(a)=S[S^n(a)]=S[(a+n)]=(a+n)+1$.

By asociativity : $(a+n)+1=a+(n+1)$ and thus we conclude with :


"Cooking them" together, we have :

$S(a)=a+1$ and : if $S^n(a)=a+n$, then $S^{n+1}(a)=a+(n+1)$.

By Induction we conclude with:

$S^k(a)=a+k$, for any $k$.

Going back to : $c=S^l[S^k(a)]$, we have :


and we have proved that : $a < c$.


First, you will need to prove the lemma that you are using, namely that every natural number can be written as $S^k(0)$ for some $k \geq 0$. This is a very simple proof by induction.

Next, consider three arbitrary numbers, $a$, $b$ and $c$, for which we know that $a < b$ and $b < c$. We must now show that $a < c$. From the above lemma, we have $a = S^k(0)$, $b = S^l(0)$ and $c = S^m(0)$ for some $k,l,m \geq 0$.

Since $a < b$, we have $b = S^{n_b+k)}(0)$. And since $b < c$, we have $c = S^{n_c+l}(0)$. This implies that $c = S^{n_c+(n_b+k)}(0) = S^{(n_c+_b)+k}(0)$. This is where associativity of addition is needed.

Since we now know that $c = S^{(n_c+n_b)+k}(0) = S^{n_c+n_b}(S^k(0)) = S^{n_c+n_b}(a)$, we conclude that $a < c$.


Your Answer

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

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