Number Theory: An Introduction to Mathematics

1 Natural Numbers 9

Proposition 3Any nonempty subset M ofNhas a least element.

Proof Assume that some nonempty subsetMofNdoes not have a least element.
Then 1∈/M, since 1 is the least element ofN.LetLbe the set of alll∈Nsuch that
l<mfor everym∈M.ThenLandMare disjoint and 1∈L.Ifl∈L,thenS(l)≤m
for everym∈M.SinceMdoes not have a least element, it follows thatS(l)/∈M.
ThusS(l)<mfor everym∈M,andsoS(l)∈L. Hence, by(N3),L=N.Since
L∩M=∅, this is a contradiction.

The method ofproof by inductionis a direct consequence of the axioms definingN.
Suppose that with eachn∈Nthere is associated a propositionPn. To show thatPnis
true for everyn∈N, we need only show thatP 1 is true and thatPn+ 1 is true ifPnis
true.
Proposition 3 provides an alternative approach. To show thatPnis true for every
n∈N, we need only show that ifPmis false for somem,thenPlis false for some
l<m. For then the set of alln∈Nfor whichPnis false has no least element and
consequently is empty.
For anyn ∈N, we denote byInthe set of allm∈Nsuch thatm ≤n. Thus
I 1 ={ 1 }andS(n)/∈In. It is easily seen that

IS(n)=In∪{S(n)}.

Also, for anyp∈IS(n), there exists a bijective mapfpofInontoIS(n)\{p}.For,if

p=S(n)we can takefpto be the identity map onIn,andifp∈Inwe can takefpto

be the map defined by

fp(p)=S(n),fp(m)=m ifm∈In\{p}.

Proposition 4For any m,n∈N,ifamap f:Im→Inis injective and f(Im)=In,

then m<n.

Proof The result certainly holds whenm=1, sinceI 1 ={ 1 }.LetMbe the set of

allm∈Nfor which the result holds. We need only show that ifm∈M,thenalso

S(m)∈M.

Let f:IS(m) → Inbe an injective map such that f(IS(m))= Inand choose

p∈In\f(IS(m)). The restrictiongofftoImis also injective andg(Im)=In.Since

m∈M, it follows thatm<n. AssumeS(m)=n. Then there exists a bijective map

gpofIS(m)\{p}ontoIm. The composite maph=gp◦fmapsIS(m)intoImand is

injective. Sincem∈M,wemusthaveh(Im)=Im.But,sinceh(S(m))∈Imandh

is injective, this is a contradiction. HenceS(m)<nand, since this holds for every

f,S(m)∈M. 

Proposition 5For any m,n∈N,ifamap f:Im→Inis not injective and f(Im)=

In,thenm>n.

Proof The result holds vacuously whenm=1, since any mapf:I 1 →Inis injec-

tive. LetMbe the set of allm∈Nfor which the result holds. We need only show that

ifm∈M,thenalsoS(m)∈M.