Methods of Logic - W. O. V. Quine

,it']- The Merits it-fethriri iliiidrnpped existential quantifier, must be new. tvture accurately: it must befree in nu line prier tu this instantiatinn. Thus censider hew unfertunate itweuld he te argue as fnllnws:PREMISES: El.r Fxuvsraivces; Hr —.F.t Fy —Fy twrengl Anuther peint, this time ene bf liberality rather than -pf hedging, is thatwe can have mure than ene premise, as abeve- Fer a valid example, taltethe familiar implicatien that was preved in the preceding chapter bypreving the validity ef [ti]. Tu preve it by the present methnd we weuldassume as premises * 11' by Fxy’ and the prenex ferm ef the negatien at\"liI\"y Ex Fay‘, and preceed te instantiate [ct a truth-functinnal incnnsis-tency:|=a1=.s1|st=:s: Hr \"tt'y Frylrtsrsrrcssz Hy Vx —F.ry \"tt\"y Fay Vs —F.riv Fgtu _]I-TE-Hi his a further simple example let us preve that \"'tt\"x ‘tfy Fxyi implies“tt'y Fyy'.ssstvttsss: \"tits \"tfy Frymstances: Eb\" -Fnr — FEE ‘ti’y Fay F atThe interesting peint abeut this implicatien is that ene is apt tu say that itis ebvieus by direct instantiatiun, \"'tt'y Fyy' being simply an instance uf“Ills \"tt'y Fry\". Une weuld be wrung: ene ceuld as well argue that\"'tI'.r Hy Fry‘ implies ‘Hy Fyy‘, but it dees nut. See ts] ef Chapter 25.“Fy Fyy' and ‘Hy F_vy' are nut instances nf \"'iI\"'.r lily F.ty' and“tit'.r Hy Fay‘. The definitien -nf instance at the end tif Chapter Z5 needs te

