logica decizii publice -engleza

7/28/2019 Logica decizii publice -engleza

1/22

Annals of Mathematics

Certain Logical Reduction and Decision ProblemsAuthor(s): Hartley Rogers, Jr.Source: Annals of Mathematics, Second Series, Vol. 64, No. 2 (Sep., 1956), pp. 264-284Published by: Annals of MathematicsStable URL: http://www.jstor.org/stable/1969974 .

Accessed: 26/06/2013 17:51

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .http://www.jstor.org/page/info/about/policies/terms.jsp

.JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range ofcontent in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms

of scholarship. For more information about JSTOR, please contact [email protected].

.

Annals of Mathematics is collaborating with JSTOR to digitize, preserve and extend access toAnnals of

Mathematics.

http://www.jstor.org

This content downloaded from 37.128.225.130 on Wed, 26 Jun 2013 17:51:54 PMAll use subject to JSTOR Terms and Conditions
http://www.jstor.org/action/showPublisher?publisherCode=annalshttp://www.jstor.org/stable/1969974?origin=JSTOR-pdfhttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/stable/1969974?origin=JSTOR-pdfhttp://www.jstor.org/action/showPublisher?publisherCode=annals


2/22

ANNALS OF MATHEMATICSVol. 64, No. 2, September, 1956Printed in U.S. A.

CERTAIN LOGICAL REDUCTION AND DECISION PROBLEMS*By HARTLEY ROGERS, JR.

(Received ecember 0,1954)(Revised eptember, 1955)?1. Introduction

This paper presents certain results concerning he reduction problem forvalidity n the first rderfunctional alculus and related theories.??2-4 give abriefreviewof the nature and significance f the problem.The results of thepaper are partially ummarized t the end of ?4. Theorem4 in ?10 presentsthe mostgeneralresult n the paper. The less trivial steps in reaching his re-sult are the constructionn ?6, and the inductiveproofsof Lemmas 3 and 4in ?8 togetherwith the substitutionwhich makes them possible.

?2. Firstorderfunctional alculusA classicalelementaryystem f ogicpresentednmanyfoundational reatises(e.g. Church [2]) is that systemknownvariouslyas First Order FunctionalCalculus (FOFC), Lower Predicate Calculus, or Quantification heory. Theformulas f this systemcan be obtained in the followingway. The symbols'x', 'y', Cz', x', 'Yi', 'z1', x2', .. will be called individualvariables.They willrepresent,when nterpreted,lements n some fixed,non-empty omain of ele-ments.The symbols F', 'G', 'H', 'F1', 'G1', H1', 'F2', ... will be called relationvariables. hey willrepresent,when nterpreted,ets ofn-tuplesofelements fthedomain. The value of n for he sets ofn-tuples ssociated with the use ofaparticular elation ariablewillbe clearfrom ontext. he expressionFx1 * A'willmean (xl, - , xn) c F, and similarly orotherexpressions omposedof arelationvariable and a finite equence of individualvariables. We allow suchexpressions o be combined n the usual way underthe standardpropositionalconnectives ofmathematics, 'C= ', 'xz:', 'v' (or), '&', 'a' (not); and, furthermore,we allow the usual use of the standardmathematicalquantifiersV' (for all)and 3' (there xists)with he mportantimitation hat thevariablesupon whichthey act must always be individualvariables (i.e. the objects to which thequantifiers efermustalways be elements f the domain). Finallywe shall re-quirethatevery ndividualvariable n a formula e actedupon by somequanti-fier. he totality fformulas btained s outlined bove constitute he formulasof FOFC. In what followswe shall use symbols A', 'B', 'A', --- to refer oformulas f FOFC; and '-A', 'A => B', etc.,will refer o correspondingom-binations fthe formulas eferredo by A', 'B', etc.A formularueunder ll interpretationsssaidtobe valid.A formula rueunder* This paper includes resultsfrom he author's doctoraldissertation, rincetonUni-versity, 952 10], ogether ith xtensions btainedbythe uthorwhile BenjaminPeirceInstructornMathematics t HarvardUniversity. he author s greatlyndebted o Pro-fessorA. Church or uggestionsndhelpful riticism.264

This content downloaded from 37.128.225.130 on Wed, 26 Jun 2013 17:51:54 PMAll use subject toJSTOR Terms and Conditions
http://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsp


3/22

LOGICAL REDUCTION AND DECISION PROBLEMS 265some nterpretations said to be satisfiable.wo immediate onsequences fthesedefinitionsre that for ny formulasA and B of FOFC:(a) A is valid if and only f --A is not satisfiable;(b) (A is valid impliesB is valid) if and only f Q-B is satisfiable mplies-Ais satisfiable).Three principalmetamathematical esults oncerning OFC are the following:(1) FOFC is axiomatizable n the sense that axioms {Ax} and rules {R) canbe foundsuch that a formulaof FOFC is deduciblefrom Ax} by means ofJR} if and only f t is valid. (Gidel completenessf FOFC.)(2) There is no effective lgorithm or determining hether r not formulasofFOFC are valid. (Church'sTheorem.)(3) A formula fFOFC is valid if and only f t is true for ll interpretationsin some countably nfinite omain. Lowenheim roperty.)Property allowsus to confine urselves o a countably nfinite omain indiscussing alidity.We shall use the rational ntegers s sucha domain,havingin mind their onvenience s labels rather han algebraicproperties.

?3. Reduction f the generaldeducibility roblem o FOFCThe General DeducibilityProblem may be stated as follows:given a set ofaxioms {Ax}, a set of symbolic ransformationules {R) (rulesofproof)and astatementT; to determinewhether rnot T is deduciblefrom Ax} by meansof {R . Underappropriate nd familiar ssumptions s to finite epresentabilityand effectiveerifiabilityf formulas nd rules, this problemcan be stated intermsof recursive unctions: ivena recursivelynumerable et; to determinewhether r nota given ntegers in that set. [That this s not the mostgeneralproblem f mathematicswas shownby Gddel [4],and subsequent ogical nvesti-gatorshave devotedmuch effort o an exploration f moregeneral problems.Many aspects of theseand of the GeneralDeducibilityProblem can be mostconvenientlyonsideredwithin hehighly ruitfulheories frecursive unctions(Kleene) and canonicalsystems Post).]The studyofthe elementary ystemFOFC derivesconsiderable ignificance

