# Prove the transitivity of $<$ relation in natural numbers using the classical definition and the associativity of addition

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.

• 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$. – Mauro ALLEGRANZA Sep 29 '16 at 13:27
• Have you proved (or already available) the fact that $S^k(a)=a + k$ ? – Mauro ALLEGRANZA Sep 29 '16 at 13:28
• @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. – Yiyi Rao Sep 29 '16 at 13:32
• If so, you can use it in the step from $c=S^l(b)=S^l[S^k(a)]$ to $S^{l+k}(a)$. – Mauro ALLEGRANZA Sep 29 '16 at 13:33
• @MauroALLEGRANZA addition defined as a map $\mathbb{N}^2 \rightarrow \mathbb{N}$ with $n+1=S(n)$ and $n+S(m)=S(n+m)$. – Yiyi Rao Sep 29 '16 at 13:39

## 2 Answers

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 :

$S^{n+1}(a)=a+(n+1)$.

"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 :

$c=S^l[a+k]=(a+k)+l=a+(k+l)=S^{k+l}(a)$

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