I ‘J1 Hi’. General Tneury cf §_I_luunt{t‘icuri'eube carefully ebserved and the reasuns behind it, namely the restrictiens ensubstitutien, fully appreciated. Here, next, is a mere substantial example. It will serve as a scrurce cfillustratien when we get ttr justifying the methed.vnertnsss: {ll Elu 'tt\"y Fuy{E} \"|lt\"x Ev 'li|\"_v — {f\"vy . Fyx]{3} ‘li\"x‘i\"y3tv{Fxy —*: —F.r-v . Fwy .v. Fyvv . Fwx}tivsrxnces: {4} \"it\"_1.' Fgy [el’ {[3]{5} Elv ‘tt'y — {Fvy . F_vt.'t [uf {Elltel \"lb\" *\"lFb* - Fxrti lefl5ll{Tl Fat lef {-1]]{El \"I\"y§w{Fgy —1-: —.Fttv . Fwy .v. Fyw . F1-vs] [uf {3}}{ill 3w{F:r —a-: —F.:w . Fwt .v. Fnv . Ftvtl [ef {Ell{I'D} FEt—1-.1—FI.i' - Fst .-\"It\". Fts . Fss [cif {Ell-Ill ll F-it [Bf l'l~ll{I2} —{Fts . Fss] [ef {fill{T}, { lb], tf I I}, and {ill are tegether incensistent by truth-value analysis.We cnnclude that {l]- {3} are le-gethet incensistent. The preef precedure fur incnnsistency that l have new described willbe called the main methed, te distinguish it frem alternatives in Chapters19 and 35-3-E. Summed up, it is the fellewing slight affair. lnstantiatiun:apply Ul and El, always eh-busing new instantial variables fur El. Termi-natiun: a truth-functienally incensistent assemblage til unquantitied in-SIHITCES. I have still te shew that the methnd is seund-—i.e., that it generates atruth-fnnctienal incensisrency enly when the premises are incensistent. Inshewing this l shall need seme termintilc-gy. l shall use ‘generic’ as theeurrelative ttf ‘instance: thus a step ut’ Ul er El derives an instance fremits generic. t shall speak. ef U-instances and E-instances. Thus in theincnnsistency preef tl}-{lit the E-instances are {-t], [I5], and {IIII}, andtheir generics are { ll, {S}, and {t-1]. Hy an El-cenditiunuf I shall mean acenditienal whese censequent and antecedent cepy an E-instanee and itsgeneric. If fer cumpacmess I simply write the numerals themselves asabbreviatiuns ef the numbered lines, then the El-cenditienals uf the in-censistency prtxrf{l]—{lE]t are ‘l —1- 4'. ‘5 —s ti’, and ‘ii —1lt]’. New ubserve that each instance, in such a preef, is implied by previeuslines plus El-cenditienals. Fur eaeh Ll-instance is implied by its generic,and each E-instance is truth-functienally implied by its generic and itsEI-cenditienal. {E.g., {4} is implied by {_l_] and ‘I —1- 4'.) Ultimately,

,iTt'.i. The .\"xfniri iirfethvivl lqdtherefere, all the instances are implied by the premises and the El-cnnditinnals. Se, since the instances are incensistent, the cnnjunctinn nfthe premises and the El-cenditienals is incnnsistent. ln eur example thiscenjunctien isrl.l.3.l-14.5-rEr.El'—1-Ill.ats neted early in Chapter 25, it will remain incensistent when an existen-tial quantifier is prefixed. Let us prefix nne cnntaining the instantial vari-able nf the last E-instance-Hs{l .2.3.l—vd.5—rfi-‘it-r It'll-New we use the fact that this instantial variable, having been new {i.e..free in an print line], is free nnwhere in nur cnnjunctinn except in the lastEl-cenditienal, and nnly in its ennsetiucnt at that. We can cnnfine thequantifier tn that part by the rules nf passage { ll and {5} nf Chapter Eli. l.1.3.|—rr-1.5--I-t'i.‘i—a-Hsll].But {'9} and ‘Es lti’ are alike except fer the alphabetical cheice nf theexistential variable. Sn '9 —r as llT is valid and can be drnpped frnm thecnnjunctinn, leaving ‘l . I . 3 . I —1- 4 . 5 -1 I5‘. Then by a similar ar-gument we get rid ef ‘5 —1- ti‘ and finally ef ‘l —1- 4'. Thus the whnleincnnsistent cnnjunctinn has bniled dnwn tn the premises, which aretherefere incensistent, n.E.n. in this argumcntl have leaned increasinglyen the particular example, but still the general reasening shines threugh. We see thus that eur main methed is a snund ene. lt is a rather naturalnne, mnrenver, despite die austerity nf the argument abeve. The pattern[I]-{ Ill} enuld be verbaliaed, as a disptn-nf nf snme cnnjunctinn ef actualstatements in lieu nf { l]—{?-jt, aleng the fnllewing line. Fteenrding tn { ll,there is snmething that isF tn everything. \"v'ery well, call it s. Sn we have-[til]. Hut {E} said that everything x is such that . . . . . Well then inparticular: will he that way. Sn we have [S]: that there is snmething suchthat . . . . . Call it t. Cnntinuing thus, we get tn the cnntradictinn {T},{ltIt]|-{_lE\"t. The premises {l]—{3} are thus disprnved. [lne er twn nf themmay be true, but nnt all three. Premises must be put in readiness in twn respects befnre the mainmethnd is applied tn them. They must be cenverted tn prenex fnrm; thiswe ltnew. The further peint is that the letters used as beund variables in

I914 Hi‘. General Tfteary aJ|'{-_*itattti|t'it'att'arteaeh premise sheuld be sn chesen as net te match a free variable nf anypremise. E.g-, censider ‘Eli-r —-Fyw‘ and \"'tt'x \"tl'y Fxy‘. They are incnn-sistent, but the reader can try in vain tn shnw them incnttsistent by themain methnd as they stand; whereas the pr-nnf gees smnnthly thrnugh ifthe beund ‘y’ is rewritten as \"t'-as salts |-is: Htv — Fywrrsstx races: ltitlx Vs Fxr - Fya Vt Fyt Fyu We shall see in Chapter 31 that the main methnd, fer all its slightness,is cnmplete. We shall see that fnr every incnnsistent cnnjunctinn nfschemata, prepared in the twn respects just nnw indicated, it alfurds anincnnsistency preef- H|5TU'R|CflrL HUTE: Re-ductin ad absurdum, alsn called indirectpreef, was ltnnwn tn the ancients under the name nf apagage. Its advan-tage nver direct prnnf nf validity turns nnly nn a small peint nf technicalcnnvenience which will be nnted in Chapter 3-ti. The first prnnf precedurefnr quantificatiun theery--Frege‘s ef 1tlT5t—pmceeded rather in theaxiematic style nf Chapter I3; see Chapter 3? belnw. This style cuntiauedtn prevail thrnugh the thirties. Already in 1923 and l93't], hewever,Sit-elem and l-Ierbrand presented prnnf prncedures mere attin tn what I amcalling the main methed‘. see Chapters 35 and 315. The main methedfigured in a i955 appendix tn earlier editiens nf the present bnett.EIERCl5E5I. Find fault with the fellewing purperted preuts uf incnnsistency.rraeratsssz Bx Fxy — Etx Fxx Ex Fxynvsrxivces: ‘tifx —Fxx ‘Fy Fyy Ex —F.ry Fyy -Far Fay —Fyy Far —Ftyls any nf these pairs nf premises really incnnsistent? Which? Pruve it51.].

:l t‘ - rtppfit'att'an I95E- Repeat Exercises 3—'t' nf Chapter 29 by the main methnd-3. Describe the nbstacle tn shewing ‘H1-v — Fytv‘ and \"t\"x \"tt\"y Fxy‘ in- censistent hy the main methed as they stand. 31 APPLICATION When nur preef prncedure is te be breught tn bear upen statementsceuched in erdinary language, the taslt ef suitably paraphrasing the state-ments and isnlating their relevant structure becnmes just as impertant asthe prnnf fer which that preliminary taslt prepares the way {see ChapterE}. ln Chapter l4 we nnted a cnnsiderable variety c-f ways in which thecategerical ferms x, E, I, and CI may appear in nrdinary language; and inChapter 22 we saw hnw tn put these fnrms nver intn quantificatienalnntatinn. These ebservatinns previde the beginning nf a guide te thetranslatinn nf wnrds intn quantificatienal symbels. But we saw alse, fremexamples such as ta. lady is present‘, ‘rt Seeut is reverent‘, ‘Inhn cannetuutmn any man nn the team‘, and ‘Tai always eats with chupstictts‘{Chapter I4}, that it is a mistalte tn trust tn a pat checltlist nf idinms. Thesafer way nf paraphrasing wnrds inte symb-nls is the harder way: by asympathetic rethinlting nf the statement in centext. If there are ebvieusways nf rectifying legically ebscure phrases by rewnrdjng, it is well tn dnsn befere manning tn lngical symbels at all. A drastic departure frem English is required in the matter ef tense. Theview tn adept is the lvlinltewsttian nne, which sees time as a feurthdimensinn nn a par with the three dimensinns nf space. Quatttifiers mustbe read as timeless. The values nf ‘x’ may themselves be thing-events,fnur-dimensinnal denizens ef space-time, and we can attribute dates andduratinns tn them as we can attribute lncatiens and lengths and breadths tnthem; but the quantifier itself attributes nnne ef these things. ‘3x‘ saysneither ‘there was‘ nur ‘there will be‘, but nnly, in a tenseiess sense.‘there This fnur-dimensinnal view was needed, as everyune ltnnws, tn maltesense cf Einstein's relativity physics. But it alsn has lnng been a great

tas Ill- General Ttieary af tQaaru{liratfanhelp in clarifying nrdinary tallt nn mnre humtltum matters. \"ti'lll'|en we sayhnw many presidents er pnpes there have been, we state the sine nf a classwhnse members have never all enexisted. when we enmpare htapnlenn tnCaesar er trace Iitavid‘s descent frem atbraham, we relate persens whnnever enexlsted. Pusxles beth cunceptual and verbal are minimised byseeing spatial and tempnral assnciatinns as lngically alilte. lvluch as Ens-tnn and Bimtingham are 3l}l]'l] miles apart, Caesar and l\"-lapnlenn are lE{l'Elyears apart; and the ‘are’ here had better be read as tenseiess. Frem lnng habituatien we are prnnf against silly fallacies nf this sert:Cenrge ‘v’ married Ctueen tvtary. Clueen lvlary is a widew, therefnt'eC=enrge “v‘ married a widnw- Clearly, hnwe ver, a legic designed tn enn trelthis snrt nf thing explicitly wnuld be needlessly elabnrate- We dn better tnmalte dn with a simpler lngical machine and then. when we want tn applyit, tt't paraphrase nur sentences tn lit it- already in Chapter ta we had aglimpse nf the varied ways in which tempnral references might fare undersueh paraphrase. hint, nf ceurse. that the ubiquity nf tense in English willrequire us tn malte explicit reference tn time in all the paraphrases. Asnften as nnt the tempnral matter is superflunus, and fnisted nn us nnly byEnglish usage. Still mnre nften. in practice, we can even leave the tensedverbs themselves undisturbed. as lnng as there is nn danger nf equiveca-tinn within the space nf the prnnf. {See Chapter 3.] tn paraphrasing mnre cemplex statements intn quantificatienal fnrm, apreblem that nbtrudes itself at every tum is that nf determining the in-tended greupings. The cues tn greuping which were nnted at the n\"uth-functinnal level in Chapter 4 centinue tn be useful here, but flie mustirripnrtant single cue prnves tn be the additinnal nne which was nnted incennectien with {l ll nf Chapter 22: The scape afa anannfier mast reachantfar eneugh ta talte in any accnrrence sf a variable that is snppased tnrefer lracilr ta that anantltier. The technique nf paraphrasing inward‘ {Chapter 3}, as a means nfdividing the pmblem nf interpretatien intn manageable pa.t1s and lteepingthe cemplexities nf greuping under cennel, is as impertant here as at thetrudt-functinnal level; mnre impertant, indeed, in prnpnrtinn tn flte in-creasing cemplexity nf the statements cnncemed. After each step nfparaphrasing, mnrenver, it is well tn check the whnle against the eriginalstatement tn malte sure that the intended idea is still being reprnduced. El-y way nf a serinus venture in paraphrasing, let us try putting thefnllewing premises and cnnclusinn nver intn quantificatienal fnrtrt pre-paratnry tn setting up a dcductinn.

.l'l'. .-tpplit-arlan 1'9?r-xexnsns: The guard searched all whn entered the building ex-Ct‘rt'~tt?l_l_l5ICtl'-ti cept thnsc whn were accnmpanied by members nf the firm. Seme nf Finrecchin‘s men entered the building unac- cnmpanied by anynne else. The guard searched nnne nf Finrecchin‘s men. Seme nf Finrecchin‘s men were members nf the firm-The first premise says in effect:Every persnn that entered the building and was nnt searched by the guard was accnmpanied by snme member{s] tif the firm.Seuing abnut nnw tn paraphrase this premise inward, we inspect it fnr itstrutermnst structure, which nbvinusly is \"'tl'x{. . -——r. . J‘:'lil‘x{x is a persen that entered the building and was nnt searched by the guard —1- x was accnmpanied by snme members nt‘ the firm].The virtue nf thus paraphrasing inward a step at a time is that the unpara-phrased internal segments can nnw be handled each as a small indepen-dent prnblcm. The clause ‘x was accnmpanied by snme members nf thefirm\", e.g., regardless nf cnntext, becnmes:Hytfx was accnmpanied by y . y was a member nf the firm].The nther clause, ‘x is a persen that entered the building and was nntsearched by the guard‘, needs little mnre attentinn; we have merely tnmalte it an explicit cnnjunctinn:x is a persen that entered the building . x was nnt searched by the guard.Sn the whnle becnmes:'lil‘x|x is a persnn that entered the building . x was nnt searched by the guard .—-r §y{x was accnmpanied by y . y was a member nf the firm]-l.

l'ElIli ill‘ . General Tlteary at‘ QaantfllicrttianC-are must be taken, as here, tn insert tlnts nr parenflieses tn indicateintended greuping. Finally, writing ‘Fx‘ fnr ‘x is a persnn dtat entered the building‘, Trix‘fnr ‘x was searched by the guard‘, 'Hxy‘ fnr ‘x was accnmpanied by y‘,and '.ly‘ fnr ‘y was a member nf the firm‘, we have: \"tl\"x[Fx . —C'x .-r- Hy{Hxy . -ly]]as the lngical fnrm nf the first premise- instead nf carrying the werd ‘persen’ explicitly thrnugh the abnveanalysis, we might, as an alternative prncedure, have limited the universetn persnns. Hut in the present example this wnuld have made rtndifference tn the final symbnlic fnrm, since ‘x is a persnn that entered thebuilding‘ has all been fused as ‘Fx’- The reasnn fnr representing sn lnng a clause as this simply as ‘Fx‘,withnut further analysis, is that we ltnew that nn further analysis nf it willbe needed fnr the prnpesed deductinn. We are assured nf this by the factthat ‘entered‘ never nccurs in premises nr cnnclusinn except as applied tnpersens entering the building. Similarly we were able tn leave ‘.1: wassearched by the guard‘ unanalyzed, because ‘searched‘ never eccurs ex-eept with ‘by the guard‘. Cln the nther hand it behnnved us tn brealt up ‘.rwas accnmpanied by snme members nf the firrn‘, since accnmpanimentand membership in the firm are appealed tn alsn nutside this cemhinatienin the cnurse nf the premises and cnnclusinn. In general, when we para-phrase werds intn lngical nntatinn and then intreduce schematic letters asabeve, it is snund pnlicy tn expase nn rnare structure than premises ta heneetlerlfar the prnpesed‘ .-:iea‘uctien- This restraint nnt nnly minimises thewnrlt nf paraphrasing. but alsn minimises the length and cnmplexity nfthe sehemata that are tn be manipulated in the deductinn. Tuming tn the secnnd premise, and writing ‘Ex’ fnr ‘x was nne nfFinrecchic-‘s men‘. we get this as the nbvinus nutward structure: 3.r{it'x . Fx . x was unaecempanied by anynne else}.lt remains tn paraphrase the cnmpnnent clause ‘.r was unaccnmpanicd byanynne else‘. Clearly the intended meaning is: anynne accnmpanyingx was nne nf Finrecchin‘s men,which becnmes \"'tI\"y{Hxy —r il'y‘,t‘, sn that the secnnd premise as a whnlebecnmes:

Jl. rtpplicatian W5‘ 5-tlilx . Fx . \"i\"y{Hxy —-1 .il'y‘_t].T'he third premise and cnnclusinn immediately becnme; \"I\"x{.llIx —-I —Cx), 11'-l_'it'x . Ix].Talting then as nur fnur premises these tln-ee premises and the negatien nfthe cnnclusinn. all cenverted te prenex fnnn, we preceed with the mainmethed.ramvttsr-s: ‘lilx 5y{Fx . —Gx .—r-. Hxy . ..ly]instances: 3x'sly{.ltI.r . Fx . Hay —ril‘yi \"I\".-'t{il'x —1- — Bx] ltilx —{it'x . .l.t} ‘lI\"y{h'r . Fa . Hay -r llfyi §y{F'r, . —Ga .—r. Hay . Jy} Fa . -62: -—r- Hrw .J'w i't'z . Fr - Hrw—r-h'w its —-r —-Ge -— {Kw . Jw}The reader ca-n verify that the fnur unquantified instanees are incnnsistent. When we undertalre tn inject legical rignr intn inferenm encnunteredin infnrmal disceurse, we are likely tn cnnfrnnt a secnnd preblem nfinterpretatien nver and abeve that nf paraphrasing verbal idinms intnlngical netatien. This secnnd preblem is that nf supplying suppres@premises; and it is nceasinued by the pepular practice nf arguing inentltyrnernes. rltn enthymeme is a lngical inference in which nne nr mnrenf flte premises are emitted frem mentinn en the grnund that their uuth iscemmen ltnnwledge and gnes withnut saying; thus we argue:Seme Greetts are wise; fnr, snme Greelrs are philnsnphers,nmining mentien nf the additinnal premise ‘All philnsnphers are wise‘ nnthe grnund that this weuld naturally be understand by all enneerued-1 In everyday discuurse mest lngical inference is enthymematie. We arecnnstantty sparing eurselves the reiteratinn nf ltnewn facts, trusting the ' Trattitienalty ‘enthyrrteme‘ meant, metre specifically, a syllegism with suppressedprcmise—|ilte the abeve example; but it is natural. new that legic has an far netstrrippedthe syllegism, tn refer tn a legical inference nf any fnrm as an enthymetttc when snmepremises an: left tacit-

EEK] HI- Ucnerrti 'i\"her.rr_y c-If flunurtjicntienlistener re supply them where needed fer the legical cnmpletien ctf artargument- But when we want te analyse and appraise a legicai inferencewhich setnerme has prepnunded, we have te talte such suppressed prem-ises int-rt accnunt. At this pnint twe prnblems demand selutien simultane-eusly: the preblem ef filling in the details ef a legical deduetien leadingfrem premises te desired cenclusien. and the preblem ef cl-ting eut thepremises se that such a decluctinn can he censtructed. Selutien ef eitherpreblem presuppeses selutien cf the ether; we can net set up the deductienwitheut adequate premises, and we cannnt ltnew what added premiseswill he needed until we ltnew hew the deductinn is te rI.In. Sernetimes. as in the syllegistic e:-tample abeve. the ferm cf legicalinference intended by the spealrer suggests itself tn us immediately he-cause ef its naturalness and simplicity. ln such a case there is ne diiiicultyin identifying the tacit premise which the spealter had in mind. Seme-times. en the ether hand. the ferm ef inference itself may net he quiteevident, but the relevant tacit premises are already semehew in the airbecause bf recently shared experiences. Such a case differs in ne practicalway frem the case where all premises are ettpiicit. Snmetimes, finally, neither the intended ferrn ef inference ner theintended tacit premises are initially evident; and in this case the best wecan dc is try tn snlve beth preblems ccmcurrently. Thus we may start atentative deductien en the basis cf the explicit premises, and tl1en, enceming te an impasse, we may invent a plausible tacit prernise whichweuld advance us tcward the desired cenclusien. Alternating thus he-tween steps cf dedaetien and supplementatien ef premises, we may, withluclt, achieve eur geal. Elf ceurse the tacit premises thus invnlted mustalways be statements which can be presumed tn be believed true by allparties at the eutset; fer it is eniy under such circumstances that a deduc-tien using these tacit pt'etr|ises weuld give reasen fer belief in the cenclu-sien. If we were tn invelte as a tacit premise seme statement which was[frem the peint cf view ef cencemed parties) as much in need bf preef asthe cenclusien itself, we sheuld be guilty ef what is ltnewn as circularreasening, ctr begging the questien. er peririe prrnci_r.u'f,' and added een-victien that might accrue te the cnnclusinn tl1re1.tg,h such argument weuldbe deceptive. Deciding whether a statement is believed true by all partiesat the etttset is a taslr. ef applied psychelegy, but in mest cases it effers nudifiiculty, there cemmenly being a wide gulf between the meet issues efan actual argument artd the cemmen fund ef platitudes. As an esample ef the ltind ef preblem discussed in the feregeingparagraph. censider the ertplieit

3 -i‘ - x-lppfir'rrtfett EDI tateimses: All natives cf Ajn have a cephalic index in excess efand the '96, All wemen whe have a cephalic index in excess ef lib tewtrtestetv: have Pima bleed anynne whese mether is a native ef Aje has Pima bleed-Let us put these statements inte legical netatien, bet fer the present let ususe ebvieus centractiens instead ef schematic letters ‘F ‘, ‘G’, ete., fer wemust lteep the meanings ef the werds in mind in erder te be able te thinltef relevant platitudes fer use as tacit premises. The fellewing, then, arethe results ef translatien, suppesing the universe te be cemprised this timeef persens:tatetatses: \"tI'x|_'x is nat —t-x has 96]. \"lt\".r|[x is wnm . x has ‘lib -—-I-I has Phi].CD-Hf_‘Ll_l5ItItH: ‘tt'x\"t\"'y[.r is me y . x is net .——1~ y has P bl].When we negate the cenclusien and cenvert it te prenex ferm, we get: 11: Hy —-{Jr is mey. x is nat .—1~y has F bl].But we can thinl-; abeut it better if we subject it immediately te theebvieus truth-fnnctienal simplificatinn. thus: Ex Hylx is me y - x is nat . — ty has P bll].Then we start trying fer an incensisten-cy preef. making the mest naturalinstantiatiens.Pltt-Istlst-Is: 'tI\"xl_'x is nat -1-x has '95] ‘dxer is wem . x has Bib .—1-x has P bl}txsrarazrtss: 1r3y[x is mey - I is nat . —{_yhasPbl}] Hyla is mey . z; is nat . —t_y has P hl}] r ismew - a is nat - —l_w 1\"1asPt=li .2 is wem . e has ‘lib -——t-r hasF‘b] z is nat—*:: has '96

Ell! Hf- Gerterdf Theery ejfflaautifit-ntienFer further stimulatien ef insights we malte truth-fnnctienal simplifica-tiens ef the accumulating unquantified instances. The three hell dewn tethis infemtatien: e is me iv, E is net, t has 95, E is wem —*I£ has F bl, — [iv has P bl].What further infemtatien is there, ef a platitudineus lend, that weuldbuild this eut inte an incensisrency‘? Being meth-er ef iv, e is a weman andse, by the abeve cenditienal, has PiITta bleed; but then se decs H-'., herchild. Se the fine] negatien abeve is centradicted. Stated as generalities, the twe saving platitudes arei \"'|iI\".r\"IiI\"y[.r is mey —s+x is wem}, \"I\"x\"a'y[x is me y . x has P bl .-+ y has F’ bl].Putting these with the eriginal three premises re malte five, and thenderiving instances frem the five in eur hy new familiar fermal fashienuntil a truth-functienally incensistent let ef unquantified instances is ac-cumulated, will be fer the reader a simple bit ef beelclteeping.HERCISESl. Derive the incensistent let ef instances as just new indicated.2. Paraphrasing inward step by step. put: Everyene whe buys a ticlret receives a prise irtte symbels using ‘Fry’ fer ‘x buys y’, ‘Gy’ fer ‘y is a ticltet’, ‘Hf fer ‘z is a prise‘, and ‘Ire’ fer ‘.1: receives t’- Then shew that this implies: If there are ne prises then nebedy buys a ticltet.3. Paraphrasing inward step by step. put: Every applicant whe is admitted is examined beferehand inte symbels using ‘Far’ fer ‘x is an applicant‘, ‘E.1r_y' fer ‘.r is admit- ted at time yl, ‘Hxe’ fer ‘Jr is examined at time -'5', and ‘Jay’ fer ‘.1 is befere y‘. Then shnw that this implies:

J2. Eempiereae.r.r EH3 Every applicant whe is admitted is examined semetirne.4. Faraphrasing inward step by step, put: There is a painting which is admired by every critic whe ad- mires any paintings at all inte symbels using ‘F ‘ fer ‘painting’, ‘t.'i‘ fer ‘critie‘, and ‘J-i\" fer ‘admires’. Then add the further premise: Every critic admires snme painting er ether and shew that these premises imply: There is a painting which all critics admire.5. Assume that l liltc anyene whe laughs at himself but detest anyenc whe laughs at all his friends. Shew that these premises, and a platitudineus further ene, tegelher imply that if anyene laughs at all his friends then semeene is ne friend ef himself. t_'Quimby1Iid: COMPLETENESS ln preving the cerriplcteness ef the main methed we shall need what lcall the law sf infinite cenjunctien. lt is substantially what has beenltnewn in tepelegy as l§.iinig's infinity lemma er Hreuwet's fan theerem,and elsewhere as the cempactness theerem. ln the ferm suited te eurpurpeses. it says that an infinite class cf truth-fnnctienal selteinara isr'rm.ri'.sten.r if each bf its finite ,rnhclus.re.r is. Figuratively spealring the law says that an infinite cenjunctien eftruth—fttncrienal schemata is censistent if each finite cenjunctien ef theseschemata is separately censistent. This fermulatien gives the law itsname, but is enly figurative, since cenjunctiens are expressiens, andexpressiens, literally spealting. are enly finite strings ef marlts. The literal 3 All the rest ef Part Ill is bracltctctl fer emissien fer purprrses eif a she|'t ceurse.

It]-it Ht- General Tltepry -:1ffitaartttjfit\"nris.ttstatement ef the law speaks rather ef an infinite class. as abeve. A class eftruth-fnnctienal schemata is called censistent if there is an assignment eftruth values te sentence letters that maltes all the schemata in the classceme eut h'ue. Te see why the law nf in finite cenju nctien is true, assume seme infiniteclass lit\" ef h‘uth-functienal schemata and assume that each itlcenjunctien[each finite cenjunctien ef members rif it’) is censistent. Let us representthe sentence letters in these schemata as ‘p,’,_ ‘pg’, etc. Definirien- A given assignment ef truth values te ene er mere sen-tence leners will be called innecueus [se far as if is cencemed] if itcenflicts with ne it’-cenjunctien, causing it te reselve te .l. er te anincensistency- Dejinirinrr. t, is T er 1. aceerding as assignment ef T te ‘pl’ isinnecueus er net- Lemma i. Assignment efr, te ‘p,’ is innecueus. Prnef. if assignment efT te ‘p,’ cenfiicted with seme E.’-cenjunctienand assignment ef J. te ‘p,’ cenfiicted with ene tee, then the cenjunctienef the twe cenjunctiens weuld be an incnnsistent K-cenjunctien eutright.centrary te ear hypethesis en it’. Se ene er nther ef T and J. must be aninnecueus assignment te ‘p1’. Either way, r, is then innecueus by itsdefinitien. Definiririn. r-_. is T er .l. aceerding as assignment ef r, re ‘p,’ and T tn‘p,’ is innecueus er net. Lemme 2. assignment ef I, te ‘p,’ and I2 te ‘p,’ is innecueus. Prrief. if assignment ef r, te ‘p,’ and T te ’_Hg’ eentlicted with semeit’-cenjunctien and assignment ef r, re ‘p,’ and J. tc ‘pg’ eenfiicted withene alse, then mere assignment ef r, te ‘p,’ weuld cenfiict with thecenjunctien ef the twe cenjunctiens. centrary te Lemma l. Se either theassignment ef t, te ‘p,’ and T te ‘pa’ er the assignment ef r, te ‘p,’ and .l.te ‘pg’ is innecueus. Either way, then, Lemma Z helds, by virtue ef thedefinitien ef fp- Definirien. r,, is T er l aceerding as assignment ef r, te ‘p,‘, rs te ‘p,‘and T tn ’Fl3” is innecueus er net. Lemme _-i’. Assignment eft‘, te ‘p,’, lg te ‘pg’, and fg tn ‘pg’ is innecu-Ell-I5. Preef frem Lemma I lilte that nf Lemma Z frem Lemma l. We have in the definitiens the beginning ef a series whese centin uatienis evident. Truth values r,, T2,, T31 r,, . . . are thereby defined which aredesigned fer assignment te 'p,’, ‘pg’, ‘pg’, ‘p.,’, . . . . Centinuing thelemmas re Lemma r’, fer any desired r’, we shew that assignment ef.t1, I2,

.if:’. IL’ernpfetettr‘s.t EH5. . - ,t‘t te ‘pl’. ”’|l’Il'g”,, . . . , ‘pr’ is innecueus. Efensider, then. any schetna.5'in it’, and taltei large eneugh se that ‘p,’, ‘ps’. . . . . ‘p,’ exhaust thesentence letters in S - Then assignment ef t,, I2. . . . , r, te these lettersreselvesfi te Ter 1.\", but, by Lemn1ai,nette .L; se re T. Beth’ was anymember ef it’. Se assigrtrnent ef t,, ry, . . . te 'p,’, ‘pg’. - . . maltes allmembers ef.li;' cetne net true. Se it’ is censistent, i;_i.E.e. l pause fer a brief digressien en censtructiveness. [Jnce the infiniteclass it’ has been specified, in whatever fashien, the truth values r|, rt. etc.are uniquely fixed by the definitiens abeve. Eur this decs net mean that,even ltnewing it’ , we can find eut whether r, is T er 1.. ner whether re it Ter 1., and se en. Even if we have a decisien precedure fer membership inft’, we may have nene fer whether the assignment ef T re ‘p,’ weuldcenflict with seme er ne cenjunctiens ef members efff . Cln this accnuntthe preef ef the law ef infinite cenjunctien is net what is called a eetr~.-rrruerive preef. it preceeded by shewing the existence ef certain suitableebjects {in this case r,, rs, ete.] witheut saying just which ebjects they are[e.g-, whether r, is T er 1.]. lvluch that is preved in mathematics isinsusceptible tn censtructive preef; much else is preved censtructiveiy. We turn new re the theerem ef centpleteness ef the main methed. itsays ef any cemhinatien rtf {ene er mere} quantificatienal schemata thateither they ceme eutjeitttly true under serne interpretatien in a nenemptyuniverse er seme truth-functienally incensistent cemhinatien ef un-quantiiied schemata can be derived frem them by the familiar eperatiens:cenvert te prenex ferm, reletter beund variables that match free enes, andthen apply LII and El. using enly new instantial variables in El. Suppese then seme premises, cenvertetl te prenex ferm and reletteredas required. lit rigid reutine will be described fer pregressively instantiat-ing them. It will be such as tn assure that each existential line teach linebeginning with an existential quantifier] gets instantiated ence, and thateach universal line gets instantiated with each free variable that ever turnsup. Begin with a great wave ef El: instantiate each existential line ence,using a variable net yet used at all. If new existential lines emerge in theprecess, instantiate them tee. Then fellnw with a great wave el’ Lil:instantiate each universal line, whether eld er emergent, with each vari-able that is already free in the prnnf. {Seme may be free in premises:ethers will have issued frem Elf] Then anether wave ef F.l, instantiatingany further existential lines breught by the wave ef l.ll. Then a deublewave ef lll: the eld universal lines get instantiated with the newly addedfree variables, and any new universal lines get instantiated with all the

res tit- General Theary cf filaantitieariartvariables new free in the preef. Then anether wave ef El; flten anetherdeuble wave ef Lil: and se en. tn the special ease where all premises are clesed and universal, thispump-priming eperatien is necessary: pcrferm Ul using a new variable. l-lere is an example ef the rigid reutine- l shall preleng the alphabet efvariables with help rtf accents: ‘t”. ’e”’, etc.Pas srrst: s: lttw Elr{Ft. v t?wr]|instances: ’ll’it'1t’ll’yl:f.’_’iwx . —-Fy} Hxtifa v tier] -[Ed wave; lst was empqrji H.r’li|\"’yl_’t']at - —Fyl {Ed wave} Ft v Gee’ lid wave} ’tI\"ytt.ZFee” . -ryi tld wave} HxfF:.=_' v G:;’.r] tdth wave, lst part} 3.rtFe v t'I.?t”.t]t tdth wave, lst part} 3.rliI\"_'vlt']e’x . —Fy]|= [filth wave, lst part] 3Jt\"tI\"_t't_’Ge”.t . —Fy} res wave, lst part] Else” . —Fe l-4th wave, Id part] Gee\" . —Fr’ [ti-th wave, Ed part} Get” . —Ft'.\"’ filth wave, Ed part} Fe vt’}’::’t'.\"” ffith wave] Fe vtlt\".t\"\" tfith wave]and se err. The reader sheuld examine this fer eenfermity te the rigidreutine. Seme examples terminate, with er witheut incensisrency, and serrte denet. ln the unending cases, new free variables get intreduced by Elwitheut end; we may suppese them generated systematically by accentu-atien as abeve. Fer each universal line. in any event, and each free variable that willever turn up, we may be sure that dtat line will eventually be instantiatedwith that variable. Fer, each wave ef El, imperting new variables, isfellewed by a wave ef l.ll that uses them all. lvlere-ever, each existentialline is beund eventually te be instantiated enee. Fer, under the abevereutine an existential line will be instantiated as seen as ail unfinishedbusiness has been cleared up; and that husiness is limited. Letal 1,.»-ts, - . . be, in an arbitrary erder, all the schemata ebtainable byapplying remi leners cf the premises te variables that are free in theperhaps infinite suite nf instances generated by the abeve reutine. Thus in