from hefact thatany instanceof the General DeducibilityProblemcan be ef-fectively educed to the question of whetheror not a particularformulaofFOFC is valid. This is an immediate corollary o several classical proofsofChurch'sTheorem. Cf. Kleene [7], p. 435.) Thus, an effectivelgorithman begiven such that for ny axioms {Ax}, rules{R}, and statementT, one can findby this algorithm formulaA of FOFC with the property hat T is deduciblefrom Ax} by {R) if and only fA is valid over a countably nfinite omain;orequivalently,fwe takeB to be -A, there s an effectivelgorithm orfind-inga formula ofFOFC such thatT is deduciblefrom Ax by {R if and onlyifB is not satisfiable vera countablynfiniteomain.?4. Reductions n FOFC

The problemofvalidity n FOFC can be further educed withinFOFC tothe problemof validity for certainsubclasses of formulas.Such reduction

This content downloaded from 37.128.225.130 on Wed, 26 Jun 2013 17:51:54 PM

All use subject to JSTOR Terms and Conditions
http://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsphttp://www.jstor.org/page/info/about/policies/terms.jsp


4/22

266 HARTLEY ROGERS, JR.theorems ake the form: t is the class of formulas fFOFC, 63 s a specifiedsubclass of G, thenthere s an effectiveransformationalgorithm)p:a -+ 63such that for ny A, A is valid ifand only f pA s valid. Theoremsof this kindhave been of great nterest o logicians, nd a number fspecial resultshavebeenobtained. mportant mong these s Kalmair'sTheorem 6] where63 s the classofformulaswhichhave only one relationvariable,that variable beingbinary[i.e.representingets of ordered airs].A more general type ofreduction heorem an be obtained f we require nplace of thevalidityof pA, he validityof pAfor omerestricted et of nterpre-tationsfor tsrelation ariables. n thisformwe have therecent esult fChurchand Quine [3] for the case where63 s the same as in Kalmar's Theorembutwherewe now showthatA is valid f nd only f pA svalid for ll interpretationsof its relation variable as a symmetric elation. Each result has its parallelformn terms fsatisfiability,hus we see,e.g. in this case, thatanyinstanceoftheGeneralDeducibilityProblemcan be effectivelyeduced to thequestionofnon-existencer existence f a symmetricelation atisfying particular ormulaofFOFC.) [A relation s symmetricf t satisfies(Vx) (Vy) Fxy== Fyx)', asym-metricf tsatisfies(Vx) (Vy) Fxy == -Fyx)', reflexivef t satisfies(Vx) (Fxx) ,transitivef it satisfies (Vx) (Vy) Vz) (Fxy & Fyz =z> Fxz)'. A partial orderingis a transitive nd asymmetricelation.An equivalences a symmetric, eflexiveand transitive elation.]This paperwill give furthereduction esults f this type.These will nclude,among others,(i) the case of twoequivalence relations for63 takento be formulas n twobinaryrelationvariables);(ii) the case ofa lattice, eitherfor a single atticeordering elationwith63takenas in (i), or forthe two lattice composition elationswith63taken to beformulas n two ternary ariables. [If, e.g., expressionsH1xyz'and 'H2xyz'oc-curredn spA,we couldread themas x n y = z and x u y = z and use only n-terpretationsorwhich he atticeaxioms weresatisfied.]);(iii) the cases of certainotherkinds of partial orderings with63takenas in

(iv) the case of an associative,commutative emigroupoperation(with 63taken to be formulas n a singleternary elationvariable [Here, if 'Gxyz'oc-curred,we wouldread it as xy = z and use only nterpretationsorwhichtherequirements f unicity,associativity and commutativitywere satisfied.]).(This is a corollary o case (ii).)?5.Decidability

Church'stheorem tates that thegeneralproblemofvalidity n FOFC is noteffectivelyolvable. Hence everyreductionresult s also an undecidability e-sult. Thus corollary esultsof this paper will include, among others, he un-decidability f the elementaryheoriesin thesense of Tarski [13] [See commentfollowing orollary in ?7 below]) oftwoequivalencerelations, fa lattice, nd




5/22

LOGICAL REDUCTION AND DECISION PROBLEMS 267of an associative, commutative emigroup. The latter two undecidability e-sults re known rom arski's fruitfulheory fessential ndecidability.f. Tarskiet al. [13]. See also theremark ollowing orollary in ?8 below.)

?6. Reductionto a singlepartialorderIn what follows, ymbolsF', 'G', - shall refer o relations sets of n-tuples)whichwe are using or constructing s specific nterpretations or variables'F', 'G', ... in given formulas of FOFC. Symbols '0', '-t, -.. will refer toopen-formulasf FOFC, i.e. expressionswhich differ romformulas f FOFConly nthattheypossess ndividualvariablesnot acted upon by quantifiers.We assumethatreduction y Kalmar's Theoremhas occurred, nd we beginwith formulaA of FOFC containing he singlebinaryrelation ariable F'. Wewillfind specific pen-formula , with thesingle binaryrelationvariable 'G'and with x' and 'y' as its unquantifiedndividualvariables,whichpossessestheproperty hatfor nygivenrelation overthe ntegers, partial ordering overthe integers an be found uch that '(Vx) (Vy) 0 ?e Fxy)' is satisfied. Strictlyspeaking, hisexpression ontaining he symbol 0' is not a formula f FOFC.Nevertheless he contextwillmake clear,here and on similaroccasions, whatformula f FOFC is beingreferredo.] Our reductionresult followswhenwedefine he effectivelgorithm ito be the substitutionf0 for F' in A. [For de-tails ofthisoperationofrelational ubstitution,ee any treatiseon FOFC (e.g.Church 2]).Theprocedures ntuitively lear; nactual practice ertain tandardmanipulative teps arenecessary o insure hatno undesired oincidences ccuramong individual variables. It is clear that any such substitutionn a validformula roducesa validformula.]f po1As valid for ll partial orderings,henA will be valid forall binaryrelations over the integers nd hence, by theLbwenheimproperty, will be valid. Conversely,ince substitution reservesvalidity, f A is valid, thenpjA will be valid and a fortiori alid forall partialorderings.huswe willbe able to conclude:A is valid ifand only fso1As validfor ll partialorderings; nd, also, A is valid if and only f r1A s valid for allpartial orderingsverthe ntegers.Let F be any givenbinaryrelation verthe ntegers.We proceedto constructa relationG as follows. ymbols r', s', 't,, u', 'v', 'w', willrefer o integers. heintegers re divided ntothe six residue classesmodulo6, whichwe denoteby'(0)', '(1)', ... , '(5)'. G will hold from he classes (0), (2), (4) to the classes(1), (3), (6).Between 0) and (1):Guv ifand only fFrs,where = 6r andv = 6s + 1. ('Guv' abbreviates'(u, v) e G'; similarly or Frs'.) Therefore rs if and only f

