1 Natural Numbers 5unique and equal. Thus, for any bijective mapf:A→B, there is a uniqueinverse
mapf−^1 :B→Asuch thatf−^1 ◦f=iAandf◦f−^1 =iB.
Iff:A→Bandg:B→Care both bijective maps, theng◦f:A→Cis also
bijective and
(g◦f)−^1 =f−^1 ◦g−^1.1 NaturalNumbers............................................
The natural numbers are the numbers usually denoted by 1, 2 , 3 , 4 , 5 ,....However,
other notations are also used, e.g. for the chapters of this book. Although one notation
may have considerable practical advantagesover another, it is the properties of the
natural numbers which are basic.
The following system of axioms for the natural numbers was essentially given by
Dedekind (1888), although it is usually attributed to Peano (1889):
The natural numbers are the elements of a setN, with a distinguished element 1
(one)and map S:N→N,such that
(N1)S is injective,i.e.if m,n∈Nand m=n,then S(m)=S(n);
(N2) 1 ∈/S(N);
(N3)if M⊆N,1∈M and S(M)⊆M,then M=N.
The elementS(n)ofNis called thesuccessorofn. The axioms are satisfied by
{ 1 , 2 , 3 ,...}if we takeS(n)to be the element immediately following the elementn.
It follows readily from the axioms that 1 is the only element ofNwhich is not in
S(N).For,ifM=S(N)∪{ 1 },thenM⊆N,1∈MandS(M)⊆M. Hence, by(N3),
M=N.
It also follows from the axioms thatS(n)=nfor everyn∈N.ForletMbe the
set of alln∈Nsuch thatS(n)=n.By(N2),1∈M.Ifn∈Mandn′=S(n)then, by
(N1),S(n′)=n′. ThusS(M)⊆Mand hence, by(N3),M=N.
The axioms(N1)–(N3)actually determineNup to ‘isomorphism’. We will deduce
this as a corollary of the following generalrecursion theorem:
Proposition 1Given a set A, an element a 1 of A and a map T:A→A, there exists
exactly one mapφ:N→A such thatφ( 1 )=a 1 and
φ(S(n))=Tφ(n) for every n∈N.Proof We show first that there is at most one map with the required properties. Letφ 1
andφ 2 be two such maps, and letMbe the set of alln∈Nsuch that
φ 1 (n)=φ 2 (n).Evidently 1∈M.Ifn∈M,thenalsoS(n)∈M,since
φ 1 (S(n))=Tφ 1 (n)=Tφ 2 (n)=φ 2 (S(n)).Hence, by(N3),M=N.Thatis,φ 1 =φ 2.