-l.'-i- Campleteuess EDTthe abeve exarnpleAg,Ag. . . .might be ‘Fa’, ‘Get’. ‘F-I”. ’l-Tet”, ‘Ge’::’.‘t’-?e’t“, ‘Ft”’, and se en- livhether there is an end re Ag. Ag, . . - willdepend en whether there is an end te the instances; in seine examplesthere is art end and in senre net. ln any event the unquantified instanceswill he truth functiens efA 1, Ag, etc. What was tn be shewn was that either the premises ceme eut true underseme interpretatien in a nenempty universe er seme finite set ef un-quantified instances is truth-functienally incensistent- This will be shewntn held even when we censider enly the instances generated under therigid reutine abeve. l shalt preve the theerem in this ferm: if each finite set ef unquantifiedin stances is truth-functienally censistent, then the premises are true underan interpretatien in a nenempty universe—and a universe, in fact, efpesitive integers. Se supp-use each finite set ef unquantified instances is censistent. Thenby the law ef infinite cenjunctien t[usingA ,,..-lg, etc. in place ef ‘pi’, ‘pg’,etc- in that law} there is an assignment ii ef truth values tg, tg, . . . teA 1.Ag, - . . that maltes all the uttquantified instances true. New let theuniverse censist ef as many ef the pesitive integers as there are freevariables in the instances—all the pesitive integers if the variables areunending. Interpret the variables, say in erder ef first appearance, asnaming l. 2. etc. Then interpret each term letter as true ef just theintegers. er pairs. etc-, that the assignment [I declares it true ef. Thus censider again eur example. An assignment £1 ef trtrth values te‘Fe’. ‘rTa;e‘, ‘Fe“, ‘i3.:.:“, ete., that mat-res all the infinitely many un-quantified instances in that example ceme eut true, is this: .l. te all ef‘Fe’, ‘Fe”. etc., and T te all ef ‘Cite’, ‘E-‘er\", ’Ge’t’. ‘Ge’e”, ’Get\"”.‘Gr’s”’, ’Ut”t’. etc. Sn. tal-ting r as l, s’ as 2, e” as 3, ete., we preceed teinterpret ‘F’ as trtre ef ne integers and ‘-t'_T’ as true ef all pairs ef integers.Thus this example turns eut unusually trivial. The plan is, in shert, sn te interpret the term letters as te grant A ,, Ag,etc. the respective truth values t,, rg. etc. In thus realizing the assignmentll. the interpretatien maltes all the unquantified instances ceme eut true. Hut then any singly quantified instance cemes eut true tee, if itsquantifier is existential. Fer, we insured that each such line -[indeed eachexistential line] gets instantiated; its instance will imply it, since ‘. . .2. . .’implies ‘Ext. . --t . . J’: and its instance will be true. being unquantified. Arise any singly quantified instance cemes eut true if its quantifier isuniversal- Fer, call it “tt';rt. - -r - - .]-‘. We insured that any such line getsinstantiated with each free variable that ever mms up. Hut all these

Illfi fill. General T.lter:u'y 1-:rj'r',:I_§‘uantr]'ieati'i-'rrtl.l-instances ’- - .e, - . ‘. . -2’ - . ete. are tme, being unquantified, andrnereever the integers l, E, etc. that are the interpretatiens ef these vari-ables exhaust the universe: se ‘- - .x . . .‘ cemes eut true er everything inthe universe. and thus 'ltt'.rl. . ..r. . .1’ cemes eut h'ue. Frem the truth ef all unquantified instances we have been able te inferthe htrth ef all singly quantified instances. Frem this result it fellewssimilarly that all deubiy quantified instances ceme eut true. Repeatingthis reasening as many times as a premise has quantifiers, we shew finallythat eaeh premise cemes eut tree. The sehemata are thus feund te ceme eut titre under an interpretatien ina nenempty universe. The universe was net empty thanlts te the pump-priming eperatien, which assur-ed at least ene free variable and thus nneinteger. Hl5T'l’JlllCPil. HUTE: The discevery and preef ef the cempletenessef a preef precedure fer the legic ef quantificatiun dates frem werlt efSltelem, Herbrand, and Gil, l91B—l\"l3tl- lt became explicit in l-Tiide|-The preef precedurcs there cencerned differ frem eu rs, but this differenceis ef little mement; a cempleteness preef fer ene methed ef quantificatiuntheery can be adapted fairly easily te ethers. in the adaptatien abeve lhave depended partly en 'Gi.idel’s eriginal argument and partly en a var-iant due te Etreben-EIEIICISESl. Centinue the illustrative instantiatiens abeve, adding a deeen mere.Z. Where the members effi.’ are ‘pg -1-pg’, ‘pg -+,t'.‘-';,’. ‘pg, —r_d,’. and sn en witheut end. determine rg. rg. lg, etc-3. The definitien ef r, that was given, fer eaeh r’, began: ‘r, is T er .l. aceerding as . . Try switching this te read ‘t,- is J. er T aceerding as. - E-‘an Lemmas 1, 2, fl, etc- still be preved fer these changed values? Checlt eaeh step-

_i_i‘ . ,|\"_.ii|t-enitet'nr'.t Thetrrent Ill?‘-ii|_-\_|i|_- ii233 LOWENHEIIWS THEOREM The cempleteness preef serves at the same time te establish alse animpertant elder theerem due te Liiwenheim {WIS}: if a quantiticatienuisehema cemes eut true under an interpretatien in rt nunenrpry universe atalt, it eanres aut true under an interpretatien in the universe trfpasitiveintegers- The reasening is as fellews- The schema cannet engender anincensisrency under the main methed. since that methed is setrnd {Chap-ter lifl]. Hy the cempleteness preef abeve, then, the schema {if it isprenex] will ceme eut true under seme interpretatien in a nenemptyuniverse ef pesitive integers. Hut then, by the argument in the middle efChapter lti, it will crime eut true alse under seme interpretatien in anycentaining universe—henee in the universe ef all pesitive integers. Liiw-enheim ‘s theerem thus helds fer prenex sehemata; and then it carries everte the ethers by virtue ef their cenvertibility te prenex ferrtt. There is ne difference between aflirming Lbwenheitn’s theerem fnrsingle schemnttt and affirming it fer finite classes ef them, since finitelymany schemata can be jeined in cenjunctien. Hut its extensien te infiniteclasses nf schemata is a genuine extensinn, and was made by Sltelem inllrllll. lt is the Liiwenheim-Sltelem theerem: if all qt a class sf quantt]‘ica-tiaual seitetnata eatne eut true ragerher under an interpretatirrn in anpnernpty universe. they came trttt true tagether under sarne interpreta-tien in the universe cfpasitive integers. The argument remains much the same as in the cempleteness preef.\"rlv'e suppese given, new, an infinite censistent class C.’ ef prenexschemata. Let E’, he C’ plus all direct E-instances ef its schemata. plusE-instances ef these instances, and se en, with a new instantial variablefer each. Let Cg be I.‘-I’, plus instances ef all its universal sehemata, theinstantial variables being all the free variables ef E’ 1. Let E’g be Cg plusE-instances; and se en. lt is just the rigid reutine again. except that thisceases new tn be a reutine ef perfermanees and becemes rather a defini-tien ef an ascending series ef infinite classes- Finally censider all the unquantified instances that are reached in anyel these elasses t.I',, Cg, - . . . lf a finite let ef these were truth-functienally