(3u)(3v)(u = 6r & v = 6s + 1 & Guv).Clearlywe can construct he desired0 if we can define he relationsu = 6randv = 6s + 1 in terms fG, using open-formulasfFOFC. The remainder fthe constructionfG is arranged o make thispossible.




6/22

268 HARTLEY ROGERS, JR.Between 2) and (3):Guv holdsfor in (2) and v in (3) provided hat either = u + 1 or u - 5.Between 2) and (1):

Guv holds foru in (2) and v in (1) provided hat v = u -1.Between 2) and (5):Guv holdsforu in (2) and v in (5) provided hat v = u + 3.Between 4) and (5):Guv holds foru in (4) and v in (5) provided hat v = u + 1.Between 4) and (3):Guv holds foru in (4) and v in (3) provided hat v = u - 1.Between 4) and (1):Guv holds foru in (4) andv in (1) provided hatv = u + 9, u + 3, u - 3oru - 9.Between 0) and (5):Guv holds foru in (0) andv in (5) provided hatv = u + 5.Between 0) and (3):If u is in (0) and v is in (3), thenu = 6 w for omew. The conditions hatGuv are:For w -1,Guv ifv = w + 14,w + 8, ,w-16

(six images foru).Forw -2, Guv ifv = w + 19,w + 13, ,w-23

(eight magesforu).Forw - 3, Guv if v = w + 12,w + 6,, w-12

(five mages foru).Forw - 4, Guv if v = w + 23,w + 17, ,w-31

(tenimages foru).Forw - 5, Guv if v = w + 28,w + 22, , w-38

(twelve magesforu).For w - 0, Guv ifv = w + 39,w + 33, , w-39

(fourteenmagesforu).This completes he constructionfG. A schematicdiagramof G appearsbe-low (Figure1). We nowmake a seriesof formaldefinitionsi.e. abbreviations)leadingto thedesiredformal efinitionsoru = 6rand v = 6s + 1, and we doso using open-formulasf FOFC. [The reader can showthe appropriatenessf

these definitionsy checking hemagainstthe schematicdiagramof G. In thecases oftheconditions n G between 0) and (3), it is the numberof magesofeachu -- 0 thatis important.]DEFINITION 1. x = y ->d (Vz) ((Gxz < Gyz) & (Gzx < Gzy)). [We will use




7/22

LOGICAL REDUCTION AND DECISION PROBLEMS 269, ) +1 s,>(2) - - )6'~

(0) A when%=L A rGs+ IX an& FAs (1)

(LIj)ra A (5)FIG. 1-SchematiciagramfG: (wherehe ixpoints epresenthe ixresiduelassesmodulo 6 and where (e.g.)(4)-- >u+1 Vv-1>-- (5)

indicates that the relation Guv holds for u in (4) and v in (5) if and only if v = u + 1).thesedefinitions ithotherndividualvariables, ndwewillassumethatquanti-fiedvariableshave been alteredso as to avoid undesired oincidences. hus thedefinitionalxpansion f x = z' wouldbecome, .g.(Vxl)((Gxxi


8/22

270 HARTLEY ROGERS, JR.(Gxly v ... v Gxtyv GyxI v ... v Gyxt Y = y, v y=y2 v ... v y= yY)

.XI,. , Xt have imagey', * y, " ]DEFINITION 5. (3Yi, . .. , Ys) . *) - >df 3y1) (3Y2) ... (3YR)(**) wherewe

makethe conventionhat thisdefinitionhall be used onlywhenthes individualvariables in the positions of yl', 'Y2', * , 'Ys' are different.DEFINITION 6. (x has an s elementmage) -->df

(3Yi, **, ys)g(x) = Yi, * , Ys).DEFINITION 7. If 'x -- r' has beendefinedwe have,

(gr(Xi , * * , Xt) = Y1, ** , Ys) -df ...right and side ofDefinition with Gxlyv ... v Gyxt' eplacedby

'(y - r) & (Gxlyv v Gyxt)'[X) ..*,Xt have (r) image Yi, , Ys "].DEFINITION 8. (x has an s elementr) image) -->df

(3yi , * * * , ys) (gr(x) = Y, * * *, Ys)-Definitions and 8 allowus to obtain thesequenceofDEFINITIONS 9.

x 2 ->df x has a 4 elementmage.x ?~ 5 -dfX has a 3 elementmage.x ? 3 -df Xhasa 2 element2) image.X 4 -df x has a 1 element3) image.x 1 - >df (x has a 1 element2) image)& -(x ~ 5).X 0 -df -(X -- 1 V x - 2 v ... v x - 5).

