Number Theory: An Introduction to Mathematics

8 I The Expanding Universe of Numbers

We show next how a relation of order may be defined on the setN.Forany

m,n∈N, we say thatmislessthann, and writem<n,if

m+m′=n for somem′∈N.

Evidentlym<S(m)for everym∈N,sinceS(m)=m+1. Also, ifm<n,then

eitherS(m)=norS(m)<n. For supposem+m′=n.Ifm′=1, thenS(m)=n.If

m′=1, thenm′=m′′+1forsomem′′∈Nand

S(m)+m′′=(m+ 1 )+m′′=m+( 1 +m′′)=m+m′=n.

Again, ifn=1, then 1<n, since the set consisting of 1 and alln∈Nsuch that

1 <ncontains 1 and containsS(n)if it containsn.

It will now be shown that the relation ‘<’ induces atotal orderonN,whichis

compatible with both addition and multiplication:for all a,b,c∈N,

(O1)if a<b and b<c,then a<c; (transitive law)

(O2)one and only one of the following alternatives holds:

a<b,a=b,b<a; (law of trichotomy)

(O3)a+c<b+c if and only if a<b;

(O4)ac<bc if and only if a<b.

The relation(O1)follows directly from the associative law for addition. We now

prove(O2).Ifa<bthen, for somea′∈N,

b=a+a′=a′+a=a.

Together with(O1), this shows that at most one of the three alternatives in(O2)holds.
For a givena∈N,letMbe the set of allb∈Nsuch that at least one of the three
alternatives in(O2)holds. Then 1∈ M,since1<aifa=1. Suppose now that
b∈M.Ifa=b,thena<S(b).Ifa<b, then againa<S(b),by(O1).Ifb<a,
then eitherS(b)=aorS(b)<a. Hence alsoS(b)∈ M. Consequently, by(N3),
M=N. This completes the proof of(O2).
It follows from the associative and commutative laws for addition that, ifa<b,
thena+c<b+c. On the other hand, by using also the cancellation law we see that
ifa+c<b+c,thena<b.
It follows from the distributive law that, ifa<b,thenac<bc. Finally, suppose
ac<bc.Thena=band hence, by(O2), eithera<borb<a.Sinceb<awould
implybc<ac, by what we have just proved, we must actually havea<b.
The law of trichotomy(O2)implies that, for givenm,n∈N, the equation

m+x=n

has a solutionx∈Nonly ifm<n.
As customary, we writea ≤bto denote eithera <bora =b. Also, it is
sometimes convenient to writeb>ainstead ofa<b,andb≥ainstead ofa≤b.
A subsetMofNis said to have aleast element m′ifm′∈Mandm′≤mfor
everym∈M. The least elementm′is uniquely determined, if it exists, by(O2).By
what we have already proved, 1 is the least element ofN.