I ll} IN . Gerterrti Thretfv ef Qunntijticetienineensistent. then the sehemata in E.‘ that were their ultimate seurees ceuldbe prnvedjeintlgt incensistent by the main tnethetl. But the whnie eriginalclass C was censistent., by hypethesis. Se we cenclude that each finite letef unquantified instanees is truth-funetienallv censistent- Se then are theyall, by the law et infinite cenjunctien. Frem these unquantified instanees.then. getsl 1.14,. - - . as in Chapter 31, and 1'1, and the interpretatien ef theterm letters in a universe ef pesitive integers. .t'-‘tn impnrtance ef the Lti-wenheirn-Sltelern theerem, in its eeverage efinfinite elasses el' schemata, may he seen as fellews. Censider anynenempty universe U and an_v assertment et terms, all interpreted in thatuniverse. Censider. funher, the whele infinite tetalitv ef truths, ltnewnand ttrrltnewn, that are expressible with help ef these tenths tegether withthe truth functiens and quantificatiun nver U. Then th-e Liiwenheirn-Sltelem theerem assures us that there is a reinterpretatiun ef the terms. inthe universe ef pesitive integers, that preserves the whele bedv uf truths. E.g.. taking U as the universe et real numbers. we are teld that thetruths abeut real numbers ean by a reinterpnetatinn be carried ever intetniths abeut pesitive integers. This eensequenee has been viewed asparadeaieal, in the light ef Center's preef that the real numbers catmet beeithaustivelv eerrelated with integers. But the air ef parades may bedispelled by this reflectien: whatever disparities between reai numbersand integers may he guaranteed in these eriginal truths abeut real num-hers. the guarantees are themselves revised in the reinterpretatien. In a werd and in general, the feree ef the Liziwenheim-Sltelem theererrtis that the natrewlv iegieal structure ef a theer]_v—the stnieture reflectedin quarttifieatien and truth functiens. in abstractien frem any speeialterrns—is insuffieient te disti nguish its ebjects Frem the pesitive integers. Te say that a sehema er elass ef sch-emata eemes eut true under settleinterpretatien in the universe ef pesitive integers is net te sav that we eanwrite eut suitable interpretatiens -at ‘F.r;-.=‘. ‘t}'x‘. ete. as fermuias inarithmetical netatien. Elttr preef ef L-iZiwenheirn's theerem assured us thatfer any censistent sehema there is a true interpretatien in the universe efpesitive integers. but it gave us ne way ef finding and phrasing it. Uurpreef used the cempleteness theerem. the preef ef which appealed, afterall. te the neneenstruetivett. ti. ete. Her dues nur preef assure us that theinterpretatien. even if it were feund, ceuld be phrased in a pureivarithrnetieai veeahular1t-—ti1e veeabualtv et ‘plus’. ‘times’, ‘p-ewer‘,‘equals’. and the iilte. There is, hewever,, a eenstruetive imprevement en Liiwenheim*s

33. .i'_ri-'u'r=nheim'.r Tltret-em El Itheerem due te Hilbert and Hernays‘ that tells us all this: hew te find andactually write eut. fer any censistent schema. a Lrtte interpretatien in theuniverse ef pesitive integers—and in purely arithmetical netatien at that.In fact a veeabulary ameunting te ' plus‘. 'times‘. \"equals‘. and thequantifiers and truth functiens is sufficient-—the vecabnlary. as ene says.el’ elementary number tlteetjv. This result appears the mere remarkable when we read. as we shall inthe nest chapter. that there can never be a fully general technique ferestablishing censistency. Hew then can Hilbert and Hetrtays give us ageneral rule fer writing eut a true interpretatien ef a censistent schema?Wl'tat they give is a general ruie fer writing eut. fer any schema. anarithmetical interpretatien which can be depended upen te ceme eut truein ease the sehema dees happen te be censistent. The preef ef this Liiiwenheim-Hilbert-Hernays theerem is beyend thescepe ef this heelt. lt will be werthwhile. hewever. te netiee a certainbearing that it has en the very netinn ef interpretatien. in Chapters IE and 2? there was ne nutright statement ef what aninterpretatien ef a term letter is. but enly a statement ef what it means tehave given ene: it means having settled what members ef the universe. erwhat pairs. ete.. the letter is te be ceunted as tnte ef. Utte way ef settlingthis is by supplying an abstract {Chapter lb}. but there are ether merediscursive ways. Alse there are degrees ef senling. and. therewith. de-grees ef having interpreted; we interpret the term letter insefar as wesettle what tn talte it as true ef. Te face it. then: what is an interpretatien? ls it an espressien. namelythe abs tract that we are prepared te substitute fer the term letter? fir is it aclass. narnely the class ef the things that the term letter is talten te he trueef‘? Primufncte. the eheice between these twe altematives sheuld rnaire amaterial difference; fnr there is ne assurance that each class et' ebjects ineur universe is specifiable as the etttensien ef seme term er epen sentencein eur language. lt depends en eur eheice ef universe and alse en hewrich a vucabulary we assume there te be at nur dispesal ever and abeveeur legical netatiens ef truth functiens and quantificatiun. If the classesthus eutrun the available expressiens. then we may eitpect there te be adifference. e.g., in the cencept ef validity. aceerding as we define it astruth under all interpretatiens in the class sense er as truth under all ‘l ‘v'elurne 2. pp- 23-it-153. Fer a strengthened versien. mere simply preved. seelllleene. I952. p- .'lEJ-=1. Theerem 35.

E l2 Hi. t']enct'rti Tltenrjv eftgnnntificntinninterpretatiens in the term sense- Mereever. it has been an accepted tenetef classical set theery fmm Canter nnward that the classes de eutrun theettpresslens- Hut new a remarkable thing abeut the Liiwenheim-Hilbert-Hernaystheerem is that it cuts threugh all this. Hewever estravagantly the classesmay eutmn the expressiens. this theerem assures us that when we definevalidity and cetisistency it is indifferent whether we tallt ef all and semeinterpretatiens in the sense ef classes er in the sense nf terms. Thetheerem assures us that all these eittra classes will be indifferent tn valid-ity and censistency. in this sense: if a schema is fulfilled tnr falsified} byseme unspecifiahle interpretatien invelving nameless classes. it is alsnfulfilled {er falsified} by seme ether interpretatien that can be written inthe netatien ef arithmetic. The Ltiwenheim-Hilbert-Bernays theerem enables us. fnr that matter.simply te bypass the term ‘interpretatien’ and tallt directly ef suhstitufinn.st schema is valid if all statements ehtainable frem it by substitutien aretrue. and it is censistent if seme ef them are tme. The theeretn assures usthat we can retreat te this hemely fermulatien with impunity as leng as thevncabulary which we suppnse available fer such substitutiens is nnt segrntes-quely impnverished as te be inadequate te elementary numbertheery. There is philnsnphieal cemfert in the assurance that we can tallt eflegical validity and censistency withnut appealing tn a limitless realmel\" abstract ebjects called classes. We feel that in talking nf substitutien nfexpressiens we still lteep eur feet nn the grnund. A related peint ceuld be made en the basis directly ef the cempletenesstheerem. even independently nf Liiwenheim. Hilbert. and Hernays. Thattheerem already furnishes fermulatiens ef validity and censisteeey thatsay nething ef classes--ner even ef substitutien ef predicates. ferthat matter. A schema is valid if. frem the preneit ferm nf its negatien. atruth-functinnal incnnsistency is derivable by the main methed.

.l=t. Drrv'.tir:rns' rind‘ the ii.-'ttri'eriri'rrbir EI3l 34 DECISIONS AND THE UNDECIDABLE lt is indifierent te the main methnd whether we write eur premises wither withnut initial existential quantifiers- This is nnt tn be wendered at. ferwe neted early in Chapter 25 that initial existential quantifiers were in-different te censistency- This indifference is reflected in the rigid reutinenf Chapter 31. since that reutine prnvides that an existential quantifier. ifnet preceded by a universal. gets instantiated enee fer all; we never gethaclt tn it. The E-instance with its instantial variable ceuld as well havebeen the premise tn begin with. it is the existential quantifiers preceded by univcrsals that malte preefsrun lnng. Such an existential quantifier returns tn the surface repeatedly asthese universal quantifiers get repeatedly and varinusly instantiated. Eachlirn-e it surfaces it gets instantiated again. since it initiates a line each timethat is altered by having received dilferent instantial variables threugh thenew Lll steps. Each ef these El steps. then. fumishes a new variable thatis grist fnr further Lil. and in this way we may gn en grinding eutinstances witheut end. The unending example at the middle ef Chapter 32sheuld he lnelted at with this in mind. When all premises are such that ne existential quantifiers are precededby universals. eur rigid reutine nf Chapter 32 always grinds gratifyinglytn a halt. There is just the fixed initial supply nf what are in fact er ineffect free variables. and these are all that get used in UI. The tetalnumber nf instances ailewed by the rigid reutine. fnr each such premise.will be just the number ef universal quantifiers in that premise times thenumber ef free [er existential] variables in the prernises altegether. ln-deed. as already remarlted. the existential quantifiers. being initial here.ceuld have been drnpped in the first place; nur ptetttises are nething meretitan pure univcrsals- We can checlt the tetality ef their unquantifiedinstances fer truth-functinnal censistency. cnnfident nf an affirrnative ernegative answer- We are net then in the pesitien nf just checlting mnreand mnre unquantified instances fnr incnnsistency with never a nntinn nfwhen tn give up; we have a decisien precedure.

Ell‘-l Hi’. Cienerni Tiienry sf t',§fnnnti_t'ientt'nn In Chapter 29 we saw a decisien precedure fer validity ef pure existen-tials. This already. implicitly. was a decisien precedure fnr censistency nfpure universals- Fer a schema is incensistent if and enly if its negatien isvalid; and the negatien ef a pure universal he-cemes a pure existentialunder the mles ef passage tit} and {ill} nf Chapter 13- What is interestingin the decisien precedure fnr censistency that has just new emerged fremthe main mel:l1nd is nnly the particular ferm in which it has appeared. andits relatien te the main methed. lt dnes suggest that in cnnvertingschemata tn prenex fnrm we sheuld faver existential quantifiers if weexpect tn apply flte main methnd. just as we did the eppesite when tryingfer pure existentials. tltcnially we cart effertlessly switch cnurse when wesee lit. thanlts te the aferementinned rules ef passage {'3'} and [ill] nfChapter E3. l have alluded twice tn the impessibility nf a decisien precedure fnrquantiiicatienal schemata generally. The preef. due tn Church and Turingin lltilti. exceeds the scepe ef this heelt.l' but seme remarlts are called ferregarding its significance. It dnes net preclude mechanical preef prece-dures; the rigid reutine nf Chapter 31 is nne. Any preef precedure can inprinciple be get dewn te a mechanical reutine in at least this silly way:just scan all the single typegraphical characters admissible in the prnnfprecedure in questien. then all pessible pairs nf them. then all strings nfthree. and se en until yeu get te the preef. The usual dependence en lueltand strategy in finding prenfs is merely a price paid fnr speed: fnr an-ticipating. by minutes nr weeks. what a mechanical reutine weuld even-tually yield. Where a cemplete preef precedure differs frem a decisien precedure.then. is net in being less mechanical. The difference isjust that the preefprecedure is net a yes-er-nn affair; it decs net deliver negative answers.Failure tn reach an ineensistency preef after a large number ef steps.hnwever systematically and mechanically prngrammed. dues net shewcensistency. it prnnf precedure is nnly half nf a decisien prneedure. Wlten there is beth a pmnf pmeedure and a disprnnf pmeedure {fervalidity er censistency er any ether preperty}. there is alse a decisienprecedure.‘ The twn halves can be jeinetl as fellews. First we weuldmechaniae beth the prnnf precedure and the disptnnf precedure. in thesilly way if nnt etherwise. \"Then. te decide whether a fnrmula had thepreperty in questien [validity er censistency er whatever]. we weuld set \" Fnr a fairly readable rendering see my Selected Legic Papers. pp. 212-Elli‘- l‘ This ebservatien is due tn ltleene. lass- Ursee I-tleene.I1l52.p.1s-t.T\"neurem tile-