DEFINITIONS 10. (z = 6x andx 1) df (x 1 & (3y)(g2(X) = Y & (3Z1, Z2)(g3(Y) = z1, Z2 & (3YI , Y2 Y3)(g2(Z1, Z2)

= YI7Y2 y3& (3z3 * Z6)(g3(YI y2 y3) = Z3, * * *, Z6& (3y4, * , Y8)(g2(Z3, * ZZ6) Y4, * Y& (3Z7 , * , Z12)93Y4, * Y8) =Z7,**, Z12&g3(z) = Z7, * ,Z12))..

In similarfashion, z = 6x and x ~ 2) -*df (x - 2)& (3z, ,Z2)(3(x) = zI ,z2 & (3Yy, 22 3)Y2(2 Z, Z2) = Y1,Y2, 3& . . . . (3z13, ... , Z20)(g3(y9, ,Y1) =Z13, Z20& g3(z)= Z13, * * *, Z20)* ).




9/22

LOGICAL REDUCTION AND DECISION PROBLEMS 271In exactly similar fashion, z = 6x and x -- 3) ---*df .- . (Here and belowwe take images back and forth etween 2) and (3) until the right ize g3 mageis obtained in this case the size is five. n each case we shall findwe have so

constructed that the final magereached s indeed the mage of the desired .)(z = 6x and x ? 4) -*df (X ' 4) & (3y)(g5(x) = y & (3yD)(g2(y) = Y1& (3z, , Z2)(g3(Y1) = Z1 Z2 & ... similarly.

(z = 6x and x 5) *df (x ' 5) & (3y)(g2(x) = y& (3z, , z2) (g3(Y) = ZI , Z2 & ... similarly.

(z = 6x and x 0) --*df (X 0) & (3y) (g5(x) = y & (3 y) (g2(y) = Y1& (3z, , Z2)(g3(y1) = Z1 , Z2 & ... similarly.In each case above, the definition,n termsoftheconstructed , has the de-siredmeaning.We finally btain

DEFINITION 11. Z = 6x df (z = 6x and x 11) v (z = 6x and x- 2) v* v (z = 6x and x 0); andDEFINITION 12. Z = 6x +1 --*df (3y)(y = 6x & (3z1)(g5(y) = z1

& (3Z2)(g2(Zl) = Z2 & gl(Z2) =Z)))We are thusenabledto construct as (3z1) (3Z2) (Z = 6x & Z2 = 6y + 1 & GzIz2).G is clearly partial orderingnd we have ourdesiredreduction esult.

THEOREM 1. Theproblem f validityn FOFC can beeffectivelyeduced o theproblem f deciding, ora formulan a singlebinary elation ariable,whetherrnotthat ormulas validforall interpretationsf ts relation ariable s a countablyinfinite artial orderingor,alternatively,hetherrnot that ormula s validforall interpretationsf tsrelation ariable s a partial ordering).?7. Some corollaries

LetG be a set ofordered airs.The relation-domainfG is the set{r (3s)(r, s) -G},and therelation-rangefG is {s (3r)(r, s) EG}. If these twosets aremutuallyexclusive,G will be called disjoint. Clearlythe relationG constructedn ?6 isdisjoint. Hence, in the same sense as Theorem1, we have provedthe strongerand moreuseful

COROLLARY 1. Theproblem f validityn FOFC can be reduced othecase ofasingledisjoint elation.A fortiori, e have,COROLLARY 2. Theproblem f validityn FOFC can be reduced othe ase ofasingle ransitiveelation.By successivenatural modificationsfG and 0, we have




10/22

272 HARTLEY ROGERS, JR.COROLLARY 3. The problemf validityn FOFC can be reduced o the ollowingcases:(a) a single ransitive-reflexiveelation,(b) a single ymmetricelationChurchand Quine [3]),(c) a single ymmetric-reflexiveelation.[For case (a) ofCorollary ,G ismodified y adding o t all ordered airs of theform r, r). We then preserveDefinition and alter each remaining efinitionby functional ubstitution f 'Gxy& -(x = y)' for Gxy' at each occurrenceof G' in thestatement f thatdefinition. now givesF; as G is transitive ndreflexive,he resultfollows.For case (b), G is modified y adding the orderedpair (s, r) foreach (r,s) inG. So modified, is symmetric. he definitionsnd proofof Theorem1 can beapplied in thiscase without lteration.For case (c), wemodify he G and0 of case (b) inthemanner f case (a).In case (b) the resultof Churchand Quine [3] is obtained as a corollary oourdevelopment.Withthe exception fthis case, theresults fTheorem1 andCorollaries 1, 2 and 3 appear to be new. Case 3(c) would not appear to be acorollary o the constructionsed inChurchand Quine [3].If one desires,one can give a sharper tatement o a numberofour results;e.g., the proofof Corollary3(b) yieldsreduction o the case of a symmetric-irreflexive-intransitive elation. (Where irreflexivemeans that '(Vx) - Gxx' issatisfied, nd intransitivemeans that '(Vx)(Vy)(Vz)(Gxti & Gyz : -Gxz)' issatisfied.)]COROLLARY 4. For eachcase in Theorem and Corollaries ,2 and 3 we haveacorrespondingndecidabilityesult.[Thisstatesfor he case ofCorollary1,e.g.,thatthere s no effective ecisionprocedure ordetermining hether r not a formulan a singlebinaryrelationvariable s valid for ll interpretationsf ts relationvariableas a disjointrela-tion; n theterminologyf Tarski-the elementary heory f a disjointrelationis undecidable.Undecidabilityfor the cases of Theorem 1, Corollary2, andCorollary3(a) is knownfromTarski [11].Undecidability orCorollary3(b) isknown romChurch nd Quine13].The cases ofCorollaries and 3(c) appear tobe new.It wouldbe naturalto inquire bout thecase of a single ransitive-symmetricrelation. t turns ut to be relatively rivial.A decisionprocedure or his case isexhibitednthe author'sdissertation10].A decisionprocedure or he case ofasingle quivalence s known n severalforms1].]In Myhill [8], it is shownthat the addition and multiplication elationsofordinary ationalarithmetican be definedn termsofa singlebinaryrelation,using open-formulasfFOFC. [I.e. thereexistopen-formulasi and 4D2witha

singlebinaryrelationvariable F' and unquantifiedndividualvariables x', 'y'and 'z' such that 'x + y = z =l' (i and 'x X y = z (D2' are satisfied by somebinary elation overthe ntegers.] rom thedefinition intheproof fTheorem




11/22

LOGICAL REDUCTION AND DECISION PROBLEMS 2731 and Corollaries and 2, and from imilar efinitionsn the proofs f Corollaries3(a), 3(b) and 3(c), we can conclude

COROLLARY 5. The additionand multiplicationelations f ordinary ationalarithmetican be definedn termsfa singlebinary elation hat s(a) disjoint,(b) transitivend reflexive,(c) symmetricnd reflexive,wheren each case thedefinitionan be expressed y an open-formulaf FOFC.[The case of a symmetric elation s stated as a corollary n Church andQuine [3].]?8. Reductionto two equivalencerelations

We define ertain ets of relations n the integers.F is the set ofall binaryrelations, .e. the setof all sets of orderedpairs of n-tegers.G is theset of all binaryrelations btainableby the constructionn ?6. (Thusfor achmember fF therewillbe a corresponding ember f G.)D is the set of all disjointbinaryrelations.D"iX s the set ofall disjointbinary elations aving n infiniteelation-domain,an infinite elation-range,nd infinitelymanyelements hat are in neither herelation-domainorthe relation ange.Do' is theset ofall disjointbinary elations aving n infinite elation-domain,an infiniteelation-range,ndno elements hatare nneither he relation-domainnor therelation-range.E2 is theset of all pairsofequivalencerelations.Thus, .g.,G c DoX c D c F.We say thata formulas valid over certain etofrelationsftheformula asappropriate elationvariables (e.g. forD, a single binaryvariable) and if theformulas truefor ll interpretationsakenfrom hat set ofrelations. imilarly,a formulanappropriate ariables s said tobe satisfiablever hat setif t is truefor ome nterpretationaken from hatset.For a set of relations nd a formulaA intheappropriate ariables, t is immediate hat:A is valid overtheset ifand only f -A is notsatisfiable verthe set.As in ?6,we assume that reduction y Kalmar's Theoremhas occurred ndwe beginwith a formulaA in a singlebinaryrelationvariable F'. We shall de-fine hreeeffectiveormula-transformationsoi s02, and (P3 yieldingA1 = (pA,A2 -


12/22

274 HARTLEY ROGERS, JR.Formulas: A Al A2 ) A3'P1 'P2 '3Relation ets: 2 3 6 2F -~D -> D -

1\ /5DoO It DCC

The numberingf arrows n thediagramcorresponds o thenumberingf lem-mas below.LEMMA 1. A, valid overD0X impliesA validover .PROOF.This is immediate rom 6, sinceG c DoX and pA validoverG implies

A valid over F.LEMMA 2. A valid over impliesAl validover .PROOF. A valid over F means that A is valid (Ldwenheimproperty). oi sa substitution f an open-formulaor F'. Any such substitution n a validformulayieldsa valid formula. See commentn ?6.] ThereforeAl is valid, anda fortiori 1 is valid overD.A, can be changed to a form ll which '3', '>', 'a' and '&' have been elimi-nated. This is a matterof elementary ogical identities;we assume that thischangehas been made and we continue o refer o theformula s Al. [Such achangealtersno validityor satisfiabilityroperty f a formula.]An inductivedefinition orthe transformationP2willnowbe given. n what follows,a' and'b' refer o individualvariables occurringt particular teps of the induction.A a) is the formula 3b) (Hba vHab) v (Vx) (Vy) - Hxy' whereb is chosento be differentrom . -c2 is definedby:

