Recursive Number Theory Explained
Recursive Number Theory Explained
1
UDIES IN LOGIC
AND THE
FOUNDATIONS OF MATHEMATICS
L. E. J. B R O U W E R / E. W. B E T H / A. H E Y T I N G
EDITORS
Recursive
Number
R. L. GOODSTEIN
R. L. GOODSTEIN
L. E. J. B R O U W E R Professor of .tlcthema&ics
E. W. B E T M Linioersi<y o f Leicestcr
A. H E Y T I N G
N O R T H - H O L L A N D P U B L I S H I N G COMPANY
AMSTERDAM
The nature of niimbers. .%rithinetic- antl tlie gRme of chess. I>t,fini-
tion of counting. Eiolution o f the concept of 5 forriiul system.
C H A P T E R.I . . . . . . . . . . . . . . . . . . . . . . . . .
The arithmet,ical operations. Deíinition b - itertition und recursion.
Contracted notatiori. Single and niultiple rrc.ur.~ii>~is.
C-R 111 . . . . . . . . . . . . . . . . . . . . . . . . .
The propositional calculus. Propositional functions. The limited
universal, existential and minimal operators A:, e,
and LE.Mathe-
metical induction. Tlie counting operator S:.
EXAVPLESI V . . . . . . . . . . . . . . . . . . . . . . . . .
CHAPTERVI . . . . . . . . . . . . . . . . . . . . . . . . .
Reductions to primitive recursion. Course-of-values recursion.
Recursion with parameter substitution. Simultaneous recursio~w.
Generalised induction schemata. Permutstion.
W COSTENTS
"What is it that all collectioiis of seven objects llave in common?" iii the follo~~ing way. We define the property of beirig ail empty
-4 good may of makiii? proreas with a question of this kind is t o collectioii as the property of not being identical with oneself. and
nsk oiwselves "Hom do \\-e know tliat a collection has severi then the number zero is defined as the poperty of beiiig similar to
ilienibers?" because tlie aiiswer t o thi.; cjiiestion shoiild certainly the einpcu collection. S e s t me clefine the standard unit coUection
briiig to liglit sometliiiig nliich collcctions of seven objects sliare as the collection mhose only member is the niiniber zero, and tlie
iii coinmoii. An obrious iiiisxer is that \ve find out tlie number of riumber one is defiiied as the property of being similar to the unit
a collection by co?t~ztin!/tlie collectioii biit tliis ansmer does iiot collectioii. Then the standard pnit is talcen to be tlie collection
seeni to lielp us becaiise, \rlieii \ve courit a collection, me appear to m-hose merribers are the numbers zero nnd uriity and the number
cio no more thaii '1:tl)í-1' c:rcli ;iieriibt>r of tlie collection mitli ;L trro is defined as the property of bniri~similar to tlie standard pair,
i:iini;>er. (Think of a l i ~ i l \o l Uoltiitrsriui::Scririg off.) I t Flcnrly dnes rintl so oii. This is. iii effect. tlie de!i~ii:ion of niirnber which mas
i:ot provide a definition of iiuiiiber to say tliat iiurnber is a property discovered by Frege iii 1SS-k aiid. indepeiiciently, by Russell in
of a collection which is found by assigning numbers t o the members 1904. It cnnnot, homever, be acccnted as a coniplete aiismer to tlie
of tlie collection. problelii of the iiatnre of number.~-4ccordiiiq to the definition,
iiumber is a similarity relatioii betwecn collc.ctions in mhich each
The Frege-Russell Definition element of orie collection is made to correspont7 to a certain elernent
To label each meniber of a collection with a number, as we seem of tlie other. and vice-versa. Tiie ~realíriessin tlie definition lies in
to do in counting, is in effect to set up a correspondence between this notioii of correspondence. Hov; do \\-e know vhen tn-o elements
the members of two r~111ectioiis.the objects to be counted and tlie correspond? Tlie cups and saucers in a collectio:i of cups standing
natural niimbers. Iii counting, for esample, a collection of seven iii their saucers have an obvious correspondence, but mhat is the
objects, we set up a correspondence between the objects counted correspondence betmeen. say, the planets and the JIuses? It is
and the numbers from one to seven. Each object is assigned a no use saying that eTen if there is no patent correspondence
unique number and eacli number (from one t o seven) is assigned bet~veenthe planets and the Iluses, \re can easily establish one,
t o some object of the collection. If we say that two collections are for how do we h o w this, and, ~ h a ist more important, what sort
simikr when each has a unique associate in the other, then counting of correspondence do me allow? I n deñning number in terms of
a collectioii may be said t o determine a collection of numbers similarity me have merely replaced the elusive concept of number
similar t o the collection counted. Since similarity is a transitive by the equally elusive concept of correspondence.
property, that is to say, two collections are similar if each of them
is similar t o a third, it follows that in similarity we may have Xumber and numeral
found the property, common t o all collections of the same number, Some matliematicians have attempted to escape the difficulty
for which we have been looking, and since similarity itself is in defining numbers, by identifying numbers n i t h numerals. The
deñned without referente t o number it is certainly eligible t o serve number one is identified with the numeral 1, the number two
in a definition of nirmber. To complete the definition we need only with the numeral 11, the number three with 11 1, and so on. But
t o specify certain standard collections of numbers one, two, three, this attempt fails as soon as one perceives that the properties of
and so on; a collection is then said t o have a certain number o d y numerals are not the properties of numbers. Xumerals may be
if i t is similar to the standard collection of that number. The blue or red, printed or handwritten, lost and found, but it makes
numbers thernselves may be made to provide the requíred standards no sense t o ascribe these properties t o numbers, and, conversely,
numbers may be even or odd. prime or composite but these are
iiot properties of numerals. A more sophisticated version of this Anthmetic and the Game of Chess
attempt t o d e h e numbers iii terms of numerals, makes niimbers, Tlie game of chess, as has often beeii ohserved, affords an escelleiit
not the same thing as, but the nnmes of the numerals ; tliis escapes paralle] with niathematics (or. for ~ l i a tmatter. witli language
thc absurdities mhich arise in attempting to ide~ltifynumber and itself). To the numerals correspond the cliess pieces, and to the
numeral but it leads t o the eqiially absurd conclusion that some operations of arithmetic, the riiox-es of the game. But tlie paralle1
one notation is the quintessence of number. For if numbers are is even closer thari this, for to tlie problem of defiiung number
tlie names of numerals then we must decide whicli tiumerals theg corresponds tlie proble~nof defining the entities of tlie game. If
name; we cannot accept the number ten for iiistance as botli the \Te ask oiirselves the questiori "TVliat is the king of cliess?" me
name of the roman numeral and the arabic .numeral. , h d if it is finct precisely tlie same difficiilties nrise in trying to h d an ansxver
said tliat tlie number ten is the name of all the iiunierala ten then whicli we met in oiir consideration of tlie problem of clehing the
we reach the absurd concliision that tlie meaning of a number word concept of iiiimber. Certainly the king of chess, mhose moves tlie
changes with each notational innovation. rules of tlie game prescribe, is not the piece of characteristic shape
The antithesis of "number" and "numeral" is oiie which is n-hich we cal2 the kiiig, just as a numeral is not a number, since
bommon in language, and perhaps its most familiar iiistance is to aiiu other object. a matchsticlr or n piece of coal. mould serve as
be found in the pair of terms "proposition" and "sentence". The me11 to play the king in any gane. Instead of the question "Wliat
sentence is some pliysical representation of the proposition, but is tlie king of chess?" let us ask "TVhat makes a particular piece
cannot be identified ~ v i t hthe proposition sirice di£ferent sentences in the game the king piece?" Clearly it is not the shape of the
(in different languages, for instance) may express the same proposi- piece or its size, since either of these can be changed a t will. What
tion. If, however, \ve attempt to say just what it is that the sentences constitute a piece king are its mores. That piece is king which has
express we find that the concept of proposition is just as difficult the king's moves. And the king of chess itself? The king of chess
to characterise as the concept of number. It is sometimes held is simply one of the parts which the pieces play in a game of chess,
that the proposition is something in our minds, by contrast with just as King L a r is a part in a drama of Shakespeare's; tlie actor
the sentence, which belongs t o the externa1 morld, but if this who plays the King is King in rirtue of the part which he takes,
means that a proposition is some sort of mental image then it is the sentences he speaks and the actioiis he makes, (and not simply
just anotlier instance of the confusion of a proposition with a because he is dressed as b g ) and the piece on the chess board
sentence, for whatever may be in our minds, whether it be a which plays the king-role in the game is the piece which makes
thought in words, or a picture, or even some more or less amorphous the king's moves.
sensation, is a representation of the proposition, differing from the Here a t last we find the answer to the problem of the nature -
written or spoken word only because it is not a communication. of numbers. \Ve see, first, that for an understanding of the meaning
I n the same way we see that the view that number is indefmable, of numbers xve inust look to the 'game' nrhich numbers play, that
being something which we know by our intuition, again confuses is to arithmetic. The numbers. one, two, tliree, and so on. are
number with numeral, that is confuses number with one of its characters in tlie game of arithmetic, tlie pieces which play these
representations. characters are tlie numerals and what makes a sign the numeral
of a particular number is the part which it plays, or as me niay
say iii a form of ~vordsmore suitable t o the conteirt. what constitute
a sigil t!ie sign of a particular niimber are tlie trrr?asformation mtles + ".
" x + 1 S 1 - 1", ''O 11 7 1 1 the last of whicll is a numeral.
of tlie sisil. I t fouo~vs,therefure, that tiie OiJECT OF OUR STODY IS This new sign \ve cal1 a 'numeral variable'. Tlie rules permitting
SOT NOSIBEP. ITSELF BCT TIIE TI¿-tSSI:OCJIATIOX RrLES OF THE
the siibstitution of " x l l " or '.Oe' for "x" iii effect allow the
r r - i \ i m n SIGXS,aiid in the cliapters \1 liicli foilo\i* me sliall have substitution of nny nxmernl for x ; the object of tlie formidation
iio fi,rtlicr occasion to refer to the iiiinihcr c o i ~ c ~ pBut
t . jiist as the n-e have adopted is that it scrres to define tlie concept of nny
rii1c.- of clieus are cwreritly forniulated i ~ terrus
i of the entities of numeral and the coricept of a nzo?1erul t.nri«ble siinidtaneously.
CIICLL~S. SO tliat we say, for iristtziice, the kiiig of chess inoves only I n the sequel, not oidy the lcttci. .c. hut otlier letters, too. will be
o n e scluare a t a time (escept iii castli~ig).iristr;xrl of tlie completely used as numeral variables.
tqi~ivalentformulatioii '%he piece p1;iyiri~tl:c part of king (or Tlie numeral formed by n~itiiigsome iiiinieral for -.z" iii ..x-L1"
>iliiply tlie kiiig-piece) is inoved oiily orie arii:ti.re : ~ ta tinie (exce@ is called the svcces.sor of that iiuii~er;il.For iiistance, n ~ i t i n g
iii c,is¿liiig)'' so we shall conti~iiie,iii piirely descriptil-e passages, "O+ 1 ; 1" for "x" in "x; 1" n-e obtain ..O - 1 4 1 - l " , tlie successor
to fjrniiilate the operations of aritlimetic in terms of aritlimetical of "O+ l L 1". For this reason .'.zL1" is called the (sign of the) .
riititivs iristead of arithmetical signs. For instance, \ve niay speak successor function. The definite article is somewhat niisleading,
*of "ihe sii~iiof the iiumbers two and tlu-ee" ratlier than confine however, since we maj- mite. in place of .t., a11y other letter mhich
'oi!rselres to tlie object formulation "2+3", mhere + is the sign is being used as a numeral variable : in a system iii mhicli x, y and z
ltiiose role in arithmetic is what is called addition, and ''2" and are all numeral variables, each of "x- 1". "y- 1". .-z+ 1" is a sign
"::" are niimerals ~vhoseroles are t h o h ~of tlie numbers two and of the successor fiinction. Nevertheless we shall tallí of the successor
t!ree. To put it another way. in defiiiing the part played by a function, the uniqueness ir1 qiiestion heiiig tlie uniqueness of tlie
1
si-ii 1iPe g ,in aritlimetic, we shali say that what we are defining sign which results when we m i t e some definite numeral for trhe
is tlic suiu function, but the dehition itself will refer only t o rariable, be it denoted by z. y or :.
operations for transforming expressions which contain the sign f. For purposes of standardisatioii of notatioii we sliaii have
occasion to introduce, insteaci of the 'alphabet' "O", "1" and "+ "
Sumber Variables for writing numerals, the 'alphabet' "O". '.S" iii which the numerals
Tlie paiallel between chess and arithmetic breaks down when become "O", "SO". "SSO", "SSSO" a i ~ dso 011. 111 this notation the
wc contrnst the predetermined set of pieces in the game of chess sign of the successor function is ..SxY'and the transformation rules
n-ith the licence granted to arithmetic t o construct numerals a t for a numeral variable x are (i) S r may be mitten for x , (ii) O may
:vill. I n tliis respect arithmetic more closely resembles a l a n g u q e be written for s.
liich places no h i t , in principie, upon the length of its words. Another notation in current use employs 'cx'" for the successor
-1familiar notation for numerals expresses them as ~vordsspelt fiinctíon. so that the numerals are vrrítten "O", ..Of", "O"", "0'""
v.-itii the 'alphabet7 "O", "1" and "+"; each 'word' has an initial and so on.
'.O" followed by a siiccession of pairs "+ 1". Thus, for instance, we
forrii in tufn '-O", "0 + l", '<O+ 1+ l", "O + 1 + 1+ 1". The forniation Definition of Counting
of nunierals may be fztlly characteriscd hy means of two operations, Il'o theory of tlie natural numbers is complete mhich cloes not
as f~llows.TT'e estend the alphabet by the introdiiction of a new also take into account the part which niimbers play outside
sijn, '.x", aiid form 'words' by writing either "O" or "xf 1" for arithmetic. I t is not only a propertj- of the number nine tliat it
'.x": for example me may form in turn, "x". "xf l", "x+ 1-k l", is a square but also that it is the number of tlie planets. and this
latter property is not a consequence simply of the laws of arithmetic. and one is two". "two and one is three", "tliree and one is fourW
According t o the Frege-Russell dehition of number, tlie number and so on. It is the recitation of these rules (in an abbreviated form
of a collection is found by testing i t for similarity with the standard in which each 'and one' is omitted, or replaced by pointing to,
unit, pair, trio, and so on, in turn, this testing being carried out or touching, the object counted) mhich gives rise t o the illnsion
by the process of counting, biit as me llave proposed a definition that in counting we are associating a number witli each of the
of number mhich does iiot rest upon tlie iindeñned concept of a elements counted, mhereas me are in fact making a trarlslation
similarity correspondencc we cannot nccept counting, in the from the notation in which tlie number signs are "one", "one and
Frege-Russell sense, as a nieans of fincling tlie nurnber of a class, one", "one and one aiid one", and so on, to the notation in mhich
without readmitting this undefined concept. Tliere is, however, the signs are "one". "two". "three", and so on. The true nature
an entirely different interpretatioii of the pi-ocess of cóunting, of counting is perhaps most clearly brought out if me re-introduce
which makes counting arailable to us as a means of recoraing the.. the older process of making a tally. 3Iaking a tally of a collection
number of a collection. without transcending tlie limitatioii we consists in some formalised representation of the elements of the
imposed iipon ourselves of expressing tlie properties of numbers collection, say by means of dashes on a sheet of paper, so that in
in ternis of tlie transformation riiles of the iiiimber signs. We making a tally we are copging a number sign in some standard
Jtart by separating tivo distiiict stages in the process of eo~inting. riotatiori - finding the number of the collection, by treating it
The k s t of tliese is m-liat we shall cal1 "using a collection as a as a number sigii and copying this sign. Thus a tally of the planets
numeral" mhich consists in overlookiilg the individual 'idio- consists in the row of dashes
syncrasies' of the elements of the collection and regarding them as
being all alike (biit not identical) for the purpose in liand. This is
simply a (perhaps rather extreme) form of a treatment of signs If we now proceed to traiisform this sign by means of the trans-
familiar in all acts of reading, writing or speaking; the letters "a" formation r d e s 11=2, 11=3, 31=4, 41=5, 51=6, 6 1 = 7 , 7 1 ~ 8 ,
on a printed page, for instante, have their several differences and, 81=9weobtaininturn111111111=21111111=3111111=411111=
subject t o sufficiently close scrutiny, are as different as say the = 51111 = 6111= 71 1= S1 = 9, which completes the transformation.
soldiers in a platoon, but for the purposes of reading me ignore I n counting as we teach it today, the processes of tally making
these differences aild treat the vnrious a's as being the same sign. and sign tzansformation are carried out simdtaneously, thus
And SO too, in speaking, we treat as the same a variety of slightly avoiding the repeated copying of the 'tail' of the number sign in
differeiit sounds. I n a differerit contest, signs which we would transforming to an arabic numeral. It is important t o realise that
accept as the same for reading purposes, are carefully distingiiished, counting does not discover the number of a collection but transfo~ms
as, for esample, when we test the quality of printing. The process the numeral which the collecticun itself instances from one notation
of overlooking some differences, but not others, is fundamental in to another. To say that any collection has a number is just to
language; it is tlie process by mhich ive subsume objects with a say that any collection may be used as a number sign.
'family likeness' under a generic name and tlie process ~ ~ 1 i i c h
makes possible the use in language of universal \trords. Without it, Formalisation of Counting
the concept of tlie number of a class could never have arisen. The Counting may be formalised in a system of signs by formulating
second stage ili the process of counting consists in a transformation the transformation rules of a counting operator "X". JVe represent
from one number notation to another by means of the rules "one t,he objects in the collections t o be counted by letters a: b: c, ....
10 ISTRODvCTION INTRODUCTIOS
and collections by conju~lctionslike a S: b, n S: ZJ LP: C ; a single considera1)le developmerit during tlie past centiiry. 3uclid7s
object being regarded also a collection. The letter 1 we use as a interition iri the "Ele~nents" was to decliice the 1vliole bod- of
variable for an object. that is. ii letter for which any object may geometrical lmowledge of his time from tt few self crideiit trutlls
; capital letter L berves as n variable for a collection
be n ~ i t t e nthe (calied asioms) by purely logical reasoning. Euclid did not. Iiowerer.
2nd maj-. in any contest. be rcl~lncc(1by a alletiiiite coilection or specify the naturc of 'logical rea?oiiiriq' nrid tlie tirst attenipt to
by "1; S: 1". The nunier~lsof tlie systcin are tlic signs (witliout X) 1 do so was made by Ckorge BooIe. iii Is17. iii Iiis JInfho)inficnl
obtairied from l. x ariti the succrssor furiction n:-- 1 hy sribstitution. dnnlysis o/ Lqic. Boole coristriicted a ;:.-rnbolíc lurigiinge. in ~vliicli
Thcn Tre define
i the 'laws of tliought'. formiilater! iis axioriis, niny be sti~cliedbu
l
Y(l)=l, S(L&l)=S(L)--l. mathematical tecliniqiies. Iii thc cnri~;lletctlcx-clo1)nicnt of the
'Lliebe equations sufice to determiiic tlie iiiiiiiber of any c~llectionl notion a forinal systcni is ari a-icrilhl:icr. of slgnc qcbpa:.nted into
various categories. tlieir usage it~nilr! 1 ; ~\:irious con\-eiitioiis (tlie
For instance, substituting "a" for tlic variable-sign "l", in the
k s t . \ve obtain N ( a ) = 1, and tlieii, substitiiting "o" for "L" asionis and transformatioii rules) tiie objvct of the systeni being
and "h" for "l" in tlie secoiid. \ve obtaiii to arraiige sequences of formiiIne (rhicii are tliemselres svqiiences
of signs mith certuin >pecified forniation r.iilcs) iii certniri relatiori-
! N ( a S: b) = N ( n )+ 1 ships to one anothcr to forin a particular pattern callec1 proof.
and so. X ( n & b) = 1 -L 1. I A formal systeni ninu contaiii l,otli !ii,tthc.rnatical nrici logical
Y P S ~ siibstituting
, "a & h" for "L" and "c" for "1" me find 1 s i p s (the distinctiori is an arbitrar'- ori:?). aiitl nintheiiintical and
N(a & O &c)=X(a & b)+1=1-~-1+1, logical asionis; its essential featurc, q ~ 1 foirnal
, systeni. is that its
and so on. operation does not presuppose any !íiiu:r letige of the significance
' I T c observe that the definition of X(L) is by recursion, that is
of the signs of the system thali is givcii hy the nsiomq aiicl trans-
to say. X ( L ) is not simply an abbreviation for some other expres- formation rules. Tiie mathematical a~ioilisare no loiiger "self
sion, as, fbr instante, when we define 2 = 1+ 1, the sign "2" may evident truths" biit arbitrary initinl ;io.;itions in a ,rran;c. and tlie
be replaced by "1 + 1" for which it is merely an abbreviation, but logical aasioms espress. not the "la-\\-=of tlioiig!it" but arbitrary
X ( L ) is determined only step by step, by introducing the members conrentions for the use of the logical .igns.
of tlie class t o be counted one a t a time (or shedding them one a t I n the formal s ~ s t e n mitii
i ~rhichn-e :iiall first be coiicerned in
a time). R'e may express this by saying t l ~ a tfor the variable L, this book, the equation calculus. the or:!y :igils are sigris for functions
S ( L ) itself is undefind, only the result of substituting a definite l aiid numeral variables. and tlie equality sigii. Tiirie are iio asioms
class (lilíe a & b & c) for L being defined by the reciirsive definition. escept tlie introductory equations for function si;ns. and there tri
Tfie recursive definition is, so to speak, a schema or mould from is no appeal t o 'logic7. the operation of tlie sj-steni being specified v
v.-hicii tlie definition (value) of X(a & b & ... & k) may be found
by siibstitution for any particular class a & b & ... & k.
l
siniply by the transformation rules for the mathec?,ztical signs.
It is sho~r-nthat a certain branch of losic is defi?iable in !he equation
u
I calcl~lusand logical signs. and theor?:i?s, are introduced as conre- u
Evolution of the Concept of a Formal System 1 nient nbbr~z.icttionsfor certain f1inctio:is ancl formulae. This brancli w
I n the following chapters we shall set up arithnietic as a formal i of logic is characterised by the fact that it caii assert the ~xistence (Lrí
S Y . S ~ P - B I .Tlie idea of a formal system is one which derives from of a number mith a giren propcrty uiily miien tlie niimber iir
Euclid's presentation of geometry, but the notion has ~indergone question can be found by a specifiahle riomber of trials. m-
Cí
w
w
u
CHAPTER 1
DEFINITIOX BY RECURSIOK
1. Variables
We have already had occasion, in the definition of a numeral.
t o refer to the use of a letter as a sign for a variable. In terms of
two operations
(1) replacing x by x i 1,
(2) replacing x by O,
\ve defined numerals to be tlie signs constructed from x by the
repeated application of tlie operation (1) folioíved by an applicatio~i
of the operation (2). Starting mith the sign x the process of
constructing numerals may be regarded as a process of eliminating
x using only tlie operations (1) and (2). For instance the numeral
O + 1 + 1 + 1 is constructed from x by three applications of operation
(1) follomed by an application of operation (2).
The defining property of a numeral variable x is that it may be
replaced by zero or x + l. Any letter may of course serve as a
numeral variable, but in this chapter only the lett-ers x, y, z and w
will be used. By means of variables we can make general statements
about numbers, statements which hold true when any particular
numeral is substituted for the rariable.
-
1.1 ADDITION
The fundamental operation of arithmetic is ctdclition. Addition
is the operation of joining together two numerals by tlie addition
sign ' + '. For instance, joining the two niimerals O + 1 + 1 + 1 + 1
and O + 1 + 1 we obtain (omitting the introductory part O + in the
- -
second numeral) the numeral O 1+ 1 + 1 + 1 + 1 1 which is calied
the sum of 0 + 1 + 1 + 1 + 1 and O + l + l .
To say tliat addition is the operation of joining together two
numerals is not, homever, a mathematical definition of the operation
--
for \ye llar-e simpli. r<.!;l;l::ctl tlie \\-oi.tlrrtldifion by t'li(' iilidefiiled previous result ; for instarice we pass from ( S + 2 ) + 1 to 7 +
by
tcrm joining. There ar:. ohrio~islyi:ia:iy "aya ill i\-liicll we i~ligllt means of the earlier equatioii 5 - 2 = 7.
joili togetller t r o nul::~:i.;;]s. !,lii oril? <,11eof t l i e ~ eazy5 gires x h a t 1 . 1 1 Addition of tliree or niore nurnerlils is defined iil terms of
wc. iiieaii b ~additioIl.
- -$ clnlIie~iiatic~il tlefinitioii ~f nddition nlust tlie repeated addition of pairs. Tlius f1)r instance n7e define
bt. foriiiiiltitc~Jin ter?ns of :iiimernI variables. niid tlic acldiiion
si(rll 2.. ;ilorle: 110 estr:iiicoiic: elemeiits niay b t introcliiced. A 4 cllild x+ytz=(x-y)-z
hrrt !cai.:;-: :O add by ti:? siriiple coiijiiiictiorl 0f ~iilllierals, for X+Y+Z+ w=((x-y)--z)-w
instnrlce t,o fincl the ~u1l-iof 3 nnd -t lir combines . . . 3 r d . . . . to and so ori. Tliese clefinitioiis. lilíe d~fi:iitioii9.treat the numerals
fOrm . . . . . . 3lld 'col!:!ts th(x (l(:is'. i.c. tra~iforiiis. . . . . .: into 7 .
,
added unsymmetricnlly. Iii dcfiiiitiori -4. x and y are not on the
Lnt,er11. l:J:tTlis to procFi.tl fToriiC, to 7 b;; t,he rcpentecl nddition of 1. *' s a n e footing arid i t is by no menii.; obvious that x+y=y+x.
;ind this fiir :nore eco!iomic:il procpcliirc is the basi:: of the followirig I n A' the three terms x, y, c are addc(1 in that order, and so too
fornial defiriition : in 9". We shall prove in the iiest chapter that the sum of two
I
for numerals are constructed from x by these same substitutions. Repeated addition of the same n u m b ~ ris called multiplication;
And s i d a r l y both x and y in A, may be replaced by any the sums x + x , x + x + x , x + x + x + x , and so on, are denoted
numeral.
SOillustrate t'he application of the transformations A me evaluate
i respectively by 2 - x , 3 . x , 4 . 2 , and so on. the fbst term of the pair
denoting the number of repetitions of the second term. The formal
the sum of 5 and 4. Substituting 5 for x in A, and A,, and 0 , 1, 2, 3, I definition of multiplication is:
in turn for y in A, we obtain O.x=O 3%
(y+ I).x=(y.x)+x M,
5+2=(5+1)+1=6+1=7
5+3=(5+3)+1=7+1=S
Substituting O, 1, 2 and so on in turn for y in & (and using MI) w
we verify in turn
5+4=(5+3)+1=8+1=9. l.x=O+x=x, 2.x=l.x+z=x+-x, 3.z=2-z+x=x+x+x w
Each partial result after the h t is obtained by means of the and so on. w
1 iCí
16 DEFMITION BY RECCRSION ! DEFINITION BY RECTRSION 17
x.y is called the product of x and y ; wheri the cont,est renders so that. taking y = O , 1 , 2 in turn \$-e rerify tliat
the sign free from ambiguity we shall denote the prodiict of x and lx=z, -x = 3 x = x ( 2 2 ) = 8and so on.
y by xy, omitting the dot betmeeii tlie terms. Similarly if x, 5 , %x, ..., are denoted by ,z, ,x, ,x, ... respectively,
1.21 Products of three or more numbers are defiiied in ternis of we may define
prodiicts of pairs. Thus "X = 1 PI
P
cv+i)~=(fl)X p,
3Iultiplication like additioil is a syinmetricsl operation, but the There remains to be defined one more fundamental operatioil
proof of this must also be postponed iintil %e have set up tlle of the arithmetic of natural numbers, namely subtraction, the
necessary proof processes. - . . converse of addition. \Ve introduce first t%e converse of the operation
+ 1 , which we denote by - 1 , m-ith the formal definition
1.3 EXPONE'TTIATION
, Repeated multiplication of tlie same number is cailed exponenti-
ation ; the products x .x, x . x. x; x.s x. x and so on, are denoted
respectively by xl, 23, x3, and so on. the 'indes' denoting the and theil the difference x L y is defined by
number of repetitions of the base. The formal definition of xv is
-.
1 Sum(x. O) = x
sum(x, Sy) = S(Sum(x, y)) .
1
Prod(x: 0) = 0 where B(x, y, z)=Sum(Esp(x. y- 1). z).
11
Prod(x, Sy) = Surn(x, Prod(x, y)) -\lore specifically thc scheme R is called recursion in y ; the
Exp(x. O) = 1 secoiid variable x ici called a parameter of the scheme. Xo limit is
!1 placed on the nunibvr of parameters, so t!lat for instance the
Es<p(x,Sy) = Prod(x, Exp(x, y))
sclienie
Tet(x, 0) = 1
T
Tet(x, Sy) = Exp(x, Tet(x, y))
Dif(x, O) =x
6
Dif(x, Sy) = P(Dif(x, y)) is also called recursion (in x).
The variables in a function sign. like x, y, z in F(x, y, z ) are
¡vilere P(x) is x- 1 defined by
sometimes called the arguments of the function. If a (unique)
numeral f can be fou:id such that F(a, b, ...) = f where a, b, ...
denote certain definite numerals then f is called the calue of the
function F(x, y, ...) for the values a, b, ... of the arguments x, y, ...
Tiie common feature of all the definitions 9 t o S is apparent;
of the function P(x, y, ...). The characteristic property of a function
e:ic!~definition takes the form
F(x, y, ...) defined by recursion is that the value of F(x, y, ...) is
F(x, O) = a(x) determinate for any set of values of the arguments provided that
F(x, Sy)= b(x, F(x, y)) the auxiliary fuiictions in the definition scheme have this property,
for P(0, y, ...) is a known function aild the ralue of P(Sx, y, ...)
~vhereF(x, y) is the functioii defined and a(x), b(x, y) are functions
is determined when the value of F(x, y, ...) is k n o m , since
previously defined or are variables or definite numerals.
F(Sx, y, ...) is espressed in terms of F(x. y? ...) by means of a
Definition scheme 1 is ca,lled iteration; deñnition by iteratioil
function with knon-n values.
20 DEFINITIOS B Y RECURSION
1.6 It \vil1 be seen: in a later cliapter that the introductioii of 1.7 SUBSTIT~~TIOS
additional parameters, as in the scheme R*, is in fact superfluous The simplest operation by which a new function may be con-
and that it suffices to consider only tlie simplest recursive scheme str~ictedfrom giren functions is substitittion. Giren a function of
any number of variables, say a functioii of four variables
P(a, b, c, d ) , and any foilr functions, say A(x. y, i ) , B(x, y. z ) .
C(x. y, z), D(x, 9. z) then a new function F(s.y, s) niay be defined
in whicli there are no parameters a t all. We collect here for futiire by the equation
reference three functions mhich hare an ituportant part to play
in this reduction. These are S i ~ b s t F ( x , y, z ) = P(A(x, y, 2). B(x, y, z ) , C(x, y, z), D(x. y, z)).
The function F so clefined is said to be defined from P, A, B, C.
illt x, Hf x = [x/2] arid R t x='[xlly and D by siibstitutioil in P. For instance in the definition of
- . (-
addition, x+Sy is defined from x l y and S by substitution in Sx.
defined by the recursions
A definition of the kind Subst is also said to be an explicit
(i) A l l ; O = O , A l t S ~ = 1 ~ ~ 4 l t x definition of the function F, by contrast with a recursive deñnition.
po that A l t l = l , A l t 2 = 0 , A l t 3 = 1 and so on; I n an esplicit definition e v e y variable which occurs on the right
(ii) H f 0 = 0 , H f S x = H f x + A l t ~ hand side of the equation must occur also in the nem function oii
so that H f l = O , H f 2 = 1 , H f 3 = 1 , a n d so on, the left, but there may be additional variables oii tlie left-hand side.
that is H f 2 x = H f ( 2 x + l ) = x ;
1 .S THE INITIALFUNCTIONS
(iii) R t O=O, R t S x = R t x + { l ~ p ( x R , t x))
It is often convenient t o be able to express any variable, or
where p(x, y)= ( S y ) 2 ~ S x;
definite numeral, in the form of a function. For this purpose we
thus R t Sx is obtained from R t 1: by adding 1 if Sx is the next introduce a number of special functions. The first of these is the
square after (Rt x)2, and adding O otherwise, i.e. R t x is the zero function Z(x) defined by the equation
greatest number whose square does not exceed X.
1.61 Contracted Notation
This definition could be given recursively in the form
When a function is d e h e d by the simplest recursion
. .
but the explicit definition is indispensible in the sequel. I n addition
its successive values F(1), F(2), F(3), ... , are given by b(O), to the zero f~inctionwe define also the identity function 9 ( x )
bb(O), bbb(O), ... , and it is natural t o denote these by bl(0), b2(0), by the equation
b3(0), ... , so that F(x) may be expressed in the form bz(0), where 9 ( x )= 5.
bO(0)stands for 0. Thus, since x + y is defined by
From the zero function we can obtain any constant function by
x+O=O , x+Sy=S(x+y) substitution in the successor function Sx. For esalnple the fiinctioii
i t follows that z+ 1 =Sx , x + 2 =Sz(x) ,x + 3 =S3x , ... , SO that C(x). wliose value is 2 for any values of x, is d e h e d by
I
z + y may be expressed in the form SY(x)where SO(x)stands for x. l
1.9 SJXGLYRECL~RSXVE
FCXCTIONS I H ( 4 . n. a). - - - define in turn addition. multipIicatioii, esponentiation,
A fuiictioii is said to be si7lqly rccztrsi?~z(or primiti~ereczcrsire) tetration, ... ; for
if it niay be defined from the zero fiinctioii, the siiccessor function H ( 1 , O . <O=a , H ( 1 , 71- 1. a ) = S I i ( i . n. U )
and tlie identity function by substitutioiis and recursions. We l
1iia.y also cspress this definition by aiiying th::..t tlie zero fiinction, so that H ( 1 . n. a ) = a t n . and tliereforp
tlie siiccessor fiinction ar,d the icleiitity fii1;ctiori arc siiigly recursive, H ( 2 , O. u )= O . H ( 2 , n - l . a )= f i ( 2 . n , r l ) - rr
~ i i dfiirtlier that a furictiori is singly recursi\-c if it is defined by
substitutiiig siiigl-j recursive fiiiictioria ir1 n. sin& rrciirsire firrictioii so that H ( 2 , 71. a)=na. aiid helice n-e filid ir] tiirn
or is defiiied by a singlj- recursive sc!ienir cmploying orily siiigly
recursive fitiictioiis. Thiis al1 the fiiiictioris cicfincd iip to t%i? pointd
are siiig!y recursive functions and any fiirictioii fvrriied from thern so that H ( 3 , n , a ) = a"
by siibztitution mil1 be singly recursire.
111 ii sciise which mil1 be made sliarper iii tlie nest chapter a
feeiinire fiiiictioii is totally eliminable, that is to say, when al1 its so that H(4, n. a ) = "a
arpu:iiarit places are filled by definite niimernls the function rnay
arid so on.
be tt~nrisformedinto a single iiiinieral. For the initial functions are
The ecjuations H do not fa11 iinder tlie siiigly ~ ~ c i i r a i vscheme
e R
certcinly cliniuiable, and substitution of eliininable functions in an
since the successors of both n and p are iiivolved. H is an example
eliminable function residts in aii eliminable f~iriction;finally a
of definition by double r~cur,:ion.
function F ( x ) . wliich may contain paranieters, defined in terms of
The general forin of a definition by tlou ble reci~rsionis aa follows :
eliniiiiable functions by a singly recursive scheme, is eliminable
A function G(p. n ) . TI-hich may de;)end also ii~torione or more
aincc F(O)is eliminable and F ( S x ) is eliminable if F ( z ) is eliminable.
parameters, is said to be clefined by doiiblc recur.~ionfroin certain
given functions if
l .1 Uoltl)ly Recursiee Punctions
i
Tlie totslity of arithmetical operations, additioii. multiplication, (?(O, n) is one of the giveii fiiiictions
esl~oiiriitiation,tetration, pentation and so on, may be expressed G(P+-1. O ) = ~ ( P , Q(p. Q)))
by inenris of a single function. If we define a function H ( p , n, a ) i2 G(p+ 1 ' 7 1~)=c(p,
~ n, G ( p ,d[p. n. G ( p - 1. n)]). G ( p T 1, n)),
by the eqii at'lons mhere a(x. y&) . L(x) . c(x, y, z. zc) and cl(x. y. z ) are given functions.
. n ) = S n , H ( 1 , O, a ) = a , H ( 2 , O , a)=O , H ( p + 3 . 0, a ) = 1
E ( ( )n, \Te observe that O(p+ 1, O ) is obtained by siihstitiitiiig a given
I
H (so that H ( p + l , O, a ) = a ( l - p ) + { l ' - ( - - p ) ) ) function for n in G ( p ,n) aiid substitutiiig the result in a gicen
aricl H ( p t 1, n t l . a ) = H ( p , H ( p f 1, n, a ) , a ) fiinction: G ( p- 1. n 1 ) is also obtauled b-j- substituting G ( p 1. n)
in given functions and substituting for n in (;(p. n ) . V e shnll
tlieii t,hc valiie of H ( p , n , (1) is determined for any values of show i n Exanzple 1.9 that the first trro equatio,is tnny be replctcecl
p. ' 1 . ancl ( 7 : for H(O, n , a ) is given, and if H ( p , n, a ) is given for by G(O,n ) = G ( p - 1. O ) = 1.
sci::ie 11 aiicl any n and a then H ( p + 1, n , a ) is definecl by single If the given functions are siiigly reciirsive tlieii tlie equations R2
recursion iii 71. The functions H ( 1 , n , a ) , H(2?n, a ) , H ( 3 , n , a ) , s h o ~thnt for any given valfce of p. the function G(p, n ) is singly
reciirsive in n, for G(0, n ) is given to be singly recursive, aiid if
for some p, G(p, n ) is singly resursive in n, then G(p+ 1, n+ 1 ) is
expressed by singly recursive functions in terms of G(p+ 1, n).
Examples 1
It does not necessarily follow, hon-ever, that G ( p , n ) is a singly
recursive function of n nritli parameter p and we shall subsequently
1. Formulate the reciirsive dehitions of t,he arithmetical processes
show that there are doubly recursive functions which are demon-
strably different from any singly recursive function; in particular of hesation and heptation.
this is true of the doiibly recursive function H ( p , n, a ) defined 1.1 Evaluate Tet ( 2 . 3 ) aiid Pent ( 2 , 3 ) and express Hex (-7. 3)
above (see Péter [ l ] )* as a repeated esponential.
By analogy witli the equations R2 one may readillv define
recursions in three or more variables, but me shall have no occasion8 1.2 If f ( O , n ) = i , f ( p , O ) = p + l a n d ,
to employ more than a double recursion. f ( p + 1: n+ l ) = f ( p , p n ) . f ( p t 1, n),
1.92 From single and multiple recursions we derive the general find the valnes of f(2, n),f(3, n) and f(4, 4).
aotion of a recursive fiinction. A function sajd to be recursive if it 1.3 If y(%) is recursive and f ( O ) = O , f ( x + l ) = ~ ( ~ i l ) .
is singly recursive, or d e h e d by a recursion in any number of
variables with recursive given functioils, or defiiled by substitution prove that f(x) is recursive.
from recursive functions. 1.31 If g ( x ) and h ( x ) are both recursive and if
We shall show that al1 the processes of clmsical arithmetic m u y be f(x)=g(x) for x g 2 .
described by means of recursive functions.
= h ( x ) for x > 2 ,
* The number in square brackets refers to the bibliograplphy. prove that f(x) is recursive.
if F alid G satisfy the same introductory equations is just another We observe that ( 2 . 2 1 ) , ( 2 . 2 5 ) are defining equations of the sum
may of saying that the processes of recursion and substitution function; ( 2 . 2 2 ) is derived from (2.21) by substituting S x for x ;
define unique functions. For instance, the equations x + O =x , ( 2 . 2 4 ) derives from ( 2 . 2 3 ) by substituting x + 0 for x (on the left
x + S y = S ( x + y ) , which introduce the sum function, define this hand side) as is permitted by ( 2 . 2 1 ) : ( 2 . 2 6 ) derires from (2.25)
fuiiction completely, so that any f (z, y ) mhich satisfies the same by substituting S x for x ; ( 2 . 2 8 ) is obtained from (-7.20)and ( 2 . 2 7 ) .
equatioiis, namely f ( x , 0 ) = x , f ( x , S!/)=Sf ( x , y ) , iu jiist another 1 Tlieequations ( 2 . 2 2 ) ,( 2 . 2 4 ) , ( 2 . 2 6 ) and ( 2 . 2 8 ) shom that both S x l y
notation for the same function. and S ( x + y) satisfy the introductory equatioiis
2.11 To illustrate the proof techniqiie, and ir1 preparatiori for
siibsequent applications, me collect together here proofs of the
.
principal properties of tlie functions we introdiiced iii the previous
' so that (2.29) is a proved equation. Substituting x for y and y for x
chapter. I
i ~ i(2.29) we obtain
Properties of the S u m Fz~nction
1 As the first esample of a proof we consider the commiitative
The nest step is the proof of the equ at'ion
property of addition which is espressed by -the equat,ion 1
-.-
9 3 x+y=y+x
the pair of equations
To make it easier to follow we divide the proof into two part,s,
starting witli the proof of the equation O+O=O O+Sx=S(O+x)
Sx+ y=S(x+y) which follow by substitution in (2.21) and ( 2 . 2 5 ) , show tliat the
The proof consists of the nine equations function O + x satisfies the introductory equations
(2.") S(x+Sy)=S(x+Sy)
* l x+y=y+x.
We take as the next example the important equation
(2.25) S ( x + # y ) = S ~ ( +Xy )
(2.29) Sx+y=S(x+ y). which espresses the associative property of addition.
TRE EQI--4TIOS CiLCTLUS
31
and Ss.yiSx=(x.y+y)-Sx
Sirice ( x - y) -i- S
. +- y) z] aiid
((z'i'-
=&
=(z.y-rSx)-y by2.4
=S(.t-.y+x)+ y
(where \ve are using aii abbreviation of the forrn a= b = c to denote -Sf(x.yTxi- y ) by 2.29
the pair of equations a = b, b = c )
=(~.ytx)-A<i,
it follo\v-; tiiat both the functioiis (r- y) -'- z and x k (y+ z) satisfy
thc c~i1u:it;l)iiy(%. y. S:) =Srp(x. y, 2 ) : ahich shows that x.Sy niid x.y-r both satisfy the i n t r o d i i c t ~ r ~
frirtheriilorc (.r + y) -L -x y = r (y - O)
J
-
equations
g>(0,2/)=0 (Asd.. :/) = Y(X,y)
bo t i i ~ tthese fuiictioris also satisfy the ecl~itition 89.
proving 2.59. The equatioiis 2.51. 2.53 show that the functions
y - x and x - y satisfj- the sanie iiitrotiuctory equations, which com-
and so 2.4 is proved. pletes the proof.
1 2.53 If for some f (..L.). f (O)= O a:id f (S;:)= O are provable then
2.5 TRODUCTS f (x)= O is provable. For froiii f : . i r )= o and O.f (x)= O we derive
f (Sx)= O .f (x) aiid since ZSx = i ) . Z x t iierefore f (x) and Z x botli
The commutative propertj- of miiltiplication, which is expressed
satisfy tlie introductory eqiiation.;
by tiic equatioii
xy ='yx y(0)= o . y ( S r )= o.'~(x)
so that f (x)= Z x aiid f (s)
= O i+ provable.
is readily prored ~ v i t hthe help of equations 2.2 and 2.4.
The defining eqiiations of the product yx are
2.6 PROPERTIES O F THE DIFFERENCE FUNCTION
We commence by pro"tig tlie important equation
as in tlie proof of 2.2 me start b y establishing the compaiiioii 5.61 x-y=sx-fy.
equations
From the equations
2-o=x, S x - S 0 = ( . ? 7 ~ ~ 0 ) ~ 1 = s x ~ 1 = x ,
The first of t,hese is proved b y the two equations O -O = 0,SZ. O =X. O and x=Sy=(x'y)- 1 . Sx~SSg=(Sx-ay)- 1
(iristances of the introductory equations of the product), which
in conjunction mith Z(O)=O,ZSx=Zx (mhere Z x is the zero (mhich are instances of tlie introtiuctory equations of the difference
function), show that function) i t follows that .c2y and Sx=Sy both satisfy the intro-
and thence y- y = 0.
-
ZSx=Zx 2 1 folloms O 2 x= O and similarly using Z ( x , y) defined
explicitly by the equation Z ( x , y) = O me may prove 9 (x+ y) = O,
' d
2.831 ( 1 :x)f @ + y )= ( 1 ' x ) f ( y )
is evident, since ( 1 -x)f ( x + y ) and (l'2x)f( y ) both satisfy
We define the positive difference of x ancl ?J
(2, by the equation d o . y ) = f (Y), cp(Sx.y)=Zrp(x, y) 1
1 (y'x) .
) x ,y1 = (2-1-y)+ substituting x L y for x in 2.631 n-e find
It follows that Ix?y1 =1y, xl, and iising 2.61, that
and after multiplying by 1 -Ir, y1 and using the provable
equation ( 1 - ( x - y ) ) { l A J E , y))= ( 1 -Ix, y)), (see Example 2.241),
The only applications of the equalisiilg rules for functions which this becomes
we have made so far have been confined to single recursions.
However, the following proof of the equation 2.65 (~'Ix,Y ] ) /( Y ) = ( ~ ~~ Il x) (f, y j ( x L y ) )-
Substituting x for y and y for x in 2.65: since lx, y1 = ] y ,21, we obtain
requires an application of the rule to a double recursion. \Ve 2.66 (lL1x, 91)f( x ) = ( l-Ix, y])/( x + ( y - x ) )
observe that and so 2.63 folloms by 2.62.
x+(O=x)=x=O+(x~0) Taking f ( x )t o be the identity function Y ( x )= x in 2.63 we have
2.67 (1+, Y ~ ) x ( =~ A I x, !/))Y
SO that x
equations
+
Sy+(Sx'Sy)=Syf
- (x-y)=S(y+(x:y))
(y - x ) and y + ( x y) both satisfy the doubly recursive
a proved equation. Conversely from F = G we derive, by xneans
of F&.F=O, both F-G=O and G-F=O and so lF?G(=O.
Thus we have shown that each of the equntions
IF,GI=O, F=G
muy be deduced from the other.
34 TIIE E Q r A T I O S CALCLZCS
f ( O ) = g(0)
f ( S r )= g(&x)
2.7 -4s a first estiiii;>i of the use of the equivalence of the are ~n-ovable.tiicri tlie eqii.ztioii f (.t.)= (1 is provable; in schematic
1.qiiatioris 1 F, GI = O niitl F =C: \ve prove tlie equalby of , two form
fii:lctioiis f and g whicli are k n o m to satisfy the equatioiis
!(U) = O
f ( O ) = g(0) , f (8s)= g(Sx) . ( 1-'f(x))f(,Cx)=O
tlicrcfore p(x) = Z z , aiid so ~ ( x=)0 , are proved equations, whence, and so if g(x) is defined bj7 the recursion
;)y the previous theorem, f(x)=g(x) is a proved equation. A
gmeralisation of this result is given in example 2.73. ~ ( 0=) 1 , ~ ( S X
=g) ( x ) ( 1 2f ( x ) )
To record the fact that a proof of some equation F = G may be niid if h ( x )= g(6.r) tlien
('Rtnined by combining tlie proofs of one or more equations
-
Ji qi. f2= g2, ... , f k =gk, me m i t e simply
biit h(0)=g(O) (since f(0) = 0 ) and so h(x)=g(x) ;
Thus g(0)= 1, g(Sx)= g(x) and so (by example 2.7304), g(x)= 1,
and therefore 1 = f ( x )= l .
Hence f ( x )= f ( x ) ( l - f ( x ) )= O? using esample 2.1.
\Te shall show later that theorem 2.8 establishes the validity of .
the method of proof known as mathematical induction.
nnd cal1 this a proof schema.
-- 2.9 .Zj, 4 and
THE FCXCTI~SS u,,.
* .~íxltiplyiiiga n equation by a factor is a shorthand way of clescribing the For any function f ( x ) me define
,: .ri\-ation
of an equation ca=cb from the equation a = b ; tliis derivation
is vf couise effected by substitciting .'bu for .'a" on tlie right-liand side
uf t h e equntion ca = cn.
THE EQO.lTIOS CALCULUS 37
so that for any numeral p so that (1-A(?n))A(Sm)=O, and therefore by 2.5, A(m)=O.
I n particular A ( n )= O. that is. ( 1 -g(n))L',(n)=O.
2.92 If for some f (x), g(x)
and lT(p)=f(o).f(l).....f(~)
;
( S n - a ) ( l f ( a ) )g(n)= O
2
with an analogous formulation for thc case of i:iore tliaii -oile aiid ( S n l S m ) ( l -f ( S m ) )g(n) .
parameter. We take for granted tlie coni~aliioil defiiiitions;for
-
By hypothesis C ( m )= O and so ( 1 -T- B ( m ) )C(m)= O ; moreover
the function n.
For any assigned numeral p r e have (1A ( m ) )B ( m )= ( 1 A ( m ) }{ A ( m )= ( 1 117,(m))g(n))= O
nnd so (by eñample 2.47, with IT,(m) for a, f ( S m ) for b and
(Sn~ S m ) g ( nfor
) c),
and ~T(P,
a)=f(O,a ) . f ( l ,n)...:f(p, n )
In using the fiinctions Z,, 17, we take tlie first vnrisbIe iii f to and therefore A ( m )= O , whence A ( n )= O, that is
be the operative variable; to study suclr a siirn as
(1 -27,(n)} g(n)= O .
( 1 - f ( x ) )17,(x)=0.
we introduce ~ ( xa ), by the explicit definition s. a ) = f (a,z ) For {l'f (O))n,(o>={l2f(o)}f(o)=o
+ +
and express f (a, O ) f (a, 1 ) ... + f (a, p ) as Z&p, a).
and ( 1 f ( S x ) }17,(Sx)= (1 f ( S x ) )f ( S x ).q ( x )= 0.
2.91 If for some functions f(z), g(z) the equtttion
is provable, then
-
2.93 I n the following section me require a number of the elementary
properties of the function u ( x )= 1 2 ( 1 x ) which are proved in
Exumples 2.26. I n particular we shall use the equations
&loreover 4 q . r ) )= fle(x) 11% note the following immediate consequerices of the definitions:
3n q
for
Y
e
.(q,(t))) =?(O) ( l L f l r ( n ) ),u,(Sn)= ( 1 -O,(n)) ,uj(n), L)b
3(17,(Sx))= L 4 & ( .~
@)()S 4 O,(n),u,(Sn)= B,(n). S I L m-
so tlist x(U,,(x)) satisfies the saitie introdiictory eqiiatioiis C~Y
17,(z) it.self.
then / ( o )( 1 - ~ , ( s x ) ) ~ , , ( =x )o .
-
Denote e(0)( 1 IIp(Sz))Z7E,(x)by --l(x). theii :
For Y ( X ) 1 = 0 and so ~ ( x'-)1 = 0 wheiice f ( x ) ( e ( x ) 1 ) = O ; but --l(O)=Q(O) ( 1 U , ( l ) )( 1 -O,(O)) = ? ( O ) ( 1 A ? ( ( ) )( 1 U0(1))
= 0. and
f(-t')(l:?(x)) = O and so. by addit,ion, f ( x ) .( ~ ( x 11) ,= 0. -4(Sx)= e ( O ) ( 1 17,(SSx))Z7Rt(~){i(17,(Sx) U,,(SSx)))
2.!):34 I j ~ ( x= )x(f ( 2 ) )then %(x) = cu(lir,(x)) =~ ( 0( 1) I ~ , ( S S X ) ) I I R ,((1X ) 17,(S.r))
L n , ( Ip!(x+r),
~ ) ) pj(x)l =o -
-
2.944 (Sn X) (/L!(x)
A pi(a))= O
proves (1
By example 2.461, from p,(x+r) - p , ( x + S r ) =O we derive Since 1 2 Z7,(x) = a ( 1 ZI,(x)), it folloms b y 2.935, tliat
1 { i2 - ( p f ( x ) ' { ~ 1 ( x i - r ){),)L L , ( X ) ~ ~ ~ ~ ( X + S ~ ) ) = O {''4("))
I{l,(x t.;r ) , p,(x)l =0 .
whence, since p,(x) -p,(x + O ) = 0, it foll0-a~that l u t ( ~- ~) t ( x+ r ) =o> 2.947 'x )f ( S x )= O .
( { L, ( S x )
and therefore, b y example 2.71, ( S n L x ) (,rl1(x):p!(a)) = O -
2.9471 (,u,(sx)' x ) ~ ( s x=o
) .
From p,(x)-x=O we deduce, b y esample 2.46,
We have 17,(0)p1(0)
= 0 and
=( 1
=( 1
-
(1 L n e ( ~ ) ~ , ( ~ ) ) ~ ( S ~ ) ~ t ( S ~ )
ne(z)p,(x))ne(x)~(Sx){Sx~e1(~) +p,(x) ( 1 e l ( x ) ) )
-17,(x)p1(x))17,(x)e(Sx)pl(x),since ~ ( S X01(x)
) . =0 ,
- {/¿,(SX)
and since ( b y esample 2.41)
- 5 ) {Sp,(x)- p , ( S x ) ) =0
and
we deduce
( 1-e,(x)) ( P ~ ( X ') p j ( S x ) )= O
( l L e i ( x ) ) Ipt(z)
. =o) ~
P~(SX 9
vhence by addition
-
p(Sx) ( p , ( S x ) xP,(x) = 0
) =0 ,
which in conjunction with ( 1 ~ 1 7 , ( x )Oj(x)
yields ( b y example 2.36) { / L , ( S X'
) x)g(Sx)= 0
Theoreni 2.9471 follows from "947 by niearis of esample 2.741. lieiice by tlieorem 2.941 (and esample 2.36)
f ( O ) ( 1 f f , ( S x ) )f ( u , ( S x ) )= O . . . . . . . . . . . . . . .
2.948 { , u ~ ( L ~ xX )) f ({!,(SX
T r ) )= .
Since. b ~ 2.63.
.
From 2.946 arid 2.9471 \ve obtain (as ir1 esaiiiple 2.36)
{ p ,(Sx'; 2 .ci l i ~ , ( St~r ):. !6,(ASz)l O - ....... .. and by 2.946 (taking z = 0 ) . ( 1 f ( O ) ) p , ( r )= O ,
n e havq. o11 miiltiplying (ii) by 1 f ( O ) ,
and so, by example 2.47.".
{1 2-
ancl similarly from 2.9-F7
I{L,(~X). .Sx/} I,t,(S.r r ) , , / ~ / ( S=Xo) ~
- aiid so ( i - f ( O ) ) ( 1 M,(Sx))f (,u,(Sx))= 0, nliich added :o (i) yields
C'
or
-
but
[l-Ip,(ICx),Sxl}f(Sx)=o ;
( 1 - - n , ( S x ) )f (,u,(Sx))= o
- ) ( 1 = j ( O ) ) !(O)
Finally we observe that ( 1 17,(0))f ( p , ( O ) =
.
=O mliich
*
e-
[ l ' I / ~ , ( S X8x1)
) . f (,u,(A\'x))= { l ljl1(8x).9x1) f ( S X ) completes tlie proof.
&iridso Qr
- e-
2.941 f ( 0 ) ( l ~ f ( x () l)~ ! l , ( x ) ) = = O .
{l Ip,(Sx), 8x1) f (,u,(Sx))= O
For ( 1 f ( x ) ) U , ( x=
) O and so, by the prcvioiis theorerii. 6i
which. by example 2.-1.81. traiisforms into
( 1 '-1 ( x ) )f ( p r ( x ) =
) " :
{{,,,(SX)
'-x) f ( { l i ( S X ) )= O . . . . . . . . . . . . . - (u)
however
B y ( i ) , (ii) and theorem 2.63 we obtaui 2.948, which may also ( 1 ~ / r ! ( x f) () p ! ( x ) )= ( 1 /c!(x))f (0)
be written in the form
and so 2.9491 follows on multiplicatioii by 1 = f ( x ) .
(1 +
I,uf(Sz),S x l } f ( p , ( S x r ) )= 0 From 2.0491 and 2.944 we deduce. by esnrnple 2.162.
2.949 ( 1 - q x ) }f (P!(x))= 0 -
Since nOi(x)= it%(x). ~ (I-@
l S x =17,(x)
) ( 1 2 e S x ) = 6,(x) aiid so, by 2.92, we have
and -
therefore 1 2 R , ( x ) = O,(x) and O,(z) O,(x) = O,(x)
R , ( x ) )Ip,(Sx), 8x1 = O ; hence by the last theorem
-
YO {l
(1 R , ( x ) ) f ( p , ( S x+ r ) ) = 0 .
It follows froin example 2.711 that First we prove tliat { l 2 f ( a ) )( p , ( a- n )' - a } = 0 .
( S x - a ) ( 1- R , ( a ) ) f ( p , S x )= O Denote ( 1 2 f ( a ) ),,,(a v.) by g(n): then since. by esample 2.74,
(1 '- f ( a ) )O,(n -- n ) = o . we liave g ( S n )= y(n) and so g ( n )= g(O)
atid therpforc by theorem 2.92 tliat is
:i f ( a ) ) t t l ( u n)= { l =f (tr))!r,(n).
(l L n ~ ff (,+(Sx))
( ~ ) =) ;
m
C
e, 44 TAE EQL7ATION CALCULUS
h
multiplying (ii) by 1-f (a) aild adding (i) we find, since
-
~ ( S n ) ( l I?.(n),p(n)l) Ii.(Sn), /c(Sn)l
= (1 I;l(n),,U(TL)I))?(S~)A(S:L),
= p(Sn){l
o(~>~)t(~71)/
- -
(by examples 2.145 and 2.41),
h thnt is
1
(1 f (a)) (,LL,(x) a ) = O .
h o(Sn)(l li.(la), ,u(n)l}Ii(Sn).Ic(A'ia)l = (i . . . . . . . . . . . . . .(iv)
We shall show in the next chaptey that theorem 2.945, 2.949 and
rr froin (ii) and its coinprinion
-
211d
2.9493 prove that when f (x)is zero for sonte x from O to n then ,Lr,(n)
h is the least value of x, between O and n, for which f (x) is zero, but {l {l(W\
14n)>P(n)ll P(n)l1.(Sn)>
B if none of f ( O ) , f ( l ) , .... f(n) is zero then p?(n)= O. = {1 IA(n),,u(n)l)Ip(n)j.(Sn),,u@)p(S?z)I
= (1A IA(n),~ ( n ) lIA(n)i(Sn),
) p(n),u(Sn)l
= {l li.(n), ,u(n)l}lJ.(n)j.(n),p(n),u(n)I= O
i.e. i r ( % ) (1 AIA(n),p(n)l} /?.(Siz),p(Sn)J= O . . . . . . . . . . . . . . . (r).
h
and A,(Sn)= R,(n)+Sn. (1 (A,(n) f (Sn))) + Finally, i~sing(iii) and the corresgonding equation for p,
then ~ r ( n=e@)
) .Un)
P
e
to which we add p(0) tirii~s(iv) aiid fiiid 2.062 The ineqiiality relatioiis are traiisitive, that is to say
2.9621 a:c follows from (1 b and b> c
i Examples 11
a ( x ) + ( l ~ c u ( x ) ) =. l(u(x)'x=O, x.cr(x)=x,
(Y(1'-x)= 1 - a ( x ) . (Y((Y(x))=(Y(x) , ~ ' ( Y ( x )1='I ,
u ( x ) a ( x )= (Y(x), cu(xy)= ~ ( b &(y),) .
and that E ( / ) - g = O follows from f .g==O.
I f ¿u(x?y) = "(15, y'l)) prove that
( 1 '(Y(x,y))x= ( 1 a ( x , y))y
and (b-b.a(c, b))+c.cr(~? b) = C .
Prove the equations 2.27 1- 2.274
S x - (5-(z)=S(x= (x'a))
Prove the index laws ?.?SI - 2.2%
.?/',
( x.y)" z x n
Prove that 3 . 2 = 6 , 4 . 2 = 8 , 3 . 7 = 2 1 , 4 . 7 = 2 8 and 34.27=918
Establish the following proof schemata 3 Ib.a+(b-~-a)l=nib
2.44 ( a ,b ~ ( b - a ) ( = a - b
{l~(g'f)}h=O
( S f-g)h=O
34 THE EQCATIOX C.\LCCLT7S
{ l ~ ( b ~ {b'-(a-(a'-b)))=O
a ) }
2.73 Prove that, for anv definite nuineral p
f ( p '- r)=O
2.7301 f(p+Sr)=O
f(z)=O
5.7
-
Prove the equation
{1 (a.-b))+ (1 ~ ( 8 b ' - a ) ) =1
Establish the schemata 4.701 - 2.72
2.3 With the notation of 1.6 prove
2.91
-
O! = 1 , ( S n ) != ( n ! ) S n
prove that 1 n!= O and ( S n )! =%(n) .
Prove the equation
( l ~ ( 1 - a () l ~ b )( )l ~ a c( )1 - ( b + ( l ~ c ) ) ) = O .
THE LOGICAL CONSTANTS 5. 7
-
the inequality la. bl > O is provable then the equation a = b is the proposit,ion
called a fcrlse proposition. Since the equations a=?, la, bl =O may
each be derived from the other it folloxvs that a t'rue proposition [a, bl /C. d( = O
is a provable equation and conversely. is denoted by p & q whicli is read 'p and q', the proposition
Moreover. as Ix, y1 is a reciirsive functioii, for any natural
piimbers a. b there is a unique natural number c such that (a,b(. (c,d[= O
ia provable; if this riumber c is zero then a = b is a true propositioii, and ( 1 :la, b [ ) . [ c dl=
, O
and if c is not zero then 1-la, b[ = O is provable, so that a = b is denoted by 2) -t q read ' p implies q'.
ia a false proposition. Bccordingly, a n y proposition i s necessarily p + q is thus the same proposition as N p v q.
either true or false, and n o proposition i s both true and false. Finally, we denote the equation
3.1 We call a(la, bl) the number of the proposition a = b , so that
a true proposition has the number zero and the number of a false
proposition is unity. Conversely, if &(\a,bl) = O then la, b) = O SO by p -eq which is read ' p is equivalent to q', so that p -S- q is
that the proposition a = b is true, and if &(la,bl)= 1 then la, bl > O the same proposition as (p + q) & ( q -+ p).
and a = b is false, and therefore the number of a proposition is We observe that, since 1 la, bl, 01 = la, bl, therefore
zero if and only if the proposition is true and the number is unity
if and only if the proposition is false.
and since (i~x)a(x)=x(i~u(~))=O
3.11 The propositioii 1 :la. bl = O is called the negation of the
proposition a = b. Since and nc(l*(x))
= a(x)
p inzplies p.
I
Y
3.15 The definition of eqiiivalence makes y and q equivalent if 3.22 Since addition and multiplication are commiitatire the
and only if p aiid q are both true or botli false. From tlie proposition following proof schemat.a are ralid:
p I A q and a proof of q we derive a proof of p. for if
(1-la, bl).Ic, d l + { l - ] C . dl].la, bl=0
and Ic, dl = 0
Tliese shom that ' a ' . . v ' and 't.' are s!j»lnietrical relations.
are proved equations. then la, bl = O is a proved equation; accord-
ingly, t o prove some proposition p it suffices to prove a proposition 3.23 From the equation x ( l =x)= O u-e deduce botlr p -t p and
equivalent to p. p ct p mhich show that '-+' and 'ct' are reflexire relations.
3.16 The signs a, v, N, -+ and tt are known as logical constants; 3.24 Since f = O and g = O follow froni f -!- g = O. nnd concersely,
their introduction effects a considerable economy in proof technique
by revealing a variety of easily recognisable patterns of procedure.
and P P+q
- 5' !-
I+P
P & Q P"Y
It folloms that like '+'
'e' is transitive.
and therefore, if p, q, r are any propositions al= %, bl= b,, c,=c,,
3.3 We consider next some of the important relations which hold
say, taking lai, +I for x, lb,, b,] for y and Icl, c,] for z respectively,
between the logical constants.
we obtain the proof schema
Since 1 .- (1 ( 1 ~ x ) =
) 1L X it follows that
Since r
x,)
-
( 1 x1)x2= o.
r me deduce from 3.321 that
=O follo\vs from
Whatever the propositions p, q, r me may take p', q', r' to liave
the forms a = O, b = O, c = O respectively, and so P is equivalent to
++ P* : O
( 1 ~ ( 1 - 1 - a ) b( 1) ~ c a ) c b =
3.341 pvq--(-p&-q) where a, b , c are certain numerals, which may be derired from
so that the truth of the third propositiori follows fi-om tliat of the provable equation (emmple 2.48)
the first and second.
-
6" THE LOGIC.41, COSST-ISTS THE LOCICAL COXSTANTS 63
(where x, y, z are numeral variables) bu substituting a. b, aiid c then n-e denote l z I F ( x ) , f (x)J= O by p(x),
for x. ?/ and z respecti\-el?.
If me allon- the lettcrs p. q. 1- t o hnre thc clual roles of ii:inies for
propositions and iiiinier:d variables tlien
in tlie forni
rnny 1;~iteG directly
-
~ (v 4P(X)
from y(1-y) = 0 by takiiig IF(n),f (z)l for y. JVe use tlie term
formula to cover both propositions and propositional functions.
I n tlie notation of tliis cliapter tlie fundamental theorem 2.68
y c derive the truth of the propositioiis - takes the form
pv-p and - ( p & - p )
which are líilomii respective11 as the priiiciple of exclzcded middle
3.5 The logical co~istaritseriable us to introduce the conditional
(or terfiurn non dattr,~)and tiie principie of noncontrndiction.
eqiiations of elementar>- algebra. Unlike the variable x wliich is
characterised by the propertj- that it may be replaced by zero
3.4 PROPOSITIONAL
FUXCTIO-*TS
or by Sx wherever it occurs, the x in a conditional equation is a
If x is a variable and f (x), g(x) are two given recursive functions missing number sign which m$!- only be replaced by some def%ite
then the equatioii numeral. For instance, wheii r e say that x = 3 is a soliition of the
f (x)=S (4 eqiiation x2= O, we mean that a true equation results from replacing
is calied a propositional fzcnetion; if for some value a of x, f (a)=g(a) x by 3 in the second equation. but neither in x = 3 nor in x2=9
is provable then the propositional function is said to be true for may we replace x by zero or by Sx. I n fact x = 3 and x2= 9 are
the value a ; if 1f (a), g(a)l > O is demonstrable then the propositional not equatiom but propositional functions; and the fact that 3 is
function is said to be false for the value a. More precisely, the a value of x which satisfies ; c L 9 is espressed by the implication
equation f ( x ) = g ( x ) is called a one-variable propositional function, F: ( 5 = 3 ) -+ (x2=0).
""'1 f ( x , y) = g(x, y) is a tmo-variable propositional function, and SO Formula F holds for any ralue of x as rnay readily be verified,
on. Propositional functions are denoted by p(x), p(x, y) etc., for
accorciing t o tlie niimher of variables. 12 13+Sr , 31 = 0 and 1= 1;: , 31 = 0 (by example 2.4'7) and
3.41 As in tlie case of propositions, if p(x), q(x) denote the 35 91 = O , so that, by esample 2.7303,
propo.citioiin1 functions (11-[.t.. 3 j ) . ( 9 . ,[=O
which completes tlie proof of formula F.
64 T H E LOGIC.1L C O N S T A h T S LOGICAL COSSTANTS 65
Similarly. the fact that the 'equation' x2 + 6 = 5 s has only the which must be added t o the list of permitted formulae in a proof;
twvo solutions x = 2 and x = 3 is espressed by the implicat.ion in this case the new signs cannot be totally eliminated but
espressions containing them may be transformed into equiz+alent
-
i.e. ( 1 Ixz+ 6. 5x1). Ix, 4. lx, 331 = 0 ; denot,iiig tlie left-hand side of
this equation by f ( x ) we liave
equations in which they do not appear.
The sign x in the operators d:(f(x)=O). E:(/ ( x )=O) and
L",f ( x )= O ) is not a true variable but an auxiliary sign k n o m as
a bozind variable. JITe could readiiy reserve a special class of signs
for bound variables but since there is ver- little risk of confusion
it is customary to use the sanie sigris as for variables. The fact
and f ( 0 )=f ( 1 )=f ( 2 )= 0 mhich proves t>liatf ( x )= O. +
q(f( x )= O ) is equivalent to
66 THE LOGICAL C'ONSTASTS THE LOGIr \ L l'OXST.\STCI
For the iiiterpretatiori of tlle operator LZ we recall tlie cliarac- Tlie companion formula
teristic properties of the f~inctionp , ( n ) proved in the lmt cliapter.
From the proved equntioiis (2.942 and 3.949) we have
may be callecl the principle of matlienirtici~lind~ct~ion.
JTe derive formula 3.5 from
mhich says that f (n) does not vanish for aii n les8 than ,ui(x),
so that if f (x) vanishes for some value of x from O t o n , then wliich holds by esample 3.031, and P(?L-1 ) is eqiiivaleiit t o
,u,(n) is the least of these values. p ( 0 ) & A ; { p ( z ) -t p ( a f 1 ) ) & ( p ( n + 1 ) -+ p ( n + 2)) -+p ( n + 1)
Tf j(s)>O for all x from O to n , i t follows from the equation mliich follo\vs from 3.81 (aild exaniple 3.031). Since P ( 0 ) and
(2.!145) P(n+ 1 ) are proved t,hen P ( n ) folloms by 6.7.
n i ( n ) P , ( n )= 0
3.9 We collect here for refcrencc tlie principle properties of the
¿hzt LE(f ( x )= O ) =p , ( n ) = O . operators A, E ancI L;the fractioiial part of the numbers of the
follov-ing formulae are the same as in tlie numbers of the theorems
U .7 ~IATHKYATICAL
I'YDUCTION in the previoiis chnpter of n-hicli tliese formulae are transcriptions.
I t folioms from theorem 2.8 that the proof schema
By esaniple 3.Y31.
Jn terms of representing functions we have to derive the equation 3.950 E:F(x) AEG(x) -t E : { F ( x ) a G'(x)).
- - ( 1~ h( ( 1) Z;(n))-f(n+ 1 ) )
For [ l ( ( 1- h ) ( 1 Z;(n))Zlg(n))]
= [1 ( ( 1~ - (.qn)+g(n+ l ) ) =
( 1 h ) ( ( 1~f (n+1 ) )-Zj(n)>
h( 1 ) Zj(n))Zg(n)}]
By 3.052 and 3.956.
-
3.955 F ( n ) + EEF(x)
g(n+ 1 ) = 0 ,
nsing the hypothesis ( 1 h ) ( 1 2 f ( x ) ) g ( x=
) O. For (1-f(O))f(O)=O and ( 1 - f ( n + l ) ) { ~ f ( x ) ) f ( ~ n + l ) = O .
S<?&
THE LOGICAL C O N S T A S T S
The validity of the schema for n = O is obvious. (which is also proved by applying 2.8 t o the variable c) with the
Since same siibstitution for a, b and c.
(1-(1-f) C
xán
g ( x ) )( 1 - f ) { C g(x)+g(n+l))
XBn 3.9641
hare
Taking - G ( x ) for F ( x ) in 3.957 and using 3.964 r e
8.961 A ; G ( x ) + E",@) ,
For G(O)iG(O) and and 3.964 we derive immediatelj
THE LOGICAL CONSTAIVTS TKE LOGICAL CONSTh\TS
52
But E; G(Y)-+ E,:+' @(Y by 3.959, 3.961 we derive AZ(F & G ( z ) )+- F
so that { P ( n )-t E: G ( y ) )-> {P(n)4 E:" G(y)) whence A,"(F a Q ( x ) )-+ F & A;G(x) follows.
whence. taking y = x & f ( y )= O for G ( y ) . Conversely from
{ x g n & f(x)=O) -t [P(n)-+ E;"{y=x f(y)=O)] . A','G(y)-t { x < n -+ G(x))
x=n+l a f ( x ) = O -t [ P ( n )-+ E;+l{y=x & f(y)=O)]. which completes the proof of 3.9661.
Again, by 3.9641, .
Since
xan+1 f(x)=O -+ { x ~ &nf(x)=O) v { x = n + l a f(x)=O),
and so F v A;G(y) + F v {x<n -+ G(x))
it follows that
whence F v A;G(y) -t ((2 < n) + ( F v G ( x ) ) )
{z<n+l a f(x)=O) -+ [P(n)--+ EY"'{y=x a f(y)=O}]
and so F v A:G(y) -t A + ( F v G ( x ) ), as above.
whence
Conversely A,"(F v @(Y)) + { X 9 n -+(Y G ( x ) ) )
P(n)--+ [{z<n+l a f ( x ) = 0 ) + E;"{y=z a f(y)=O)]
and so AV(F v G ( y ) )a - F + { x a n -+ G ( x ) )
i.e. P(n)-+ P(n+ 1 ) , mhich completes the proof.
If F does not depend upon x then:
and therefore AY(F v G ( y ) )& - F + A;G(y) ,
whence 3.9662 follows.
3.9661
3.9662
A = ( F a G ( x ) )tt F
A:(F v G ( x ) )-eF v AZG(x)
& AEG(x)
-
Theorems 3.9663 and 3.9664 follow from 3.9662, 3.9661 by taking
F for F and G ( x ) for G(x).
N
3.9663 E:(F & G ( x ) )tt F & EZG(x) 3.97 The Counting Operator X ; F ( x )
3.9664 EZ(F v G ( x ) )tt F v E:G(x) . To express the number of roots of an equation f (x)=O in the
1
! 74 THE LOGICAL CONST.\'<l'S
I
-
I f f ( x ) is the representing fiinctioii of tiic ~)i'ol)ositionalfunction
F ( z ) then \ve lvrite S : F ( x ) S ; ; i ( x )= 0 .
The first theorem n-e 1,rovt. f»r tlie coiiiitiiip o p cv.itoi'
.~ h
n-lience A:; F(x)a [ S I P ( x=
) 01 .
l Tlie eqiiivalerice 3.972 iiiay also 11e espress:~i iii tlic forni
l
l
-
[ l ~ al ~, b \ = l ~ { l ~ l ( l (~l ~a b) )ba,.l ]
Thus from ( 1 2 f ( x ) ) ~ (=x {) l g(z)}/( 2 )= O we derive
Proof as for above, usii~gthe equatioii.
1~~=(11-p)-[l~{q--(l:p))]
1-f(x)=l'-g(2).
3.9i5 N:(F(x) a G ( x ) )G S t F ( x )
It follows that NZF(x)=x G ( x )
= -- ( 1 ~ p ) ]=)O
I n the equation { 1 2 (a: b)} {[rz - ( 1 (1)~ q ) ) ] [b
and I X ~ + ' F ( x )N;+'G(x)l=
, (X"(x), N;G(x)l which is prored by applying schema 2.7 to tlie variable q, \Te take
whence, by -3.8, IN;F(x), N;G(x)l= O , mhich completes the proof. NE(F(x)& G(x))for a,NEF(x)for h. F(n-c 1 ) for p and G ( n L 1 ) for q.
~ f ( O ) )=O
Por n = O the equivalence becomes simply ( 1 :
e(1-f(O))=O.
Let P ( n ) denote the implication: then P(0)is equirnlent to
{l:(l:x)) [l:r)=O.
Since x > n L 1 + x > n and >n f l -> (1-Ix,nLll)=O
Silice X;'-'(f ( 5 )= o) = N;(f ( x )= O ) + (1 / ( n+ 1 ) ) .i,
follon-s
.r ;
: IL & f (x)= O -> = O) = ,
;' +- 1 - .- xr'(f(y)
. = 0 & !j 7;X) 1;)
!I
nnd so 011.
u-licncc {St(f(y)=O)=X:+
1: -+ {(.t..:: n & f ( x ) = O ) Tliese equivalentes show tliat tlie operator .Y:{/( x )= O ) Iias tlie p
;- sg(f(;l/)=O& y+x)=l;)- desired properties. Thus S:(f(.r)=O) has tlie value unitv if and ciP
;tllci SO {q(f
( y )= 0) -.. :/ i-11 -
L ir. 1, & /(.t.) :~- í-t f ( x )=O
{,zp~:n-&
only if there is a uniqzlr r froiu O to n for which f (x)=O. Xnd
,Vz(f ( x )= O ) has tlie valuc 2 if aiid only if theic is an x and y from
w
e@
-&
& I Y ~ ~ ( ? / )a=?/+I;:c)=L)]
O O t o n, x different froni y. siich that. f ( x )= O and f (y)= O and f ( t )
whe!ice. by 3.951, does not vanish for nny otlier V R ~ U Vof t from O to n, and so on. w
:Xt(! (y)= '1) = k + 11 -> :E:(.c ;,
IZ & f (x)= O)
v
J -- EZ(n:< n & f ( x )=O & A7;(f( y )= 0 & !/ + X ) = li)]
arid therefore, by 3.957,
3.063 P+cl
( p v r )+ ( q v r )
Examples 111
9
3.061 p-i (q+r)
P+T
P+P *
3.0611 q-tq*
p&q-ip*&q*
1 TKE LOGICAL COXST-tVTS
3.194 4 , r -t { ( ~ ' r ) - ( q ~ r ) = ~ ~ ~ )
3.31 (l~~~)L~{~(n~z)=O)=0
Since x =y -+ a ( x , y ) = O therefore
4.023 R ( a , b) < b -+ {SR(a.,b) < b v a ( S R ( a ,b), b) =O) .
Proof of 4.01
Denoting the formula O < h -> {R(a,b) < b ) by P(cc),we derive from
If f ( a )=bQ(a, b ) + R ( a , b) 4.02l, 2, 3 (and example 3.085)
theii f ( O ) = bQ(0, b) + R ( 0 , b)= O P ( a )iP ( S a ).
ant1 / ( S u )= bQ(Su, b)+ R(Sa, b) Since P ( 0 ) holds by definition of R(a, h). 4.02 is proved.
= bQ(a, b) +b ( i x(SR(a. b), 6 ) )+8R(a. 6 ) .x ( S R ( a , b), b)
Proof of 4.03
= hQ(a. b) +SR(a. b). by- esamples 2 . 2 7 , 2.08, IVriting Q, R, for Q(a. b). R ( a . b) respectirely we have. by
= $ / ( a ) , so that f(a)=a. theorem 3.43,
SS TE€E FUNDAMESTAL THEOREMS OF ARITIINETIC THE F C T D . \ X E S T A L TíFEOILCXS OF ARITEAíETIC Y(3
(bc+r=bQ+R)
(bc= b&)} , so that (using theorem 2.91 and example 3.063)
n > 1 -+ { q ( n ) > l A ~ " ' ( n ~ 1a = ~ (vnR(n,
) a)>O)},
that is n > 1 + p(q(n))= O
it follows from 4.034 that
which says that q ( n ) is prime if n > l .
G biit
From the formula
90 T R E FLTXDA>CE>T.%LT H E O R E J l S O F .XI:TTt~JlI-TIC THE FUXDIDIESTAL THEOREJIS O F ARITHIIETIC 9t
we deduce that We show first, tliat p(n) is prime for any n. Since
?i .1 &q(n)=n - p(n)-O. q ( P ( k ) !'- 1)
From R ( n . n )= O and aiid p(q(p(E)!- 1))= 0
therefore p(k+-l).,p(k) . p ( p ( k - 1 ) ) = O
we derive, firstl?. aiid ~ ( k -1r) < q ( p ( k ) ! - -1) ,
so tliat p ( k - 1 ) is prime: but. by esarnple 4.45, u((')
is priiiic. aiid
so p(n) is prime for any 71.
It foiloms by esaniples 4.5 aiid 4.61 that p ( n - 1) is an odd
prime. To sliow that (for n > O ) p(n) is ir1 fact tlie ntli odd prime,
By means of the proved formula q ( n )';;n 1%--r derive
v e shall show that every prinie is a p(n) for soriie ri. that is
Accordingly, by esaniple 3.42 Oiir principal result is that any niiniber inay be espressecl in one
wa5- orily as a product of prime factors. JI7e st'art by considering
tlie liighest power of a given prime contained in a given number.
4.5 Iii preparatioii for theorein 4.51 belo~v.we piuve -riext : We define
if bd> O and R(nb,d ) = O. and if ~, v(O, k )= O
"(AS%, k)= L:R(sn, ( p ( k ) Y')f > 0
1, tlierefore by esample 4.701, (p(k) > n and so
Siilce p ( k ) :-
thieri R(b, 1) = 0 .
R(Sn, ( p ( k ) J n " )> O
We observe first tliat
ancl therefore (by t!ieoreni 3.940)
>O
R(Sn, (p(k))"'S"."+l)
and d>O & R(ad,d)=O -+ Z g d . i.e.
Let B, Q denote Q(b, l ) , R(b,1) respectively so that 4.61 1.1 > O + R(n, (p(~))"'"."+l)
>O
b=Pl +e aníl e<l ; and (by 3.9493), v(n,k) < n, and
+
since R(ab, d ) = O tlierefore R(al? ae, d ) = O ; x < v(n, k ) + 1 + R(n, (p(E))") = O
whence, since R(nZ,d) = O , we have R(ap, d ) = O ; so tliat, in particular,
but (x<1 & R(ax,d)=O)+x=O
and so, from the inequality <l it follows that e = O, ~vhichcoiil- Formulae 4.61 and 4.62 shom that v(n,k ) is the exponent of the
pletes the proof. greatest power of tlie izth odd prime contained in n.
t
4.51 If p is prime then 4.63 m>0 -+ m= 17 (p(x))"'"~")
Zdm
S
By esample 4.86, m is divisible by 17 (p(x))"".", nnd if Q is
zdrn
For by the previous result, since p> O R(up,p) = 0, it follo~vs
tlie quotieiit, it follows from forniula 4.61 and esample 4.87 tlint
that R(p, 1)=0 and l ~ p and , therefore, since p is prime, eitiicr
1 = 1 or l = p . But R(a1,p ) = O and R(a. p) > O so that
and tlierefore 1 =p. By 4.5, R(b, 1) = 0 and so R(b, p) = O.
(1 l ) , -- ailcl heiice (by esan~ple4.W) that m > 0 + Q = 1.
THE FVNDAXEsTAL THEOREMS OF . m I T I I E T I C
05
4.64 To show that factoristitioii is iinique we isolate an individiial and so, by theorem 4.51 (and esample 4.82 again).
factor iii n product 1 1 ~ -menlis of the followirig theoreiiis:
r < k + { J ( k )-+ J ( S k ) )
if p (m.r: 0 )= 1
and the proof is completecl as before.
x* l.
- 1 1 ~ ( . rk ) ) [p(I.Ck))"("'.').
2- q(ni. r, k )
and so (by esample 4.71 1). v(m, x ) 3 [(m.x) for all X G m. Similarly F
:(m, x ) > v ( m . x). so that [(m. x ) = v ( m . x). for all x < m .
e-
and so
{r < k ) - [H(I:)-+ { 17 { p ( ~ ) ) " ~=. {p(r))"rn."q(m,
~) r, S k ) ) ]
Since v
i.e.
Z<Sk
( r ~ k-t) { H ( k )-+ H ( S k ) ) . . . . . . . . . . . . ( U ) 1 { ~ ( mx ,) = O ) -> { [ m> O -+ R(m. {p(x))""."-' )>o] e-
T t follon-s from (i) and (ii),
. . using- esample 2.491, that
-+ [m > O -+ R(m, ~ ( x >
) )O ] ) p
( ( r< k ) -+ H ( k ) }-t ((7 <S k ) -+ H ( S k ) ) and m > O -+ R ( m , { p ( x ) ) ' ( m . z ) 4 1 ):O
therefore, by esa.n~ple3.064,
which completes a proof by induction of 4.641.
The proof of 4.642 proceeds on the same lines; v(m. x ) = O - {nz > O + R ( m , ~ ( x >
) )O )
if r=Sk t,lien ~ ( mr,, S k ) = 17 { p ( ~ ) ) " ~ .and
~ ' so (by examples which proves 4.71.
zg k
4.82. 4.55) It folioms that
( r = S k ) + R ( q ( m ,r, S k ) , p(Sk))> O
so that. if nt > O , v(nt. x ) > O is a necessary and siifficient condition
If r *:k then q ( m , r, S k ) = {p(Sk))""'.").q(m, r, k ) for m to be divisible by M X ) .
l THE FCSD.IJIEST.\L THE0REJI.S O F ARITUJETTC
97
l
4.71 THE GREATESTPRIMEFACTOR
I 4.9 THE GREATESTC O ~ I O ' FACTOR
T
I Followirig esample 3.36 we can readily define the greatest value
If l(n)=L",v(n, n 2 z) > O ) aiid q(n)= n 2 1(n) \re shaU sho~vt hat
of x which divides each of tu-o non-zero numbers a and b. FTe
p ( g ( n ) ) is the greatest prime factor of n.
For, by example 4.S3,
l
prefer however to proceed differently and to establish tlie greatest
comnion factor as the least non-zero value of the function a x A b g .
\Te shalí determine fiinctions k(n, b) and l(a, b) such that
whence h(a, b)=ak(n,b)=bl(«. b) has tlie least possible value, not less than
n >1 - y, n) > O )
[ ~ l ( n , . iinity.
From tlie equatioii
I t follows. by esample 3.36. :Iiat
we derive
and E~(h.a~l.h=ub)
aiid froni this in turn we derive
Since n > n -+R ( n , P(a))= 71, t,herefore n > n .+ v(n. a )= O and 4.722
may be rewritten in the forni
From this. and the inequality nb > O, follolvs
EC{c 2 1 & Ei(EP(kn2 lb =c ) ) )
Formulae 4.721 and 4.723 show tliat p(g(n))is tlie greatest prime
factor of n. and, therefore, if
-
Q(X) and so if
z<N
by theorem 4.63,
ancl so, since factorisation is uniqiie, l(a, b) = LU(a.k(a, b ) yb = li (a:b ) )
we have
x á g ( N ) -t v ( N ,x ) = a,,
;.e. the numbers v ( N , O ) , v ( N , l), v ( X .9,..., v(X, g ( N ) ) reproduce
the given collection (where g ( N ) is defined as in 4.72).
98 THE FUXD IJIESTAL THEOREXS O F A R I T H ~ I E T I C TI% FUND4'dEYTAL TSEORE>fS OF ARITIl\IETIC 99
4.01 When one of u or b is zero me define h(a. b ) = a A b , so that which we shall m i t e for short in tlie forni
'C
( l a 0 & b-0 -- l . n ~ O . b = h ( n .6 ) x«-yh=~.
'w'
a=O a b-:O 1.h-O.q=Ii(n. 6 ) .
1 'IP
and - By example 3.193. if nb .<x, nn y ancl !/J n x tlien ' íp
<-
,-
-
For k q b l s a & k n ~ l b = c Eb,(Ef(lrn~-lb=c)) and herice if is the greatest n satisfyirig ~i1,q.r n n ~ (given
~ y by 'e'
Ei(Ef(k(i-= lb = e)) & c 1 h(rr. b ) -,c ( b y theorem 2.0493). example 3.7) ancl if we denote . r 2 S h . !/ L S a by S. 1' re have 'w
4.93 Ry esample 3.1s ~X=bl-=~. 'u'
kgb & 1<,, + [ l ; r r - Z b = ( a l - l ) b ~ ( b ~ k ) a ~
I
If Y > u . S : b . theii b y esample 2.41. froni the iiiequalities w'
wherice, since a ll(rc, b) < n , b L k ( a , b) g b ,
-
N b < x , N n < TJ \re derive .c > (S 1)O, !/ ( S- 1)a coiitradicting cía
the definition of .Y, nnd so either Y í n or X; h.
;Yi
h(b, n ) G h(a, b ) . If S : b and I ' ; n then a X 2 b Y - rtb-bi7-b(n-1')--O aiid so
i, FSL-- w
-
-
bin~ilnrly li(n, b ) 9 h(b. a ) ,Y,b Y ; ( I --E!EY(ax-by=c) & c - - u &c-.h
m'
khence, from E y ; ( n x by = c ) & c > 0 +- c J h (theoreiii 4.92) we
R ( n . bc) = O -t R(cr. b ) = O
If a -
b> 1 + R(ab+ 1 , b)= 1
cd = b and b > O prove t,hat
R ( n , d ) =R ( b , d )
Show t h a t a = b - d x + a = b ( m o d d )
Prove t h e schematn 4.3.' !- 4.323
a =h (inoti d )
h=c (mod d )
u = c (mod d )
a = h (mod tl)
nr =br (rilod (i)
THE FL7lDAYE'iTAL THEOREJI': OF .\I:ITR(TJIETIC TEiE F C N D A 3 I E S T A L THEOHESlS O F ARITIIMETIC 103
al=bl (mod d ) 4.802 R(m, a ) = O a R(m,pk)= O a R(u, p) > O -f R(m, apk)= O
a,=b2 (mod d )
a,+ a,=b,+b,(modd) Prove the forrnulae
function definitions, and the only inference rules are the sub-
stitution schemata
The passage froni U, t,o U is obl-ious;' for the converse we derive
f . g(x)= HZg(0)
( 5 )= HTf( 0 )
We establisli nevt some results for additioii, subtraction and ]\-e use a - ~ S o = S a = S a + 0 ,a-';.Sh=S(a+Sb), Sa-Sb=S(Sni.b)
multiplication, taking the definin; cqiiatioiis for thesc operations aiid 1;.
to be:
a-O=a . u + S h = S ( a ~ b ):
From a + 0 = 0 +-a , a fSb = - 3 j. iising 5.07. follon-S
O ~ l = O . s a : l = ( - .~a - O = a . a ' - S h = ( ~ ~ ' - h ) - l ;
S b -L n = b +So = S ( h + a). Then 5.l'lS f o l i o ~ ~by
s U,.
n - @ = O ,n . S h = a . h - o .
For ( u - ~ ) ) - l = ( a ~ l ) : ( >( U
. - S { I ) : ~ = { ( ( .L. f > ) L l l : l . -
1)-Rb= { ( a - 1) 1- hj 1, illl(l the resiilt fnllows by-C;.
J?-ith c as variable, apply I;,.
For S « - S b = ( S a ~ l ) - b = a - b , using (5.01).
5.13 a(1-a)=O.
For (a+Sb)-Sb=S(a+b)'-Sb=(a+b)-b so that (a+b)-b=a,
by E,. For 0 ( 1 ~ 0 ) = Oand Sn(1-Srl)=.Sn(O-o.)=Sn.O=O.
- + +
For ( u t S n ) ( b+ S n ) = S ( a + n)2 S ( b n)= ( a n) ( b m), and
(a-c0)2(b+O)=a~b.
+
5.15 a(b- c)=lz.b-a.c.
This is a consequence by El of the provable equations
By 5.051 and 5.04.
a(b~0)=a.b=a.b~a-O.
n(b-Pc)=a.SíF, - c ) = u ( h 4 c ) ~ n ,
For O - O = O , O + S u =#(O + a ) , S a = S u , and the result foilows
by U,. n.h-ct.Sr=nb-(rlr -a)=(ah~oc)+a.
For a(b- 0 )= O = ( a .b) . O and a(b.Sc) = a(bc + b ) = n(bc)+ ab,
(ab)- S c = (ab)c+ ab.
\Ve prore non- aii esteiision of schenia &.
whence $2, follows by U,. for froni Id,BI = O fol10n.s \ A . BJ1(B'-_4)= O by 5.04, mhelice
b y 5.05, A - E = O, and sin~ilarly.B = A = O ; from these we reacli
Plor ( 1 - O ) b = b = b - ~ . b , ( l - S ~ ) b = ( O ~ - c r ) b = Oand
,
b ~ S a . b = b - ( b f u.b)=O. and therice A = B, by 5.17. The derivation of [ A .B [ =O from
Next r e prove the key equation A = B is of course trivial.
We come now t o some induction schemata. Let P ( x ) denote
the eqtiation f ( x )=g(x).
Define f ( a , b ) = a + (b- a ) , so that f ( u , O ) = u , f(0, b) = b, The familiar induction schema is
f (SCL,S b ) = S f ( a , b) ; and define g(u, b )= b + (a: b) so that
da,O ) = a, g(0, b ) = b, g(Sa.,S b ) =Sg(o, O). JVe start by proving
or va-iting p ( x ) = 1f (x),g(x)(
By E,, = ( a ) - { ( ) whence / ( a , O ) = f ( a - 1 , O)+
( 1 ~ (i a l) ) which establishes 5.171 ~vithO for b. 1Vith Sb for b,
5.17 1 becomes
f ( a ,S b ) = S f ( a = 1. O ) As in the proof of 2.8 we define q(0)= 1, q ( S n )= q(n)( 1 -r-p(n));
then q(SSn)=q(Sn) ( 1 .- p ( S n ) )=q ( n ) (1 2 p ( n ) ) ( 1~ p ( S n ) )
which is a corisequeilce of the equations f(0. Sb)=Sb=Sf(O, b),
f (SU,S b ) = S / ( a , b ) , completing the proof of 5.17 l . Kext we define
where the last equality sign holds according to hYvpothesissince
e
{ l = f ( o , h.- 1); ! ( S u . b) = O .
-
To complete the constriiction of recursive aritlinictic there
tlierefore
reniains oiilj- to prove tlie siibstitution theorciri
{ l =!(u: 1, b 1): ! ( u . i,) 11
hnti so
( 1 ' - f ( a - ~ n , b ~ S n ) ) f ( a - n h-n)=O.
. This iu :.tbarlily derived fronl tlie equatiuii
( 1 :Ix. y j ) F ( . ~=) ( 1 -1x. y / ) F ( y ).
Esactly as in 2.63, we stnrt froin tlie equntioii
To this end we prove
( a ,fb ) { l = f ( a ~ nb ,~ n ) }f (]a , b ) ( lf ~(a:&,
[ l ~ b2Sn))=O; 1 which is proved by applyiiig E2 with z as variable, and derive
1
We call t,he foregoing formalisation of recursive arithmetic this of course is a consequence of Sb, itself. For Sb2 we hare t o
system G?. prove the validity of the derivation
(1-IF,GJ)F={l=IF.GI}G
whence. using the schemata
land the final equation becomes
from which we may derive which follow from the provable equations
we prove
(R.A= R.3) + {R.F(A)=R.F(B)) ,
If P=Q is a proved equation then for any function R, and so, (taking 0 = 0 for H in the second of the above sohemata)
we see that R.F(A) = R.F(B) folloms from R.A = R.B.
Por T we have only to prove the schema
is a proved equation, and so multiplication by 1 1 F, Gl turns
a proved equation into a proved equatioli.
We show next that multiplication by a factor does not ixivafidate
an application of any of the schemata Sb,, Sb,, T and U. Por and this follows by T itself. It remains t o prove that an application
Sb, --e have t o prove that of U, remains valid under mutiplication by R, i.e. that the
derivation
R. F(0) =R.G(O)
R.F(Sx)=R.H(x,F(x))
is valid wlien the factor R does not contain the variable s. and
is valid. when R cfoes :iot contüiii the variable x. \Te start by by niiiltiplyiiig each equation iii :he derivation from these hypo-
proving tlie achema t heses by
( l L ] F 1G
, , ] ) ( l = l f i . G?l) (l.-/&. c:,l),
and so on.
aild the desired derivation follows by the schema niid, in place of tlie familiar introductory eqiiations of tlie
l predecessor functioii, the axiom
P Sa=Sb=a-1.b.
which is also proved by Sb-. Tlie axiom a -i (b a ) = b + ( a b) enables us to deduce a = b from
From the formula (X.a= 1;b) + { k J ( a )= M ( b ) ) , whicli is pioved a-b=O and b l a = O . For by Sb,.
above, follows
MTeturn now to a reconsideration of the equations and schemata The proofs of 5.051, 5.052 remain unchanged. and from 5.051 it
prored in 9. follows that
Equat.ion 5.01 we leave to the end. Equation 5.02 is riow an la t n, b - nj = ja. bl .
asiom. The proofs of 5.03 ancl 0.05 remain unchanged.
Proof of 5.10
Proof in &'* of 5.07
(a+SO)-(Sa+O)=Sa2Sa=O.
I C L + ( b+ 0 ) . ( a + 6 ) 01 O.
- =
( a + S S b ) 1( S u +Sb) =S(CL
j S b ) - S ( S a 4-b )= (a T S b ) ( ~
Sa b), + In + ( b -! Sn). ((L + b) i S n l = ltr - ( h - n). ( a -:-b ) -- nl . etc.
The schema ( F ( x )+ G ( x ) ) ~ G ( =
x )F ( x )
and 0 - G ( x ) =0 .
To prove schema E,
-
The proof of eqiiation 5.01 in 9 is therefore ralid also in g*.
We nlay 013viously take the equation ( a O ) L.1 = ( a 1 ) b as a n
axiom in W* in place of S a 2 S b = a l O. The system 9*may be
prime p, which divides g(n).
Let y(n, b) =v(b, n ) i v ( b . 1). so tliat
in place of asiom A, provided tliat we add the axiom SO that g(n) is primitix-e reciirsive and tlierefore f (n) is primitive
o-l=O. recursive.
For by S and Sb, The function I7 prr' is cnlled tlie cou,ae-of-rctlue function of
alb=O,b:c=O r<n
function of k + 1 variables and if &(n)is primitive recursive and To determine f ( n - 1, a) from the second of these equations \ve
satisfies A,(n)g n for r = l . 2 . ..., k, then the coiirse-of-values need to know the 1-alue of f ( n , z) not just for x = a , but for the
recursion value y(n, a ) of x, which of course raries witli n.
f (n+1)=B(n. f ( l i ( n ) )f, (;lz(n)),... , f ( U n ) ) ) The method of traiisforming this recursion (due to R. Péter)
is of considerable interest apart from the present application. If
is transformed into a primitive recursion by means of the course-
we calculate in tiirn the values of f (n,a) for n = 0. 1. 2. 3. and so
of-values function
on, we determine the sequence of terms
fin)
g(n)=p~'".p:'".... .pn ,
a>y(O, a ) , y(0, ~ ( 1a ,) ) ,./(O,y(1. y(-, a ) ) ) .
and so on. which are formed by repeated substitutioii for the
Por if y(n, b)=B(.n,v(b, 17,(n)),~ ( b&, ( n ) ) ,... , i ( b , &(m))),80 that y parameter. The essential idea of the transformation is to disentangle
is primitive recursive tlien
. ..
these substitutions by means of a function y ( n , a ) with the following
property :
for any n we can find p. q and for any p, q we can find n so that
+
so that g(n)is defined by primitire recursion and f ( n 1 ) is obtained With a suitable initial condition, like y(0, a ) = a , this function
by substitution from y and g. transforms any term like y(0, y(1, y(2, a ) ) ) successively into
Similarly, if í.(n) is primitioe recursive and ~ ( 0~ ,( 1 ~9 ( 2Y(O3
, a))))~ , a ) ) ) ,y(0, y(h,, a ) ) . and finauy
, ( 0~ , ( 1Y(h,,
into v(h3,a ) , for appropiate h,, h,, lb,, so that if y can be defined
by primitive recursion, and also the auxiliary function h,, then
so can f (n,a).
then we take g(n) as above and To construct such a function y(n, a ) we observe that, for any
n, n+ 1 is expressible in only one way in the form 2*(2q + l ) , where
+
in fact p =~ ( n1, 0 ) and q = [ ( n+ l)/2'+ '1, so that p and q are
primitive recursive functions of n (and of course 12 is primitive
$0 that y(n, g ( n ) )= f (n+ 1) and
recursive in p ancl q). IVe define
y(n. o(n))
s(n+ 1)=s(n).P,+,
as before.
(where p, q are the functions of n just introduced); since q t n f 1
6.1 RECURSIOX
WITH PARAMETER
SUBSTITUTION this is a course-of-value recursion so that y is primitive recursive.
Another recursion transformable to primitive recursion is To complete the transformation it remains t o show that there
recursion with parameter substitution. As an example of such a is a primitive recursive k ( n ) such that f(n, a ) = y ( k ( n ) ,a ) : first
recursion we consider however we introdiice g(n, a ) such that
TO determine g(n, a ) we consirler the relatioii
$1, ~ 1 ) )
= ; ' ( p , 1/l(!~(q,
=7p(2P(2g(q, S ) -- 1 ) . a )
so that f ( n )=v(h(n),0 ) : g(n)=v(h(n).1 ) . Tlie eqiiat,ioii (1,) iu evident with 0 for b : n-ith Sh for b the eqiiation gi
becomes Cs
Tt remrtiiis t o show that h(n) is primitive recursive.
. V ( X , 1 ) ) . q ( x )= Q(v(x,O ) , V ( X . 1 ) )
11-riting p(x) = P ( i ~ ( sO),
n-liich follo\r-3 by tlie substitiitiori tlieoi.eni (2.13) froni
REDUCTIO'IS TO PRIMiTIVE RECURSION 12.;
1 24
-
ItEDUCTIOXS TO PRIXITIVE RECURSION
-
+b = n + S ( b ~ S n )
b 2 n =S(b-Sn) .
1;
(ir)
(j')
P(a, 0 )
A:("."'P(f (c.a, 71). n ) -+ P ( a ,-
Sn)
- p v q and p v- -
For tlie schema we note that the hypotheses are equivalent to
r v S and so iniply p v S v (- r & q) which
in tiirn is equivalent to ( q -t r ) -t ( p + S ) as required.
(k') p ( a . n)
(The liypothesis (j') is the conjiinction of k(a, n ) terrns
To prove schema 1, we define g(n, n. b ) by the primitive recursion P(f,, n ) a P(f,, n ) a ... a P(f,. n ) n-here f , stands for f (r?n. n ) ) .
d o , a , 6 )=a To prove schema 1: we introduce first the function
g(Sn. a. b) = f (g(n.a. b) , b - S n ) .
F(a,n ) =
1 f ( x , a , n)
From hypothesis (i) follows P(g(b,a , b). 0 ) and thence < kío. ni r
e)
follows.
o < b + P(g(b o. n , b), O ) which by esample 3.103, satisfies
~ n ) ).
x g k(a. n ) + { f ( x , r l , n )F(tr,
From (1,) and the substitution theorem (3.43) we h d
Nest we define
Sn <b -+ { f(g(b1-Sn,a , b). n)=f (g(b'Sn. a. b), b ~ S ( b z S n ) ) ) G(0, n)= F ( 0 , n)
and so, by (1,) , G(Sa?n )=G(a, n ) + F ( S a , n)
S n g b + {f (g(b- S n , a , b), n)=g(b n , a , b ) ) . from which it readily follows that
But by hypothesis (j)
F ( a , n)a G ( a , n ) and G(a, n)á G ( S a , n)
P ( f ( g ( b z S n , a , b), m), n) -+ P ( g ( b L S n , a , b), S n )
From the second inequality, me derive, by induction over m,
whence we derive
S n G b -+ { P ( g ( b z n ,a , b), n ) -+ P ( g ( b ~ S na , b), S n ) ) and hence, taking b L a for m and using the implication
and since S n g b -t n g b, it follows by schema (m) that a ~ -tb (a+ (b-a)=b)
{ ( n a b ) -+ P ( y ( h ~ na , b), n ) }-+ { ( S n G b ) -+ P ( g ( b 2 S n , a , b ) ,S n ) ) v e derive
which in conjunction with (n) completes an inductive proof of (1') a G b + {G(a,n )gG(b, n ) ) .
equivalent t,o - -
which is proved by observing tliat ( A a ( B += C ) )-t (C a D ) is
d v ( Ba C ) v (C a D ) , and tlie equatiori In this section we define by recursion the processes of t,rans-
posit~ion and permutation, and apply the results obtained to
prove that the sum of a variable number of terms
follows from the equations (1:n)b = O , ( 1 :a)d = O.
We take Q(g(Sa,n ) , n) , Q(g(u,7t),n ) for A . B
a ( l ) l a ( 2 ) +... + a ( p + l )
and &(a,Sn), P(f (Su,n), n ) for C, D. is independent of tlie order of the ternis.
The implication A -+ B follo~vsfrom (1") since g(Sa, n )>g(n. n ) K e coinmence by defining iii terms of a ( k ) tlie function t ( k ,n,)
and similarly from f (Sa,n ) <g(Sa,n ) follo~vs by the recursion
Q(g(Sn.n). n ) + Q ( f(da, n ) ,n,) ;
but Q ( f (Su,n). n ) + P ( f(Sa,n ) ,n,)
-
it follows by induction orer r thnt
and so &(g(Sa,n ) , n ) + P ( f(Sajn ) , n ) 6.41 ~ ( pq ), + t ( p + q + l . r ) = t ( ~q +
. r+ 1).
l i.e. d+D. Denoting 1 :(l -I-z) by a(x)we define
From A + B , A -+ D we derive { A & (&+ C ) )-+ (C a D ) a(p,q)= d p , q L p).n(Sq-I-p )
so that
which is equivalent to
Gnsider first the equation with O for q, i.e.
+
which is equivalent to r ( 1 , p+ 1 ) = r ( 1 . P ) U ( P + 2 ) "hich f~llows It follows esactly as in 6.422 above that
from the definition of T .
With g + 1 inst.ead of q. (atid using 6.121). equation 6,42 is equi-
.xhicli follows from 6.41. and this completes the proof of 6.42. We prove nest the three equations
6.422 It follows that
Fiirther, since
Hence if b(r, S , k ) = a(B(r,S , k ) ) then
and
t ( 1 ,r + l ) = t ( l , r)+a(r+2)
I
therefore
TO f ~ r mthe sum ~ ( 14 -) 4 2 )+ ... + a ( n ) with a ( r ) and a ( r + s )
tra,ns?osed we introduce t * ( r , S , k , n ) and a*(r, S , p, q ) by the P ( k + 1 , r ) -t P ( k , r+ 1)
equations and P ( k , r ) follows b y the generalised induction schema 1,.
Hence P ( 0 , r) follows, and this is equation 6.451, which completes
the proof of 6.45.
The proof of 6.46 proceeds along similar lines; mith q=O the
KEDCCTIOXS TO PRIV~TIX-E ~LE('L-RSIOT 1::s
132 REDUCTIONS SO PRI3IITItLE EECURSIOX
siibstitnti~igr L 1 for r we derive
equation is eviclent. With q - 1 in place of q the equntiori is cqiii-
valent to
t * ( r + 1, q + 2 . r - 1 2 , q ) = t ( r i - 2 . y )
and licnce, by the siibstitutioii theoreili. using the equation
6.461
1 - - ( r 1~) = 1 . - ~ (~1 r ) .
wliich follows from ( l A r = ( > )+ R ( r . q l 1 . r - 1 1 - q ~ p ) .
6.462 t * ( r + 1, q+E12, r 4 2, q ) = t ( r J - 2 , y). Siibstitiiting s L l for y it follon-s tliat
\Ve denote 6.462 by R(E,q). ITe readily establisli {(l's)=O} -t ( ( l A r ) = O + R ( , . . s. r f ( s ~ l ) - p ) : .
for the equation liolds for x = 0. and tlie equation iii x implies that Since ( ( u + ~ ) ~ + u ) ~ gLJ' )( <
z ~( (. U + V ) ~ + U + ~ ) ~
mith S x in place of X . F(w, x ) is derivable from ~ ( z cx ?) by sub- therefore R t J(u,>a ) = (U + u)?+ .
stitution only since
E J ( x . c)= z:
F(20, x ) = V v ( w ,x ) .
and E R.t J('IL.v) = I L .
Next define ~ ' ( wx ), by the iteratioii
so that CJ(.u.C ) = I L , VJ(.zl.u)= v .
1 , rpf(.w,S x ) = ( 8 ' ~ ' 5( )~ ,
$(w, O ) =cc'(¿c)
This second set of pairing f~inctionshas the additional property:
where ~ ' ( w=)J(0. a(uj)), @'y=J ( S U y , (8(Uy, V y ) ): if ESz>O then U S x = U x and V S x = S V x ;
as before we prove for if E Sx'O theri S x is not a square and so
- Rt S x = R t x
v'(w9 S ) =J ( x , v(tu, 4 )
by observing that this equation holds for the value O of x, and that whence Z J S x = E R t S x = E R t x= Ux
' J ( S U J ( x ,~ 4 ), B(UJ(x,,d..
( 2 % 4) I V J @ >P ) ( ~ ~ .4
> ))) and V S z = S x 2 ( R t S ~ ) ~ = ( l i x ) = x( R) t~
=J ( S x , j(x, . ,
rp(w, x ) ) )=J ( S x , ~ ( u i8x1) = { x1( ~x)"t - ( 1 {(Rtx ) ~ :2 ) )
so that v f ( w ,x ) =J ( x , v(w, 2 ) ) = { x i ( R tx)?)+l=S V X
implies rpl(w,S S )=J ( S x , ~ ( wS x, ) ). siiice E S x > O entaiis (Rt Sz)*<Sx and therefore (Rt x)?< x so that
(Rt x ) ~ = =x 0 (which by example ?.S3 liolds also when E S x = O ) .
The function v' is defined by iteration without parameters and If we now define G ( x ) by the recursion without parameter
Ux=E Rt x , V z = E x . =G S X ,
138 E L I Y I S 4 T I O S OF i'1R iJIETERS ELIXIXATIOS OF P . \ R A J m T E R S 139
and if ESx>O then aiisiliary functioiis al1 of wliich are definable by siibstitutioii in
ternis of the functions
F ( U S x , V S r ) = F(C'.z. S V x ) =h (E'(C'x,V x ) )
=c(x. F(CIx, V x ) )
whicli we shall cal1 the initinl fiinctions.
itnd so froni the Iiypothesis G(x)= F(U X . V x ) we derive
We llave therefore proved tliut if t h r . foli
~ ~ r functionx nrc n cailnble
C ( 5 x )= F(C7Sr,V Sr) fhen nll primitive recllrsire fztnctions rrrr ohtninnhl~hy s~rhstitiltion
and clpplicntion of the ,;.ingZr schemn
which completes the prc~of.F is ohtnined frorn (? by t,he substitution
F.r= -4 -0
fnr g~nerntin!]f~c?l('fion.rof »?ir vrrrinhlc.
- L .
The variable x may be eliminated froni c(x. y) exactly as from the 7.1 It can be showii tliat in fact jii.jt tlie two initial fuiictions
functiori F! above. JITe define
11 - 11 ,
I H O=O, H S x = d H z are sufficient but this rediictioii ir1 the initinl fiirictioiis tlioiigli of
where great interest iii sliowirig tlint a sirigle fiinctioii of twn variables
enables us to reacli ail primitive recursive functions of aiiy number
cíy =J ( S l;yl C( a?/?
vg)) , of variables, is iiot esseritial to oiir plirpose and xviil be omitted.
H x =J ( x , Gx).
7 . 1 I n the coiistruction of primitii-e recursive functions of m e
The proof of the case x= 0 is evident, and from the hypothesis variable it is never necessary t o define by siibstitution a function
HX=J ( x , Gx) follows of more than one variable. For instaiice if we can obtain a function
f ( n ) from a function F ( x . y ) by taking. say.
H Sx=d Hx=d J ( x , Gx)
f ( n )= F(g(n).N n ) )
=J ( S x , c(x, Gx))
with F ( x , y) defhied in ternis of given functions n(u. t . ) , b(z, y ) ,
=J ( S x , G S x )
c(x. y ) by the siibstitution
as required.
F ( x , y) =a(b(x.y). c(x. y)).
Thus Gx is derived from H x by the substitution
then since
G x = V HX f ( n )=a(b(ll(n).h(n)).c(g(n),
and H x is defined by the schema instead of definiiig the tnro variable functiori F ( x , y) we coilld
define the one variable functions
H O=O, H S x = d Hx,
S(n)==h(g(n),h ( n ) ). ;J(~L) = c(g(n).h(n,))
so that H x =8 0 . aiid so define f ( n ) directly by
To carry oiit this reduction we have introduced a number of f ( n )= 4 P ( n ) .:,(n)).
140 ELIMINATIOX OP PAR.\XETERS
It follows that. one variable prirnitive reciirsive functions Tlie sequence contains the initial functions 0. n, Sn. and R t n.
niay be obtained usiiig only the schemata If it coiitnins the functions g(n) and It(n) then there are integers
.
, f (n)= g(,n) h(n) j (n)= g(n).h(n) ,
f (72) =.g(n) i1~(n) p. q such that
f (n)= R t n , f (n)= g(h(n.)). f (n)= gnO .
--
, . a Tliis last result enables us to enumerate al1 oiie-rariable If \ve choose a value of nl for ~vhicli?,(m,1)- p, v ( m . 2 ) = q tlien
primitive recursive functioiis. n-e shali llave
Thc enumerating function is pm(n)defiiied as follo\vs:
for the f i s t four fiiiictions iii tlie enumerntiori we take the fiiiictioiis
O. n, Sn, R t n, so that such a valuc of m is for instance
S e s t me assign five ranges of values of 7n to the operntions + , -. ..: where the factor 7 has been incliided to ensure tliat 111 > 3. Denote
substitution and recursion. Denoting as in 5 4.61 the exponeiit
of the greatest power of the kth odd prime in n by ~ ( nk), , we
Y . 3P.5q.7 by m, S 0 tl1at
associate eacli operation with tlic cases ~ ( m0), = 0, 1, 2 , 3 and v(nz,. O) = k . ?,(m,. 1)= p , v(n¿,, 2 ) = q and ni, > O
v(m. 0) > 3, for values of m > 3. Consider riQw tlie function qm(n)
ancl therefore for tlie valiics l;= 0, 1, 2 . 3 the functions vmk(n)are
whose values are listed in the following table.
1 respectirely
Vntk(O) = O 3 ~rn,(n+1)=3(qrnk(n))
f(n)=@
tchich is verifinble but not provable in g*.
This remarkable result. n-hicli n-as discovered by Kurt Godel
in 1031, suggests that the natural niimbers may iiot be the only
class of objects for mhich the provable formulae of W* are verifiable
and that there may exist a class of entities wliich includes the
natural numbers and other eritities besides for mhicli the prorable
formulae of 9*are verifiable. Tliat such a class in fact esists was
actually established three years after Godel's result, by Thoralf
Skolem, the inventor of resiirsive arithmetic, m110 shomed (in-
dependently of Godel's methods and results) that not only systems
like %
. ! o r g * , but every formaliscition of arithmetic fails to characterise
the number concept completely and admits as values of the number
variables a class of entities of which the natural numbers form
only the initial segment.
5.1 The construction of tlie unprovable equation
f (?¿)=O
is effected by means o€ a code in which the terms of B* are
expressed by numbers, aiid the syntas of 9*by primitive recursive
relations. This code is called a Godel numbering of d*.
GODEL >TTIIBERIP~G AND THE ISCOMPLETESESS OF .\RITHXETIC 145
We shall take the variables of .9* to be m , n, z,. %, 2, ... ; the where p , is the kth odd prime. From the iiumber of the formula
functions to be yo(n),pl,(n), q,(n). .. . together mith m + n, m. n alone we can w i t e down the full forniula. simply by factorising
and m - n ; and the proof schemata to be the formula-number. For instance the number of the formula
Sb,
since 'S' is standiiig for '9,'.
Sb, Siiigle signs all have odd numbers, but the nuinber of a sequence
is necessarily even.
For axioms me shall take
Of course 'nonsense' sequences of symbols like
also have numbers but this does not gire rise to any complications.
the defining equations of the functions m.+n, nz2n and m . n ,
and the deñning equation of v,,(n) m l y . 8.3 Kext we observe that since a proof iii .%'* is a sequence of
Thus the various primitive recursive functions of one variable formulae then proofs too may be numbered. Thus a proof which
are all deñned by the single asiom, the defining equation of consists of a sequence of formulae x-itli numbers
plm(n).
8.2 The several elements of 9*are numbered as follows: to tlie is assigned the number
functions pl, we assign the numbers 4k+ 17 , k= O, 1, 2, ... and t o
the variables x, the numbers 41; + 10 , k = 1 , 2, ... . The numbers
of the remaining signs are as indicated in tlie table so tliat if N is the number of a proof and X: is the greatest value
of r for which v ( N , r ) > 0 (and therefore iV is divisible by a non-zero
power of p,, and p, is the largest prime for mhich this is true) then
v ( N , k) is the number of the formula proved by proof number N.
NOW any formula of g*is simply a sequence of signs of W * ; We shall see how t o single out the values of N which are in fact
numbers of proofs.
are the numbers of the componeiit signs in a formula (in the 8.31 Like all formulae the axioms of 9?* may be numbered, and
correct order) then we assign to the formula the number we shall denote by A,, A-, A,, A,, A5 and A, the numbers of the
6 axioms. We shall have no occasion to require the actual values of
the numbers denoted by these letters. We denote by Ax(n) the
CODEL S C M B E K I N < : A S D TTí!: : S C O M P L E T E N E S S O F ARITII~KETIC
-
dkjiinction n = A, v n = -4, v n 8, v n A4 v n = A5 v n = A6 which
aays that 12 is the nurnber of ari asiom.
;=
instarice. thc iiiimber of 'q~,,(m)'is .'33.3".515.7' aiid tlie number
147
I , = O if f is odtl, and if f is even 1, is the least integer ín such that f the variable whose numknr is z, is to be replaced by object number n.
is divisih!e by tlie mth odd prime but not by any greater prime). Let us tlien deñne
Tlie predicate F ( n ) which says that n is the number of a formula
may now be expressed by R(n, 2) = 0 & Af.+'{R(v(n, r ) , 2) = 1).
and
S.5 Bti.fore we consider the fundamental syntacticd operatioii
of siibstitiitioii we introduce the primitive recursive function
m A ri -,rI;íc!i determines the number of the espressioii formed by then Sub,.(c/n) is the desireci iiurnber of the espression obtained
v~itin: es~ressionnumber n aftcr expression number m. For by substituting object riumber n for variable number t. in formula
number f . For instante, the number of the formula the formulation of the predicate 'n is the iiumber of a proof'.
To this end we must consider the relations between the numbers
of premisses and conclusions ir1 the derivation schemata.
-
by substituting a recursive term for a variable in a recursive term.
The numbers of the functions m + n, m n, m . n and q,(n) are
representing function of the equation which G ( m ) denotes is in a simple sequeiice, starting with the pair f,, fl followed in turn
expressed. However the assertion that this equation is not provable by f,, f 2 : f,, f 3 ; fl. f z : f,, f,: fl. f,; f,, f5: fl. f,; f2,f, alid so 011. thepair
is equivalent to saying that noiie of the numbers O, 1, 2, 3, ... is +
f i, f coming (e2 i + 1)"' or (e" e - i l)th in the sequence
the number of a proof of equation niimber St,(lS/p), i.e. that according as i + j is even or odd, where ?e is the greatest even
each of the equations number contained in i j.
For any two fiinctions p(t). y(t) we can find a iiionotonic
iiicreasing functioii v(t) siicli tliat one of the relations
holds and is therefore derivable in g*.
Thus there is a primitive recursive function 1 such that each of
the equations holds for all values of t: to determine v me dix-ide the natural
numbers t into 3 classes C,, C= or C ; according as the relation
-,, = or > holds between pt and yt.
ia provable in 9*:
biit the equation ,4t least one of the three classes is infinite and we take the
members of that class in increasing order of magnitude as the
values of v(t) for the values 1 , 2, 3, ... of t, and we m i t e T- for the
with a free variable m is nof provable in g*. relation ( < , = or > ) which holds between pu(t) and yc(t) for all
values of t.
8.9 The presence in B* of an unprovable equation is not a mere
Next me define in tiirn vl(t), ~ ( t ..). with associated relations
accident arising from the particular axioms of 9*; we may add
VI, V,. ... as follows; vl(t) and Vl are the function and relation
as many more (verifiable) asioms as we please t o B* and still determined as above so that
carry through the foregoing construction. I n particular me may
add the equation f ( m ) = itself
~ as an axiom and still determine
an unprovable equation in the extended system 9 2' say. This result for all values of t ; then we take fozl and f,v, for q and y and
suggests that the natural numbers O. 1, 2, ... do not exhaust the
determine v,, V, so that
values of the variable.
We can in fact readily show directly that the natural numbers
do not constitute the largest class of objects which satisfy the
for all t. Ir1 this way we determine step by step u,, V,; 77,. Y,: ... ;
axioms of recursive arithmetic.
u,, V,, so that
8.91 To this end me prove that, given any sequence of functions
fot, flt, f2t, f3t, and so on, (recursive or not) there is a monotonic
increasirig function g(t) and a fiinction v(i, j) so that, for all i, j, for all t , where n is the ordinal of the pair fi, f j in the orderiiig
one of the relations prescribed above.
fi g(t)< f j g(t) 9 f
f i g(t)= j g(t) 2 f i g(t)> fjg(t) Write g(n)= c1v2 ... ~',-~c,(n)
holds for al1 t v(i, j). so that (taking t = n in equation E)
\Ve start by arranging all pairs of functions f,, f,, with r t s , f is(n)vJig(n) .
Similarly substituting T,, -,u,,, ... I * , , _,(t) for t iii crliiation E for if thcrc \vere a fiinctiori Ii such that f ih <f l . tlien n.e
we fiiicl that fiy1r2... r , , - o (t) J-,, jl ... i',, . ,,(O shoiiltl ha\-e
for ali t. and tliereforc. takirig t = ?r -' p.
8.93 Let iis now take for fa. j,. f?. f,. ... tlic secjuencc of al1 orie
xvhich proves tliat g(n) is moiiotoiiic iiicrcasirig. variable primitive reciirsix-e fiiiictioiis ~rrit!i ,/, as tlie zeio fiiiictiori.
I We shall show that al1 tlie triic stntemcnts of rcciiisivc nrithinetic
S.!Y!!:y riieans of tliis theorem we niay introdiice a linear orderiiig reniain valid if me tak? j,. f,. j2. f,. ... i i i p!ace of tlir iiatiiral
betn c.en tlie functions fa. f,. f,. f,. ... . nambers.
\T7e write Giveii ltiiy rcciirsive fiiiictiori
F(.c,. .-. ... . x,,)
accortiiiig as T7,, has tlie value <, = or >, i.e. according as of iiatural iiumbers, wc iiitroduce function variables g l ( t ) .y2(t),...
xvhose 'valiies' are the fuiictions f1 . f 2, ... .
For eacli assignment of raliies of tlie variables
for iili t , n. It is readily verified that
+
+
for the values a,, a,, ... , a, of the arguments x,, x2, ... , 5,.
Thus a functiori of natiirnl number variables may be interpreted
as n function in the space of tlie furictions f,.f,. f2. ... q-ithoiit Solutions to Examples 1
ir0 chaiigiiig its sigriificance.
1. We define in tiirri
S.94 Under this interpretation a t,riic eqiiation (whetlier an
asiom or derived from the asioms) Peiit(x, O ) = 1 , Pcrit(x. Ry) =Tet(x, Pent(x. y))
Hes(x, O) = 1 . Hes(x. Ry) = Pcrit(x, Hes(x, y ) )
. . x,,)
F(x,,s,, ... . ~ , ) = G ( s , . x ~...
Hept(x, O ) = 1 , Hept(x. S y ) = Hes(x. Hept (.c. y)).
becomes a true equation in the function space; for if this-equatiori
holds for all x,, x,. ... . .x,, and if i, j are the sufises for-which *,
factors.
F(fic,, f k 2 >
1.4
+ -
I f k ( x ) = l ~ ( x - 2 )then
f ( x )= k(x)g(x) (1 k(x))h(x).
Let Q(x,y), R ( x , y) denote quotient and remainder when
x is divided by y and H f ( x , y), Lm(x, y) the highest common
5.95 Since we have defined equality and inequality independently
factor and least common multiple of x, y. Then
it remains t o be verified that the equations x <y and x y = O are
R(0, 2)=O, R ( x + l , 2 ) = 1 ~ R ( xS,) ,
-+
equivalent under the fiinctional interpretation.
+
Q(O, 2)= O , Q ( x 1, 2)=Q(x,2) R ( x , 2),
For the truth of f S f i we require fg(t) G fig(t) for t > v(i, j ) ; H f ( x , 2)= 2 R ( x , 2) , L m ( x , 2)= x { l + R ( x , 2 ) ) .
for the triith of f f = O, ~vritingf l f = f k , we require Similarly
fd(t) = f,,q(t) for t > v ( k , O ) . R(0, 3)= 0 , R ( x ; 1, 3 )= (1 -I- ( R ( x ,3) l ) ] S R ( x ,3 ) ,
&(O, 3)=O, Q(x+ 1, 3)=Q(x,3)+ ( R ( x ,3 ) - 1 ) )
Since f&(t)= f;g(t)2 fjg(t) and f,,g(t)= 0, therefore the conditioiis
fh54t) = fog(t) and f i ( t )G f s ( t )
are eqilivalent for any t, which completes the proof. 1.5
-
H f ( x t 3 )= 1 + 2(1 R ( x , 3 ) ),
L m ( x t 3)=x{3 2(1- R ( x , 3 ) ) ).
+R ( x , 2)h(x).
f ( x )= (1 A R ( x , 2))C/(x)
153 S O L ; -YI<::;S TO I..S.:SIPLI:S
1.6 If C(n,r ) is the coefficieiit of z' iii tli:. rspaiisioii of This esample shorvs that a functiori G(p. n) defined by
( 1 + x ) theii
~ doubly recursive equations R, may be obtained by the
C(n, 0 )= 1 , C'ic). r -- 1)= U substitiition G(p,n ) = y ( p $ 1 . n + 1)
C ( n + 1, r $ l ) = c ( n .r)-;-(?(iz.r :- 1 ) : from the doubly recursive functioi: y(p, 11) n-liicli satisfies
the function {.'(í?. ); is iiel-eriticicss píiniit Ii-e r.cciit.~i~.c.. the simpler introductor' equations
Ir ! is pririiitiue recurciv~c:itl (,,'(;?. ,-) = n ! ir! ( n - r ! !
, f (nl T 1, 7 t l + 1, n3)))
c ( ~n,,~ n,,
fi(n,. ~t,,12,) =f +
(72, 1, n,, d(n,, n,, 72,. f l . nzL 1, %)))
1.9 C(O.n ) = y ( l , n + l)=?.(O, n , y(0, p(0, n,y(1, n ) ) ) y(1,
, n))
and
SOLGTIONS TO EX.%JIPLES 161
- .-"32 a ( b ~ O ) = a b = a b - a . 0 ; a ( b - S c ) = a ( ( b ~ - c ) ~ i ) = a ( b ~ c ) - a
9
-
Let d x , y ) = ( f ( x , y ) , y / , then ~ ( 0y ), = 0
and q ( S x , y ) = ~ ( xy ), so that (1 q ( x , ?j))q(Sx,y) = 0 ,
2.24
2.241
By theorem 2.63, (1 In. bl}(hI - n )= (1 I- la. bl >(b b) = O
Use 2.232 aiid 2.24.
- .
whence q ( x , y ) = O and so f ( x . y) =y.
Write f ( c ) , g(c) for a(b+c), nb+ac respectively: then 2.242 If f ( u , b ) = ( b - a ) ( S a l b), theil f (a, 0 )= 0 .
f ( O ) = nb = g(0) aiid f ( S c )= a(b+ S c ) = aS(b+ c )Ff ( c )+ a , f (0, b) = b ( l b ) = 0 ancl f (Sn. S b ) = f ( a , b) so that f (a, b )
g(Sc)=ab+aSc=ab+ (ac+a)= y(c)+n. satisfies the same doubly recursire introdiictory equations
Thus f ( x ) and g ( x ) satisfy tlie sariie introductory equations, as the zero function Z ( a , b) =O.
so that f (c)=g(c). 2.243 Proof as for 2.342.
(ab) O = O = a(b. O ) ; (ab)Sc= (ab)c+ (ab) and 2.244 as above.
a(b.Sc) = a(hc + b) = a(bc)+ (nb), wlience the proof is com- 2.2441 as above (using 2.201).
pleted as in 2.01.
2.245 If f ( a , b ) = ( b - a ) + ( S u ~ - b ) and g ( a , b ) = l + ( a ~ b ) + ( b : S a )
(ab). (cd)= a(b. (cd))= a((cd).b ) = (a(cc1))b then f ( a , O ) = S u =g(a, O ) , f ( O , S b ) =Sb = g(0. S b ) and
= (ac). (db) .
= ((ac)d)b f ( S u ,S b ) = f( a , b ) ,g(Sa, S b ) =g(a, b).
If f ( x ) = x ( l - x ) , f ( O ) = O and f ( S x ) = O . 2.246 Proof as in 2.245.
2.25 Use clouble recursion as in 2.245.
2.251 Substitute O and S r in turn for r.
(1I-O)+ (1-(1-0))=SZO, ( 1 - S x ) + ( l I - ( 1 I - S x ) ) = S Z S x
so that (1-x)+{l-(1'-x))=SZx=l . 2.26 a ( x ) - 1 = ( l - 1 ) - ( 1 - x ) , by 2.22, and so a ( x ) - 1 = O .
a-(b+O)=a-b=(a-b):O ;
a ~ ( b + ~ c ) = a - ~ ( b + c ) = { a ~ ( b +,c ) } ~ l
+
-
u ( x ) (1 a ( x ) )= 1..
&(O) O =~ ( S -Sx=
+
4 0 ) ( 1 -&(O)) = 1 , ~ ( S X {)l ~ ( S X=
+
) 1) so that
X ) O, proving a ( x )- x = O .
and ( a - b ) - ~ S c = ( ( a - b ) ~ c ).~ l x . a ( x ) = x - x ( 1 - x ) = x ; a(l-x)=l-(l1-(l-x))=l-ar(x).
Use esample 2.21. a ( a ( 0 )=) a ( 0 )= O , u ( a ( S x ) )= ~ ( 1=)1 = ~ ( S X )so, that
a ( a ( x ) ) = a ( x ) . Similarly 1 ~ a ( x ) 1=- x .
( a + O ) ~ ( b + ~ ) = a - ;b
a(x)-a(x)=a(x)~(l~x)a(x)=a(x)-{l~a(x))a(x)=a(x), by
(~+Sx)~(b+Sx)=S(a+x)~S(b+x)=(a+x)~(b+x), 2.1
whence the result folíows as in example 2.
Furthermore
a ( O ~ l ) = O = a . o - ;~a ( S x - 1 ) = a ( S z = S O ) = ~ and
a - S x 2 a = ( u x + a ) - a = a x , by 2.23. ) 0 = a ( O ) - a ( y ) ,U ( X , O ) = O = a(x).a(O) and
& ( o - y=
K(SX-S~)=OL(S(X+~+X~))=~=~(SX)~K(S~). 2-29 By repeatecl use of the formulae a + S b =SCL+ b. and
Finally from f .g = O follon-a a ( / - 9 )= 0 and so ~ ( f ..\(g)
) =O, l=SO, 2=S1. ... , I)=SS. 10=S9. we hare
n ( f ) . g - a ( q ) = O .* ( / ) . y = ( ) . 3 . 2 = 3 - S 1 = 3 - 1 + 3 = 3 + 3 = 4 - 2 = 5 . 1=6. niid similar]?
4.2 = S. S e s t me proceed thus :
c b ) , g(b. C) =c, theri
?..>ti1 If f (b, c ) = { b l b .&(c. b ) ) ~.'.(c.
f ( 0 , c)=c=g(O. c ) : f(b. U)=O=y(D. U) :
3.7=7.3=7.S2=7.2+7=(7-7)+7, aild
f (Sb. S C )= (b' 1 ) ( 1: & ( C . 6))7 ( c - l).u(c.b) 7+7=7+(3+4)=(7+3)-4=10+4,
( 1 0 + 4 ) + 7 = 1 0 + ( 7 + 4 ) = 1 0 - ( 7 + 3 ) + 1 = 1 0 + 10+1
=f (6. c ) + { 1 = .\(c. b ) ) t n(c, h ) =Sf (h, C ) = 2 . 1 0 + 1 so that 3 . i = 2 . 1 0 ~ 1 .
and g(Sb, S c ) =Sc=Sg(b. C) , so tliat f ( h . c ) =g(b, c). Similarly 4.7 = 2.1 O -:-S. So el-aluate 34.27 me tnke
(3.10+4) (2.107 7)=(3.10-4)2.10+(3.10+4)7, by 2.01,
=6.102+S.10+(2.10+ 1 ) 1 0 ~ 2 . 1 0 + 8
= ( 6 + 2 ) 1 0 2 + ( S ~ 2 ) 1 0 ~ l . 1 0 + S = 9 . 1 0 2l.lO+S.
+ by 2.01
agaiii, and 2.03.
.I
1 Substitute O nnd Sc in turn for C:
0.32 { x i ( 1l x ) ) f = ( 1 :-
(
.
L
.' 1))f = f ( x l l ) f whence the result
2.272 Use double reeiirsion as iri 2.245.
1I folio\rs by 2.31.
- -
2.273 XTrite f ( a , b, c) for ( 1 ( 1-a)b) ( 1-ac)b
and g(a, b, c ) for ( 1 ( 1 -a)h) ( 1 2 c ) b
then f ( a , b, c ) g(a, b, c )
2.33
so (Sf -g)h = O, since, by 2.242, (Sf l g ) (g f )= O. -
From ( 1 -L ( g 2 f )}h= O we derive (Sf - 9 ) ( 1 2 ( g f ))h = O and
and -
d a , b, c ) f ( a , b, c )
l
l
2.34
2.341
Use 2.2441.
O = ( l ~ f( )1 - a ( g ) ) = ( 1 2 f ) - a ( g ) ( l ~ f ) = ( l - f ) ~ a ( g ) ,
2.074
ñ-hence it folloms that 1f , gj = O and therefore f =g.
Substitute O and S a in turn for a.
i, -
since f.a(g)=O; but a(g)-1=Oandso ( l l - f ) a ( g ) l ( l = f ) = O
whence m ( g ) ( 1 f ) = O. Accordingly In(g), 1 f 1 = 0 and
so a ( g ) = l - f .
, xm.XSn = (xm- xn)x
i
2.28 zm.fi=xmi.=xm+O
and p+sn=d(m+n)=xm+ , whence 2.281 ~O~~OWS.
(.")O = 1 = xm.O , (xm)Sn= ( x ~ xm )~. I 2.351 To f"g=O add ( l = f ) f g = O aild use 2.32.
and ~ . S n = x m n + m = X m n . x m , by 2.281. !
-
( g ~
: ~1
write f ( x , z ) = ( x - - I / ) - z , g(x, z ) = ( x - z ) + { ~ - ( 4
then f (O, z ) =I/ z = g(0, z):, f ( x . O ) = 1:+ y = g ( x , 0 ) alid
- -
p ( c - n ) = p ( b 2 a ) . Or from plb. cl = O me derire in timi
1 pb. pcl= o, pb =pc and hence from pa pb =;va pb follon-S
p n ~ p b = p a ' p c , etc.
S-). =g ( x , 2 ) .
f ( S x , S z ) = f (x.5 ) , ~ ( S X
2.452 Tiiis follows from 2.451 aiid 2.1
Siibstitiite 1 for y snd x - a for z iii 2.41.
2.453 This folloms from 2.451
Double recursiori. using 2.42. The . common -value of
a - ( a - b ) and 6 .- ( h L a ) is the lesser of a , b, denoted bj:
min ( a , b). Or wc ma5r use equations 2.62. 2.61 1 a ~ i d
exanlple 2.22 as f o l l o ~ ~ s :
a-(a~ó)={(~+(6~a))~(b-a))~(a~b)
={ ( b + ( a ~ b ) ) + ( a - b ) ) ) ~ ( b : n ) 1.461 ( u ~ c ) (~ i( c r ~ b )( }{=( ab ~) - c ) i b ) { l ~ ( a - b ) }
=b.-(b-a). = ( ( a - ( c - b ) ) - b ) ( 1 - ( a - 6 ) : : sincc b - c = O .
= ( ( a ~ b ) - ( c - b ) }( 1 - ( a - b ) ) = O .
(a-b) (Sb-c)=(~(:b) { ( ( a + S b ) - ~ ) I - c )
=(a-b){((a+Sb)=~)~a} 2.462 p(n - c ) = p { ( ( a$ b ) - c ) -- b )
= (a:b){[(a-c)+ {Sb2(cLa)}lLa}
=p{[(b~'c)~{a2(~-b))]~b)
=p{(a-b)-(c-b)j=O. since p ( b - c ) = p ( a - b ) = O .
=(U.-b){(Sb-a)-(c-a)}, since ( a ~ b( a) L c ) = O ,
2.47 From (1-a)c=O and (1-b)c=O we clerive c ~ b c = Oaiid
= O , by 2.242.
It follows of course that ( a b ) ( b - e )
.
- = O: since -
bc-abc = 0 whence, by 2.462, c l n b c = 0 , t-hat. is
(1 ab)c = 0.
-
Sb-c=(b-c)+(l-(c-b))
3.4701 From ( 1 ~ a b ) c =
O follows ( 1 -nb) ( 1 :a)c= O which added
By 2-41 and 2.32, ( a - b ) (c-b)=O follows fi.0111 t o ab(1 :a)c = 0 yields ( 1- a ) c = O ; similarly ( 1 b)c = O.
( a - b ) ( S c - b ) = ~ ,a n d ( a 2 b ) ( c - b ) = ( a 2 b ) { ( ( c i a ) ~ a ) - b ) 2.471 From ( l = a ) b c = O and nbc(1- b ) = 0 %ve derive, by 2.462,
>
--(a-b){((c-a)+a):b)=(a~b){a2b+((cLa)-(b2a)), bc(l~nb)=O.
whence (a-b)z=O and SO (by 2.233) a-b=O.
2.472 ( 1 - l a , Ll)c=(l - ( ( a - b ) (b-CL)))~
' -
and denoting Rt x by Rx for brevity,
(1 (SSx- (SRX)~J)RSX
2.35.
-
= (1 {SSx- ( S R X ) ~ }and
) so by
(1 {Sx- (SRx)?))(1 { ( R X ) ~ ((RSX)~-T-SX)
and therefore by (vi)
(12 ((Rx)~=x))((RSX)~-SX) =0
~~)) =O
(1-{SSX-(SRx)?)).(Rx. RSxl = O ...:............... (i) which together with the equation (RO)?I O = 0 proves
By theorem 2.68
-
(1 1 Rx, RSx1) (1 (SSx- (SRX)~))
Multiplying (i) by SSx- (SRSX)~
(SSx- (SRSX)~)
and adding to (ii)we find
= O . . (u)
2.9
(RX)~-X = 0.
-- -
follows, by esarnple 2.47
By esample 2.241, multiplying the introductory equation
(1 (1-n!)} (1 (n!)Sn}= O
by 1 1 (SRX)~, 8x1 we obtain
i.e. (1 (1~ n ! ) (1 ) 2(Sn)!)= O
(1 -I(SRX)~,Sxl}. RSx= 1-.-{I(SRX)~, SzI}-SRX
which, Tvith 1 O! = 0, proves 1-n! = O. Further,
and so
(SO)! = 1=%(O) ; (SSn)!= ((Sn)!}SSn and
(1 21 (SRX)~, 8x1). 1 RSx, SRxl= O . . . . . . . . . . . . . . . . . . . . (E)
n,
IT,(Sn) = (n).SSn
Again by theorem 2.68
-
(1 1 RSx, SRxI ) (1 1 (SRX)~, 8x1} - 1 (RSX)~, SxI = O .....fiv)
mhich proves that (Sn)!=1T,(n).
and so adding I(RSx)2,SxI times (iii) to (iv) we find
(1 -I(SRX)~,8x1). ~ ( R S X8x1
It folloms that
) ~ ,= 0 . . . . . . . . . . . . . . . . . . . . (v)
2.91
- -
From (1-c)(l-(1-c)}=O
-
and
(1 (1-a) (1 b)} (1- a ) (1 b) = O follow the two equations
( 1 - ( l l n ) ( l ~ b )(1-c)
} {(l.-(1.-c))-b}=O
(1 I(SRX)~, 8x1 j {SxL (RSX)~) =O (1-(1-a) ( l = b ) } (1-a) ((12b)'-(1-c)}=O
and therefore
(1 1 (SRx)" 8x1) {SSX (SRSX)~} -
From (A) and (B) by example 2.34
= O . . . . . . . . . . . . . . . . (B)
whence by esample 2.47
(1- (1A ~ (1) 2 b)} (1~ a c {l) 2 (b + (1l c ) ) } = O
3.171
3.1s
3.14
3.101
3.101
3.193
+
+- SOLUTIOSS TO EXAYPLES
-
and l g a - t a = l + - ( a - 1 ) ,
kn lb = k ( l + ( aA 1 ) ) 2 l(k -E ( b 1;))
- -- - -
= k ( a L l ) A l ( b - k ) , by esample 2.13.
and thercfore
l g n & m g n&n-l<n-n~
P>Q
-
b ~ i tn ~ l < n - r n + S ( n ~ l ) < n - r n
-> { S m +- ( r ~ m ) ) - S ( n 2 1)
=sm+ ( ( n - m ) - S ( n ~ 1 ) )
-+ l = S m + ( l - S m ) -> l>vt.
{p=q+(plq)) {r=s+(r-S))
. ..
= (k (6 k ) ) ( a 1) (1 -E ( a 1 ) ) (6 E ) , by t.lie same example
=b(a~l)~a(b-k).
h > : c + b = c + ( b l c ) aiid
b=c+(b'c) -+ ( n + b ) ~ c = { n i(IJ~c)+c):c
1 ~ 4n n - l + ( n ~ l, 7) n . g n -t n=rn+(u-m.)
- -
+ ( ( p + s ) ~ ( q ~ r ) } = ( ( q + s ~ ( p - q ) ) :' (s q
(""){f(x)-f(o))=o.
=(p-q)=(r-s)
Denote the implicatioii by P ( n ) .P ( o ) is siriiply
+(rLs))}
3.31
3.32
3.311
3.322
3.33
n < b -+ a ,-b 4 c we derive P ( n ) -+ { ( xa n ) -t ( f ( x )< S , ( S n ) ) .
Hence by example 2.47, P ( n ) -> { ( x ~ nv )(x= S n )
-+ ( f ( x )á Z , ( S n ) ) )and tlien by esample 3.11 n-e derive
P ( n ) -t P ( 8 n ) rrhich proves P ( n ) by incluct,ioii.
~ ( n= Z,(n)
)
-
froni a proved cquatioii f (.r, a ) = O wr derive f (O, a ) = O
aiid f (Sn,a ) O and tlierefore
(1 S,(n))Z;(Sn)
-
Since
= { l L Z,(n)}{Z;(n)
For tlie second schema nre observe that
( 1 f (z))fl,(x)
= 0 by esample 2.741
p íz p me llave to prove
( 1 -- Z,(O))f( O ) =O
-
[ l L { Z l l f ( n ) + -( fl ( S n ) ) ) l
3.35
-
Lct 1 =L:p(x) then
EZy(x) p(1) & 1 .L 71
-
(b~r)+{b~(b~r))=b+{(b~r)~b}=b,
{b = b ) -+ ( p ( b )+ q(b r ) )
and so . p(b) -+q ( br).
~
l ~ nl = = n ~ ( f ~ - . - ? )
1 = n (11: 1) -- ;))(!) p(ri ( n 1)))
aiid SO (iisiiig esaiiij~le:3.002) 3.42 Let P ( b ) denote the formula.
E(p(z)-+p(n = (,L 1))
+ E:p(n 7 ) . - a g b p(n) + EEp(x)
nrliere p(x) is tlie propositional fiiiiction f (x)= O.
P(O) liolds by theorern 3.43
- '
Since EEp(x) -t E'bp(x) (by esaniples 3.322, 3.31) therefore
3.37 Write g;(u, 2 )=f(x, u ) : hy essniple 3.36 we liave botli P ( b ) + {a g b a p(a) -t g b p ( x ) ;)
-4: ' { f ( t , u+c)=O) - + / ( u . n -c)=O but {(a=Sb) a p(a)) -+ p(Sb) , (theorem 3.43) ,
a11tl and so (a=Sb) a p(a) + E:bp(z).
t -I:-'[p(t, a+c)=O) -> p(a. (1 +c)=O
;.e. ApAe(f(a+ c. t )= O } -+ f (a+ c, a ) O
Tliiis if P ( x , a ) denotes
-
Siiice (a <Sb) -> (a6 b ) v ( a=Sb) . ( ~ s a m p l 3.1
e l ) , it follows,
bx esample 3.081, that P ( b ) P(Sb), ~ h i c hcompletes a
proof of P ( b ) by induction.
4; ( f ( t , a )= O ) & d;{f ( x , U ) = O )-+ f ( x ,a )= O
we have proved both P(u+- c, a ) and P ( a , a + c) whence 3.5 Let Q(r) denote A:+"q(x) tlieii Q(O) follows from A:q(x)
P ( x . a ) foliolvs by esample 2.272 and q(p+ 1 ) ; since &(Sr) is equivalent t o Q(r)a q(p+SSr)
then q(p+SSr) + ( Q ( r )+ Q ( S r ) )and so Q ( r )+ Q(Sr)foliows
3.38 Denote L r ( f ( x ) = a ) by b, so that from q(p+SSr) which prores &(r), that is AE+Srq(x).By
E,"(f(x)=a)-+ f (b)=a. examples 3.34 and 3.392 me liave A:"q(x) foliows from
Since f (b)= a + {p(a)+ p(f ( b ) ) ) A;q(x), and so AEq(x) follows by esample 2.7301.
i.e. { f (b)= a ) a p(a) -+ p(f ( b ) ) , and b a m ,
t>herefore 3.6 We have b < 1 -+ .up ( n L b) b? a characteristic property
EEy{f(x)= a ) a p(a) -t EFp(f (x)),by example 3.42. of the L-operator.
Sinceg<a & a g n -t n - a < l , (takingnLaforminexample
3.39 f (a)=O foUows from { I L l a , al)f(a)=O 3.191),
3.391 1-l-f(n)=O foiiows from ( 1 - l - f ( a ) ) { l - l a , al}=O therefore g c a ?i a á n -+ - p ( n : ( n - a ) ) ;
I -
( l L q ( x ) ) p =0
follows ( 1 q ( 0 ) ) p= O aiid ( 1 - q ( x -L 1 ) ) p= O and hence,
using example 2.272,
introductory equations, and therefore
{ l A X r ( n ) ){PT Z g ( n ) ) ={ ( l ~ ( p ~ q ( n ) ) ) ~ n pZQ(n))
"nd f 1 ( P f Zq(n)))&(n) = ( 1 (P+ Z q ( n ) ) ) n p
](p=
+O
{ 1 - ! - ( l A f l q ( x ) ) p()l L D q ( x + 1 ) ) ~ =( ( 1 - p ) ~ ~ ( n ) ) p = o .
= {1 L ( 1-17,(a))p) ( 1 ~ q ( x l+) ) p = O
which completes a proof by induction. 3.93 The functions Z',+,(n)and Z p ( n )+ Zu(n)are readily shown
to satisfy the same introductory equations and from the
3.831 From the true formula equality
( n = r ) > n + (0=0)
N
whence
E:((n-r)>n) -+ N (O=0)
3.931 Negate both sides of 3.93, with - p, N q in place of p, q.
-
( 0 = 0 ) -+
N
-+
E:((n-r)>n)
EZ(x>n) , by example 3.35,
3 AZ(x <n )
3.94 Let r ( x ) = ( l ~ p ( x ) ) q ( x )so , that we must prove
y ( n )= ( l L Z ; ( n ) ) ( 1 - Z p ( n ) ) Z q ( n =
Clearly y ( 0 ) = O, and
) O.
-L Zq(n)>
3.96 Negate both sides of 3.95, with p iii place of p. 3.90 E;E;(p(x)&p(y)tkx>g)
t .E;E:(p(u) & p(v) (t 7: > L?)
3.97 Froni the equatioii -t q E y ( p ( y )& p ( r ) a y r.r)
( 1 - ( 1 - p ) q ) ( l ~ ( 1 ~ (l=p)=U
q ) ) ' 4q E Y ( p ( x )81 p(3) & y: - x ) . 11. 3.983 ;
-
(proved by taking O and S p in turn for y ) we &rive
( ~ (+4q ( x ) )-t (- q(5)-+ ~ ( 4 )
and from this proved equation we obtain
from the equation
( 1 - ( ~ + b c )()n i - b )( a i c ) = ( a - c ) ((1-a)-bc)b=
= ( ( 1L bc) -a)bc = O
me derive p(x) & p(y) (i ( ( x> y) v ( x< 3))
( ~ (a 4 P(Y) a ( x > Y ) ) ( ~ (& 4 P(Y) ( x < y ) )
and so, by two applications of esarnple 3.931. a n d the
equation ( 1 '- (1:b)a) ( 1 -ab)a = 0,
~ ~ ; ( p (a x?)(y) +
) a x y ) ++ E:E;(P(x) p(y) a x > y).
3.95 Combine 3.97 mitli the formula obtained from it by inter-
changing p(x), q(x) and then apply example 3.93.
and SO
i.e. Sx<Sn
SO tliat O<a
-
x < n -> R ( ( S a ) ! S, x ) = O
R ( ( S t ¿ ) !S. x ) = O
( b y 1.42)
but, if c = Q(b. P"), R(ú, pk) = O -t b = c$, and AS,"R(f( x ) ,p) > 0 -+ AeR(f(x),p) > O a R ( / ( S k ) ,p) > O
and SO (by 4.014) whence
P ( k ) a R ( a . p) > 0 a R(nb. p"') = O -+ R(ac, p) = O. F ( k ) A + k R ( f ( x )p)>O+R(
: 17 f ( x ) , p ) > O a R ( f ( S k ) , p ) > O
However z<k
R ( n , p)>O a R(nc. p)=O -+R(c, p)=O -+ R ( 17 f ( x ) , p) > O, b y theorem
z<k
and 4.51,
R(c, p) = O + c = pQ(c. p). i.e. F ( k ) -+ F ( S k ) , which proves F ( k ) .
Accordingly
P ( k ) & R ( n . p) > O & R(ab. pk+') =O+ b = pk+' &(c, P ) 4.86 We have R ( m , pZrn."')= O ; let P ( k ) denote the given formula
3 R(b, pk+') = O
(4.86). Then P ( 0 ) holds. Br 4.82 and 4.85
that is, P ( k ) -t P ( ~ l I) , which proves P ( k ) . - R( 17 pZrn."' , pk+J > O
zgk
R(m, a ) = O -+ m = @Q. ( m , a). and, by 4.801, and so by 4.802, since R ( m , p E + l l ) = O ,
R ( Q ( m ,a ) , pk)= O . P ( k ) + R(m, { 17 p~m.z')p";k+'') = 0
zSk
Since p, is prime i.e. P ( k ) -+ P ( k + l ) , so that P ( k ) is proved.
R(p,, x ) = O - t x = l vx=p,:
and so, since p , > l . 4.87 Denoting LF{R(b, p,) = O ) by 5 we have
R(@k, P1) = (Pl=Pk)
=(R(b, p,) = O } R(b, p,) = O a 5 á m .
-+
.
u n d vemandter Systeme I . Monatshefte fiir Math und Phys., Vol 38. . ++ .
. . . . . . . . . . 3..
1
counting . . . . . . . . . 7
pp . 173-198 .
- operator . . . . . . . 9, 73
HILBERT. D . and BERNAYS.P . [l] Grundlagen der Mathematik . Vol . 1.
Berlin 1934. Vol . 11. Berlin 1939 . coiirse-of-raliies function . . 119
- recursion . . . . . . . . 119
&ENE. S. C. [ l ] Introduction to Metamathematics. Amsterdam . 1952. e(x) . . . . . . . . . . 3s
Mos~owsm. A . [ l ] Sentences Undecidable in Fonnalised Arithmetic . Deduction theoreni . . . . . 112 Sx . . . . . . . . . . . 7
Amsterdam . 1952 . divisor. least . . . . . . . . S9 z, . . . . .. . . . . . 35
.
PETER.R [ l ] Rekursive Funktionen . Budapest 1951. double recursion . . . . . .
[2] Rewiew of S k d e m [2]. Journal of Symbolic Logic. Vol . 5 (1940)
.
pp 34-35 .
. Knumeration of primitive
22 0.(x) .
U(x) . .
.
.
.
..
. .
.
.
.
.
.
. . 3s
134. 136
recursive functions . . . . 140 V(x) . . . .. . . . 134. 136
ROBINSON. .
R . M [l] Primitive recursive functiwns . Bulletin of the American
equation calculus . . . . . Z(x) . . . .. . . . . . 21
. .
Math. Soc Vol 53 (1947). pp . 925-942 .
SKOLEM.TH. [1] Begründung der elementaren Arithmetik durcl~die rekur-
-.-.introductory . . . .
provable . . . . . .
.
.
.
.
27
27
-.-. A . . . . ..
course.of.vaI~ies.
. .
.
.
.
. . 146
. . 110
rierende Denkweise ohne Anwendung scheinbarer Veranderlichen mit
unendlichern Awdehnungsbere.ieh. Skrifter Norske Videnskaps.akademi.
-. verifiable . . . . .
exponentiation . . . . .. .
. .
27
44
16 -. initial . . . . .
propositional . .
.
.
.
.
. . 21
. . 62
1. No . 6b. Oslo .
SEOLEH.TH. [2] E i n e Bemerkungüber die Induktionaacl~ematnin der rekursiven Factor. greatent common . . Gijdel. K . . . . . . . . . .
Zahlentheorie . Monatshefte für Math . und Phys., 48 (1939) pp . 265-276 . .
- prime . . . . . . . . .
99
93 - number . . . . . . . .
143
144
[3] Uber die Xcht-charakterisierbarkeit der Zahlenreihe mittels endlich Frege. G- . . v . . . . . . 2 greatest common factor . . . 97
o ~ ~ a b z a l ~ l b a r u n e n dvieler
l i c h A ~ s a g e ntit
n awsc1~1~iesslichZahlenvariablen . formal system . . . . . . . 10
Fundamenta Mathematicae. Vol . 23. (1934) pp . 150-161 . functions . . . . . . . . . 17 Inequalities . . . . . . . .
[41 T h e develolmzent of recursive arithmetic . S t h Congress of Scandinavian
Mathematicians . Copenhagen 1946.
-. .+ . . . . . . . . .14. 18. 28
. . . . . .15. 18. 30
induction . .
- scliema 1,
. . . . . . .
. . . . . . .
46
66
123
189
Pge Pxae
. . . . 125
iiidiictioii sclieiiia 1.' prot'f srlit?riin . . . . . . . . 34
- . r,. . . . . . . . . . ( 2 ; !~r'~l)~>%itic;n . . . . . .
. . .it j
initinl fiinc.tiolis . . . . . . . . 1 .l
! ) ~ ~ t i v n l ~ l c . c c ~ i i a t.i ~.! i i.
. . 27
iiitroductnry rquations . . . 2;
< . i t ~ r ica:it . . . . . . . . .
iteratiori . . . . . . . . . . ld
i ..t.c.ii!.>;io
n. uuiirs<.-ot-vnliics . i 19
~fultipliciition . . . . . . . 15 .. ! b e . . . . . . . . .-- ,.7
-, roiiiiniitnti\.ity of . . . . :!O . ~~ririiitivo. . . . . 19, 1 19
Siimbcv . . . . . . . . . . 1 .,>;iiipl c. . . . . . . . . . l!)
\-nrinlile . . . . . . . . fj u-it li pcirnlnetcr
..
i:otlcl . . . . . . . . . 14.1
, priine . . S3
. . . V . . .
>;ob.utiti i t iori . .
rt.ii~aindci.. . . .
.
.
.
.
. . .
.-. .
120
S6 .
riiimernl .. . . . . . . . . 3 l~ussc11,13.A.l\'. . . . . . . 3
. .
P a r a m ~ t r isrihatitution.
.
rcciirsiun witb . .
permutstion . . . . .
. . .
. . .
120
129
1. . T . . . . . . . . . . . 110
K . . . . . . . . . . . 105
S . . . . . . . . . . . 11s
pentatioti . . . . . . . 16. 17 Sb.. Sb2 . . . . . . . . 104
Péter. X . . . . . . . . 24. 121 T . . . . . . . . . . . 104
prcdicntca: E(17) . . . . . 14s U . . . . . . . . . . . 104
. I..
E ( ~ T pL) . ~. . . . . . 150 U. . . . . . . . . . . . 105
Pf(.ri . . . . . . . . . . 150 single recursion . . . . . . . 19
Pr(r~f.tl) . . . . . . . . 150 Skoleni. Tli . . . . . . . . . 143
S,!??t.n).
S,(III.
12) . . . . . 149 system. formal . . . . . . . 10
t . ) . . . . . . . . 150 - S: 9 . . . . . . . . . . 112
Scb,,(l./tt) . . . . . . . . 147 W * . . . . . . . . . . 115
T(n) . . . . . . . . . . 148 9?+ . . . . . . . . . . 152
T(nr.11.p ) . . . . .... 149
Tctration . . . . . . . . . 16
prime ni:iilbers . . . . . . .
- -..
ir~iinitiideof .
- - scqiience of .
.
.
. . .
. . .
S9
90
transposition ..
Variable . . . .
.
.
.
.
.
.
. . .
. . .
129
-.-.
90 13
- factors . . . . . . . . . 93 bound . . . . . . . . . 65
primitir? recursion . . . . . ,,
99 nurnber . . . . . . . . G
proot' . . . . . . . . . . . 27 vcrifiable equatioii . . . . . 47