id. Der-i.'tinn.r nrtel the Lin-decidnhie Elinne man nr machine in quest nf a preef and annther in quest nf disprenfand await the eventual answer frem nne nf them. ln particular. then. ltnewing as we dn frem Chapter 32 that there is aeemplete prn-cedure fnr disprnving the censistency nf a quantificatienalsehema. and frem Church and Turing that there is ne decisien pmeedure.we cnnclude that there is nu eemplete precedure fnr preving quantifica-tinnnl schemata censistent. Cnmmnrtly we preve a schema censistent bypteducing a true interpretatien; and this is quite the right way. as leng aswe can find truths tn the purpese and shnw them true. Se what we havetn recngnite is that nn snund prnnf precedure can be sn stmng as tn aftferd prnnfs nf statements illustrative nf all censistent quantificatienalschemata. lvleanwhile there is an nbvinus precedure fnr deciding whether asehema cemes nut true under all nr snme nr nn interpretatiens in a uni-verse nf given finite siae n. lust transcribe the universal and existentialquantificatiens as rt-fnld cnnjunctinns and altcrnatinrts. as nnted in Chap-ter 2?. and then checlt: fnr truth-functinnal validity and censistency. Itfellews that there is a eemplete precedure [rte lenger a decisien prnce-dure, but still a prnnf precedure] fnr shnwing that a schema is finitelycen.ti.rtent—i .e.. that it cemes eut true under at least ene interpretatien inat least nne nenempty finite universe. This prnnf precedure cnnsists sim-ply in alleging an adequate size n nf the universe. and leaving the readertn checlt it by the tmth-functinnal methed. Thus an impertant centrast emerges between finite and infinite uni-verses: there is a eemplete prnnf precedure fer finite censistency. butnnne fnr censistency. The sehemata that are censistent but net finitely anare the stubb-nrn ltind. They may he called infinity rchentntu. An easilyrecegniaable example is:{ll \"tl'.r[—F.xx . ltt'y\"It\"'rt[Fxy . Fyr .—x Fxr] . Hw Fxw].ll requires an infinite universe. Fer. talte anything x|. By the last part ef[1] we have Fx-.x, fer snme I2; alsn Fxgxg fnr seme xg; and sn nn witheutend. Then. by the transitivity aflirmed in the middle nf ll]. we get alseFx,.r,-.. F.rtx.,. F.tgt.,.Fx1.t,.. and sn nn. lvlerenver. by the ‘—F.t;x’ in ill.these things x|. xg. x,-.. . . . are all distinct. Thus {ll is net finitelycensistent. ‘fer it is censistent; it cemes nut true in the universe nf integerswhen ‘F‘ is interpreted as ‘st’. Here is annther infinity schema. briefer but less readily renegniaed:

I lfi Hi‘. Cienerni Thenry cf -Qlunnnjlicntinn ltfx §lylll't{Fxy . — Fxx - Fyr -1 FIE].Frem a I933 paper by Gbdel it is ltnewn that this prefix \"vb: Hy life‘ isthe simplest that a prenex infinity schema can have. There is ne cnmplete prnnf precedure fnr shewing schemata te beinfinity schemata- Fnr. if there were. we ceuld add it tn nur cnmpleteprnnf precedure fnr finite censistency. and get a eemplete prnnf prnce-dure fnr censistency. The infinity schemata cnnstitute a stubbnrn class which is the cemmenpautni? nf twn stubbnrn classes: el. the class nf all censistent schemata.and H. the class nf all finitely incnnsistent schemata [schemata true underne interpretatiens in nenempty finite universes]. ‘We have ebserved thatthere is nn cnmplete prnnf precedure let membership either in .d er ini-til. The same can be said efllt this fellews frem a theerem nf Trachten~bret. aceerding tn which there is nn cnmplete preef pt'ecedure fnr finitevalidity. Talten in cembinatinn with the Liiwenheim-Hilbert-Hernays theerem{Chapter 33}. the impnssibility nf a cnmplete prnnf precedure fern has astartling further cnnsequence: Cuiidel‘s theerem ef die impnssibility nf acnmplete prnnf precedure fer elementary number theery. If we ceuldpreve each trite sentence ef elementary number theery. then we ceuldpreve the censistency nf each censistent quantificatienal schema bypreving a nuth nf elementary number theery illustrative nf that schema. This is nnt the histnrical reute tn Ct-i;'tdel’s theerem. I have appealedhere te the impnssibility ef a cnmplete prnnf precedure fnr censistency.This I inferred frem the Church-Turing theerem tl1at there is ne decisienprecedure fnr quantificatien validity. But the prnnf nf the Church-Turingtheerem. emitted here. uses the essential tri clt nf Clhdel’s prnnf nf his ewntheerem; and G-iidelis came first. in I93 l. i.]i.iti=el’s way was tn argue directly te the incnmpletahility nf elemen-tary number theery. by shewing hnw. fnr any given prnnf precedure P fnrelementary number theery. a statement its nf elementary number theerycan be censtructed which will he true if and enly if it is nnt prnvable bythe precedure P. Either Sp is prnvable. in which ease it is false and sn thegeneral preef precedure P is discredited. nr else Sp is n'ue and net prnva-ble. in which ease the prnnf precedure P is incnmplete. In brnadest nutlines. C~iidel’s cnnsnuctinn nfilp is as fnllnws. It is easytn assign integers in a systematic way tn all the finite strings. hnweverlnng. nf signs ef a given alphabet. lf the alphabet has just nine signs. wecan assign them the integers frem l tn '5‘ and then we can get the integer

.i'ri'- Decisintts nit‘the Unrsierridnblr I l l‘fnr any string nf signs by cnncatenating die cnrrespnnding digits inte aleng numeral. If the alphabet has mnre than nine signs. we can easilyadapt this methnd er cheese annther- E-uppnse this dnne int the netatien nfelementary number theery. Thus each sentence in that netatien has itssn-called [iiidel number. G-iidel then shews that. given F. it is pessiblewithin the netatien nf elementary number theery tn fnrmulate an epensentence. ‘. . ..r . . .* say. which is n-ue nf any nurnberx if and nrrly if x isthe Giidel number nf a statement prnvable by P. 1f we put fer ‘xi in‘— [. . .x . . .}' the actual numeral designating snme particular number rt.clearly the resulting statement. schematically ‘— t. . .n. . .}’. will be true ifand nnly if that chesen n is nnt the Cildel number nf a statement pmvableby P. But tliidel shews that n can be sn chesen as te tum nut te be theEiiidel number nf a statement equivalent tn ‘— i. - . n -..l’ itself. Thestatement prnduced by that sly chnice nf n is the snught Sp. true if andnnly if nnt prnvable by PF when we are cnncerned with cnmplete prnnf prncedures and decisienprncedures fnr the truth nf statements. as in elementary number theery.rather than fnr preperties nf sehemata. the difference between the twndisappears——at any rate if nur vncabulary includes negatinn. Fnr. a prnnfprecedure fnr the truth nf statements carries with it a disptnnf precedure:ynu disprnve a statement by preving its negatien. Sn. by the aigaagargument lately attributed tn it-Eleene. a cnmplete preef precedure fnr thelrI.lth ef statements assures a decisien precedure. Still a eemplete preefprecedure fnr validity er censistency er incnnsistency ef schemata re-mains far shert nf a decisien precedure. simply because a schema can becen sistent withnut its negatien‘ s being incnnsistent. and a schema can failef validity withnut its negatinn's being valid. Thus. thnugh the impnssibility nf a cnmplete prnnf precedure fnrelementary number theery cemes as a sheclt. the impnssibility ef a decl-sinn precedure fnr elementary number theery says as much. This is acurieus pnint. since the impnssibility nf a decisien precedure seems lesssurprising than the nther. ‘varieus unselvcd prnblems nf lnng standing.after all-—-nntably the celebrated nne nf Ferrnat—can be fnrmulatedwithin the nntatinn nf elementary number theery. and a decisien prnce-dure fer that demain weuld have made a clean sweep nf them all. Presburger and Sltnlem have shnwn that when elementary numberthenry is funher limited tn the extent nf drepping muitiplicatinn and T Fuller details ef t]iidet's argu ment may be feund nnt nnly in his l5|'3l paper hut alsnin his i934 English prese ntatinn. and in Caniap's Lugient Syntax (esp. pp- I29» I3-=1-jt. andin Chapter i‘ nf my rlrtnthernsticrrl Lrrgir.-.

E I E llt , General Theery sf fllunntrjicntienlteeping just additinn. er vice versa. the resulting thcery dues admit nf adecisien precedure. lrlttrat is mnre surprising. Tarsiri has shewn that theelementary algebra nf real numbers likewise admits ef a decisien prece-dure. The netatien nf this elementary algebra is precisely the same as dtatdescribed abeve fnr elementary number theery. including beth additinnand multiplicatinn; the enly difference is that the variables are censtruednnw as referring tn real numbers generally rather than just te whele enes.Despite the seemingly greater cnmplexiry nf its subject matter. elemen-tary algebra is cnmpletahle and mechanically decidable while elementarynumber theery is nnt. New if in view nf Gfidells result nur lntnwledge abeut number issubject tn unexpected Iimitalinns. the very nppnsite is trtte ef eur l:newI-edge abeut such itnnwledge. Elne nf the few things mere surprising thanthe incnmpletahility nf elementary number theery is the fact that suchincnmpletahility can actually have becnme ltnewn te us. Giidells resultbrings a new branch nf mathematical theery te maturity. a branch ltnewnas “metamathen1atics“ er preef theery. whnse subject maner is math-ematical theery itself. lvluch remains tn be discnvered regarding the limits cf cnmpletahlethenries. and the essential structural features which set such thenties apartfrem thnse which are incempletable. Etut the reader whn weuld acquirethe ltey cencepts and techniques nf this crucial new field ef study.metamathematics er the theery ef prnnf. must lnnlr. beyend the beunds efthis legic bnnlt. See Tarslri. et al.. Undeciduhie Thenries; Hilbert andBernays; Kleene; Smullyan; Davis; Rngers; Shnenfield.EIERCISESI. Can there be a eemplete disptnnf precedure fnr elementary number theery? Ur a decisien pmcedure adequate te all but a firtite number nf the statements in the netatien nf elementary number theery? Justify ynur answers.2. Fmm Trachtenbrnt’s theerem hnw dnes it fnllnw that there can be nn cnmplete prnnf precedure fnr membership in B‘?

_i‘5_ Frrrrr-rirrnrrl Hnrrrrcrl Ferrns llill—s§I FUNCTIONAL NORMAL FORMS Getting all existential quantifiers nut in frnnt has. we saw. twe advan-tages under nur main methnd: the miner advantage that we can just fergetthnse quantifiers. and the majer advantage that the preef precedure be-cnmes a decisien precedure. lt alsn has a third advantage: the remainingqu antifiers. being unifnrmly universal. can be instantiated simultaneeuslyrather than in sequence. New there is a devinus device that enables us tn enjey this dtird benefiteven when existential quantifiers can nnt all be gut le the frent and adecisinn precedure is nnt tn be heped fnr. Te sec the fundamental idea.cnnsider \"'Iil'.r Hy Fry‘. lt says that fer any ebject x there is an ebject y.pessihly different fnr different chnices ef .r. such that F.r_y. Reughlyspealting therefere it says there is a_,r\"nnetinn —a way nf piclting. fnr eachebject .r. a dependent ebject _v,—such that llilll Fr:_1.-I. The gain in thisrephrasing is that nur new tacit existential quantif|cr—‘there is afunctien\"--cemes befnre ‘ltfr’ instead nf after it as ‘Hy’ did. Cnmingthus initially. it can be left tacit in incnnsistency prnnfs. Such is the theught behind what l call the functienal nnrrnrilfnrm nf aprenex quantificatienal schema. Delete all existential quantifiers and at-tach. te the recurrences nf the variable nf each such quantifier. subscriptslisting the variables nf all the universal quantifiers that preceded dtatexistential quantifier. Thus the functienal nnrmal ferm nf ‘lttlx Hy Fxjy’ is'lv'x Fxy,'. The functienal nnrmal fnrm nf: 11.’ llify ltif; aw llifn Ev Fryrwuvis: lily la’: \"fir Fxyrrrswuvuy... The accnu nt nf this netatien in terms ef the existence ef functiens is nntan accnunt tn rest with. as in any sense a prnnf nf equivalence ef a sche matn its functienal nnrmal ferm. The accnunt slurred nver peints nf set

221'] Ht. General Tlrrnry rs’ [Qtrnnthlcrttinntheery that I shall nnt gn intn—the nature and existence nf functiens and.what is mnre serieus. snmething ltnewn as the axiem nf chnice. Hnne nfthis is needed tn shnw the seundness nr cnrnpleteness nf the prnnf prnce-dure that l shall present in terms nf functienal nemral fnrms; these virtueswill be breught nut rather by a direct enllafinn nf this prnnf precedurewith the main methnd. The pninr nf the tallt nf functiens was just tn give afeeling fnr the netatien. We turn new tn illustraticn and cinser examinatinn nf the methed efprnving incnnsistency by functienal nermal ferms- Jastifi catien will cnmeafterward. Let us gn baelt tn the premises {ll—{3] in Chapter 3tl=. A nrle nf themethnd nf functienal nnrmal fnrms is that befere cenvening premises tnfunctienal nennal fnrm we must reletter all existential quantifiers sn thattheir variables are distinct frem nne annther and frnm variables that arefree in any premise. The premises {ll—r{3l are already in nrder en thisseem. Putting them intn functienal nnrmal ferm and deriving instancespurely by Ul. we get this new incnnsistency prnnf:Prrasrrsas: \"tt\"y Frryinstances: ‘Ex ‘sly —[Fv,y . Fyx} ‘vlx ‘v\"ytFxy —r-t —-Fxwn. . Fwuy .v. Fywy... . .Fw....x} Fur-.. Fury... —-it —Fuw....‘ . Fwghv, .'tt. Fvuwmg . Frewirn Fuwm. —{Fr»',,w,g. . FwwlulThese fnur instances. lilte the fnur unquantified instances {T}. rflfl]. it 1},and ill} in the rendering in Chapter 3t]. are truth-functienally incensis-tent. But it is characteristic ef the methed ef functienal nermal fnrms thatdie enly instances dtat appear at all are unquantified. The instances cnmedirectly frem the premises by multiple Lil. and it is irnpnrtant tn nnte thatthe universal variables are instantiated in subscript pnsitinns as well aselsewhere. The expressiens instantiating them are nn lenger just simplevariables. but any expressiens belnnging tn what l call the lexicnn ef thepremises. Te get the lexicnn we innlr re the premises in functienal nermalferm and piclt eut. first. the simple ft'ee vatiables——in this case just ‘til.They belnng tn the lexicnn. Then we talte alsn the functien letters. i.e..the letters that carry subscripts; each functien letter. talten tegelher withany members nf the lexicnn in place nf its subscripts. censtitutes amember in turn nf the lexicnn. Thus the lexicnn nf the premises abeve

35 . Frrnr‘tr'rinrrl' r\"'v'er-In-rtf Frtt'-v't.'F 11!cnmprises ‘tri. ‘r'..\". 'w....‘. ‘v..H‘. ‘rr:,.|..,’. 'tr=,.,.\"'. 'w..m.‘. ‘v.r,..,‘. and seen.in prnving incnnsistency there is never any need tn instantiate with any-thing hur lexicnn. [If there is rrn free variable. start lexicnn with ‘.r’.l This methnd ef incnnsistency prnnf is an extensinn nf nne that waspresented by Sltnlem in IEITS. Essentially the difference is just that hisserved enly tn preve the incnnsistency nf a single prenex premise ratherthan a cembinarinn nf them. The methed is advanragenus nnt merely in allewing us te pcrfermseveral Lil steps at encc. rlt mnre impertant advantage is. in a mnun-taineering rnethaphnr. that it eliminates the need nf advance bases- Un-der the main methnd we wnuld mnvc perhaps frnm a premise\"tit'r H'_y ‘tile Fxjrrf tn ‘Hy \"It's Fr'y.r' tn ‘bl: Fvwr’ te ‘Fvr-vr-‘. recnrdingand saving the twn intermediate lines. and then later we might recur reene ef these intermediate lines. \"'tt'.=; Fvwr‘. tn get tn ‘F-rrvw‘. Under themethed nf functienal nnrmal ferms. en the nther hand. we pass frnm thepremise direct tn ‘Fv-wv‘ and again direct tn 'Fvrvw' in twn independentand uninterrupted snrties. with nn need ef the branching pnint ‘ltifa Fvwrg‘as a way statinn. Under this methnd the premise has really becnme“'I:t'.r ‘tit’: Fxyyr‘. nf ceurse. and the twn end results ‘Fvrvv‘ and *Fvww'have becnme. strictly spealting. 'Fvy,v‘ and 'Fr'y.._v,’. Tn relate this methnd te the main methnd. talte the main methnd in therelaxed fnrm in which it was last centemplated. vir... with initial existen-tial quantillers drnpped frnm all premises. The nnly existential quantifiersin the premises are these buried under universal quantifi ers. New enn siderthe reute. aceerding tn the main methnd. frnm nne nf these premises—say again ‘ltfx Hy ‘st’: F:rys’—tn each ef its unquantified instances. Whycan we nnt cever each such rnute in enc leap‘? Simply because the eheicenf instantial variables fnr the El step is nnt free. Whenever the ‘lltlx’ isinstantiated anew. tn yield a nnvel intermediate line. the ensuing El stepdemands a fresh variable. When en the nther hand the reutes frnm thepremises tn twn unquantified instances instantiate “'tt\".=r‘ identically butdiverge ultimately en \"tt's'. we arc free tn instantiate ‘§_v' identically;under the rigid reutine nf Chapter 32. indeed. we wnuld be beund te. Themain methnd handles these dcpendences by establishing an advance baseer way statinn litre \"ti\".-1 Fstats‘. we nnted. frnm which tn preceed nnw tn‘Fr.-vr-r-\" and nnw tn ‘Fvnrrrri. The alternative. instant insrantiatien. requiresautematic bnnlrlteeping. calculated tn allnw twn unquantified instances nf'ltt'.r Hy \"tt'.'; F.r_v.:‘ tn have any variables in place nf ‘.r’ and ‘s‘. but temalte thcm agree nr disagree en the variable fnr ‘y’ aceerding as theyagree nr disagree nn that fnr ‘.r‘- [I put the matter strnngly because l am

22.2 Hi‘. Gen-amt Thenry sf Qaeatijirnriqn baelt an the rigid reutine-) The functienal nermal ferm prnvides thebe-atthzeeping deviee: a eemplea ettistential \"variable\", in effect, nataely ‘yr’, whieh will autematically instantiate identically under identieal in-stantiatiens nf the preceding quantitier \"\"li'r' and differently under dif-ferent instantiatiens ef “'il'.r'- Stteh, then, *-vitheui tallt til functiens, is the rele at the subscripts anthe esisteatiat variables- it beeernes eiear, despite the speeifieity nf theeitampie abeve, that the me-thnd pi ft! netienal ntirrnal ferms isjttst a quieltway rif deing the wetlt that is dune by the rnain methnd under the rigidreutine. There is a variant melhti-d at functienal nermal feirms, due tri Dreben,that dens net depend en prenex tenn. sehemata need little preparatinn.Cenditinnals and bicenditienals need te be expanded inte alternatien.eanjunetitin, and negatien iftheir ea-mpanents centain quantifiers, but netti-tlierwise. Hegati-an signs need tn be driven inward by Detviergatfs iawsand the rules ef passage ef negatien {{9} and t Ill} ttf Chapter 23}, but enlyuntil I1-I} quantifier appears in a negated sehema. In shert. what is requiredis that quantifiers be tiverlain enly by cenjunctien, altematien, andquantifiers. Alse. as in the previeus methed ef funetinnal nermal tnrrns.the existential quantifiers must be relettered se that their variables aredistinct frem the free variables and frnm ene anether. Thus suppese we want tn preve these premises incensistent:{Ii HI Vi’ FIJI’,ill — 3.r\"tI\"e3yt[Fey . Fyirjl.{3} 'tl'.r\"d'y[Fry —i-. \"tit-[Fey -1- Feel —* 3etFye - Peri].We prepare [2] by using the reles at passage te drive the negatien signinward: ‘I’: El: ‘Itty —{Fzy . Fys].We prepare {3} by translating flte eater twn ennditinnai signs and thendriving a resulting negatien sign inward. \"t\".r‘tI'y[—F.r_v v He —tFey -I-F.rei v 3el_'Fy.: . Fari]-We prepare tl]—{3) further by relettering the eaistential quantifiers ferdiversity. Fer clarity I carry this relettering a little farther than is strietlyneeessary.

_i'_\"i- i\"*':int'ti'tJrmt' Nermni‘ Ferrer Z13 Ha ‘tidy Fay. \"tit Ev \"tt'y —|[Fvy . Fyirl. \"li|\"'J;' \"ti|\":|.t[—-_F_!:_\"_j-,= 't.|I\" at-tr — [Fw_'y —t- FIW} \"it 3-'tlF}‘t' - .F.tIl|.The reader may have begun te reeegniee that these are equivalent te thepremises t'l]—t_'3} ef Chapter Iitil, whieh were used again in the presentchapter te iitastrate the first methed et\" funetienal nermal ferms. Bet let usge ahead new with the new methed- We ferm the ftinetienal nermal fermsagain,just as befere.|[-fl] Vt‘ Fave -' -'{5} ‘tt'.r ‘Ii\"'y —tFt'_,.].~ . Fyr],lb} \"IiI\"_r 'tit'_=i\"| -— .F.r_y ‘v‘ — tFn*y,,)' —P~ F.rw”} ti’. F_y.t_,,,, . Ftmr].This time the lesieen eemprises \"it\", ‘t-3,‘, ‘tv,m', ‘tn’, ‘vhf, and se en.lneensistent instances are fertheeming- This hypassing ef the prenes term has an effeet en the rule fnr ferrningthe functienal nermal ferm, theugh it did net happen te shew itself in theabeve esample- The sebseripts en an esiste-ntial variable sheuld list justthe variables ef the universal quantifiers whese seepes eentained that-e1r_iste.|'itial quantifier; and these need net be ail the preceding universalqttantitiers. when the sehema is net prenezt. E.g.. the sehema:{T} his Hy F:-ry . his Hts Eizwhas the tunetienai nermal ferm “Ii\"'.t Firy, . ‘lite Grit-E\"; the eeeurrenee ef‘hit’ eff te the left dees net iinpese a suhseript Zr\" en the ‘iv’, beeause theseepe ef “'tI\".=r’ steps shert ef there. lf we had begun by turning {T} inte preaes ferm se as tn sabjeet it terhe previeus methed et functienal nerrnai ferms, we sheuld have had tnsettle fer ene er ether ef:liI\";r H}-‘Vs Ht+'{F,r_t= . Gent}, his Ht1rliI\".r 3y[F,ry . Gent},net te mentien less prudent eheiees sueh as:\"'i|\".1\"i':: 5}‘ Htvtfiry . t§Fan'}.This weuld tnean ending up with ene er ether ef the iunetinnal nermalferms:

224 tit. tier-teretTt1rerye_tI2urinrtjirertee \"e'r\"t\".:tFr_v, - Gate“). \"tt':‘t\"rtFxy,,- . Gewyl.Either way we get a deuble subscript. as we did net when we preceededdirectly frem [Ti in lJrel:>ei1’s way- This brings eut an advantage ef Dre-hen's methed additienal te the advantage et sparing us the eseursien inteprenctt ferm: it semetimes issues in simpler subscripts. thereby simplify-ing the eventual search fer incensistent instances. lustiiicatien n-ii this methed will he emitted here.EIERCISESl. Find incensistent instances at |[-1]—t'fi-].2. Hy way et\" further esercises in genereus number. repeat the esamples and esercises tit\" Chapters 29 and Til by the tnetheds ei functienal nermal ferms.Fae MHEElTtBHROADND'5 The main methed and the metheds ef functienal nermal ferms weremetheds ei preving incnnsistency. New validity is truth under all in-terpretatiens, as incensistency is falsity under all interpretatiens. ‘tlalidltyand incnnsistency are related as truth and falsity, hence by duality{Chapter I1}. iitlternatien is similarly related te eenjunctiene and esisten-tial quantificatiun te universal. Each el’ these incnnsistency metheds,then. can be cenverted te a validity methed by duality. Thus talte againthe main methed. The fermal meves undergti little change. Lil and Elfiwiit-‘it illeir mica; hewever. since beth were present and beth remainpresent, this nnly means transferring te Lil the requirement that the in-stantial variable be new. Hut the geal changes radically; what is wantednew el an accurnulatien ef unquantified instances is net that their cen-

35- Herhri:tne\".'t Methrid 115junctien he truth-functienally incensistent, but that their altematien betrtlth-functienally valid- What we preve by achieving this geal,rnereeverc is net that the cenjunctien ef the premises was ltlcflflsislcflt.but that their alternatien was valid. Thus censider, te begin with. a trivial ineensistency preef by the mainmethed- The tep twe lines are premises and the succeeding fetir areinstances. 3.: \"tty Fay Ely Vs — Fxy ‘tty Fejv his —F;ra-' Fe iv — FawThis preves the ineensistency ef the cenjunctien: it h\"_v Fry . Hy \"II\".t —F.:}'.New the validity ef the alternatien: Var Hy Fry v\"tt\"y 11: —Fxyhas the fellewing preef. the dual ef the ineensistency preef abeve: Vs Hy Fry lily El: ~-Fry Ely Fey Hr —F.rn-' Few —FetvIt is the validity ef the alternatien ‘Few ‘v‘ —F:;tv’ ef these last twe in-stances, net the ineensistency ef their cenjunctien, that attests te thevalidity ef the alternatien ef the twe tep schemata. This same latter preef might be theught te deuble as a preef ef theineensistency ef the cenjunctien ef its tep schemata by the main methed.This weuld be wreng: the iinal step ef El vielates the ineensistencymethed in using an eld instantial variable ‘s‘. lviereever the tep sehemataare in fact censistent; interpret ‘Fry' as ‘ii = yl and they beth becnmetrue.

Elb Hi. [Teuerttl T'hrer_v at QrttinIt'j'ic'rtri'eh Frem the peint ef view ef implicatien. the ineensistency pre-efs and thevalidity prnnfs face eppesite ways- ln the ineensistency prnnfs. implica-tien tended dewnward. Ul was implicative. El was net. and that was whatcemplicated the seundness argument. in the validity prr-refs. implicatientends upward- El is what is implicative here. but upward. The reasen thelast step ef the validity preef abeve decs ne harm. despite the staleness efthe It‘. is simply that ‘—Ft'w’ implies ‘Ex —F.rt-.1‘. ll we were indepen-dently tn establish the seundness ef this preef precedure fer validity—which we ceuld de by precisely arguing the seundness preef in Chapter313 ef the main methed. duality fer dt|ality—we weuld find that whatcemplicates this argument is that the Lil ef this methnd is net impiicativeupward- Find new it is Lil, nnt El, that has te he hedged by the fresh-vartahle requirement in erder that the justiticatien be made te ge threugh. Fnr a mere substantial er-tatnpie let us term the dual ei the incensis-leney preef-tl}—t ll} ef Chapter 3!]. Fts an aid te writing the dtlnl we thinltef the ‘-1-‘ in that preef as ‘v‘ with the antecedent negated. The duals t-ti\"the eld premises will he called \"alternative the-ses.\" since they are newschemata whese alternatien is te be preved valid-.t|.tsarvst|ve t_l} vs Ely Fa-_v tttasas: {E} i Fl E-t vs Ely — {Ft-_y u I-'_1.-it Jit-Isrsrtcr-s: till Er 3_t-\"\"tI\"wt'— F.t'y t — F.rv.-' vFv.'_s . l'~'_t.'w v Ftvr} tst Ely I-ti\" inf {l}i [til \"iI\"v Ely - tFt-_-.- v F_vei ief{1}} {T} 3}‘ — {Fry v F_vs_l' inf {5}} iii} Fct [ef t_-tt}j ts} 5_}\"'llr1-I-‘l-F£§_}' . —Fsvt- ‘v‘ Fwy t Fy'vt' ‘Iv’ Fa-at} inf ill] {ll-ll vs-t-Fn . ——F;w v Ftvt . rat 'v'F'a-g_] tartar] {Ill — Fct . --F.-at v F-rt . Fts vF-tr tef-[ill] till‘ F.I.t |c|li{sl}l —{Fr-tvFs-;_] [t:|ii{fi}lThe alternatien -nf {T}. tlfil. tl I}. and {ll} is feund by truth-valueanalysis tel he valid- and this is meant tn preve that the alternatien dill}.{T}. and {3} is valid- Present metheds aside, prnnfs ef validity are intuitively preferable t-npre-efs ef ineensistency. Truth is eur game. and direct aim is merestraightterward than snaring and trapping. Hewever. we see frem theettamples abeve that the prnnf ef ineensistency preceeds mere naturallyunder the main methed than that ei validity under the present methed.There arc twn reasens fer this. {Zine is that a dewnward-trending implica-