'P2 , A/ = '92A!'P2(A' B') = 2A' V 2B',s02(Va)A' = (Va) (A(a) ==2A%

'P2'Gab' = 'Hab'whereA' and B' are subformulasfAl [a subformulafAl is a formula r open-formula ccurrings a part ofA1]. If A' is a subformula fA1, A' and 'P2A'will be called correspondingubformulas fAl and A2.LEMMA 3. Al validover impliesA2validover .PROOF. We provethe equivalentstatement,-A2 satisfiable verD implies-A, satisfiable ver D. Assume thatH is a relation n D which satisfies-A2.FromH we construct notherdisjointrelationwhichwe call G. The construc-tion s as follows. et g be theset of rational ntegers,nd let be the unionoftherelation-domainnd relation-rangefH. A map a is chosento be:

anymapofg onto j,ifgj snon-empty;the dentitymapofg ontog, fgj s empty.




13/22

LOGICAL REDUCTION AND DECISION PROBLEMS 275G is takento be the set of all orderedpairs (r, s) suchthat (or, as) belongstoH, i.e. (r, s) e G if and only f (or, as) eH. Since H is disjoint,G willbe also. IfG werenot disjoint thenan integer wouldexist n both relation-domainndrelation-rangef G. This would mply rr n both relation-domainnd relation-rangeofH, contraryo theassumption hatH is disjoint.If we can now showthat G satisfies A,, the proofof our lemmawill becomplete.This is accomplished n an induction emma.

INDUCTION LEMMA. A1 is satisfied y G if and only f r.A2 is satisfied yH.PROOF OF INDUCTION LEMMA. Assumethe contrary.We make an inductiongoingto smaller orrespondingubformulas f -A1 and -A2 . In the courseofthis induction, s individualvariablesbecome unquantified,we shall associateintegerswiththem nd we shall find t possibleto do so in sucha fashion hat fr is associated with an unquantified ndividualvariable of a subformulaof-A1, then or will be associatedwiththe same variable in the correspondingsubformula f -A2. Our inductionwillshowthat,givenany subformula of,A, and a correspondingubformulaP2B of -A2 if one of these is satisfiedand the other s not, thiswill also be true of some pair of correspondingub-formulasof these subformulas,where integersare assigned to unquantifiedvariablesas described n thepreceding entence-this is all to be true providedthat any further ubformulas xist. When the induction s demonstrated,timmediately arries s downto correspondingubformulasGab' and 'Hab' withassigned ntegers , s, ar and as. Furthermoret statesthat of thetwo statements

'(r, s) eG' and '(ar, as) e H', one strueand the other s not.This contradictsheconstructionf G and ourInductionLemmawill thusbe proved. t remains oprovethe induction. et B be a subformula f -A1 and (p2B he correspondingsubformula f -A2.Case (i) B is ofthe formJB'. Thens02B s oftheform-ioB'. The inductionis immediate or his case.Case (ii) B is of the formB'v B". Then (P2B is of the form O2B'vip2B".Againthe inductions immediate.Case (iii) B is ofthe form Va)B'. Then (P2B is oftheform Va) (A(a) XSp2B').We observe, omparing he definitionf A(a) withthe definitionfa,that A(a) withthe integer assignedto a will be satisfiedf and only fs =ar for ome r.First,assumeB is satisfied ut p2B s not.Then therewillbe someintegers whichcan be associatedwitha in A(a) =X Ip2B' such that A(a) is satisfiedbut (p2B' (with,of course,assignments f integers o its otherunquantifiedvariablescarriedoverfromprevioussteps in the induction) s not satisfied.Then s = erfor omer. Assignrto thevariablea inB' and er to the variablea in (p2B'.Then B' is satisfied nd S02B's not.Second, assumeB is not satisfiedbut IP2B is satisfied.Then there will besome nteger which an be associatedwith inB' suchthatB' is not satisfied.Associateerwitha in A a) =X (P2B. A(a) is satisfied nd hence p2B' s satisfied.Thus B' is notsatisfied,nd (p2Bis satisfied.




14/22

276 HARTLEY ROGERS, JR.This completes heproofof the Induction Lemma and hence completestheproof f Lemma 3.LEMMA 4. A2 valid overD" impliesA, valid overD".PROOF. We prove the equivalentstatement,-A1 satisfiable verDo" implies-A2 satisfiable verD". Assume that G is a relation n Do" satisfyingA1lWe construct relationH inD.. as follows. et a be the map ofg intog whichmaps each integer into 2t. DefineH to be the set of all orderedpairs (u, v)such that u = or,v = as and (r, s) eG, i.e. (r, s) eG ifand only f (or, as) eH.ClearlyH is in D0X. It remains o show thatH satisfies A2 . This willfollowifwe can provean induction emma similar o the InductionLemma of Lemma3. The statement nd proofof that previous nduction Lemma willbe seen toapply without lteration, xcept that G, H, and a are now taken to be as inLemma 4. This completes he proofof Lemma 4.Beforedefining he effectiveransformationO3, we show the existence of anopen-formula5 withbinary G6' and 'G2' as its relationvariables and 'x' and 'y'as its unquantifiedndividual variables, withthe property hat for ny givenrelationH in Da, we can find wo equivalencerelationsG1 and G2 over the in-tegers uch that (Vx) (Vy) (4)


15/22

LOGICAL REDUCTION AND DECISION PROBLEMS 277We then defineDisjoint(b)' to be the formula btainedby substituting for'H' in 'Disjoint(H)'. With these formulaswe defineA, an open-formulawith'x' and 'y' as unquantifiedvariables,

T --df 4 & Disjoint(b).The transformation is now defined o be thesubstitution fT forH, yield-ingA3 = (P3A2.LEMMA 5. A3 validover 2 impliesA2 valid overDo,.PROOF. We prove theequivalent statement, -A2 satisfiable verD" implies-A3 satisfiable ver E2. Assume that H is a relation n D" satisfying A2.FromH we constructquivalencerelationsG1 and G2 as described bove. Then'Disjoint(?)' will be satisfied; herefore(Vx) (Vy) () A 'I')' will be satisfied;and hence (Vx) (Vy) (I - Hxy)' will be satisfied. t follows hat -A3 is satis-fiedby G1and G2 sinceit is obtainedby substituting i for H'.LEMMA 6. A2 valid over impliesA3 valid over 2.PROOF. We provethe equivalent statement, -A3 satisfiable verE2 implies-A2 satisfiable ver D. Assumethat G1 and G2 are equivalence relations atis-fying A3. DefineH to be the set ofordered airs (r, s) suchthatT is satisfiedby G1 and G2whenr is assignedto 'x' and s is assignedto 'y'. ClearlyH willsatisfy A2, sinceA3differs romA2 only n thatT replaces H'. It remains oshow thatH is disjoint.Considerthe set of orderedpairs (r, s) such that 1 issatisfied y G1and G2whenr is assigned o 'x' and s is assigned o 'y'. If thissetconstitutes disjointrelation, hen Disjoint(b)' is satisfied, is identicalwiththisset since (Vx) (Vy) (1 -#-*)' is nowsatisfied,nd henceH is disjoint. fthis set is not disjoint,then Disjoint(b))' is not satisfied, (Vx) (Vy) (m-)' issatisfied, is the nullrelation,ndhenceH is disjoint.ThusLemma6 is proved.Our circleof mplicationss completed. t remains o make twoobservations.First, by the L6wenheimproperty, is valid ifand onlyA is valid over F.Second,A3is valid overE2 if and only fA3is valid for ll interpretationsfits relationvariables as equivalencerelations over any domain). This secondobservation ollowsfrom he factthatG1 and G2willbe equivalencerelations