eld. H¢=rilu'rtue\".r Methrid TTTtien. in which the implying schema ls given and the implied ene isseught. cemes mere easily than the eppesite. The ether reasen is that wefind it much mere natural te view an accumulating let cif instances cen-junctively than in alternatien. This ditference in naturalness en the part ef the twe metheds can bepartly effset by ad_iusting the netatien- We can tnrn eur earlier linlevalidity preef upside dewn and render the altematiens esplicit. dilemmafashien: Ftw tr —F.tw Hy Fay v El-it —F-rw Vs Hy Fsr_'|-' v ‘ttI\"_i' 3-r —F-ryThis is indeed natural. We set dewn. te begin with. an unquantifiedschema that is palpabiy truth-functienally valid- Then we derive funherlines by eperating en the elauses ef the alternatien. Hew that the preef isturned ever. these eperatiens are the inverses ef L1] and El; hence Lit} andECI. which is tn say universal and c-rtsreurlel gerterelisntinn. instead efpreducing instances frem their generics {Chapter lift}. they lead freminstances te their generics. lvlere specifically they are t.'leii.rnt Lit] and EC}.eperating as they dri en clauses ef the new alternatiens and net just en thewhnle newlines. Let us try a sitnilar inversien and transfermatinn ef the preef { l}—{ I E}-Eiur tep line new will be the valid alternatien ef {T}. {iii}. {l l}. and {ll}-Tl1e nest line will he the alternatien rather ef {rt}. {Ill}. {'4}. and {Er}; thusthe clauses {T}. {I l}. and {I2} ef the first line give way here te theirettistential generics. We delete the estra {-4}. The third line will be thealternatien nf {st}, {El}. and {ti}; thus the clause {ID} ef the secend linegives way here te its universal generic {ii}. The feurth line will be thealternatien ef {st}. {E}. and {ti}; the fifth line will be the alternatien nf {ti},{3}. and {5}; and the last line will be the alternatien ef{l}.. {3}. and {Z}.This is the alternatien whese validity was te be preved. The reader isadvised te write eut the abeve preef esplicitly in full schemata. usingwide paper.{*} This precedure starts with a truth-functienally valid line and derivesfurther valid lines pregressively by clausal l-lCr. clausal ECi. and. we haveseen. a trivial third eperatien: deletien ef duplicate clauses. This thirdeperatien accetnplishes what. befere inversien. had been accemplishedby using ene line as seurce ef mere than ene instance. The change in styleis caused by eur having jeined up the instances in alternatien.

TZE til. t’-Tenisrnt Thcery effimnrhicnrien The preef precedure tn which we are led by these rearrangements isene that dates frem Herbrand. It eshibits an asiematie style cemparable tewhat we saw in Chapter I3. Ctur asiem schemata new, unlilte theseethers, are infinite in number: all the truth-functienally valid schemataqualify eutright. This is all right; infinitude ef attiems is manageable asleng as we have a way ef deciding whether a schc ma is an aitiem. and thiswe have in truth-value analysis. Elur rules ef inference new are three innumber; ne lenger medus penens and substitutien. but rather clausal LlCr.clausal El]. and deletien ef duplicates. The twe preefs by which we have thus far illustrated the Herbrandmethrtd have been needlessly cempact. what with the simultaneeusgeneralieatien ef ceerdinate elauses. The asiematic structure ef the pre-cedure emerges better il' we talte the steps ene at a time. The preef ef: lit’-it Hy F-ry v ‘tfy HI —F-ry,which was represented in three lines abeve. weuld then appear ratherthus: Ftnvv —F.t_'iv Hy Feyv —F:-tw Ely Fry v Hr --F.rw 'fl'.r Ely F.:ry v Hr —F-rw ‘fr 3yF.ry v lily H-r —F-ryEach line preeeeds fre-m its predeeesser by a step ef clausal LlCr er EG-The reader weuld de well te write eut the preef ef the alternatien ef {l},{Z}. and {3} new in this style el’ ene step at a time. There will be elevenleng lines attegether. beginning with the tmth-functienally valid aitierncensisting ef [T]. [lll}. {l ll. and {I2}. Each succeeding line will pnneeedfrem its predecesser by LlCr er EU er—in ene case—-deletien el a dupli-cate. ft} Let us fermulate clausal l_lCr eitplieitly. We l-eelt baelt te the Lil whichit inverts. That was Lil in the ferm suited te the style ef validity preef withwhich this chapter began. lt was subject te the requirement that theinstanti al variable be new—-i .e. . free newhere hitherte. New that we haveinverted the preef. this newness requirement gives way te an ebseles-eence requirement: the instantial variable must net still be free anywherein the derived line-

Jlti- Herhrand’.s Heihrrri 115' Indeed. since we newjein the eld shet‘-t lines inte leng enes by alterna-tien, we must net let the instantial variable be free even in the etherclauses ef altematien within its ewn line-- Hewever, this reqttirernent. thatthe variable net be free in a ceerdinate elause. tums eut te he assuredalready by the requirement that it net be free in the derived line. {It isassured as leng as we set eut eur preefs esplicitly in the style ef ene stepat a time-} Fer. if the variable were free in a ceerdinate clause. then itweuld be free in the nest line tee. sinee these clauses ceme dewn. Clausal Lit}. then. ferrnulated directly. is just this: tjf a line is analternatien ef ene er mere clauses. supplant any cif iheht by a universalqraentificatian whereaflt is an instance. pravided that the instantial vari-ahie is net free in the line that derived. It must be stressed that the clau sescencerned are strictly clauses ef altematien. lt may seem that. symmetrically with the eriginal requirement that theinstantial variable be new. we sheuld new require that it be free newherein any future lines. In fact this preeautien is idle. as leng as the variable isnet free in the immediately derived line- Fer eur three rttles ef inferenceprevide ne way ef intredueing a free variable. er ef freeing a variable. Clausal EC: is simpler: if a line is an alternatien ef‘ ene er mereclauses. supplant any afthern by an existential quantificatiun whereef it isan instance. There is ne restrictien en the instantial variable here. as therewas nene en that ef El in the style ef validity preef at the beginning ef thechapter. ‘alhat is required ef a title ef inference in an asiematic system ef validsehemata is net that it be implicative. but just that it transmit validity: thatit lead frem valid schemata te nene hut valid schemata. lmplicativity isene way ef meeting this requirement; schemata implied by valid schemataare indeed valid- But a nile ef inference can transmit validity witheutbeing implicative- An ettample is substitutien. it is net implieative;‘p v arl yields ‘q v l‘s* by substitutien, but decs net imply it. ‘ihfltat mat-ters is just that when we start with a valid schema. e.g. ‘p vp va*.substinttien gives enly valid schemata- New the systems in Chapter 13 had ene rule ef inference that wasirnplieative. namely medus penens. and ene that was net. namely sub-stitutien. The asiem system newly arrived at has twe rules ef inferencethat are implicatjve and ene that is net. Ll-bvieusly the |'ule ef deletien efduplicates is implicative. alse clausal E-E3 is implicative- Fer. te beginwith. the instance clause implies its generalieatien; ‘Fyi implies ‘Hr F-1:’.Further. if a -ElEll.l$tI.-\"-'l implies a clausell then the alternatien efal with any

EHU ill . General Theary inf Qaaatificritianfurther material C implies the altematien ef E with. C \". this is evident entruth-functienal greunds. Clausal UG is net implicative. but it transmits validity. This is essen-tially just the fact. familiar frem Chapter 25. that universal quan tificatiensef valid schemata are valid. Further censideratiens are a relettering and arule ef passage. {4} ef Chapter 23. Let us sert eut these censideratiens. lf te a valid schema we apply a universal quantifier geveming thewhele line. the result is again valid; that is the familiar fact frem ChapterE5. Der present LTG is enly clausal. but it results in a line that is equiv-alent te the line that ceuld be get by quantifying the whele; this we seefrem the rule ef passage {4} ef Chapter 23. Thus teel-t haclt te the five-tinevalidity preef last displayed. The feurth line cemes frem the third byclausal LHJ. The reasening behind the transmissien ef validity is that.having feund the third line valid. we ltnew that its qtlantificatien: liftt 3}‘ FE)’ ‘it as —-Fr-v}is valid: and this reduces. by the n.|le ef passage. te: ‘tie Hyl-\"ty v H-it —F.tw.which is the same as the feurth line eseept fer an incensequential relet-tering. The step ef clausal LIE that leads frem this feurth line te the lastline admits ef similar analysis- The appeal te the rule ef passage requires that the variable that we aregeneralitting net be free in ether clauses ef the altematien. llut we sawthat this assurance is previded indirectly by the previse regarding instan-tial variables that was incerperated inte the fermulatien ef clausal UG- vvhat new ef the incensequcntial relettering neted abeve‘? Clausal t-It]ailews it: but hew dees the fermulatien ef clausal Li-[3 lteep the lenetingincensequential? Te reletter ‘t’ in ‘lift Gsw‘ as ‘iv’. c.g.. weuld give“tfw Gwwi and thus change net just the netatien but the sanctum. It isprevented as fellews. Wliat in eur present analysis ef clausal Ll-Cr we arepicturing as a step first ef generaiieatien frem \"t.'Tew' te \"ti\": Claw‘. andthen ef {faultyl relettering te \"vw Gww’, weuld have been seen in tennsef clausal Lit] rather as a single step changing the clause ‘Claw’ te‘vw Gww‘; and this step vielates clausal l-it’-3 simply because *t3ew* is netan instance ef ‘lifw G-aw’. Crranted. ‘C-'ww\" is an instance ef *\"tft.' Gtw‘;but nnt ‘Claw’ ef ‘hfw Gt-aw’.

315. Heri:-rrtnd‘.-v it-fethed 13 I l'-light we then use clausal l-JG te supplant ‘Gite-i=‘ semewhere by‘Va t-Taw‘? Ne. net that either—fer a different reasen. The instantialvariable. ‘t-v‘ here. weuld centinue free in the “'tt\".t Gsw‘ ef the derivedline. in vielati-en ef the previse en instantial variables in the fermulatienef clausal Ll'Ct. First. in this chapter. we get a preef precedure fer validity frem eurmain methed fer ineensistency. by duality censideratiens. its seundnesswas prnvable by an argument dual te that fer the seundness ef the mainmethed- T'hen we gave this validity methed an asiematic fetrn. indeedHerhrand‘s. by inverting it and writing in the alternatien signs. Finally.fer geed measure. we have just seen a direct preef ef the seundness ef themethed thus refermulated. lust as the main methed was a methed efpreving the jeint ineensistency ef ene er mere prenett schemata. se thisene is a methe-d ef preving the validity ef an alternatien ef ene er mereprenett schemata. Te simplify the fertnulatien and justificatien ef this methed l switchedte the style. a few pages back. ef ene step at a time. This impeses thelaber. needless in practice. ef rewriting the whele leng line fer eachchange ef a single clause. ln practice we weuld retreat ef ceurse tn eurintermediate cendensed style. that nf eperating en clauses side by side. it seems. even se. that ineensistency preefs are swifter and easierstill--despite the seeming perversity ef erientatien. There we can leavethe premises shert and numercats. and the instances liltewise. and we cancensider them in greups witheut straining the imaginatinn. all because therelevance ef the greuping is cenjunctienal rather than altematinnal.EIERCISESI. See {tr} and {t}. Tum yeur paper se as te allew leng lines.2. De esamples and esercises frem Chapter 29 by Herhrand‘s methed. Hew is this methed a direct estensien ef that ef Chapter 29?

232 ill. t‘-Tenerai Theery af tflaanrtyicattenl 37 OTHER METHODS FOR VALIDITY we saw hew te meve frem the main methed tn a validity methed byduality. and thence te Herhrand‘s by inverting the preefs and linlting upits lines in alternatien- Similar transfermatiens can be perfenned en themethed ef functienal nennal ferms {Chapter 35}. Let us begin by simply talting the dual ef that methed. Universal andettistential quantificatiun switch reles. Thus. in ferming the functienalnermal ferm fer validity preefs. we drep universal quantifiers rather titane:-tistentiai enes; and te the recurrences ef their variables we attach sub-scripts recnrding the variables ef prier ettistential quantifiers. ln lieu efpremises new we have alternative theses; and their alternatien is prevedvalid by instantiating the esistential quantificatiens by means ef leiticenuntil instances have been accumulated whese altematien is trI.tth-functienally valid. We may illustrate l-l'll5 methed by preving. again. the validity ef thealternatien ef {l]—{3} ef the preceding chapter. The preef is simply thedual ef the ineensistency preef seen early in Chapter 35. and begins withthe new functienal nennal ferms.strcarvartvs {I} Hy Fay THes|ts: {E} Hr Hy — {Fv_..y v Fy-t} {3} it 3y{—F.ry . —F-rw_...v Fw_....y . F_.vw_..,.v Fw_.....r}trtsrsncss: {4} Fav, {5} — Fav... . — Fawn... v Fw ....|.v.. . Fv..w....“ '-.-' Fa=....“u {I5} Faw ,..., {T} —{Fv..wg....v Fw......u}The alternatien ef {4}-—{T} can be seen te be tnith-functienally valid. if we prefer re invert this validity preef and malte the altematienseitplicit. we can malte twe leng lines sufliee. Clur tep line becemes thealternatien ef {~=i-}- {T}. genereusly spaced se as te facilitate eur writingdeubiy generalised clauses underneath. Then eur secend line is the alter-

37\". Either Meihadsfar Validity I33natien ef{l}. {3}. {l} again. and {Z}; each ef these clauses stands beneaththe instance that it generalizes. Then we cress eut the repetitlen ef {l}.\"tlt\"l1at remains. the alternatien ef { |}—{3}. ameunts te a functienal nermalferm ef the alternatien ef quantificatienal schemata whese validity was tebe preved {vic. that ef {1}—{ 3} ef Chapter 3-ti}. {ll} Simultaneeus multiple EG has enabled us te get this all at ence. Thisadvantage ef functienal nermal ferms in validity pmefs eerrespends tethe advantage ef them that we neted in ineensistency pre-efs {Chapter 35}.via. that we ceuld plunge directly te unquantified instances by multipleUl- Let us leelt nest te Dreben‘s methed ef functienal nermal femts widt-eut prenetting. This time l shall ge directly te the final methed whichcemes ef that ene by dualieing. inverting. and marlting altematiens. Wewartt. say. te preve die validity efi‘ttI\"y{'1i|\"'-tl3.'t{F.te . Fat} —s —F.ryj —'r H-.r{—F.1y . liI\"'w{F.1tw —r -—Fw.r]]}.We prepare it by clearing it ef the cenditienal signs that everiie thequantifiers.‘tt\"y{—\"tt'-r|— 3.t;{Frr . Fat} v —F.ry] v 1r[— Fry .‘lit'w{F.rw --tr ——Fw.r}]}..Fltl!i'lI|' we drive in all such negatien signs.\"liI\"y{3.Il_3r,{F.tt-* - Fat} . F.1.y]v 3.r[—F.ry . \"I\"w{F.riv -1 -Fw.1r}]}.We weuld reletter the universal quantifiers {ne lenger the esistential} ifthey shewed duplicatiens; but they de net. Se we meve te the functienalnermal ferm.{l} 3.t[Hr,{F.r:: . Fat} . Fry]; v H.t{—F;ry . F.rw.. -—r —Fiv...t}.We preceed with the preef by writing dewn this tn.|th-funetienally validfermula.Fyy . Fyy . Fyy .v. Fw..y . Fyw.. . Fw...y .v. —Fyy . Fywj. —1- —Fw._.y.