if and only if they satisfy he formulaof FOFC which expressessymmetry,reflexivenessnd transitiveness or Gi' and 'G2'. If we call this formulaB1,thenA3is valid overE2 ifand only fB1 =X A3is valid for ll relations ver theintegers. y theL6wenheim roperty, he atter s true fand only f B1=X A3 svalid; i.e., ifand only fA3 s valid for ll interpretationsf tsrelation ariablesas equivalencerelations.The desiredreduction o the case of two equivalence relations s now proved,and we haveTHEOREM 2. The problem f validityn FOFC can be effectivelyeduced otheproblem f deciding, ora formula n twobinary elation ariables,whetherrnotthat ormula s validforall interpretationsfits relation ariables s equivalencerelations ver countably nfinite omain (or, alternatively,hetherr not that




16/22

278 HARTLEY ROGERS, JR.formula s validforall interpretationsf ts relation ariables s equivalence ela-tions).

COROLLARY 6. There s no effectiverocedureor decidingwhetherrnot a for-mula in twobinary elation ariables s validforall interpretationsf ts relationvariables s equivalenceelations.In theterminologyf Tarski [13]: theelemen-tary theory ftwo equivalencerelationss undecidable.) [Thisresult Corollary6) was presentedby the author n his dissertation 10]. It was obtainedinde-pendently y Janiczak 5]using the methodsof Tarski et al. [13].] [Theorem1was proved by a directdefinitionnd substitutionthe methodof ChurchandQuine [3]). In Theorem 2, however, he methodsof Lemmas 3 and 4 and theuse of the implications romD to E2 to D" appear to be moregeneral tech-niques. Indeed,thefollowingeems a plausibleconjecture: here s no open for-mula Q of FOFC in two binaryrelationvariables G1' and 'G2' withthepropertythat forany disjointrelationH, one can find quivalencerelationsG1 and G2suchthat (Vx) (Vy) (Q X Hxy)' is satisfied.]

?9. Reduction o a latticeWe make thedefinition

X >- Y df G3Xyand thenconsider hefollowingormula fFOFC:

(Vx) (x > x) &(Vx) (Vy) (Vz) (x > y & y > z =X x > z) &(Vx) (Vy) (3z) (Vzl) (z1 > y & z1 ? x X Zi _ z) &(Vx) (Vy) (3z) (Vzl) (y > z1& x > z1Xz > z1).

A relationG whichsatisfies his formulaover some domain is called a latticeif, n addition,for nyelements and y in thedomain, x, y) e G and (y, x) e Gimpliesx is identicalwithy.Take L to be the set of all binaryrelationsover the integers atisfyinghisformula.GivenanyrelationG3inL, take H3 to be the binaryrelationovertheintegerswhich atisfies(Vx) (Vy) (H3xy x > y & y > x)'; i.e., take H3 tobetheset ofall (r, s) suchthat (r,s) e Goand (s, r) G3 It is immediate hatH3is an equivalencerelation,ndwe can state thefollowing: relationG3will be inL if and only fG3is an orderingwhichdefines latticeover somepartition fthe integers nto equivalence classes (wherethese equivalence classes will begivenby the corresponding 3). In particular, very atticeover the integerswill be inL.Considerthe circleof implications roved n ?8. We shall define n effectivetransformation4 carryinghe formulaA2 intoA4, whereA4 = (pj42and A4willhave the singlebinaryvariable G3'.We shallprovetwo furthermplications,




17/22