234 H’-*. Genera! i\"'!tet:Ir_v tr-I QaaatrjieartpnUnder this, finally, we pertie-rrn five simultaliedus steps cif EG. Urldet theelause ‘Fyy - Fyy - Fyy‘ we write, as its generaliaatidn, the first half ef[I]; under the clause ‘Fwpy . Fyrv, . F1-v,,y' we write again the first halfeftlit and under the final ‘-—Fyy . Fyw, —=- _._.Fl\"'lul}r! we write the see-end haif el’ It 1 l. The resulting line, with its duplicate clause crdssed eat, is{I} as desired- {ti Eef-are ieaving the tepic at preef precetlures far validity, we sheuldpause a mement ever the asiamatie apprtiach- The Herbrand methed inthe preceding chapter was seen ta fall under this head. with its infinitudepf a:-tie-ms {the t]'tttl't-functi-nttally valid schemata} and its three rules Hfinference {clausal LIE, clausal E13, and deletien ef duplicates}. But thereare alse aitidmatiaatidas mt:-re sirnjlar in character ta the truth-functienalsystems tri\" Chapter 13: systems with just a few aitidrn schemata and withmrrdus penens and substitutien as rules pf inference. This was dnce theaccepted way df tleveld-ping the subject. A typical azti-amatiaatien el’ theltintl, edveriag beth the truth functiens and qttatitificatitlli, has as ar-tiernsthe schemata if ti-[3] ef Chapter I3 and, in additien, these:{2} liI\".r Fir -1-Fy, \"I\"J:(p -1-F.=r] -+.p —r ‘ill: F1.its rules at inference include again medus penens and substitutien, butsubstitutien in the sense pf Chapter IE. In atiditidn there is a rule allewingthe relettering at varial:-les. Alse there is simple. nenclausal LIE‘-r: theattachment df a universal quantifier td a preved line. The system visiblytreats enly pf negatien, the cenditienal, and universal quantificatiun;hewever. the cuverage is extended as desired hy translating the ethertruth-functien signs and the existential quantifiers inte this netatien in thewell-ltnewn ways. I pause enly fer ene srnali sample pf a preef in this system. Bysubstituting in the twe t1I.IliIiI'i'I5 last stated, and relettering ene beundvariable, we have: ‘II’: liI\".\"r[U-t —5\"FI]' —1- ltflttfiy -1 Fit]. 'tI\".rlfGy ~—I- Fr} —-I-. Gy —1- \"alt: Fr.By suhstimting in the aiti-am II 1} at Chapter 13, we have: ‘F\": \"i\".r|;tIFt —1- Fr] -1 Vxtfiy ——i- Fit} .—+: . \"s\"'.rt'tF_v —1- F1] —1- Gy -1 V1 Fsr I-12 ls\"-t \"'ii'.t{tI?t —1- Ft} -1. Gy —e l'il\"Jt' F1.

3?. Other‘ Mrrhnrisjthr l*’tri'iti'r'rv 135Frem these three results, by twe steps ef medus pencns, we get: \"Iii\": \"s\"'xl_'U.t: ——1* Fx] -1. t'F_v —* \"'i\"'.I Fx.Preef ei interesting sehemata by this methnd is hardly werthwhile,theugh the systern is ltnewn te be eemplete- tits urged in Chapter I3, derivatien ei theererns is nnrewarding intletnains admitting ef a decisien precedure. Hence the ennvenienee eitalting all truth-functienally valid sehemata euiright as axiems, as inHerhrand‘s methnd. We can carry this principle yet farther, since we havea decisien precedure fer menadic quantificatienal schemata: we can talteall rnenadieally valid quantificatienal sehemata as axiems- By this, as neted early in Chapter Iii, l mean mere than the validmenadic sehetnata- l mean alse the pelyadic sehemata that ean he getfrem valid menadic enes by suhstitutien. There is a decisien precedurenet nnly fer validity ei menadic schernata but fer menadic validity nfpelyadic schemata. Fer, given any sehema, malte all pessible menadic .tuper.rtirutiertr enit; i.e., frame all the menadic schemata frem which it can he get bysubstitutien. They are seen exhausted, if we ignnre purely arhitrarydifferences having tn de with the alphabetical eheice ef schematic letters-E.g., the enly pessible superstirutiens en ‘Fyy —+ Ex Fry‘, igneringsueh differences, are ‘Gy —1- 3.1\" Gr’, ‘C-‘y —1~ Hy‘, ‘Hy —1- Ex Ex‘, andfurther trivialities lilte ‘p —t- 31' GI‘, ‘,e —1- t;-\", 'p'. Then, in principle,we may test all these menadic sehemata and sec if ene is valid. In practiceel’ ceurse ene sees immediately whieh superstitutinn te malte and test- Given the cempleteness ef sueh axiem systems as the ene last neted, itis easily seen that we get a eemplete system ef quantificatiun theery if wetalte all rnenadieally valid sehemata as axiems and just medus penens andsimple Lit] as rules ef inference. Here is an example ef a preef in it. Theschemata:F.t_v —-1 Ex Fxy,li\"_vtF.ry —r Ex Fry} --1-. \"Elly Fxy —1+ \"Iii'_y Hr Fxy,\"s\"x[‘liI\"_y Fry —-r \"Elly it Fxyl we Ex ‘sly Fry —1- ‘sly 1r Fryall preve, by test, te be m-nnadically valid and henee te qualify as axiems.{The reader weuld dd well te elicit the relevant valid menadic schematahere by superstitutien. The third ene is 'llil'x[Gx —i- pi —1-. Elx [ix —* tr‘ -}Then frem the first ef the three hy UG we have:

ass Hi. C-'erternItl Thee-ry sf [Qt-ttrrutyirnrinn ‘slyt_'Fry —1- it Fry}-Frem this and the secend ef the three we have by medus penens: ‘sly Fxy —-'* ‘sly Hx Fityand thence by UB1 ‘slx[‘sly Fxy —1- ‘sly 31: Fry]-Frem this and the last ef the three we have by medus penens eur iaveriteiinie essentially pelyadic theerem: H:-t ‘sly F,1r_y—1-‘sly 3.1'F.ry.in an adaptatien ef the cendensed preef netatien ei Chapter I3 we maywrite the whele preef thus: [I] F:i_'_y —1- 3.-'1.‘ FJ|:}' [1] [lsly l -1.] ‘sly Fxy —1- ‘sly it Fry l‘s‘x I -1.] Ex ‘sly Firy —s ‘sly 11' FryThe numeral ‘E’ in the last line stands fer the line [Z] minus its bracketedmatter ‘[‘sly I —e-.]'- The intentien ef the netatien is that eaeh line, withits initial hraelteted matter included, is menadieally valid. Hlsreltreat were is remarked at the end ef Chapter se. tl1eaxiematic style illustrated by {ll was Frege's. The particular axinms {1}were Russellls, IQUE, except that he used ‘v‘ twice instead ef ‘—r-'. Hissupperting trtttlt-fun-etinnal axiems were less neat than the Lultasiewieeaxierns chesen abeve, vie. I[l}—{3] ef Chapter 13.EIEICISESl. Carry eut ts} and {+1.

_i'h‘. Dedetrriee 133'2. tits a basis fer further exercises. the last methed ef the chapter is recemmended: derivatien Frem ntenadically valid schemata using the cendensed preef netatien. [1-e varieus ei‘ the examples and exercises ef Chapters Ell and 3| again by this methed.i§ DEDUCTION blet enly can the main methed be inverted te give a direct preefprecedure fer validity {Chapter 36]; it can alsn be split and partly invertedtn give a direct preef precedure fer implicatien. This plan may best beseen threugh an example. Cc-nsider again the example in Chapter 2?abeut paintings and critics. The reader preved it in Exercise E ef Chapter3|] by preving that the premise:[ll 3y‘slx{Fy - Gx —1- Hxy]was incnnsistent with what the desired cenclusien:{I} ‘slxayttilx -—r. Fy . Hey‘!became under negatien, namely:[3] 11: ‘s'y —- [Gr -1-.Fy.HJry].He preved the ineensistency ct‘ l ll and {3} by deriving ‘Fr - Gw -1- HWE‘item [1] by El and Ul, and deriving ‘—-[Gw A. Fe - Hwrl‘ frem {3} bysimilar but suitably intercalated steps, and then neting the truth-functienalineensistency cf these twe instances. l\"'-iew the new plan, aeeentustingthe pesitive, says te preceed nnt frnm if I} and {3} te absurdity but fremll} alene le {E}. We preceed te the instance ‘Ft - G1-v -1 Hive‘ ef [llas befere. But this must trutli-funetienally irnply ‘Ciw —1-. Fr . Hive‘,it‘ it was geing te be truth-functienally incensistent with

135 Hi‘- {,1-‘ereeretl Ti-leery sf I:-fudntrjlieeriert‘—{t_\"Fw —1-. Fa . Hive)‘. Se frem ‘Fr . Gw —1- Hrvg‘ we simply infer‘Gw —-I-. F:-5 . Hvvz‘ by a new nrle TF, trrrt.l't-_l'i-rrtetiemti inference.’ andfrem this we climb te the desired {2} by steps nil EG and U13, the reversent‘ the steps ef El and Lil which in the aid preef led frem {3} tn*—{Gw -1». Fr; . Hwzj‘- in this way we get a denlneriert el‘ {Z1 frem {I}- lt runs as fellews:|=rtesttss.: 3y‘s\"..t{Fy - Gx —* Hxy} lE-lleseucnntv: ‘v'.t{Fs . G1 —1- Hrs} {Ull- {TF1 F: . G1-v —-+ Hwz {EU} Ciw —r. F: . Hwt: {UGJ 3y{C|‘w —>. Fy . Hwy] ‘lslx Hyt-II-‘.r —-—:-. Fy . Hxy} The precedure is essentially the same when, as in the fellewing exam-ple. the premise is milked fer mere than ene unquantified instance.P]tEMIsE: ‘slvv ‘slx —{F.1ry . F'.=riv - Fwx] {Lil}nsneenerv: vs —{F.ty . Fxy . Fyx] {Uh —tF:-e\" - Fri\" - Fxvll {ill} - {Fey - Fer - Fire} {TF1 —Fyy . —F‘_y..-'5 ‘s‘ -Fay {U131 ‘s‘wt—FJ-a‘ - “Fry v —FP-tri {EGJ 3.r‘sl1-v{—-F;ty . -\"-.FIl-ll v —Fwx}A difference between this deduetien and the preceding ene is that the lineget by TF here is get frem the twe lines preceding it; it is implied by themjeintly. The same thing happens in the next example, which has twe premises.intssnsssr ‘slx{Gx —1-. Fx v Hx} {Elinsneerterv: Hxifix . —Hx] {U1} Ely t -Hy {TF1 Gy —1-. Fy v Hy {EC} Fr - —Hi\" 3.r{Fx . —H;r} But a eemplicatien arises when mere than ene unquantified instanee efthe cenclusien is called fer. Suppese we are given the premise:

33. Dedtttneri E39{4} ‘lb’ 5lIiFie-' - Fri -'-’ Fe’)and want the cenclusien “sly Elr Fry‘. Under the rriain methnd we weuldnegate the cenclusien, cenvert the negatien te ‘Hy ‘slx — Fxy‘, and thenshew this tn be incensistent with {4} by deriving incensistent instancesfrem ‘Hy ‘slx —Fx_y‘ and {4} as fellews: ‘slx —Fxe Elx{F.te . Fex .v Fire} Fee . Feiv .v Five -~Fee —F'-veBut when we try te turn this ineensistency preef inte a deductien byeur triclt ef partial inversien, we fail; fer ‘Hy lslx -Fxy‘ eentributednet just ene unquantified instance but twn, ‘—Fee‘ and ‘—Fi-ve‘. Thetruth-functienal ineensistency cif these twe with the instance‘Fee . Few .v Five‘ tit‘ {4} dees net entitle us te claim either 'Fee‘ er‘F-ive‘ as a TF ccin sequence ef ‘Fee - Few .'v' Five‘; the mest we can claimis their alternatien, ‘Fee v Five‘. Frem this alternatien we can get te eurdesired cenclusien “lily 3.! Fxy‘ enly by strengthening eur rules: twesteps cf cl‘-sushi‘ EC: will yield the alternatien ef ‘Ex Fxe‘ with itself, andthen TF will get rid cif the duplicatien and we can ge en afterward by UGtri \"sly Ex Fxy‘. Se eur belstered deductive precedure uses these rules‘. Lil, El, TF,clausal E113, and {fer similar needs in ether examples) clausal UG. SimpleEC‘: arid LTCi are still there, being just the special cases cf clausal EC: andLit] where the clause is tal-ten te be the whele line. Let us new assemble the deductitin ef “sly 3.1: F.iry‘ frem {-1}.PitElvl[5E: lily Hx{Fyy , Fyx .v Fry] {U1}eseticrtetv: 3.t{Fee . Fex .v Fxe} {El} Fee . Feiv .v Five {TF} {cl. EC] Fee- ‘it Fwe {cl- EC-ii 11: Fxe v'Five {TF} Hr Fxe v Hr Fxe {U13} HI Fxe ‘sl_i' 3.1: Fry

Itlfl lll. tleneral Tlieeifv sf filaaiaifltitviiiaa If the deductiens seen thus far in this chapter are cempared with theineensistency preefs te which they are related by partial inversien, it willbe seen that what the El ef the ineensistency preef gives way tri underinversien is net EG, but UG. Fer instance the last step ef the deduetienabeve gees frem ‘Eli Fxe‘ te the desired cenclusien “sly 3.1‘ Fry‘ by UCII,the enrrespetitiliiig step in the incnnsistency preef went frem the negatienef that desired cenclusien, vie. ‘Hy ‘slx —Fxy‘, te “I“.1‘ —Fxe‘ by El.Censequenlly, just as El in the main methnd was hedged by requiring anew instantial variable, se beth El and LiCr must new be hedged in semecerrespending way- Indeed, since deduetien is a way ef preving implica-tien, and yet neither El ner UG is implicative, seme such restrictien wasbeund te be needed. But the nature at the apprepriate restrictinn is ne lenger se simple andevident as it was in the main methed- We cannet require that the instantialvariable ef UG be new, fer U113 dees net intreduce an instantial variable: iteliminates it. Her weuld it be sufficient new te invert matters and require,as in the Herbrand methed {Chapter 3ii-ll, that the instantial variable el‘ UC-rnet reappear afterward; fer eur deductive precedure uses El as well asUT3, and their instantial variables ean eellide in pernicic-us ways that thisrequirement weuld net prevent. Thus ebserve this fallacy:Pitsiiiisis: Elx Firesneerteiv: Fy {El} ‘slit Fx {HG} {wreng}Certainly ‘ 5.1: F.r‘ dees net imply “sl.r Fir‘. There are, hewever, twe neat restrictiens that preve suflieient: thelrisrairrlnl varlal:-le.r sf El and UG mast he dlfilsrem far earl: .'l'l.l!r_'ill step,and the instantial variable tzfsaclr saelt step mast its alphabetically laterthan all _,l'i'ss variables cf the generic liar sf that step. The seundnesspreef is in the next chapter. If clausal UG er ECI is retained, then netefurther that its instantial variable must be free in ne ether clause ef thatline; hewever, clausal UCI and EC: will be superseded presently. The fallacieus little deduetien last exhibited is disqualified by the banen using the same instantial variable ly‘ fer twe steps ef the sensitiveltinds El and l..lCr. llictutdly the big deduetien just previc-usiy exhibited isdisqualified lee, in its El step; far the ‘e‘ in the generic line is alphabeti-cally later than the instantial variable ‘w‘. Hewever, this vielatien can herectified witheut less; we can simply use a variable alphabetically laterthan ‘e‘, say ‘e“, instead ef ‘iv‘ in the three lines where liv‘ appeared.