LOGICAL REDUCTION AND DECISION PROBLEMS 279A2 (valid) overD -+ A4 overL -+ A2 overD". This willprovidereduction othe case of a lattice.Before defining he effective ransformation4, we showthe existenceof anopen-formula, having binaryG3'as its relationvariable and 'x' and 'y' as itsunquantifiedndividual variables,with the property hat forany relationHin Dam,we can find relationG3 nL such that (Vx) (Vy) (Hxy I)' is satis-fied.Let H be a givenrelation n Da. Take j to be the relation-domainfH and92 to be therelation-rangefH. We dividetheremainingntegersnto two count-ably infiniteetsWClnd aC2With sets h, J2 and ,C1 e construct matrix ikethematrixof ?8, exceptthat we here use ,Ci(rather han aC)forfillingn thedesiredrow-columnntersections.We choose two integers ut of WC2hichwecall ro ndso The restofWC2 ecall WC'nd wesetup a one-to-oneorrespondenceX between9g2nd WC'. onsiderthe set of orderedpairs (r, s) such that at leastone ofthefollowing onditions olds:(i) r= s(ii) r o=(iii) s =so(iv) rE2 and s = Xr(v) s -92 and r is in the same matrix columnas s(vi) s e - Y -df G3xy.

DEFINITIONS 2.X = Y -df (VZ) (X ?> Z 'X X >? Y).

X > Y -df X > Y & - (X = Y) .DEFINITIONS 3.

ro(x) --+df Vy) (x > y).So(X) -*df (VY) (Y > X).

DEFINITION 4.Successor(x,y) --*df x > y & -(3z) (x > z & z > y) F"xsucceedsy"].




18/22

280 HARTLEY ROGERS, JR.DEFINITIONS 5.

.1(x) ->(df (3y) (ro(y)& Successor(y, )).0q(X) df (3y) (xc1(y) & Successor(y,)).9i(X) -*df (3y) (9(x) & So(y) & Successor(x, )).&2(X) ->df gJ(X)& 9J1(X)).We finally ake cI) o be

91(X) & 9J2(Y) & (3z) (JC1(z)& z ? x & z > y).It is immediate rom heconstructionfG3 that Definitions -5 are justifiedand thatb has the desired property hat '(xx) (Vy) (Hxy X d1)' be satisfied.

|' ~~~~~I

Fi(u. 2-sS'chentaticDiagram of G3The definitionf 4 is thesame as thatofV3 in ?8 exceptthat41nowrefers othe formula efined mmediatelybove; i.e. T is 'c1& Disjoint(b)' and 4 is thesubstitution fT for H' in A2yieldingA4 = A2We nowprovetwolemmas similar o Lemmas5 and 6 of ?8.LEMMA 7. A4 validover impliesA2valid overDo.PROOF. The proof s identicalwiththe proofofLemma 5 exceptthatA4 re-

placesA3, L replacesE2, and the constructed elationG3 nL replacesthe con-structedrelationsG1 and G2 in E2.LEMMA 8. A2 valid over impliesA4 validover .PROOF. The proof s identical with the proofof Lemma 6 except that A4replacesA3, L replacesE2, and a satisfyingelationG3 nL replacesthe pair ofsatisfyingquivalencerelationsG1 and G2 n E2.Lemmas7 and 8 togetherwithLemmas 1-4 complete circleof mplicationssimilarto that of ?8. We make two further bservations.First,by the Ldwenheim roperty, is valid if and only fA is valid overF.Second, A4 is valid overL if and only fA4 is valid forall interpretationsf'G3'as a latticeordering overany domain).This secondobservationwill followifwe can showthat-A4 is satisfiable verL ifand only f-A4 is satisfiable yalatticeordering in some domain). If -A4 is satisfiable verL, -A4 is satis-




19/22

LOGICAL REDUCTION AND DECISION PROBLEMS 281fied by some lattice relationover equivalence classes of integers,wheretheequivalenceis as described bove in the definitionf L. Since 'G3' is the onlyrelation variable appearing n A4 and since the satisfying elationfor G6' iscompatiblewiththe equivalencerelationderivedfromt, we can concludethat-A4 is satisfied y a latticeorderingver the domainwhoseelements re theseequivalenceclasses. Conversely,f -A4 is satisfiedby a latticerelation, henB2 & -A4 is satisfied, hereB2is theformula resented t the beginningf thissection.By the L6wenheimproperty, 2 & -A4 is satisfiable verthe integers,and hence,from he definitionf L, -A4 is satisfiable verL. Thus thesecondobservations true.The desiredreduction o thecase of a lattice s nowproved and we have

THEOREM 3. Theproblem fvalidityn FOFC can be effectivelyeduced o theproblemf deciding,or a formulan a singlebinary elation ariable,whetherr-not hat ormula s validforall interpretationsf its relation ariable s a latticeordering.The standardcompositionperations f a latticeare the addition least upperbound) operation u' and the multiplicationgreatest owerbound) operation4n'. These can be definedn termof the ordering elationby

x u y = z (Vzl) (z1 > y & Z1 _ x X z1 > z),xny = zoo (Vzl) (y > z1 & x > z14--* > za).Similarly,heorderinganbe definednterms feither fthecomposition pera-tionsby

x _ y -*xuy =xx > y - x ny = y.

For any relationG3 in L, therewill exist a correspondingernary elationG4overthe ntegerswhich atisfies(Vx) (Vy) (Vz) (G4xyz (Vzi) (G3zly G3zlxG3zlz))'.We call thesetofternary elations btainable nthiswayL1 If we useL1 nplace ofL and "G4xyx'n place of x > y',theproof f Theorem3 leads toCOROLLARY. Theproblemfvalidityn FOFC can beeffectivelyeduced otheproblemfdeciding, ora formulan a single ernaryelation ariable,whetherrnot hat ormulas valid or ll interpretationsf ts relation ariable s the dditionoperation fa lattice; similarly orthemultiplicationperation).Let G3 be the set of all binaryrelationsobtainable by the construction fTheorem3. A generalfeature fthecircleof mplications roved n Theorem3is thatthecircle ould havebeenproved nexactly he samewaywithL replacedby any otherset of binaryrelationsover the integerswhichcontainsG3. Aortiori,t could have been provedwithany set which containsL. [A similarstatementholdsfortheproofof Theorem2. In Theorem2, E2 can be replacedbyanysetofpairsofrelations ontainingll obtainableconstructedairsG1andG2.] In the same way Corollary7 could have been provedusing, n place of




20/22

282 HARTLEY ROGERS, JR.L1, any set ofternary elationsover the integerswhich containsL1 We thushave

COROLLARY 8. The problem f validity n FOFC can be reduced o the ollowingcases:(a) the composition elation of a semi-lattice,(b) the ompositionelation fa directedet,(c) the composition elationof a commutative,ssociative emigroup.[A directed-sets a partial orderingn which any two elementshave an upperbound; a semi-lattices a partial orderingnwhich ny two elementshave a leastupper bound.]From Church'sTheoremwehave

COROLLARY 9. There s no effectiveecisionprocedure or the lementaryheoryofa lattice rfor the lementaryheories ftherelationsmentionedn Corollary .(This result s knownfromTarski [11].)[By methods imilarto those ofTheorems 2 and 3, the author [10] has ob-tained reduction esults or he cases of(1) an equivalenceand a total ordering;and (2) twototalorderings. total rderings a partial orderingwiththecondi-tion added thatx > yvx < yvx = y. These resultswill notbe presented ere.An interestingpen question s that ofreducibility-undecidabilityor the caseofa single otalordering.]?10. Final comments

1. The methods fproof orTheorems and 3 are quite similar. ndeed, theyexemplify generalmethodforobtainingreduction esultswhich we state be-low as Theorem 4. We state the theorem ora set ofn-aryrelations e.g. theset ofbinaryrelations ); the moregeneral tatement or a set ofm-tuplesofn-,.. , nm-aryelations e.g. the set of pairs of binaryrelationsE2) will beobvious.

THEOREM 4. LetR be a setof n-ary elations ver he ntegers.f there xists nopen-formula) havingn-aryG' as itsrelation ariable nd 'x' and 'y' as its un-quantifiedndividual ariableswith hepropertyhat oranyH in Dewwe canfinda relationG in R suchthat(Vx) (Vy) (Hxy =A4)' is satisfied,hen heproblem fvalidityn FOFC can beeffectivelyeduced o theproblem fdeciding, or formulain a singlen-ary elation ariable,whetherrnotthat ormulas validforall inter-pretations f tsrelation ariable s a memberfR.The formula 1 in the theorem s seen to have the same relevantpropertiesas the formula 1used in the proofofTheorem3. The proofof Theorem4 isthereforedenticalwiththeproofofreducibilityo L which occurs n theproofofTheorem3, exceptthatR replacesL.The flexibilitynd usefulness f Theorem4 lie in thefact that relationH isin D" and that we therefore ossess, in any specific pplication,an infinitenumber fdummy bjectsto use in theconstructionfa correspondingelationG in R. Theorems and 3 can be viewed as illustrative pplications fTheorem4. A numberoffurther,imilar pplications houldbe possible.The fact that




21/22

LOGICAL REDUCTION AND DECISION PROBLEMS 283Theorem 4 gives reduction esultsfor a numberof elementary heoriesprevi-ously shownundecidableby Tarski's method lso raises the questionof whetheror not every axiomatizable (i.e. recursively numerable) theory hown unde-cidable by the Tarski methodsgives a reduction f the problemof validity nFOFC. This in turn s part of the more generalunsolved problem Post [9]):does everyundecidable xiomatizable heory ive a reduction f the problemofvalidity n FOFC?2. In ??6-9 we obtained reduction nd undecidability esults n connectionwith uccessive yntactical ransformationsf formulas. he particularmethodscan be viewedas an elaboration f deas originatingn the workof Church andQuine [3]. One should observe,however, hat properties f reduction nd de-cision can be directly ssociated with the sets of relationsconsidered; andfurthermore,ome of the syntacticalmappingswhichwe have used yield cor-respondingmappingson the sets of relations.There are indicationsof a moregeneral heory o be explored oncerning eduction nd decision n sets ofrela-tions.For example,B is someset of binaryrelations nd an open-formula in abinary variable and two unquantifiedndividual variables is given, then 0yieldsa mappingu ofB into F. If such a u exists givingF = u(B), we couldcall B a direct eductionet. f C = pu(B),we could call B a direct eductionetof C. Some general theoremswould be forthcomingelatingto decidability,iteration fmappings, tc.In suggesting uch a development,ne shouldmention he closelyrelated ndelegantwork fTarski [12]on the theory f rithmeticallasses nd the suggestiveinvestigations f Post [9] and Kleene [7] into kinds of reducibility.arski'sformulationsesFOFC with n identity elation ndhas an algebraicform on-venient orproving esultswhich ssert, .g., that particular lassesofalgebraicstructures ave portions ftheir lementary heorieswhich re identical trans-fer results).Our theorywould notuse the identity, ince theLowenheimprop-erty,which cannot be applieddirectlywhenthe identity s present,would becentral to our method;furthermoreur interest n effectiveransformationswouldgiveourtheory generally ifferentmphasis. n fundamentals,owever,the theorieswould have much n common nd forthis reason ourdevelopmentmightbest be undertaken s a part of the Tarski theory.

HARVARD UNIVERSITYBIBLIOGRAPHY

[1] H. BEHMANN, Beitrage zur Algebra der Logik, insbesonderezum Entscheidungsproblem,Math. Ann., 86 (1922), pp. 163-229.[2] A. CHURCH, Introductiono MathematicalLogic (Part I), Princeton, 944.t3] - andW. V. QUINE, Some theorems n definability nd decidability,J. SymoblicLogic,17 (1952),pp. 179-187.141K. G6DEL, Uberformalunentscheidbare dtze derPrincipia Mathematicaund verwandterSysteme, MonatshefteurMath.undPhys.,38 (1931),pp. 173-198.15]A. JANICZAK, Undecidability of some simple formalized theories, Fund. Math., 40(1953),pp. 131-139.




22/22

284 HARTLEY ROGERS, JR.[6] L. KALMXR, Zurfickftihrunges Entscheidungsproblemsuf den Fall vonFormelnmiteinereinzigen, indren unktionsvariablen,ompositoMath., 4 (1936-37),pp.137-144.[7] S. KLEENE, Introductiono Metamathematics, ewYork,Amsterdam,roningen,952.[8] J. MYHILL, A reductionn thenumber f primitivedeas of arithmetic,. SymbolicLogic, 15 (1950),p. 130.[9] E. POST, Recursively numerableets of positive ntegersnd theirdecision problems,Bull. Amer.Math. Soc., 50 (1944),pp. 284-316.[10] H. ROGERS, JR., Some results n definabilitynd decidabilityn elementary heories,Doctoraldissertation, rinceton, 952.[11] A. TARSKI, Undecidabilityf he heoriesf attices nd projectiveeometries,. SymbolicLogic,14 (1949),pp. 77-78.[12] - , Some notions nd methods n the borderline f algebra and metamathematics,Proc. Int. Cong. Math. Cambridge, (1950),pp. 705-720.[13] -X A. MOSTOWSKI, R. M. ROBINSON, UndecidableTheories,Amsterdam,953.

logica decizii publice -engleza

Documents