SOLVABLE CASES OF THE DECISION PROBLEM BY
W. ACKERMANN Hon. Professor of Mathematical Logic and Foundations of Mathematics University of Miinster
1 9 5 4
N 0 R T H - H 0 L L A N D P U B L IS H I N G C 0 MPA NY AMSTERDAM
COPYRIGHT1954
NORTH-HOLLAND PUBLISHING COMPANY AMSTERDAM
P R I N T E D IN T H E N E T H E R L A N D S
PREFACE This book is intended to give a survey of the more important cases of the decision problem for the predicate calculus with equality of the first and second order which have so far been solved. It strictly restricts to this subject. Other investigations connected with the said problem, e.g. the reduction theorems, are only mentioned as far as they are of relevance for the selection o f special cases. There was the alternative to give a syntactic or a semantic formulation of the decision problem. The author has chosen the second way, though this implies the use of set-theoretic concepts. For a syntactic formulation would have to be preceded by the proof of completeness for a certain system of axioms, which can only be done by semantic methods. Furthermore, a semantic formulation is more convenient if the class of special cases is not restricted to formulas of the f i s t order calculus and if we consider not only the problem of universal validity, but also the problem o f determining the domains for which a given formula is valid or not valid. To regard both formulations of the problem would have gone beyond the limits of the book. Relations to systems of axioms are therefore not given here in general, but such relations may easily be established. The report on the more important solutions, e.g. those for the monadic predicate calculus and complete solutions for classes of prefixes, is given in full detail, whereas other rather special solutions are only mentioned. The author has been trying to give a systematic treatment as far as this is possible regarding the nature of the subject so that the different methods which have proved successful, are elaborated. For instance, the reduction to the monadic predicate calculus has been used wherever i t was possible. No effort has been taken to exhibit such decision methods as lead to the desired aim in the
VIII
PREFACE
smallest number of steps, since the interest in the solution of special cases is chiefly a theoretical one. The expert reader will recognize how far the treatment of the problems is new (e.g. the methods of chapter 111, some of the results of chapter V and VII etc.). Most of the results hitherto known have been extended to the predicate calculus with equality. I n chapter VIII there is given a new formulation of the decision problem in a functional calculus instead of in a predicate calculus, which may offer a greater variety for the selection of special problems to be investigated. The compilation of the special cases solved has been made from a general point of symbolic logic. There are certain elementary parts of mathematics, such as elementary algebra, for which solutions of the relative decision problem have been given. These solutions, though important on their part, are only mentioned (cp. page 55), since a report on them would have required a separate treatment. The book is rather self-contained. The reader is supposed only to possess some general knowledge of the propositional and the predicate calculus, as may be acquired by the lecture of any introduction to mathematical logic. The author is indebted to Prof. ARNOLDSCHMIDT for reading the proofs. The publishers provided for a linguistic revision of the English text according to the author’s wish. Harch 1954
W. ACKERMANN
I VALIDITY AND SATISFIABILITY I N FINITE DOMAINS
1. Well-formed formulas In this book we have to do with a certain formal language. We h s t give a survey of the primitive symbols used in constructing the formulas of this language. The first group of symbols consists of the logical constants. They are “$” (and), “v” (or), “-” (not), “ = ” (is equal to). “&”, “v”, L< , - are called respectively the sign of conjunction, the sign of disjunction, the sign of negation or the negation-bar, and the sign of equality. The words set in parentheses may be used in reading the symbols and may also serve to suggest the interpretation in a preliminary way. A second group of primitive symbols are the variables. These are Latin capitals or minuscules to which subscripts or superscripts may be added. We distinguish 1) propositional variables (Latin capitals): X , Y , 2, XI, X,, ...; 2) individual variables (Latin minuscules, but only those succeeding r in the alphabetic order); x,y , z, u, v , w, xl,x2, ... ; 3) predicate variables (Latin capitals with superscripts): G I , H I , K2,G3,G,4,G;, .... Variables G”, H”, H“, ... are called n-adic predicate variables, the superscript indicating the n-adic character. Particularly, GI, H I , ,.. are monadic predicate variables, G2, H 2 , ... dyadic ones, and so forth. A third group of symbols is that of the quantifiers. These are in a certain way already complex symbols. They consist of a variable or of a variable preceded by the sign E put into brackets. ( E x ) , (EGl),( E X ) ,... are called existential quantifiers; (x),(GI), ( X ) ,... are universal quantifiers. ( E x ) ,(EGl),... may be read respectively as “there is an x”,and “there is a G1, ...” ; (x),(GI) are read respectively as “for all x”, and “for all GI, ...”. Certain finite sequences of these primitive symbols which we are going to define subsequently, are called well-formed formulas. C‘-,
7,
2
VALIDITY AND SATISFIABILITY IN FINITE DOMAINS
Later on, we shall introduce other symbols, namely German (Gothic) letters, Greek letters and Latin minuscules preceding r in the alphabetic order. These symbols do not augment the list of primitive symbols and do not occur in the well-formed formulas, but are only used in statements about these formulas. I n principle we could do without them, but they are very useful in avoiding cumbrous textual explanations. We now proceed to the notion of well-formed formula (abbreviated wff). By this term we understand those, and only those, conibinations of symbols which may be shown to be such by a finite number of applications of the following rules W1-WS. W1. A propositional variable is a wff; the variable is said to occur in a free form in the wff. W 2 . A wff is obtained by placing any n individual variables behind an n-adic predicate variable; all the variables are said t o Occur in a free form in the wff. (Exa,mples: G2xy, Gzxx, H3xy.z.) W3. A wff is obtained by placing an individual variable before and behind the sign of equality; the variables are said to occw in a jree form in the formula. (Examples: x=x, y=z.) W4. If is a wff in which there occurs a certain variable in one or more places, but always in a free form, another wff is obtained by placing the existential or the universal quantifier for this has been enclosed by brackets. The variable before "x, after occurrence of the variable is said to be bound in the new formula. a is called the scope of the quantifier. The occurrences of the other variables are free or bound, according as they are free or bound in a. The brackets may be omitted, if a does not contain "$" and "v", or if fl begins with a quantifier the scope of which extends to the end of the formula. (Examples: (x)x=y, (G)Gxx.) W5. If stands for a wff, % is a wff; the occurrences of the variables in are free or bound, according as they are free or bound in a. WS. If a and '$3 stand for wffs and if the same variable does not occur bound in one of them and free in the other, then (a)& ('$3) and (a)v ('23) are wffs. The brackets may be omitted under the same conditions as in W4. The occurrences of the variables are free
a
WELL-FORMED FORMULAS
3
or bound according as they are free or bound in $ or!8. l (Examples : P'z v G2zz, X & (z)(x=Yv x=x).) Wffs described by W l - W 3 are called prime jormulas. They are wffs that contain no quantifiers and no logical constants except' << -99
I n the text dealing with wffs we are using another kind of variables called syntactical variables. They are designated by German (Gothic) letters. a, %, 6, Sl, ... stand for any wffs; they have been used already in formulating the preceding six rules. %(x), %(x, Gl), ... stand for wffs in which z (x and G1) occur in a free form. Q , 6 , c, ... stand for any individual variable, U, 23, Fm, ... for any propositional variable and U", %", %3", ... for any n-adic predicate variable. The use of the syntactical variables permits us to express general statements about wffs, or individual variables, or propositional variables, or predicate variables in a short form. I n writing wffs we usually omit the superscript of an U", provided this can be done without danger of misunderstanding. This is generally the case if the same letter with two different superscripts does not occur in the formula. A wff of the form (a) & (8)is called a conjunction; % and % are called the terms of the conjunction. (a)v ('$3) is called a disjunction, B and % being the terms of the disjunction. A wff '% is called the negation of %. To reduce further the number of brackets, the following conventions are adopted. If we write g1v 212v ... v %" or '& & 212& ... & %", this is to mean association to the left. Thus, (21 v % v 6 stands for ( % v % ) v 6 , % & % & 6 & % for ((a& % ) & Q ) & a . A wff & ... & a*, (a, v ... v %J is also called a conjunction (a dis..., i? are ln the conjunction terms (the disjunction junction); terms). The symbol "&" shall have precedence over "v", so that for instance % & 23 v 6 is to be understood as % & ('23 v 6). Sometimes we use the symbols -+ and tf in formulas % -+ % and % + %. These are only abbreviations for 3 v % and for @ v % & v%. The wffs described here are those of the so-called predicate calculus of second order or of second level. A wff a is called a P-constituent of the wff 8 (using an expression
4
VALIDITY AND SATISFIABILITY I N FINITE DOMAINS
of A. Church [3]), if % is a part of 2 3 and % is not within the scope of any quantifier in 8, and further, % has none of the forms E, (5 & s;D or (5 v %. Every P-constituent of a wff is either a prime formula or is a formula beginning with a quantifier and consisting of the quantifier together with its scope. Example: The P-constituents of the wff
X v ( z ) ( x = y v z = u ) & ( G ) ( x ) G x v u = w are X , ( x ) ( x = y v z = u ) , (G)(x)Gx,and u=v. Valuation of well-formed formulas in a finite domain. Validity and satisfiability The problem with which we are concerned in this book, to state it generally, is how to decide for a given wff whether the assertion it expresses is true. This would require an interpretation of the wff, i.e. a definition of what is meant by its truth in accordance with the adopted meaning of the symbols. But the truth of a wf€ may depend on extralogical facts. Consider e.g. ( E x ) ( E y ) ( = x y) which says that there areindividuals x and y which are distinct. The wff expresses truth if there are two distinct individuals, and falsity if there are not. Thus we cannot give a definition of the truth of a wff without referring to the supposed number of individuals. In the following, we first give a truth-definition of the wffs if the number of individuals is finite. Let D be a domain or set with k individuals or elements. Elements of a domain will be designated by Latin minuscules (but only those preceding r in the alphabetic order, since the other letters are reserved for individual variables) with or without subscripts. The elements of D may be a,, ..., ak. By a monadic propositional function over D we understand a function which has one of the values T or F for every aiof D.T and F are undefined terms ; the choice of the letters suggests “true” and “false”. An n-adic propositional function over D (n> 1) has one of the values T or F for every n-tuple (b,, ..., b,) of elements of D.There are only a finite number of propositional functions of every kind, namely ZCk*’ n-adic propositional functions. Propositional functions over D will be 2.
VALIDITY AND S9TISFIABILITY
5
designated by Greek capitals. We speak of a complete assignment for the free variables of a wff in a domain D,if an n-adic propositional function over D is assigned to every free n-adic predicate variable, an element of D to every free individual variable, and T or F to every free propositional variable occurring in the wff. A complete assignment for a wff without free variables is a vacuous one; complete assignments for a wff will be designated by 9,Ql,.Q,, .... Sometimes assignments for a part of the free variables are also designated by 9, .... By the following method of truth-definition we intend to give to each wff 8 the value T or F relative to a complete assignment for the free variables in a domain D. The value of 8 depends upon this assignment for the free variables and upon the domain D; that is, upon the number k of the elements of D. If there are no free variables in '$,I, the value of 8 depends only upon k. The valuation of 8 is completely determined by the following rules V l - V 6 , which contain a recursion corresponding to the construction of wffs. The rules give a direct valuation of the prime formulas and reduce the valuation of another wff t o the valuation of a finite number of wffs for which the total number of quantifiers and logical constants occurring in them is less than the corresponding number for the given wff. V1. A propositional variable has the value which is assigned to it. V 2 . A wff U'a (Unal ... a,) has the value T or F , according as the propositional function assigned to U1 (U") has this value for a ((al, ..., an)),a (al, ..., a,) being the elements of D assigned to (a19 ...I an). 7 3 . A wff a = b has the value T or F depending upon whether the elements of D assigned to a and b are the same or not. has the value T ( F ) by an assignment, if 8 has the V4. value F (T) by this assignment. V5. A wff B & B has the value T by an assignment, if both 8 and $'3 have the value T for this assignment (dropping the assignment for variables not occurring in '$,I resp. B); a wff 8 v B has the value T by an assignment, if a t least one of the formulas 8 and $'3
6
VALIDITY AND SATISFIABILITY IN FINITE DOMAINS
has the value T for this assignment. I n all other cases % & 8 and have the value F by the given assignment. %v 7 6 . A wff (U)%(U) has the value T by an assignment for the free variables, if %(U) has the value T by the same assignment for the free variables different from U and an arbitrary assignment for the variable U ; a wff (EU)%(U)has the value T for an assignment, if there is an assignment for U which together with the given assignment for the free variables of (EU)%(U) gives the value T to %(U). I n every other case, (U)%(U) and (EU)%(U) have the value F by an assignment. The value of wffs (a)%(a), (Ea)%(a),(Un)%(Ltn), (EUn)%(Un) is determined by reference to %(a)or %(Un) in the same way as has been done above for (U)%(U) or (EU)%(U) by reference to %(U). B y these six rules V1- V6 the valuation of a wfl for a n assignment for the free variables relative to a domain D with a given finite number of elements is not only uniquely determined, but may also be egectively carried out. Note that the effectiveness of the procedure is granted only if the number of elements of D is not only finite but fixed and completely known, for instance, if it is 1 or 7 or 285. For in this case we can give a complete list of the monadic propositional functions, of the dyadic propositional functions over D,etc., and of the elements of D. If an assignment for the free variables of a wf€ is given, the valuation for this assignment is reduced by V6 to the valuation of a simpler wff for a fixed finite number of assignments. By V4 and V5 it is reduced to the valuation of one or two simpler wffs for a fixed assignment, while V1-V3 give a direct valuation for prime formulas. As an example we consider the wff
-
-
( z ) ( E u ) ( E v ) ( zv=Z~= V & U = V ) & (G)(x=Y v GZXv Qy). This formula contains the two free variables x and y. A valuation of the wff in a certain domain B will depend upon the elements assigned to x and y. We first give the valuation for a domain containing only one element designated by a. In this case, only a can be assigned to x and y and generally to any individual variable. U = V has t’he
-
7
VALIDITY AND SATISFIABILITY
value T , and u = v the value F for anyassignment for u and v according t o V 3 and V4; z=u v z = v & u=v has the value F by any assignment (see V5 ). According to V 6 ,
-
-
(Ev)(z=uv z=v & u=v), (Eu)(Ev)(z=uv 2 = w & u = v ) and
-
v z=v & u = v ) (Z)(EU)(EV)(Z=2A
have the value P for any assignment; the last wff has simply the value P,since no free variables occur. According to V5, the whole wff gets the value F. Now let D be composed of two elements a and 6 ;c and d are two elements of D assigned to x and y. z = u v z = v & u = v gets the value T by an assignment, if the elements of D assigned to u and v are different ; for as there are only the elements a and 6, the element assigned to z is the same as one of the elements -assigned to u and v. Then z = u v z = v gets the value T as does u = v. (Ev)(z= u v z = v & & u = v ) gets the value T by any assignment, since there is an assignment for v which together with -the assignment for z and u gets the value T for z = u v z=v & u=v. We need only assign to v the element of D different from that assigned to u.
-
-
(Eu)(Ev)(x=uv x=v & u = v ) and (z)(Eu)(Ev)(z=uvz=w &u=w)
-
get the value T in any case. By V 5 the value of the whole wff is the same as that -of the second term of the conjunction, ( G ) ( x = y v v Gxx v Gyy). x =y v Gxx v C y gets the value T if c and d are not the same elements, since in this case x = y and therefore the whole disjunction gets the value T. If c and d are the same elements, Gxx and Gyy get the same value by any assignment - of a propositional function t o G, so that Gxx v C y and x = y v Gxx v G y get the value T . As this is independent on the assignment for G, ( G ) ( Gv Gxx v @) gets the value T for any assignment for x and y. The value of the wff
-
-
-
(z)(Eu)(Ev)(z=u v Z = V & U = V ) & (G)(x=Y v GXXv Gyy) is therefore T in a domain with two elements, no matter which elements of D are assigned to x and y.
8
VALIDITY AND SATISFIABILITY IN FINITE DOMAINS
If the universal quantifiers for x and y are placed before the wff, their scopes extending to the end of the wff, this new wff gets the value T in a domain with two elements. It gets the value F in a domain with one element, as was shown above. A wg containing no free variables i s called valid in a domain D , if it gets the value T in D. It is customary to define the notion of validity also for wffs containing free variables. A wff of this kind is called valid in a domain D,if the wff is valid which results from it by placing the universal quantifiers for the free variables in any succession before the wff, the scopes of the quantifiers extending to the end of the wff. A wff containing free variables is said to be satisfiable in a domain D, if the wff is valid which results from it by placing the existential quantifiers for the free variables in any succession before the wff, their scopes extending to the end of the wff. With regard to the last two definitions, note that in a wff beginning with only existential quantifiers or with only universal quantifiers the scopes of which end in the same place, the succession of these quantifiers may be altered arbitrarily with the value of the wff remaining the same. This is easily seen by the valuation rule V6. Examples: The wff
(z)(Eu)(Ev)(z=u v Z = V & U = V ) & (G)(x=Y v GXXv Gyy)
is valid in a domain with two elements, but not valid in a domain with one element, was shown before. - as The wff x= y & x = z & y=x is satisfiable in a domain with three elements, may beshown by giving the valuation of -as (Ex)(Ey)(Ex)(x= y & x = z & y = z ) for such a domain.
I1 THE DECISION PROBLEM 1. Valuation in arbitrary domains. Universal validity In 5 2 of the preceding chapter we gave a definition of validity and satisfiability of wffs in finite domains. We now proceed to define the valuation of a w$ for a n arbitrary non-empty domain D , the elements of which may be of infinite number. This does not require any change in the relative definitions. The notions of propositional function and of an assignment for the free variables of a wff remain the same as before. The only difference is that the number of the n-adic propositional functions over D is infinite, if D has an infinite number of elements. Likewise, the valuation rules V l - V 6 remain unchanged as well as the notions of validity and satisfiability of a wff in a domain D. But now there may be an infinite number of assignments for individual variables and for predicate variables. Though the valuation of a wff is defined by the six rules ‘Vl-VVS, these rules in general do not afford a procedure by which the valuation may be effectively carried out. For by V6, the valuation of a wff for a given assignment is in general reduced to the valuation of another wff for an infinite number of assignments. A w$ i s called universally valid, if it i s valid in every non-empty domain. A w 8 is called satisfiable simply if there is a non-empty domain in which it i s satisfiable. The definitions of validity and satisfiability, together with the valuation rules V 4 and V6,immediately yield the following relations between these two concepts. If a wff % containing free variables is not valid in a domain D,3 is satisfiable in that domain, and with free variables is not universally valid, conversely. If a wff 3 is satisfiable, and vice versa. Since for wffs with free variables each of the two concepts of validity and satisfiability, as well as each of the concepts of
10
THE DECISION PROBLEM
universal validity and simple satisfiability, may be reduced to the other, it is sufficient to treat one of them. In the subsequent chapters we shall occupy ourselves only with the validity of wffs, though in some respects the concept of satisfiability is more easily handled when interpreting the wffs. The reason is that the semantic truth-definition for wffs we have given here may then be more conveniently brought into connection with a syntactical truthdefinition (cf. the preface). A syntactical truth-definition, which is not given in this book, is relative to a certain system of axioms. Such a system contains stipulations declaring a special class of wffs (the axioms) t o be universally valid. These stipulations further give prescriptions (deduction rules) for generating a new universally valid wff from a finite number of such wffs under certain conditions. A wff is provable in the system, if it is an axiom or if it may be generated from bhe set of axioms by a finite number of applications of the deduction rules. Syntactically true means provable. As the provable wffs are universally valid the notion of validity, but not that of satisfiability, has a direct connection with the syntactical truthdefinition. Even when using such a syntactical truth-definition a semantical truth-definition is not superfluous. For we must convince ourselves that the wffs called axioms are universally valid and that the deduction rules proceed from universally valid wffs to universally valid wffs, and that the wffs which are syntactically true really comprise all universally valid wffs. This can only be done by semantic methods. For the total number of wffs regarded here, there is no system of axioms delivering all universally valid wffs. Moreover, we are not only interested in the universal validity of wffs. Systems of axioms yielding all universally valid wffs exist for special classes of wffs. Wffs forming such a class are 1)the wffs of the propositional calculus, i.e. the wffs containing only propositional variables as prime formulas, 2) the wffs containing no predicate variables (the wffs of the pure calculus of equality), 3) the wffs containing no bound predicate variables (the wffs of the predicate calculus of
11
VALUATION IN ARBITRARY DOMAINS
first order) wherein the wffs containing the sign of equality may be included or not, and wffs of other special classes. We illustrate the notions of validity, satisfiability and universal validity by giving some examples.
ay)
(Ey)(Gx v This wff is universally valid; for if the element a of an arbitrary domain D is assigned to x and any monadic propositional function over D to G, the assignment a for y gives Gx v Gy the value T, since Gx and Gy get the same value. (1)
(2)
(EG)(x)(Ey)(Gxx& z y ) .
This formula is valid in a domain D which contains at least two elements; it is not valid in domains with only one element. If there is only one element in D ,Gxx & gets the value F by any assignment, since the elements assigned to x and y are the same. Consequently, the wff itself gets the value F. If there are at least two elements in D,we assign to G the dyadic propositional function over D the value of which is T only for an ordered pair of elements of D,the first and second member of which are the same. Then, given any assignment for x, an assignment for y can be found, namely an element of D different from the element assigned to x, so that Gxx&Ky gets the value T,which means that (EG)(x)(Ey)(Gxx& gets the value T.
6
G)
GX & Cy & X = Y . (3) This wff is valid in no domain at all; it is not even satisfiable. For if we assign to G an arbitrary monadic propositional function over a domain D and the elements a and b of D to x and y, either a and b are not the same elements, in which case x = y gets the value F ,or a and b are the same elements; in this case, Gx and Gy get the same value, so that either Gx or z y gets the value F. In & x = y gets the value F. any case Gx & (4)
(EG)((x)(Ey)Gxy& ( x ) G & ( x ) ( y ) ( z ) ( Gv
v Gxz))
This wff is valid in any domain having an infinite number of elements, and only in such a domain.
12
THE DECISION PROBLEM
If D has an infinite number of elements, there is a denumerably infinite subdomain of D called D, with the elements a,, a,, a,, .... We assign to G the dyadic propositional function over D the value of which is T only for the ordered pairs (un,a,,) (k> O ) and (6, uk)(k 3 l ) , b not being an element of D,.It is easy see that -toby this assignment (x)(Ey)Gxy & ( x ) G G & (z)(y)(z)(GxyvGyz vGxx) gets the value T, since each conjunction term gets the value T. On the other hand, if D has only a finite number of elements, let @ be an arbitrary dyadic propositional function over D . There is a subdomain of D having the following property $: If a is an arbitrary element of the subdomain and the ordered pair ( a , b ) gets the value T by @, then b is an element of the subdomain also. For instance, D itself is such a subdomain. Let Dlbe one of the subdomains with the property $ having the smallest - number of elements. If (x)(Ey)Gxy & (x)= & (x)(y)(x)(Gxyv Gyx v Gxx) is to get the value T by assigning @ to G and if c is some element of D,, there is another element el of D, not identical with e such that (c, cl) gets the value T by @, since (x)(Ey)Gxy & (x)= is to have the value T. Let D, be the set of all these elements cl. D, has a smaller number of elements than D,. If c2 is an arbitrary element of D, and if b is an element of D such that (c,, b ) gets the value T by @, the value -of (c, 6 ) for @ is T, since we are supposing that (~)(y)(z)(Gzy v Gyz v Gxz) gets the value T by assigning @ to G. Therefore, 6 is an element of D,. This means that D, also has the property '$. Since D, was supposed to be one of the smallest subdomains of D with the property '$, this is a contradiction.Therefore our supposition that the wff gets the value T by assigning @ to G, cannot be true. Since @ was arbitrary, our wff (4) gets the value F in any finite domain.
2. Equivalences If a wff $ ++ ? 23, I i.e. v 23 & 8 v % is valid in a domain D, the valuations of 8 and of 23 are the same for two relative assignments which coincide with respect t o the variables common to % and B. For it is an immediate consequence of the valuation rules V4 and V 5 that by any assignment rzI tf 23 gets the value T, if and only
a
13
EQUIVALENCES
if both '21 and % get the value T by this assignment, or if both wffs get the value F. If '21 ++ '23 is valid in D,if (21 is part of a wff C5 and if the wff & is obtained from 6 by replacing the part '21 of 0: by $'3 and by dropping, if necessary, vacuous quantifiers (those quantifiers the scopes of which do not contain the variable of the quantifier), C5 ++Elis valid in D, provided that contains no free variables not occurring in '21. For it is clear that any assignment gives the same value to 6 and El. '21 and % are called equivalent wfjs, if '21 ++ 93 is universally valid. If 8 and 2 '3 are equivalent wffs and if 6 and have the same meaning as before, 6 and El are equivalent wffs. Equivalent wffs are valid or not valid in exactly the same domains. In the following we state several equivalences which are used later on. E l . From a wff % we get an equivalent wff $' 3 by the following transformation. The variable of a quantifier of 8 and the same variable in all places of the scope of the quantifier is replaced by another variable of the same character. This transformation is restricted to the case in which !8 is a wff and the newly introduced variable is not identical with one of the variables occurring in the scope of the quantifier. Example: (Ex)Gx & (Ex)Gx may be transformed into (Ez)Gx& & (Ey)Gy, and conversely. Indeed, it is seen by V 6 that by any assignment for the free variables of '21 in any domain the part of '21 consisting of the quantifier and its scope gets the same value T or F before and after the transformation, as does %. If a wff (21 is transformed in the described way one or more times we shall say that we have rewritten the bound variables of 8. Subsequently we shall not make much use of the syntactical variables a, b, C, ..., U, %, 2 ' 33, ..., and U", %", iBn,..., which stand respectively for any individual variable, any propositional variable and for any n-adic predicate variable. A statement, for instance, concerning the validity of some wff (z)(Ey)(z)%(x,y, x ) equally m *-
14
THE DECISION PROBLEM
holds for any wff (a)(Eb)(c)%(a, b, c) resulting from (x)(Ey)(z)%(x,y,z) by rewriting the bound variables. Therefore it is sufficient to state such statements for specially chosen bound variables. In stating the equivalences E 5 - E l 6 a may designate individual variables as well as propositional variables and predicate variables, since these equivalences hold for all kinds of variables. Pairs of equivalent wffs are the following ones: E2.
E3.
%%%
E4.
(m)
E5. E6.
E7. E8E9. E10. Ell. E12. E13. E14. El5. E16.
(m) (Ea)(%(a)v %(a))
%(a)) (Ea)%(a)& % % & (Ea)%(a) (Ea)%(a)v % B v (Ea)%(a) (a)(%(a)
(a)%(a) & B B & (a)%(a)
(a)%(a) v % % v(a)%(a) E17. ( x ) ( x =v~%(x, y)) E18. (Ex)(x=y & %(x, y))
and and and and and and and and and and and and and and and and and
The equivalences E2 - E l 6 are an immediate consequence of the valuation rules V l - - 6 . I n E 9 - E l 6 , the wff B of course cannot contain the variable a, because we have assumed that we have a pair of wffs. I n El7 and E18, %(y, y) is the wff resulting from %(x, y) by substituting y for x in all places where x occurs. The pairs of wffs mentioned in El7 and E l 8 are recognized as pairs of equivalent wffs as follows. If we have an assignment for the free variables of %(y,y) in a domain D and an assignment for %(x, y) which is the same as that for %(y, y) for the variables different from x, and by which the same element of D is assigned to x and to y, then these assignments give the same value to %(y, y) and to
#-FORMULAS
15
X(x, y). This is clear for prime formulas and may be proven for other wffs by induction, according to the construction of wffs by W1-W6 of Chapter I, 9 1. If an assignment €or the free variables of %(y, y) is given, this assignment gives the same value t o (Ex)(x=y & %(x, y)). For if X(y, y) gets the value T by this assignment, so does x = y & %(x, y), provided t’he assignment is completed by assigning to 2 the same element as to y, If X(y, y) gets the value F by this assignment, x = y & %(x, y) also receives the value P by any assignment coinciding with the assignment for X(y, y) with respect to the variables different from x. This results from what we have said above if the same element is assigned to x and y. If different elements are assigned to x and to y, x= y and therefore x = y & 8 ( x ,y) get thevalue F . I n a similar manner it is to be seen that %(y, y) and (z)(x=y v %(x, y)) are equivalent wffs. v ... v 8, is transformed into an equiE19. A disjunction valent wff if the succession of the disjunction terms is somehow altered. The analogous statement is true for a conjunction. E20. The wffs X and X & ‘23 are equivalent if ‘23 is universally valid. The wffs X and % v 23 are equivalent, if 23 is not satisfiable is universally valid. in any domain, i.e. if E21. The wffs X v (23 & C?) and % v ‘23 & % v 6 as well as the wffs 8 & ‘23 v 6 and (8 & ‘23) v (X & 6)are equivalent wffs. E19--E21 are easily recognized to be true by the valuation rules.
3. #-formulas. Elimination of the propositional variables We often have to form sentences like this: “A wff gets the value T or F if the element a is assigned to x, the element b to y, the monadic propositional function Y to GI, etc.” It is desirable to have a shorter form for such statements; this will be obtained as follows. Instead of saying “ x = y & (z)Gzz gets the value T ( F ) , if we assign a to x, b to y and 0 to G”, we use in a synonymous manner the sentence”, a=b & (z)@az is true (false)”. Likewise, “X v Y & (G)(Gx v Gy) gets the value F , if we assign T to X , F to Y , a to x, and a t o y” and “T v F & (G)(GavGa) is false” shall have the same sense. By this we do not intend to extend the notion of wff. Formal expressions like T v F & (G)(Ga v Ga) only
16
THE DECISION PROBLEM
occur in statements about wffs; they do not belong to our formal language. We shall call such formal expressions S-formulas. S-formulas are those, and only those, formal expressions which result from a wff with free variables by replacing all or some of these variables by the names of things assigned to them in a domain. The replacement of a free variable must be done in all places where it occurs. Wffs without free variables may also occur among the S-formulas. If an S-formula results from a wff in this way, we say that the 8-formula belongs to the wff and the assignment for the free variables of the wff. The wff and the assignment to which an S-formula belongs, is not uniquely determined by the S-formula, even if we disregard the fact that different letters may be used for the free variables of the wff. E.g. a=a belongs to x = x and the assignment a for x, but also to x= y and the assignment a for x and a for y. T v & Z belongs to X v & Z and the assignment T for X , but also to Y vx $ 2 and the assignment T for X and T for Y (but not to 2 v z & 2). The same S-formula may belong to a wff % and an assignment Ql and to a wff 23 and the assignment Q, which is relative to the same domain as Ql. % and 93 can only differ in such a way that the place for a variable in B is occupied by another variable of the same character in 23. Variables in corresponding places of B and ‘B get, if any, the same assignments by Q, and Q2. If two places are occupied by the same variable in one wff and the corresponding places in the other wff by different variables, then the assignment for the two variables of the second wff is the same. Q, and Q2 give the same value to % and to 23 if they are complete assignments and otherwise, if their completion is achieved by adding the same assignments for the other free variables. This is seen at once for prime formulas by inspecting the valuation rules 8 1 - V 3 and is proved for other wffs by induction according to 84- 8 6 . Thus the statement “An S-formula is true in a domain D” has sense without naming a special wff to which the S-formula belongs. “An S-formula without free variables is true (false) in a domain D” is only another expression for “The S-formula belongs to a wff and an assignment for its free variables over D which gives the wff the value T(F)”, or
x
S -FORMULAS
17
“Any wff and pertaining assignment gives the wff the value T ( F )in D if the X-formula belongs to them”. “An 8-formula with free variables is true (false) in D for an assignment for the free vari-
ables” means “The 8-formula belongs to a wff and an assignment for a part of the free variables of the wff over D which, completed by assigning to the other free variables the same things as to the free variables of the X-formula identical with them, gives the wff the value T ( F ) in D”.Note that not for every assignment for the free variables of an X-formula in an arbitrary domain the formula, is true or false, since this assignment must be made up to form a complete assignment with the assignment to which the X-formula belongs. The X-formula Yxx,for instance, can be true or false only if an element of the domain D over which Y i s defined, is assigned to x. a=x & Gax is true or false only for assignments for x and G in domains of which a is an element. Two 8-formulas Gland Gz are called equivalent if Gltf G2is true in every domain for all assignments for the free variables of G1 tf Gz. For wffs this notion of equivalence is the same as that given in $ 2 of this chapter. G3and G4 are equivalent 8-formulas if the following conditions are fulfilled: GI and G2are equivalent 8-formulas; Gz does not contain any free variables not occurring the X-formula G4results from in Gl;G1is part of an S-formula G3; G3 by replacing the part Gl of G3 by Gz and by dropping, if necessary, quantifiers which have become superfluous. If a wff is equivalent to the X-formula T ( F ) , then the wff is universally valid (valid in no domain at all). As i s seen by the definition of equivalence, this notion i s restricted to X-formulas containing only T and F besides the primitive symbols of wgs. Such 8-formulas can be transformed into equivalent wffs or into one of the two 8-formulas, T or F . This is done by replacing in the S-formula, beginning anywhere, T by F , by T , T v and a v T by T , F v 8 and ’% v P by a, T & rll and ‘% & T by a, F & % and & F by F and by simultaneously dropping vacuous quantifiers, if necessary. Since all the mentioned pairs of S-formulas are pairs of equivalent 8-formulas, the 8-formula is transformed into an equivalent one. Since each reduction step diminishes the number
18
THE DECISION PROBLEM
of logical constants, this reduction can be carried on until T and F have disappeared from the S-formula, or until the S-formula is reduced to T or to F . This may be used to show that we need not investigate the validity or satisfiability of wffs containing propositional variables, because the propositional variables can be eliminated from a wff. Validity or satisfiability of a wff always means the validity of a certain wff containing no free variables. A WTJ with bound propositional variables may always be repluced by a n equivalent w g containing no propositional variables, or it m y be recognized at once as universally valid or valid in no domain at all. Each such wff can at first be transformed into an equivalent S-formula without bound propositional variables by replacing in the wff, beginning at an arbitrary point, every part ( X ) % ( X )by %(T)& %(F) and every part ( E X ) % ( X ) by %(T)v %(F). This S-formula is then reduced in the way described above. If the formula resulting in the end is T or F , the wff is universally valid or valid in no domain at all; otherwise, we get an equivalent wff without propositional variables. The well-known truth-table decision procedure for wffs of the propositional calculus, i.e. for wffs containing no individual and no predicate variables, is included herein. As an example we consider the wff:
( X ) ( Xv ( y ) ( F yv 15)) & ( E Y ) ( Y& (EG)(Ex)(Gz& Y ) ) . We first replace
( X ) ( X v (Y)(y=Y
" m by T v ( Y ) ( y = y v m
-
F v (Y)(Y=Y+
F)
which reduces to T,so that the wff itself is reduced to
(EY)(Y & (EG)(Ez)(Gz& Y ) ) . We replace this wff by
(T & (EG)(Ez)(Gx& T))v ( F & (EG)(Ez)(Gz& P ) ) which reduces to (EG)(Ex)Gx.(EG)(Ex)Gxis equivalent to the wff from which we were starting.
19
NORMAL FORMS
4.
Normal forms For this section we need the concept of P-constituent of a wff defined in 9 1 of Chapter I. A wff is said to express a tautology, or to be tautologous, if every S-formula reduces to T which results from the wff by replacing the P-constituents in an arbitrary way by T or F , but so that equally shaped P-constituents are replaced by the same letter. A tautologous wff is of course universally valid, but not every universally valid wff is tautologous. E.g. (z)(z= x) and (z)(Gzv&) are universally valid, but not tautologous. Two tautologous wffs are equivalent. Every wff can be brought into certain normal forms by means of equivalence transformations. There are several normal forms. A wff is said to be in conjunctive normal form if it is a disjunction the terms of which are P-constituents or the negations of P-constituents of the wff or if it is a conjunction of such disjunctions. Wffs which consist only of one P-constituent or of the negation of a P-constituent shall be included among the above disjunctions. We first show that for every non-tautologous wff an equivalent wff in conjunctive normal form can be constructed. a1,212, ..., am may be the P-constituents of the wff, P-constituents equally shaped not being counted twice. We will designate the wff by B(a1,..., a,). B(T, a2,..., a,) and B(F,212, ..., a,) are the #-formulas resulting from B(2Xl, ..., am)by replacing 2I1 everywhere by T ( F ) . B('2I1,..., a,) is equivalent to the S-formula
B(T,a2,..., %,). gets the value F , then the S-formula
a1v B(F, 212, ..., a,)
&,
v
For if by any assignment gets the same value by this assignment as
B v B ( F , a2,..., %), tk v B(T, a2,..., %,). This formula reduces to B(F, 212, ..., a,) which gets the same value
%(al,
as ..., a,). If by any assignment S-formula gets the same value as
a1 gets
the value T,the
T v B ( F , g2,..., '3%) & ?I v B(T,'?I2, ..., a,), which reduces to %(T,S2,..., a,).
20
THE DECISION PROBLEM
We shall prove our theorem by induction on the number n of P-constituents. If this number is one, %(9ll) is equivalent to v % ( F )& v %(T).We eliminate T and F in this 8-formula or 211 & % as conby the methods of 5 3 and get either 2117 or junctive normal form, since B(F)and %(T) cannot both reduce to T ;otherwise %(211) would be tautologous. Let us assume that we have shown our theorem to be true for a wff with less than n P-constituents. ..., a,) is equivalent to
a1
%(al,
211 v % ( F ,a2,..., a,) &
v
%(T,a2,...)am)
I n this S-formula F and T are again eliminated by the methods .of 0 3. The result is a wff of one of the following forms: 2l1v6&l,v%, 8 1 83%
v 9,
211v&&q, v 9,
a l V &
a1 &Z1, %I, &.
The wff cannot reduce to F , as is seen by its structure; it cannot reduce t o T,for in that case both %(F,a2,..., am) and %(T,g2,...,3%) would reduce to T,which is impossible since a2,..., is not tautologous. The last three of the above eight wffs are in conjunctive normal form. I n the other five wffs, 6 and 3 are wffs with only the P-constituents az7 ..., which according to our assumption can be brought into conjunctive normal forms 6’ and 9’. Because ‘ill1v G’ and v 9’can be transformed into a conjunctive normal form by means of the first equivalence E 2 1 of 5 2 , this holds too for the five wffs. This completes our induction. A tautologous wff with the P-constituents a17 ...)‘i&can also be given a conjunctive normal form; e.g. 3, v is such a form. A wff is in disjunctive normal form if it is a conjunction of P-constituents and the negations of P-constituents or if it is a disjunction of such conjunctions. Wffs consisting only of one P-constituent or of the negation of a P-constituent shall be included among the above conjunctions. I n order to show that a wff a can always be brought into a n equivalent disjunctive normal form, we fist construct a conjunctive normal form B1& ... & Brn of 8. According to E 2 of 5 2, 2l is equivalent to and therefore to B1& ... & 58%. Using E3,
%(al,
al
an)
21
NORMAL FORMS
Em.
is v ... v By E4 every !?jl& ... & !Bmis transformed into transformed into a conjunction whose terms are negations of P-constituents or double negated P-constituents. By eliminating the double negations according to E2, we get a disjunctive normal form of '21. Every wfl can be given an equivalent normal form in which the negation-bar stands only over prime formulas. If a wff is given, by successive applications of E3, E 4 , E5 and E6 the negation signs can be brought farther and farther inside until finally they stand, one or more times, only over the prime formulas. By means of E2 the negation signs over the prime formulas are removed until there is at most one left. Example: The wff
(G)(Ex)(Ey)(Gxy &2
7 )
becomes (EG)(x)(y)(= v x= y )
by the transformation. We m y further transform any w 8 into an equivalent one in which the quantifiers occur only at the beginning with scopes extending to the end of the w4, no quantifier standing under a negation-bar. We first transform the given wff into one in which the negationbars stand a t most over prime formulas. Then we rewrite the bound variables (see E l of 3 2 ) in a way such that all quantifiers have different variables. Subsequently, we place all the quantifiers at the beginning of the wff with scopes extending to the end of the wff, by using several times the equivalences E9-El6 of 5 2. This generally can be done in more than one way. For instance, the quantifiers can be placed a t the beginning of the wff in the order in which they occur, but also any succession of the initially placed quantifiers can be obtained such that any quantifier which was in the scope of another quantifier remains in the scope of that quantifier. A wff in which all the quantifiers are placed at the beginning of the wff with scopes extending to the end of the wff is said t o be in a prenex normal form. The succession of quantifiers with which the wff begins is called the prefix of the wff. The part of the wff which remains if all the quantifiers are deleted is called the matrix of the wff.
22
TI333 DECISION PROBLEM
Example: A prenex normal form of (x)(Ey)Gxy& (Ez)Hz is ( E x ) ( y ) ( E z ) ( K& y H z ) with the prefix ( E x ) ( y ) ( E zand ) the matrix & Hz. Other prenex normal forms are ( E x ) ( E z ) ( y ) ( K & y Hz) and ( E z ) ( E x ) ( y ) ( G& Hz). 5.
Three forms of the decision problem If a wff is valid (satisfiable) in a domain D, it is also valid (satisfiable) in a domain D, which has the same cardinal number as D,i.e. the elements of which may be put into one-to-one correspondence with those of D. Indeed, through the assignment used for the valuation of a wff in D,there may be determined in an unambigous way assignments relative to D, which give the same valuation. If a is assigned to an individual variable relative to D , the corresponding element a, of D, is used for the assignment relative to D,. If the n-adic propositional function rP is assigned to U" in D,the assignment for Unrelative to D,is the propositional function rP1 over Dlwhich assigns the value T to those, and only those, n-tuples (b,, ..., b,) over D,for which rP gives the value T to the corresponding n-tuples (a,, ..., a,) over D , a, corresponding t o bi. Therefore, disregarding those wfla which are universally valid (satisfiable in every non-empty domain) and disregarding those which have this property in no domain, the assertion of the validity (or satisfiability) of a w@ in a domain D is equivalent to a statement about the cardinal number of D. The definition of validity does not supply us with a criterion for recognizing in the general case whether a given wff is valid (satisfiable) in a given domain, or whether it is universally valid (satisfiable) at all. The problem of finding an effective procedure for determining the validity (satisfiability) of a given wff is called the decision problem. More precisely, as the validity and satisfiability of a wf€ depend on the cardinal number of the relative domain, the decision problem may be stated in several distinct forms. We formulate all of them with respect t o the problem of validity, since this is sufficient (see 8 1 of this chapter). The most important form is this:
THREE FORMS OF THE DECISION PROBLEM
23
I. T o decide for a given wfl whether it i s universally valid or not. A more comprising form of the problem is this: 11. To decide for a given wfl whether it is universally valid. If it i s not universally valid, to decide whether it i s valid in no domain whatsoever or in some domain. I n the last case the cardinal numbers of the domains for which it i s valid are to be determined. Other forms of the decision problem may be stated as well, e.g. the following one: 111. T o decide for a given wfl whether it i s valid in all domains with a finite number of elements or not. As far as the literature goes nearly all investigations about soluble cases of the decision problem concern problems I and 11; I11 has been dealt with only in connection with 11,since a solution of I1 includes a solution of I11 (but see Q 2 of chapter VIII). Of course it would be most desirable to have a decision procedure applicable to all wffs. Investigations made at first by A. Church [l, 21, then by A. Turing [l] and others, by which the somewhat vague intuitive notion of a decision procedure was replaced by a precise definition, show that a general solution of the decision problem in the forms I and I1 cannot be found. B. A. Trachtenbrod [l] has shown also that a general solution of the form I11 of the decision problem is not possible. To enter into the particulars of these investigations is outside the limits of this book. It remains t o look for a solution of the problem for special cases, i.e. for certain special well-defined classes of wffs. I n the following we give a survey of the more important special cases for which a solution has hitherto been reached.
I11 SOLUTION OF THE DECISION PROBLEM FOR EQUALITY FORMULAS
In this chapter we give a solution of the decision problem for wffs which contain no predicate variables, but only individual variables. The prime formulas of such wffs are all of the form a= b. We will call those formulas for short equality formulas. This problem seems to have been solved first, in connection with the more comprehensive problem of chapter IV, by L. Lowenheini [l]. We give here an independent treatment.
1. Solution of the form I1 of the decision problem It is sufficient to give a decision procedure for wffs in prenex
normal form. Let '%(z,,
...,)z,
be such a wff with the free variables
x,, ..., x, and with a prefix consisting of n quantifiers. Further, let k be m i - n . We have the following theorem: If % i s valid in a domain with k elements, it is also valid in any domain with more than k elements. If '% i s valid in some domain with more than k elements, it i s also valid in a domain with k elements. We prove a furthergoing theorem. Let D, be a domain with k elements and D one with more than k elements. a,, ...,a,,,
and b,, ..., b, may be m-tuples of elements of D,(D) such that a one-to-one correspondence can be established between a,, ..., a, and b,, ..., b,, each ai corresponding to bi. We may also say equivalently that these elements fulfill t,he following condition : For each p and q, a, and a, are identical, if and only if b, and 6, are identical, Under these conditions %(a,, ..., a,) is true in D, if 'U(bl, ..., b,) is in D,and vice versa. This includes the theorem above. For if a($,, ..., x,) is valid in D,, then %(al, ..., a,) is true in Dk for arbitrarily chosen elements a,, ..., a, of D,.If bl, ..., b, are arbitrary elements of D , we can find elements a,, ..., a, of D, satisfying the above-mentioned con-
SOLUTION OF THE FORM I1
25
ditions between a, and b,, since 12 2 m. %(b,, ..., 6,) is then always true in D.Likewise, if %(b,, ,..,b,) is true in D for arbitrary elements b,, ..., b, of D,%(a,, ..., a,) is always true in Dk,for we can establish a one-to-one correspondence between given elements a,, ..., a, and certain elements b,, ..., 6, of D. The second theorem is proved for an arbitrary k by induction on the number n of the quantifiers of %(x,, ..., x,). If n is 0, the theorem is evident, since all the prime formulas of %(x,, ..., x,) are of the form xp= x, and since a p=a,and b, = b, are supposed to be both true or both false. We assume the theorem to be proven for n quantifiers. If %(x,, ...,x,) has n+ 1 quantifiers, it either has a form (y)B(y,x,, ...,xm) or (Ey)B(y, x,, ..., x,). a,, ...,a, and b,, ..., b, may be m-tuples of elements of D, and D fulfilling the condition expressed in the theorem. If (y)B(y,a,, ...,a,) is true in Dk, B(c, a,, ..., a,) is true in D, however the element c may be chosen in Dk.Now take an arbitrary element d of D. We select an element c, of D, which is identical with ai,if d is identical with bi, and which is different from all the elements a,, ..., a,, if d is different from every bi. Such an element c, can be found in D,, since k >, m + 1. Because B(c,, a,, ..., a,) is true in D,,B(d, b,, ..., b,) is true in D,since $'3 has only n quantifiers. Since d was arbitrary, (y) B(y, b,, ..., b,) is true in D. If (y)B(y, b,, ..., b,) is true in D, B(d, b,, ..., b,) is true for an arbitrary d of D ;then B(c, a,, ...,a,) is true in D,for an arbitrary c. For we can find an element d, of D such that d,, b,, ..., b, and c, a,, ..., a, are in one-to-one correspondence, since D has more elements than D,. Since @(d,, b,, ..., b,) is true, B(c, a,, ..., a,) is also true, which means that (y)B(y, a,, ..., a,) is true in D,. If (Ey)B(y,a,, ..., a,) is true in Dk,this means that there is an element c of Dk such that %(c, a,, ..., a,) is true. Using a similar argumentation as before, we can find an element d of D such that d , b,, ..., b, and c , a,, ..., a, can be put into one-to-one correspondence. By our supposition (Ey)@(y,b,, ..., b,) is true in D. If (Ey)B(y, b,, ..., b,) is true in D, (Ey)B(y, a,, ..., a,) is true in Dk.This is proven by the same method. Since our induction is thus complete, the second theorem and
26
DECISION PROBLEM FOR EQUALITY FORMULAS
therefore the first one, the only one in which we are interested, has been proved. This theorem at once solves the decision problem for the equality formulas. It is sufficient t o state the solution for wffs without free variables. An equality formula without free variables which i s in prenex normal form and has k quantifiers, is universally valid if it i s valid in the domains with 1, 2, ..., and k elements. I t i s valid in no domain at all if it is not valid in any of the domains with 1, 2, ..., k elements. Generally it i s valid in those domains with 1, 2, ..., or k elements which may be found out by the decision procedure for domains with a finite number of elements (see 5 2 of chapter I ) , and in every other domain, resp. in no other domain, if it is valid resp. not valid in a domain with k elements. As an example the reader may take the wff
-
( E x ) ( E y ) ~ =& y (Ex)(E~)(Ez)(Eu)(v)(v==x v V=Y v V=Z v
V=U)
- - - -
&
& (Ex)(E~)((z)(z=xvz=~)v(Ez)(Eu)(x=~ & X = Z &X=U &Y=Z &
- -
& y=u & z=u))
and prove that it is only valid in a domain of two and in a domain of four elements, so that the assertion of the validity of the wff is equivalent to the statement that the domain of individuals has two or four elements. I n special cases, as in that of the last wff, the decision procedure may be abbreviated by using the following theorems : E22. A wfl rzI & B i s valid in a domain if rzI and B are valid in that domain, and conversely. A wfl % v B is valid in a domain if rzI or B is valid in that domain, and conversely, provided that 'ZT and $'3 have no free variables.
2. Another criterion for the universal validity of equality formulas We will give another solution of the decision problem for equality formulas, but only for the form I of the problem. If only the universal validity of equality formulas has to be decided, this criterion sometimes reaches the desired result in fewer steps than the previous one. This is independent of the fact that the proof of
ANOTHER CRITERION
27
the validity of the criterion is more complicated. This second method, by the way, does not make use of the valuation in finite domains. An equality formula without free variables is called reduced if it is a conjunction of wffs or a single wff of the following kind. The wfTs are in prenex normal form; their prefixes consist only of universal quantifiers ; their matrices are in conjunctive normal form and do not contain prime formulas of the form a = b with different variables a and b which stand under a negation-bar. Prom every equality formula which is in prenex normal form or which i s a conjunction of wfjs in prenex normal form we can construct a reduced formula so that the equality formula is universally valid, if and only if the reduced formula is universally valid. To avoid misunderstandings this does not mean that the equality formula and its reduced formula are equivalent. E.g. if two wffs are both not universally valid, it is possible that one of them is valid in a certain domain, while the other is not. We first describe the construction of the reduced formula. This is done in several steps. We start from a conjunction 211 & ... & 21k of wffs in prenex normal form. We will characterize each 8, by a natural number. If 21i is reduced, the number is 0. If f14 is not reduced but has only universal quantifiers, the number is 1. If 8, has m existential quantifiers preceding universal ones and n other existential quantifiers, the number is 2m+n+l. I n such a conjunction, we replace in a certain manner the first conjunction term %,, which is not reduced, by a wff '23, or by a conjunction '23 & 6 such that the numbers assigned to '23 and GY are less than the number as signed to &. By repeating such a transformation a finite number of times, 211 & ... & 21n evidently becomes a reduced formula. We distinguish several cases. 1 ) 9Ii has only universal quantifiers. We bring the matrix of 21d into conjunctive normal form. Each conjunction term of the matrix is a disjunction of formulas of the form a = b or including the case when there is only one such formula. If a conjunction term contains adisjunction term a = b with different variables a and b, we delete a = b and replace a by b
a,
28
D E C I S I O N PROBLEM F O R E Q U A L I T Y BORMULAS
in all occurrences of ain the conjunction term. If the conjunction term consists only of a = b, we replace it by ’b = b. This is repeated as often as possible, vacuous quantifiers being deleted, until is transformed into a reduced formula. The transformation of is an equivalence -transformation; for by E8, E17, and El4 of 11, $ 2 , (x)(x=y -v %(x, y) & B(x)) can be transformed successively into (x)(z=y v %(x, y)) & (x)%(s), %(y, y) & (x)B(x),
(.)(a(%Y) 83 Wx)).
ai
begins with an existential quantifier. We 2 ) The prefix of replace the existential quantifier by a universal quantifier for the same variable; the characteristic number of ‘$Xi is thereby diminished. 3) The prefix of %4 begins with a universal quantifier. There are n existential quantifiers, but none of them precedes a universal one. 2Ii has a form
(x1) *
f
*
(~,)(Ey,)(EYz)* - * (&h&)B(~,> ...> XP7
Yl,
Yz,
*
-
*
J
%a)
where B contains no quantifiers. We replace this formula by
... (%)(EYz) (EY,)(B(xl> 5 . 5 1 , Yz, Yi) v v Wx,, 5 ,xz, yz, y), v . * - v B(x,, ..-,5s’ x p , yz, * - * , yd). 4) The prefix of %ibegins with a universal quantifier. There (51)
a * - ,
. * a >
are existential quantifiers preceding universal ones. has the form (zl)... (xp)(Ey)B(xl,..., xp,y). B this time contains quantifiers, some of which are universal quantifiers. We replace %$ at first by the conjunction of the two formulas (i)
(%I)
... ( x p ) ( 8 ( z 1 7 v
5
7
*.f
v %(XI,
-
*..i xp,
%p)
v
(Ey)(y=x, & ... & y=x,))
and (ii)
(XI) * . *
(x*)(Y)(B(%, 5 ,z,) v ... v B(x,, 5 ,xp)v v B(x,, ... xp,y) v y = z l v ... v y=x,). * a * ,
* a * ,
)
The wffs (i) and (ii) are not in prenex normal form. After having rewritten the bound variables, we restore the prenex normal forms of (i) and (ii) in the following way. First, the universal quantifiers
29
ANOTHER CRITERION
of the disjunction terms of the form B(xl, ..., x,, b), which are not preceded in these wffs by existential quantifiers, are placed behind (x,) ... (x,) resp. (xl)...(x,)(y) in the order in which they occur in (i) ((ii)). Then, or a t once if no universal quantifiers of the abovementioned kind exist, the existential quantifiers of the wffs B(x,,. .., x,, b) now not preceded in these wffs by universal ones, are placed behind the quantifiers already in correct posit,ion, but only in the number in which they occur in a single wff 8 ( x l ,..., x,, b). This can be done by use of the equivalence between
( E ~ l ) ( w vl )(Ez2)62(z2)v
***
" (EQ&J(z*) and (Ez,)(&,(x,)v
***
v
e&))
which is a consequence of E7 of 111, Q 2. With the new wff we repeat the procedure until all the quantifiers of the wffs B(x,, ..., x,, b) are placed at the beginning of the wff. (ii) is then in prenex normal form. I n (i), as a last step, the quantifier (By)is placed so as t o conclude the prefix. The prenex normal forms of (i) and (ii) have fewer existential quantifiers preceding the universal ones ones than ai, while the tot'al number of existential quantifiers has not increased. As an example we construct the reduced formula of The two formulas (ii) and (i) are here
-
and
-
(x)(y)((z)(x=z& x = x ) v (z)(y=x & y=z) v y=x)
-
-
( x ) ( ( z ) ( x = x& x = z ) v (Ey)(y=x)).
Their prenex normal forms are
-
(x)(y)(z)(u)((x=x:& x = z ) v ( y = x and
82
-
y = u ) v y=x)
- -
(x )(z)(E y )((x =& x x - 2 ) v y=x).
Bringing the matrix of the first of the last two formulas into conjunctive normal form yields
-
( x ) ( y ) ( z ) ( x = xv y = x & x = x v y = x )
30
DECISION PROBLEM FOR EQUALITY FORMULAS
and
*(x)(y)(x=xv y=x & y = x )
as its reduced form. The second of the two formulas is further transformed into
- -
and
- -
( x ) ( z ) ( ( ( z =&x x = z ) v x=x) v ((x=x & x = z ) v Z ' X ) )
- - -
( x ) ( z ) ( x = zv x = x v z = x )
if the matrix is brought into conjunctive form. The reduced - - normalformula of the last wff is (z)(z==z v z = z ) , or ( z ) ( z = z ) . The reduced formula of (x)(Ey)(z)(y=x & y = z ) is therefore the conjunction of the last formula and of *. The construction of the reduced formula can be abbreviated by replacing in some wffs a prime formula of the form a=a by T , and by eliminating T after the methods of 11, 5 3. For instance, when treating the previous example, the first two formulas (ii) and (i) are and
(z)(y)((z)(T & Z = Z ) v ( z ) ( ~ = x . Y&= Z ) v Y = X ) (x)((z)(T =2) v (Ey)y = 4
which by elimination of T become
-
-
-
-
(x)(y)((z)x=zv (z)(y=x & y = z ) vy-x) and ( x ) ( ( z ) x = zv (Ey)y=x). The two prenex normal forms are
-
-
- -
( x ) ( y ) ( z ) ( u ) ( z = z ~ ( y =&z y = u ) v y = s ) and (x)(z)(Ey)(x=zvy=x). The reduced form of the first wff is (y)(z)(y=z). The second wff is transformed again into (z)(z=z). The reduced formula of (z)(Ey)(z)(y=x& y = z ) is now I n order to make use of the asserted relation between an equality formula and its reduced formula for the decision problem, we must know the conditions under which a reduced formula is universally valid. A reduced formula & . . & 9lk is universally valid if each
.
ANOTHER CRITERION
31
conjunction term is universally valid. A conjunction term such as is universally valid, if and only if every conjunction term of its matrix contains a disjunction term of the form a=a. Otherwise, there wouldbe a conjunction term which is a disjunction of terms of the form a = a and b = c only where c and b are different variables. If we take a domain in which there are as many elements as different variables in this conjunction term, and if we assign to each variable an element of the domain, but different elements to different variables; then this conjunction term, and consequently the reduced formula, would get the value P. On the other hand, it is obvious that 21i is universally valid under the above conditions, since x = x is universally valid. Example : The wff (x)(Ey)(z)(y=x & y = z ) is not universally valid, since its reduced formula is not. Now for the proof of the criterion. We have to show that each transformation 1) through 4) of a wff into another wff satisfies the condition that the two formulas are both universally valid, or both not universally valid. For 1) this is clear, since 1) is an equivalence transformation. This is the case too for 2). If the equality formula (Ex)%(x),where %(x) contains no free variables other than x, is true in a domain D,there is an element a of D such that %(a)is true; %(b) is then true for every other element b of D (see the second theorem in 9 1 of this chapter). This means that (x)%(x) is true in D.On the other hand, it is obvious that (Ex)%(x)is true in a domain D if (x)cLl(x)is. The other transformations are no equivalence transformations. (Ey,)* . * (Eyn)(B(a,,. ..,a,,al?Y2,... J n ) v * * v 'B(a1,...,a,,% yz, * *. ,yJ) may be true in a domain D for certain elements a,, ..., up of that domain. There is then an element b, namely one of the elements a,, ..., up,such that (Ey,) ... (Ey,)'B(a,, ..., a,, b, y,, ..., yn), and con... (Eyn)B(a1,..., a,, y,, y,, ..., yn), are true in sequently (EyJ(Ey,) D.On the other hand, (x,)... ( x p ) ( E y l ... ) (Ey,)'B(x,, ...,xp,y,, ..., yn) may be universally valid. Let a,, ..., up be an arbitrary set of elements, not necessarily all different, taken from some domain D. Since the wff is universally valid, it is valid in the domain consisting only of the elements a,, ..., a,. This means that there may be found
ai
-
32
DECISION PROBLED5 FOR EQUALITY FORMULAS
elements b,, ..., b, in that domain such that %(al, ..., up,b,, ..., b,) is true in the domain. The last formula is true in any other domain containing the elements a,, ..., a,, for the valuation of this formula depends only upon the relation of equality between a,, ...,a,, b,, ...,bn. Since b, is one of the elements a,,: ..., up, and
%(a,, ...)ap,a,, bz,
(Eyz)
-..)bn) v ..* v %(a,, *-*,a,,a,,
(Eym)(B(al, a,, ~ 2 ...> , yn) v %(a,, .-.,a,, a,, YZ, - - * ) yn))
b,, -.*, bn) *.*
v
are true in any such domain. This means that
x,, ~ 1 ~, 2 , y), v ... v (Ey,)(%(x,, v %(%!..., z, x,, yz, *.-, Y,)) is universally valid. Let (xl)... (x,)(Ey)%(x,, ..., x,, y) be a wff which has the structure described in transformation 4) and which is universally valid. I n any domain D containing the elements a,, ..., a,, there is an element b such that @(al,..., a,, b ) is true. Either b is one of the elements a,, ..., a, or it is different from all these elements; in the second case, %(a,, ..., a,, c) is true for any element G different from a,, ..., up (see the second theorem of 5 1 of this chapter). Therefore, (XI)
***
(xp)(Eyz)
a * * ,
is true, and
(.a)
%(a,,
..., a,,
a,) v
... v %(a,, ...)a,, a,) c=a, v ... v C'U,
v %(a,,
...,a,,
c) v
v
is true for an arbitrary c. This means that
-
(XI) * * . (x,)(%(xl? *"> xp,
and
.*.
- ...
v %(xl,
j
29,
xi) v
... & y=xp)) (XI)... (xp)(y)(%(xl, x,, 21) v '.. v B(x1, x*, 2,) v v %(x,, ...)x,, y) v y = x l v ... v y=xp) v
(Ey)(y=x, & .*.,
are universally valid.
'*.,
ANOTHER CRITERION
33
On the other hand, let the last two wffs be universally valid and further, let a,, ..., a, be elements of some domain D ;then there is an element b such that ( a )is true in D,and suchthat ( a m ) is true if in that formula c is replaced by b. If b is identical with one of the elements a,, ..., a,, then B(a,, ..., a,, b ) is true, since ( a ) is; if b is different from a,, ..., a,, then, since (aa) is true, one of the wffs %(a,, ..., a,, u,),..., %($, ..., a,, a,), '%(a,, ..., a,,, b ) is true. At any rate, (Ey)%(a,, ..., a,, y) is true. This means that (z,)... (z,)(Ey) '%(zl, ...,xg,y) is universally valid. Thus, a11 the transformations 1) through 4) have been shown to have the asserted property. The argumentation of this 5 2 would also show the completeness of any axiomatic system for universally valid equality formulas by which the reduced formulas having this property are deducible and which contains the inverses of the transformation rules 1)-4) as primitive or derived deduction rules.
IV SOLUTION OF THE DECISION PROBLEM FOR WELLFORMED FORMULAS CONTAINING ONLY MONADIC PREDICATE VARIABLES I n this chapter we consider wffs which have only prime formulas of the form a = b and Ula, from which n-adic predicate variables are excluded if n 2 . The possibility of decision in this case as well as in the previousIy treated case of the equality formulas, was first recognized by L. Lowenheim [l]. Simpler proofs have been given by Th. Skolem [l] and by H. Behmann [l]. The method used by all of them consists in transforming a wff into an equivalent one from which the predicate variables have been eliminated. The three authors could make use of the preparatory work of E. Schroder in the first and second volume of his “Algebra der Logik”. A representation of the method used by H. Behmann is to be found in D. Hilbert and P. Bernays [I], I, pp. 146ff). More recent modifications of the methods (see W. V. Quine [l], G. H. von Wright [l], D. Hilbert and W. Ackermann [l], pp. 4143) treat the more special case in which bound quantifiers for predicate variables and the sign of equality do not occur in the wffs; then the decision method can be simplified. The first mentioned three papers solve the problem in full generality.
>
1. Solution of the form I1 of the decision problem for wffs which do not contain bound predicate variables and the sign of equality I n the solution given here, use is made of the valuation of a wff in finite domains. The free monadic predicate variables occurring in a given wff may be of the number k. We prove the following theorem : If the wfl i s valid in a domain with 2k or more elements, it i s universally valid. We first establish a lemma, which will also be used in later sections
SOLUTION OF THE FORM I1 FOR WFFS
35
and the validity of which is not restricted to wffs with only monadic predicate variables. Let %(x,, ..., xm,G,, ...,Gk)(m 3 0 ) be a wff without bound predicate variables and without the sign of equality containing the free individual variables x,, ..., x, and the free predicate variables (not necessarily monadic ones) G,, ..., Gk.D and D’ may be two domains such that D has a cardinal number which is greater than, or equal to, that of D‘.An assignment a,, ..., a,, !PI, ..., yk for the free variables of % in D is called an extension of an assignment a;, ..., a;, !Pi, ..., YL in D’provided the following conditions are fulfilled : (1) To every element b of D there corresponds in a unique way an element b‘ of D’,and every element of D’corresponds to some element of D.(2) The elements corresponding to a,, ..., a, are respectively a;, ..., a;. (3) The ordered pair (a’, b’) of D’corresponds to the ordered pair (a, b ) of D and so forth. (4)For any i, Yi is true (false) for an element of D (for an ordered n-tuple of elements of D)if Yi is true (false) for the corresponding element (the corresponding n-tuple of D’). Our assertion is: %(al, ..., a,, Y,, ..., yk) is true in D,if and only if %(a;, ..., ah, Yl;, ..., Y;) is true in D’. We prove this by induction on the total number of logical constants and quantifiers occurring in %. The assertion is evident for prime formulas, since prime formulas of the form a = b do not occur. Otherwise, % has one of the forms B, 8 & &, $‘3 v &, (Ey)B(y) or (y)B(y). I n the first three cases, the assertion obviously is true for % if it holds for B (Band 0). If (Ey)B(y,a,, ..., a,, Y,, ..., yk)is true in D,there is an element b of D such that B(b, a,, ..., a,, Y,, ..., yk) is true; then, as ‘8 has less quantifiers than %, B(b‘,a;, ..., ak7!Pi7..., Yi) is true in D‘,and therefore,
(Ey)B(y,a;, *..,a;, Y ; , ..., YL) is true. If (Ey)B(y,a;, ..., a;, Yl;, ..., YL) is true in D’, then there is an element b’ of D‘ such that B(b’, a;, ..., a;, Yl;, ..., !Pi) is true. If b is an element of D such that b‘ corresponds to b, B(b, a,, ..., a,, Y,, ..., Yk), and therefore, (Ey)%(y,a,, ..., a,, Y,, ..., Yk) are true in D. If (y)B(y, a,, ..., a,, Y,, ..., Y,) is true
36
DECISION PROBLEM FOR m L L - F O E M E D FORMULAS
(false) in D,then (y)B(y,a;, ..., a;, !Pi, ..., Pi)is true (false) in D', since these two formulas have the same truth-value as the negations ..., Yk) and (Ey)'B(y, a;, ..., a;, Yi, ..., of (Ey)B(y,%, ...) a,, Y1, This completes our induction and the proof of our lemma. Let %(x,, ..., x,, G,, ..., Gk)have the same meaning as in the lemma except that the predicate variables G,, ..., Gk are all monadic ones. Further, let D,be a domain with 2k or more elements in which % may be valid and let D,be some other domain in which monadic propositional functions Y,, ..., Yk are defined. We divide D, into several classes. Two elements a and b of D, are said to belong to have the same values; the same class if for all i, Y&) and Y$(b) otherwise they belong to different classes. The number of classes of D,is at most 2k. We now construct a subdomain 0,of D, consisting of just one element of each class. To every element of D, we let correspond the element of 0,belonging to the same class. We define propositional functions ..., in 0,which have the same value for elements of D, as the functions !P, ..., Yk.If a,, ..., a, are arbitrary elements of D, and a;, ..., a; the corresponding elements of D,,then the assignment a,, ..., a,, Y,, ..., Yk in D,is an extension of the assignment a;, ..., a;, ..., !PL in D,. According to our lemma, %(a,, ...)a,, Y,, ..., Yk) is true in D, if %(a;, ..., a;, !Pi) ..., Y;) is in D,. Since D, has at least as many elements as D,,we can let an element of D, correspond in a unique way to each element of D, and have elements a;, ..., a: of D, and propositional functions Y:) ...)YL over that domain such that a;, ..., a;, Y:, ..., YL is an extension of a;, ..., a;, !Pi, ..., Yi. Since %(x,, ..., x,, G,, ...,G,) is valid in D,,%(a:, ...,a;) !P:) ..., Y;) is true in D,.According to our lemma, %(a;,..., a;, !Pi, ..., YL) is true in D,, and so %(a,, ..., a,, Y,, ..., Yk) is true in D,.Because a,, ..., a,, Y,, ..., Yk were arbitrary, %(x,, ..., x,, G,, ..., Gk) is valid in D,,and thus our theorem has been proved. By the theorem we obtain a decision procedure for the wffs in question. A wfj with k free monadic predicate variables is zsniversally valid if it is valid in a domain with 2k elements. I f it i s not valid in such a domain, it cannot be valid in a domain with more than 2k elements. I n order to obtain in the last case a complete solution of
ELIMINATION THEOREMS
37
the form II of the decision problem, the validity in domains with 1, 2, ..., k-1 elements has to be determined.
Elimination theorems The solution of the decision problem for wffs with bound predicate variables is obtained, as will be seen in 5 3, by eliminating these predicate variables from the wff. The following elimination theorem is sufficient for this purpose. E23. Let %(x) and %(x) be wgs (also with dyadic predicate variables, etc.) not containing the predicate variable G. (EG)(x)(%(x) v v G z & %(z) v &) i s then equivalent to ( x ) ( % ( xv) %(x)); likewise, ( G ) ( E x ) ( ( % ( x&) G x ) v (%(x) &G)) i s equivalent to ( E x ) ( % ( x&%(x)). ) The case when % or 23 do not contuin the free variable x i s included if vacuous quuntifiers are not written. Indeed, if (EG)(x)(%(x) v Gx & %(x) v G )is true in a domain D, or if it is true by an assignment for its free variables if such occur, there is a propositional function Y such that %(a)v Y(a)& m(a)v Y ( a ) is true for every element -a of the domain by the given assignment. Because Y ( a ) and Y ( a ) cannot both be true, %(a)or %(a), i.e. % ( a )v %(a) is true. Since a was arbitrary, ( x ) ( % ( xv) %(x)) is true by the given assignment. If the last formula is true in D by an assignment for its free variables, we define a propositional function Y relative to this assignment such that for every a of D,Y ( a )is true if %(a)is true by the assignment; then (x)(%(x)v Y ( x )& %(x) v only v Y ( x ) ) is true by the assignment and so is (EG)(x)(%(x) vGx & & %(z) v &). The second equivalence is a consequence of the first one; ( G ) ( E x ) ( ( % (x&) Gx) -v (B(x) - &&)) can be given the ( E G ) ( z ) ( % ( z v ) Gx & %(x) v G z ) which is equivalent equivalent form - again to ( x ) ( % ( xv) %(x)) and to ( E X ) ( % ( & ~ )%(x)). Similar theorems not needed for the solution of the decision problem treated in this chapter may be stated for dyadic, triadic, ... predicate variables such as, for instance, a theorem about the y ) v Gxy & %(x, y) v K y ) and equivalence between (EG)(x)(y)(%(x, ( z ) ( y ) ( 8 ( xy)%(x, , Y ) ) , or between ( G ) ( E ~ ) ( E Y ) ( (YW) , GXY) v (%(x, y) & Gxy)) and ( E x ) ( E y ) ( % ( xy) , & @(z,y ) ) . The proof is similar to that of E23. 2.
”
38
DECISION PROBLEM FOR WELL-FORMED FORMULAS
Setting aside the actual purpose of this chapter, elimination theorems may be generally of some use. Besides giving the solution of the decision problem in certain special cases they may also sometimes simplify a wff so that the solution of the decision problem, to be obtained by other methods, is more easily reached. Studies on the elimination problem are to be found in the third volume of Schroder’s “Algebra der Logik” and with W. Ackermann [2, 31. We mention only the following theorems taken from the last cited paper, which are a generalisation of E23 and the corresponding theorems for dyadic, etc. predicate variables. E24. %(x,G x ) may be a w 8 with the free individual variable x , the free monadic predicate variable G and possibly other free variables. The prime f o r m u h of % containing G m y be all of the form Gx. (EG)(x)%(x,Gx) is then equivalent to
( x ) ( E Y ) % ( xY , ) , and (G)(JW%(X,a x ) i s equivalent to ( E x ) ( Y ) % ( x ,Y ) ,where Y i s a propositional variable. E23 is a consequence of E24. For (EG)(x)(%(x)vGx &B(x)v&) may be replaced by ( x ) ( E Y ) ( % ( xv) Y & % ( x ) v P), which according to 11, 6 3 may be replaced by the equivalent S-formula
( x ) ( ( % ( xv) T & B(x) v
r)v (%(x)v F & B ( X )v p ) ) . a(%)).
The last formula reduces to ( x ) ( % ( x v) For the proof we may replace ( x ) ( E Y ) % ( x ,Y ) by the equivalent 8-formula (x)(%(x,T ) v %(x, F ) ) .If IV is a propositional function in a domain D which is true (false) by a given assignment for any element a of this domain provided that %(a,T)respectively %(a,T ) & (%(a,F ) ) is true, then %(a,T ) v %(a,F ) and %(a, P ( a ) ) have the same value for any a by the given assignment. Prom this the equivalence is immediately derived. E25. Let %Jx, Gxy) be a wfl with the free variables x and G and possibly other free variables. Let the prime formulas o f % containing G be all of the form Gxa, where a is or i s not identical with x . Let %Jx, H y ) be the wfl resulting from the previous one by replacing each prime formula Gxa by Ha. H does not occur in %,(x,Gxy). Under these conditions (EG)(x)%,(x,Gxy) and ( X ) ( E H ) % ~H ( Xy ,) , as well as
39
ELIMINATION THEOREMS
(G)(Ez)%,(x,Gzy) and (Ex)(H)'2lV(z, H y ) , are equivalent wfls. An analogous theorem holds for wfls %,(x, Gyx). By application of this theorem a bound dyadic predicate variable is changed to a monadic one. Similar theorems concern the replacement of a bound triadic predicate variable by a dyadic predicate variable, and so forth. If (EG)(z)%Jx,Gxy) is true by an assignment in a domain D, then there is a dyadic propositional function Y such that for any a , %,(a, P ( a , y)) is true by this assignment. For any a, there is a monadic propositional function @a for which @Jb) has the same value as !$(a', b ) for an7 b. %Ja, QP,(y))is true by the given assignment; this may be proved by induction on the structure of the wff. Therefore, (EH)%,(a,H y ) is true for any a. This means that (z)(EB)%Jz, By) is true by the assignment. On the other hand, let (x)(EH)%,(x,Hy) be true by some assignment ; for every a, there is then a monadic propositional function r such that %,(a, I'y) is true. We select one such r for each a, which we shall designate by @a. Let Y be the dyadic propositional function such that for any a and b, @Jb) and P(a, b ) have the same value. Since %*(a, @,(y)) is true for any a , so is %&u, Y ( u ,y)), which can be demonstrated in a simple manner by induction on the structure of a. This proves G z y ) is true by the given assignment. that (EG)(x)%&s, We illustrate the elimination of monadic predicate variables by carrying it out with the help of the wff
-
-
- -
( x ) ( E G ) ( ( E y ) ( x =& y Gy) & ( E z ) ( u ) ( ~ =&z Z = U vGu)). We place (Ey) and ( E x ) at the beginning and change the succession of ( E G ) , (Ey) and (Ex). The formula
-
- - -
( z ) ( E y ) ( E z ) ( E G ) ( x =& y Gy & ( u ) ( z = z& Z = U v Gu)) is equivalent to ( x ) ( E y ) ( E z ) ( E G ) ( Z& y Gy & = zx & G) by El4 and El7 of 11, 3 2. By El9 and E l 0 we may write
- -
(z)(Ey)(E~)(x= & yX = Z & (EG)(Gy&CZ)).
a)
-
- -
(EG)(Gy & is replaced by ( E G ) ( u ) ( u =y v Gu & u =z v Gu) according to E17. By E23, this is equivalent to ( u ) ( u = y v u = z )
40
D E C I S I O N PRO B L E M FOR WELL-FORMED FORMULAS
-
which, by making use of E17, be simplified to y=z. The -may equality formula ( x ) ( E y ) ( E z ) (=z y & z = z & y = z ) is therefore equivalent to the wff from which we started. We give another example for the reduction of a dyadic predicate variable to a monadic one. The wff
-
( G ) ( E H ) ( ( x ) ( E ~ ) ( z )v( GX & H X Z )& - - z = ~& Y = Z v Gz & ( ~ ) ( E v ) ( w ) ( uv =v GV & v = w v GV v Huw)) is equivalent to
( G ) ( E H ) ( x ) ( ( E y ) ( z ) v( G Gx & y=z v?% & H z z ) & - & (Ev)(w)(x = v v GV & v = w v GV v H x w ) ) , according to E8 of 11, $ 2. Applying E25 we get
( G ) ( z ) ( E H ) ( ( E y ) ( z ) ( S =v yGx & y = z v G & H z ) & - & ( E v ) ( w ) ( x = v v G v& u = w v G v v H w ) ) . There is a case in which an arbitrary bound predicate variable may be eliminated and not only replaced by another such variable. E26. Let b ( G ) be a w8 which contains the free predicate variable G, but no bound variables at all. W e can produce W ~ which S are equivalent to (EG)%(Gjand to (G)%(G)and which contain no bound variables. If %(G ) contains only existential (universal qwtntifiers) which do not stand under a negation-bar, (EG)%(G)and (G)%(G)are equivalent to a wg from which the bound variable G i s eliminated. The second part of the assertion is included in the first part, for the quantifiers of %(G) may be placed outside the scope of (EG)((G)).It is irrelevant for the theorem whether G is a monadic, triadic, ... variable. It will be sufficient to show this for a dyadic predicate variable, since the procedure in the other cases is analogous. We bring %(G) into the disjunctive normal form %,(G) v ... v ak(G).By E7 of 11, 5 2 (EG)%(G)is equivalent to (EG)%,(G) v ... v (EG)ak(G).Each conjunction term of a $(G) containing G has the form Gab or G X . By using E l 9 and by contracting the scope of ( E G ) in a wff (EG)'?Zli(G)according to E9 and E l 0 so as to exclude all conjunction
41
GENERAL SOLUTION
terms not containing G, the scope of (EG) receives the form Gal
bl &
... & Ga,
b, & GC1 b1 &
...
GCn bn.
By applying El7 of 11, Q 2, we may write
- -
(EG)(x)(y)(x=alvy=blvGxy &
- - -
--
...&x=a,vy=b,vGzy - -
&
& X = C , V ~ = ~ , V C X&~... & ~ = c , v y = b ~ v G ~ y ) ,
provided that x and y are not among the variables al, According to E21, the last wff is equivalent to
- -
(EG)(x)(y)(x=a,vy=b, &
--
- -
... &z=a,vy=b,)
- - -
..., b,.
vGxy &
& ( ~ = c ~ v y = b &... , &~=c,vy=b~)~G~y)
which again according to E23, is equivalent to
--
- - - -
... & z=a, v y=bm) & ... &z=c,vy=b,)
(x)(y)(z=a, v y=bl &
v (z=c, v y=bl &
I n the last wff the individual quantifiers (2) and (y) can be eliminated by El7 after the matrix of the wff has been brought into conjunctive normal form. The elimination of (G) in (G)a(G) is a consequence of the elimination of (EG), for (G)rZT(G) is equivalent to (EG)B(G).
General solution of the decision problem for wffs with only monadic predicate variables The general solution of the decision problem for the wffs dealt with in this chapter is obtained by transforming a wlT which we can suppose to contain only bound predicate variables into an equivalent equality formula. I n our exposition we follow Behmann and partly, Hilbert and Bernays. Subsequently we shall have to do with wffs 3.
(Ex)fl(x), - (-w(Ey)(z=y - - a(4 a(Y)), ( E z ) ( E ~ ) ( E z ) ( z&=X~= Z & Y = Z & a ( ~ & ) a ( ~&)a(~)), ... (with wffs ( W w x ) , ( E y ) ( x ) ( s = yv W4), ( E y ) ( E z ) ( x ) ( x =vy 2 = z v %(x)), ...).
42
DECISION PROBLEM FOR W E L L - F O R M E D FORMULAS
For these wffs, we use the abbreviations
(E,s)%(4,(
~ 2 4 9 w 7(E34%(347
*. * 7
((1@w> (24%(4, ( 3 4 W 4 ,
...,1
which were introduced by Hilbert and Bernays. Generally, (E,x)%(x) is a wff with the prefix (Ex,) ... (Ex,),whose matrix is the conjunction of all terms x4 =x, ( i < k ) and of all terms %(x,), ..., %(x,). (x,+,)%(x) has the prefix (Ex,) ... (Exm)(y);the matrix is the disjunction of %(y) and of all terms y = x i . The abbreviations (E,x)%(s) and (,x)%(x) are used also for wffs resulting from the wffs above by rewriting the variables or by changing the succession of the conjunction (disjunction) terms or by replacing the terms a= b or a= b by b = a or b = a. (E,x)%(z) is true by an assignment in a domain, if and only if there are at least m different elements a,, ..., a, of that domain such that %(u,), ..., %(a,) are all true. (,x)%(x) is true by an assignment, if and only if there are at most m-1 different elements a,, ..., a,-, in the domain such that %(a,), ..., %(urn-,)are all false.Therefore, (,x)%(x) and (E,z)%(x) as well as (E,x)%(x) and (,x)%(x) are equivalent wffs. We prove three lemmas. Lemma 1 . %(x) may be a wff with the free variable x, but without the variables yk and without any bound variable. - y,, ..., (E,x)(%(x)& x= y, & ... & x= yk) can be transformed into an equivalent wff which has only existential quantifiers and in which the variables y,, ..., yk do not occur in the scopes of quantifiers. The existential quantifiers do not stand under a negation-bar. The new wff has no free variables other than the first one. The lemma is proved by induction on k. If k is 0, the wff already has the desired form. The reduction of k+ 1 to k is achieved by use of the equivalence between and (Em+lx)(%(x)
(E,x)(%(x)
-
8L
-
& x=yk+,)
x=y1 &
- -
"
x=Yl 8L * * * 8& x = Y k ) (%(Yk+l) & x = y, & ... & x=yk)).
(Emx)(fl(x)
8Z
The two wffs are recognized as equivalent in the following way. If there are at least m different elements a of a domain D for which
GENERAL SOLUTION
43
%(a) is true and which are all different from certain elements b,, ..., bk+,, then a(&+,)is either true or false; in the first case, there are m+ 1 elements for which % is true and which are different from b,, ..., bk ; in the second case, %(bk+l) is false and there are of course still m different elements and these elements are different also from b l , A k , for which % is true. On the other hand, if (E,+,)(%(z) & & x=y, & ... & x=y,) is true by an assignment, m of the m + 1 elements for which % is true must be different from the elements assigned to Y k + l . If %(yk+J& (E,x)(%(x) & x = y l & ... & z=yJ is true by an assignment, the element assigned to yk+, is different from all the elements for which % is true, since %(a,) and %(a) cannot both be true for the same a. Lemma 2 . Let %(x),y,, ..., yk have the same meaning as with lemma 1 ; then (,&)(%(x) v x=y, v ... v x'&) can be transformed into an equivalent wff in which the variables yl,..., yk do not appear in the scope of a quantifier and in which the quantifiers appear only in groups of the form (Ea,) ... (E&)(b), the scopes of (Ea,), ..., (Ea,), (b) extending to the same point in the formula. Further, no quantifier stands under a negation-bar and the new wff has no free variables other than those which appear free in the old wff. The scopes of the different groups of quantifiers do not overlap. This is again proved by induction on k. The reduction of the case for k+ 1 to that for k is accomplished by making use of the equivalence between (,x)(%(x) v x=yl v ... v X = y k f l ) and (m+14(%I(X) v x=y, v v z=yJC) & %(Yk+l) v (;4(%(4v v x=y1 v ... v z=y& This equivalence is a consequence of that used in the proof of lemma 1 ; for ifwe take the negations of the two wffs and observe that (,x)%(z), a & ' $ 3, a v '$3, a n d q are respectively equivalent to - _ (Em~)%% (~v)'2,3, % & and a, the equivalence becomes that of lemma if %(x) is substituted for a(x). I n the following, the two lemmas are used only for m= 1, but for the proof it is necessary to state them for an arbitrary m.
a
44
D E C I S I O N PRO B L E M FO R WE L L -FO RM ED F OR MU LA S
Lemma 3 . For any wff without bound predicate variables we can construct an equivalent wff having the following properties : (1) All existential quantifiers are placed at the beginning of the formula with scopes extending to the end of the formula. (2) The scope of each universal quantifier is a disjunction of negated or nonnegated prime formulas and does not contain free individual variables except that of the quantifier. (3) No quantifier stands under a negation-bar. (The case that there are no universal or no existential quantifiers is included.) Let 8 be a wff in which the negation-bar stands only over prime formulas and which contains no bound predicate variables. There may be quantifiers initially placed in 8 with scopes extending to the end of the formula. Let p be the number of these quantifiers, provided we do not count the existential quantifiers which are preceeded by no universal quantifier. To have a short expression we will call these p quantifiers the essential quantifiers. Besides these initially placed quantifiers, there are only universal quantifiers the scopes of which have the structure described in the lemma. If the number p is one or greater, we shall construct an equivalent wf€ of the same character for which p is less. This construction suffices to prove the lemma. For any wff can be given a prenex normal form with the properties of 8. We distinguish two cases. 1) The last of the essential quantifiers is an existential one. Let (Ex)be this quantifier and B(x) its scope. We bring B(x) into a disjunctive normal form B1(X)
v
... v BJX)
v
9,v ... v %*,
where the wffs %imay not contain the variable x. We transform (Ex)B(x) into the equivalent form
(Ex)B,(x) v ... v (Ex)Bm(x)v SD,
v
... v TI*,
-
Each BJx) is a conjunction of formulas of the forms b = c, b = c, Ulb, F b , (c)SD(c). The variables b and c may, or may not, be the same as x. We now contract, if possible, the scope of (Ex)in each (Ex)Bi(x)by excluding from it all conjunction terms not containing
45
GENERAL SOLUTION
the variable x. This can be done by changing the succession of the conjunction terms and by use of the equivalences E9 and E l 0 of 11, Q 2. No conjunction term with universal quantifiers then occurs in the scope of ( E x ) ,for these terms were supposed not to contain the variable x. &(x) may be the new scope of (Ex). If $(x) has a conjunction term of the form x = b or b=x, where b is different from x, we then replace (Ex)$(x) by &(b) according t o El8 of 11, Q 2, and the transformation of (Ex)&(x)is finished. If this is not the case, (Ex)$(x) has a form (Ex)(x=b,& ... & s=b,& (I!(.)) ( m >, 0 ) , where b,, ..., b , are variables belonging to the left p-1 essential quantifiers and where @(z)is free from such variables. If m >, 1, we replace (Ex)$(%) according to lemma 1 by a wff with only existential quantifiers not standing under a negation-bar, the variables b,, ..., b, not appearing in the scope of a quantifier. After this transformation has been effected with each (Ex)$(x) and after rewriting bound variables, we place all the existential quantifiers occurring in the transformed formulas (Ez)&(x)immediately before the left essential quantifiers in a, extending their scopes to the end of the formula. The new wff has fewer essential quantifiers. 2 ) Let the last of the essential quantifiers be (2) with the scope B(x). We proceed in a similar way. We bring @(x) into a conjunctive normal form
B1(x)& ... & BJx) & 9 1 &
1..
& 5DP
and write
(x)B,(x) &
... & (x)Bw(x)& 9,& ... & 5Dp
instead of (z)B(x).I n a formula (x)i&(z)we contract the scope of (2) so as to exclude any disjunction term not containing the variable x. Let (&(x) be the new scope of (2). If (&(x) has a disjunction term of the form x = b or b = x where b is a variable different from x, we replace ( x ) $ ( x ) by gi(b)according t o El7 of 11, Q 2 ; otherwise, (x)$(a) is of the form
( x ) ( z =b, v
... v x=b,
v
%(Z))
(WL>, 0))
46
DECISION PROBLEM FOR WELL-FORMED FORMULAS
where %(x) contains no free individual variables besides x. If 2 1, we replace (x)&.((x) according to lemma 2. We then put all the existential quantifiers of the transformed wffs (x)$(x) before the essential quantifiers of (21 after having rewritten the bound variables. The universal quantifiers appear now as they did at first in (21. Thus again (21 is reduced to an equivalent wff of the same character with fewer essential quantifiers. By applying this reduction p times, '% is transformed into a wff as described in the lemma. We now point out how to eliminate the bound predicate variables from a given wff. Let (EG)%(G)be a part of the wff such that a ( G ) contains no bound predicate variables. We give % ( a ) the form mentioned in lemma 3. Let (Exl) ... (Ex,)%(G, x,, ..., x,) be this form. In (EG)(Ex,) ... (Ex,,,)%(G, x, ..., x,,,), the quantifier ( E G ) can be placed behind (Ex,) (Ex,); then B ( G , x,, ..., xm) is brought into disjunctive normal form and the quantifier ( E G ) is placed before each of these disjunction terms if they contain G. This is done by applying E7, E l l , El2 of 11, $ 2. The scope of each ( E G ) is contracted so as to exclude all component parts not containing G. Let &(G) be such a contracted scope. &(G) is a conjunction of terms of the form Ga, Gb, ( c ) ( ~ ( cv)Gc) and (c)(%(c)v where and %(c)do not contain G.Theterms Ga and 6% are replaced by (c)(c=a vGc) (or by (c)(c=bvGc)). By applying ES of 11, $ 2, (EG)&(G) is transformed into a wff (EG)(c)%(c, Gc) where G occurs only in prime formulas of the form Gc. By E2fof $ 2 of this chapter, (EG)(c)%(c, Gc) is equivalent to ( c ) ( E X ) % ( cX). , From the last wff, the propositional quantifier can be eliminated according to 11, 5 3. This procedure is followed wherever (EG)appears. (EG)%(G,xl,..., z,,,is )thus transformed into a wff &(x,, ..., x,) without bound predicate variables. (EG)%(G)is equivalent to (Ex,) ... (Ex,,,)&(z,,..., x,,,). If we have a part (G)%(G)of the wff without bound predicate variables other than G, then this is replaced by the equivalent wff ( E G ) a ( G )and the G in (EG)Yl(G)is eliminated in the above described way. m
...
a), a(c)
G E N E R A L SOLUTION
47
By this method, the bound predicate variables of a wff can be eliminated successively until none is left. If the wff contains no free predicate variables, the result of the elimination is an equality formula. We therefore may state the theorem: A n y w# with bound monadic predicate variables but without any other predicate variable can be transformed into an equivalent equality formula. As the decision problem in the form I1 is solved for equality formulas, this holds too for the wffs considered in this chapter. Taking into consideration how the decision problem was solved for equality formulas, we see that the following statement holds not only for the special class of wffs treated in 5 1 of this chapter, but also for any wffs containing only monadic predicate variables. A n y wfl with only monadic predicate variables is either universally valid, or not valid in any domain, or valid only in a finite number of domains with a finite number of individuals, or valid in any domain with the exception of a finite number of finite domains.
V SOME GENERAL THEOREMS ABOUT THE VALIDITY OF FORMULAS O F THE PREDICATE CALCULUS O F FIRST ORDER INCLUDING EQUALITY Henceforth we shall only be concerned with the problem of validity for wffs in which the predicate variables appear only in a free form. These wffs are usually called the wfls of the predicate calculus of first order, or for short, the wfls of first order. With regard to our definition of validity we may also say that we shall be occupied only with the wffs which result from the wffs of fist order by placing the universal quantifiers for the predicate variables before those quantifiers with scopes extending over the whole wff of first order. The wffs with which we have to do, apart from those appearing in the proofs, are supposed to contain no free individual variables. For if they should occur, they may be bound by universal quantifiers.
1. Skolem’s normal form For proving general theorems about wffs of first order, it is convenient to make use of a special normal form, called the Skolem normal form (see Th. Skolem [2]). A Skolem normal form is a prenex normal form in which all existential quantifiers precede all universal ones. T I . For each wfl of first order, one can construct another in a Skolem normal form such that both formulas are valid in the same domains, or both not valid in any domain. We start from a wff in prenex normal form. We may assume that the prefix of the wff begins with an existential quantifier ; for if the wff, designated by %, begins with a universal quantifier, we replace 8 by the equivalent wff (Ex)(%& Gx v G),where x and G are supposed not to occur in % (see E22 of 111, 3 1). The last wff
SKOLEM'S
NORMAL FORM
49
can be brought into prenex normal form in a way such that (Ex) is the first quantifier of the prefix. Our wff thus begins with n existential quantifiers (n 1). By the degree of such a formula, we understand the number of universal quantifiers preceding at least one existential quantifier. If the degree is 0, nothing remains to be proved; otherwise, there is a universal quantifier immediately succeeding the n existential quantifiers, and the wff has t.he form (j1
(Ex,) * * . (Exn)(y)%(x,,* * * > xn, Y)*
contains only the free individual variables x,, ..., x,, y and is in prenex normal form. Let H be a n+ 1-adic predicate variable and x an individual variable, both not occurring in 23. We show that the wff (jj) (Ex,) ... (Ex,)(Ez)((%(x,, ...,x,,~)8~Hx, ... xnz)v (y)Hx,...x,y) is valid in the same domains as (j). Let 9 be an arbitrary assignment for the predicate variables of (jj) with the exception of H . We define an n+ 1-adic proportional function Y in the relative domain D in the following way. For any elements a,, ..., a,, b of D the value of Y(a,, ..., a,, b ) is the same as that of @(a,, ..., a,, b ) by 9. Let now (jj) be valid in D.There are then elements a,, ..., a,,, c such that
(%(a,,
..., a,,
c) & Fa,
... a,, c) v (y)Ya, ... a, y
is true by 9. Since @(al,..., a,, c) and Ya, ... a, c get the same value by this assignment, %(a,, ..., a,, c) & Ya, ... a, c is false; consequently, (y)Ya, ... a, y is true. Owing to the definition of Y , this holds also for (y)%(a,, ..., a,, y). Since 9 was arbitrary, this means that ( j ) is valid. Let us now suppose (j) to be valid in a domain D. Let 9 be an arbitrary assignment for its predicate variables. There are then elements a,, ..., a, of D such that (y)'B(a,, ..., a,, y) is true by 9. Let Y be an arbitrary n+ 1-adic propositional function over D. Either (y)Ya, ... a, y is true, in which case (jj) is true by the assignment 9, Y ; or (y)Ya, ... a,, y is false, and then there is an
50
SO-
GENERAL THEOREMS
element c of D such that Y a , ... a,, c is true. Consequently, B(%,..., a,, c) & Y a , ... a, c is true by 9. Then (jj) is again true by 9, Y. (jj) is therefore valid in D also. We bring (jj) into prenex normal form. This can be done in a way such that the prefix begins with (Ex,)... (Ex,)(Ez), continues with the quantifiers of B(xl, ..., x,, z ) in unchanged succession and ends with the quantifier ( y ) . Obviously, the degree of this formula is lower by one than that of (j). By repeating this transformation we get a wff of degree 0.
Theorems about the validity of wffs not containing the sign of equality I n this 2, we restrict ourselves to wffs not containing the sign of equality. T I I . If a wfl which has no prime formulas of the form a = b is valid in a domain, it i s also valid in any domain containing a smaller number of elements. Let M(G,, ...,G,) be a wff valid in a domain Dl;let D, be a smaller domain. Further, let Y,, ..., Y,, be arbitrary propositional functions over D, suitable for assignments for G,, ..., G,. Since D, has more elements than D,, we can define propositional functions !Pi, ..., YA over D, which are an extension of !PI,..., Y,, as defined in the lemma of IV, Q 1. Because %(G,, ...,G,) is valid in D,, M(?Pi,..., ?Pi)is true in that domain. According to the mentioned lemma, '$ Yl,I( ..., Y,) is true in D, ; since Y,, ..., Y, were arbitrary, M(Gl, ..., G,) is valid in D,. We now prove a remarkable theorem which was first obtained by L. Lowenheim [I] and the proof of which was afterwards considerably simplified by Th. Skolem [2] through application of his normal form. This theorem reads as follows: T I I I . If a wfl i s valid in a denumerably infinite donzain and is also valid in every finite domain, then it i s universally valid. I n this formulation of the theorem, the supposition that the w f does not contain the sign of equality is not necessary, as will be seen by the proof. Let M be a wff valid in a denumerably infinite domain and also 2.
WEFS NOT CONTAINING THE SIGN O F EQUALITY
51
in every finite domain and we may assume also that it is in Skolem normal form. 8 has the form
(B%).*. (Ex )(y,) ... (y,)B(x,,
x,, Y,, .-*, y,);
B has no free individual variables besides xl, ..., x,, y,, ...,yn. Let D be an arbitrary non-empty domain and SZ an arbitrary assignment for the free predicate variables of % in D. We shall show that 8 is true by SZ in D.
We prove this in an indirect way. Let us suppose that % is false in D by SZ. We construct a sequence of finite subdomains of D, called D,, D,, D,, ..., with the following properties. Each Di is a subdomain of Di+,. D, consists of just one arbitrarily chosen element of D. If cl, ..., c, are elements of D i , there are always elements d,, ..., d, of D such that B(c,, ..., c,, d,, ..., d,) is false by 9 ;otherwise, % would be true by SZ. Then there is at least one m,-tuple c,, ..., c, of elements of Di such that the elements d,, ..., dn belonging to them are not all elements of Di. For if this were not the case, % could not be valid in the finite domain Di, contrary to our supposition. Di+l shall consist of all the elements of Diand of all the elements d,, ..., d,, pertaining to some m-tuple c,, ..., c, of elements of Di, in so far as these last elements are not already in Dd. D,+, has at least one element not contained in D i . Let D‘ be the domain containing any element of D which is an element of some Di. If c,, ..., c, is an arbitrziry m-tuple of elements of D’, there are always elements d,, ..., d, of D’ such that B(c,, ..., c,, 4,..., d,) is false by 52; for the elements $, ..., c, are all contained in some domain Di , and the elements d,, ..., d, can be found in Di+,. Then 8 cannot be valid in D’, and since D’ is a denumerably infinite domain, this is a contradiction; therefore 8 cannot be false in D by 9. Since SZ was arbitrary, 3 is valid in D. Combining TI1 and TI11 we have: T I V . A wfl which has no prime formulas of the form a = b is universally valid, if it i s valid in a denumerably infinite domain. If it i s not valid in such a domain, validity at most exists in finite domains.
52
S O M E GENERAL THEOREMS
3. Theorems about the validity of wffs which may contain the sign of equality The theorems pronounced in 4 2 do not all hold for any wffs in which the sign of equality occurs. TIII, it is true, remains in the general case, but not TI1 and TIV. Indeed, the wff (Ex)(Ey)(x=y) for instance, is valid in all domains with two or more elements, but not valid in a domain with one single element. The following theorem states a relation between a wff containing the equality sign and a certain other one without this sign. T V . T o every wfl 8 containing the sign of equality one can construct another one 93 not containing ihe sign of equality which has the following relation to a. If B is valid in a domain D, 8 i s valid in D. If 8 i s valid in a domain D and in all domains having a smaller cardinal number than D , '$3 is also valid in these domains. This theorem reduces the decision problem for wffs with prime formulas a = b to that for wffs without such prime formulas, but only if we restrict ourselves to the form I or the form I11 of the problem. For the two wffs 8 and B mentioned in TV are both universally valid or both not universally valid; likewise, they are both valid in every finite domain, or both not valid. The theorem TV may be of some value in proving general theorems about the validity of wffs. When solving special cases of the decision problem, even if only the forms I or I11 of the problem are considered, it is not of much use; for the wff '$3 mentioned in the theorem has more quantifiers than 8 and it has one dyadic predicate variable more. For instance, the decision problem for the wffs of the monadic predicate calculus with equality treated in 5 3 of the preceding chapter is not reduced to the problem for wffs of the monadic predicate calculus without equality. but to the problem for wffs containing one dyadic predicate variable besides the monadic ones. Let a ( G , = ) be a wff with the free triadic predicate variable G containing the equality sign, let 8 ( G , H ) be the wff resulting from %(G, = ) by replacing all prime formulas a = b by Hub. Lastly, let B(G, H ) be an abbreviation for (Ex)Hxxv (Ex)(Ey)(Ez)(Hxy & Hzy & Hzz) v ( E x ) ( E y ) ( E z ) ( E u ) (Hxy & (Gxzu & Gyzu) v (Gzxu & Gzyu) v (Gsux & Gzuy)) v %(G, H ) .
WFFS WHICH MAY CONTAIN THE SIGN OF EQUALITY
53
We shall prove that %(G, = ) and %(G, H ) are in the relation described in TV. Let %(a, H ) be valid in a domain D ; then @(G, = ) is valid in D. Since ( E x ) ( x = x ) , ( E x ) ( E y ) ( E z ) ( x =&y z=y & x = z ) ,
-
-
-
(EX)(E~)(EZ)(EU)(Z = ZJ&(GXZU& G ~ z u ) v ( G ~ xGZ~U)V(GZUX& u& Gzu~)) are fahe in D by any assignment for G, %(G, = ) is valid in D. Let %(G, = ) be valid in D and in all domains having a smaller cardinal number and further, let Y and @ be arbitrary propositional functions over D suitable for assignments to the predicate variables G and H of B(G, H ) . We want to show that B(Y, @) is true in D. This is only doubtful if
(Ex)=, (Ex)(Ey)(Ez)(@xy & @zy & G) and
-
(Ex)(Ey)(Ez)(Eu)(@xy & (Yxzu & Y y z u ) v
-
v (Yzxu & Y z y u ) v (Yzuz & Y z u y ) )
are all false. In this case 4j is reflexive; i.e. for all elements a of D @aa is true. @ is symmetric; i.e. if @ab is true, @ba is true. For @bb & @ub & =a is always false. @ is transitive; i.e. if @ab and
@bc are true, then @ac is true. We divide the domain D into several classes. Two elements a and b of D belong t o the same class if @ubis true; otherwise, they belong to different classes. If Yabc is true, Yu,b,c, is true, provided that a and a,, b and b,, c and c, belong to the same class; this follows because the disjunction term of %(Y,@) with the prefix
(J@4(Ey)(Ez)(EU) is false. Let D’ be a subdomain of D containing just one element of each class. To every element a of D we let correspond an element a’ of D’, namely the element a‘ belonging to the same class as a. In D’, we define two propositional functions @‘ and Y . For elements a‘, b‘, c’ of D‘ @‘a‘b‘(Ya‘b‘c’) is true, if and only if @a’b’(!Pa’b’c’) is true. Since D‘ contains just one element of each
54
SO=
UENERAL THEOREMS
class of D, @'arb'is true, if and only if a' and 6' are identical elements. On account of the stated properties of @ and !P) the set of propositional functions @, Y in D is an extension of the set @', ?P'in D' in the sense of the lemma of IV, Q 1. % ( Y = , ) is true in D' according to our supposition. Since a' = 6' and Pa'b' always have the same truth-value, % ( Y ,@') is true in D'. Applying the above-mentioned lemma, we recognize that %(Y, @) and therefore B(Y, @)) is true in D. Since Y and @ were arbitrary, B(G, H ) is valid in D and is valid in all domains with a smaller cardinal number according to TII. TV thus has been proven in case there is only one triadic predicate variable occurring in %. This restriction has been made only for the sake of a simpler presentation of the proof and is in no way essential. If there are more or other predicate variables in 8,the only change in the construction of B ' is that the disjunction term ( E x ) ( E y ) ( E z ) ( E u ) ( H x&y (Gxzu & Gyzu) v v (Gmu & Gzyu) v (Gzus & cfiuy))
-
is replaced by several disjunction terms. For every monadic predicate variable K there is a term ( E s ) ( E y ) ( H q& Ks & to be added, for every dyadic predicate variable L a term (Ex)(Ey)(Ez)(Hx& y (Lxz& L?) v (Lzx & Ax)) for,every triadic predicate variable a term of the form mentioned above, and so forth. The proof is given in the same way. For the wffs not containing the equality sign, the validity in any domain is known, provided this is so in finite and denumerably infinite domains. I n the general case, the theorems so far derived do not permit such conclusions. It is sufficient, of course, to determine the validity in finite and denumerably infinite domains, if we are interested in knowing only whether a wff is universally valid or not. But if a wff is not universally valid, the knowledge of the validity in finite and denumerably infinite domains, for the present, does not give information about the validity in other domains. To f?ll in this gap we prove the following two theorems.
6)
W F F S WHICH MAY CONTAIN THE SIGN OF EQUALITY
55
T V I . If a wfl is valid in a denumerably infinite domain, it is valid in any infinite domain. Let '21 be a wff which is valid in a denumerably infinite domain and which does not contain the predicate variables G and H . Znf(G, H ) shall be an abbreviation for (Ex)Gx & (z)(Ey)(& v H z y ) & ( z ) ( E y ) ( H y x& Gy) & - - - & ( ~ ) ( y ) ( z ) ( ( vHH~Xy Z& HYX v H Z S )v Y = z ) . Inf(G, H ) is satisfiable in all infinite domains, but not in any finite domain. For Inf(!P, @) is true in a domain D, if and only if there is a non-empty subdomain of D consisting of the elements for which !€'(a) is true such that the elements of this subdomain can be put into one-to-one correspondence with the elements of D by means of @. This is the definition of an infinite domain set up by R. Dedekind. Inf(G, H ) is valid in any finite domain, but not in an infinite domain. The wff Inf(G, H ) v '21 is valid in any finite domain and in a denumerably infinite domain and according to TIII, it is universally valid. Because Inf(G, H ) is not valid in an infinite domain, '21 is valid in any infinite domain. T V I I . If a wfl is valid in an infinite domain, it is valid in a denumerably infinite domain and there is a finite number k 5uch that the wfl i s valid in all finite dmain5 with k or more elements. The theorem, however, provides no way of determining this number k for a given wff. For the proof of the theorem we shall suppose that the elements of the infinite domain in question are the ordinals preceding a certain transfinite ordinal b ; such a domain will be designated by D,. This is equivalent to the assumption that the infinite domain can be well-ordered, for the elements of any well-ordered domain can be put into one-to-one correspondence with those of a certain domain D,. Ordered k-tuples (a,,..., ak)of ordinals can be well-ordered by a relation 2. The definition is: (q, ...,ak)2 (b,, ...,bk) if Max (a,, ... ...,ak) < Max (b,, ..., b k ) ; or Max (a,, ..., ak)=Max (b,, ...,bk) and a, < 6, ; or Max (al, ..., uk)= Max (b,, ..., bk),a, = 61 and a,
56
SOME GENERAL THEOREMS
Max (a,, ..., ak) is the element among a,, ..., a, which does not precede any other. We further define a function p for ordinals which assigns the ordinal p(%, ...,a,) to an m-tuple (a,, ..., a,) of ordinals and which depends on the number n. q~ is defined by transfinite induction. If 1 is the first ordinal, p( 1, ..., 1) is the nthsuccessor of 1. Let p be defined for all (a,, ..,, a,) with (a,, ..., a,) 2 (d,, ..., d,) and let e be the first ordinal succeeding all these ordinals qI(a,, ..., a,) ; p(d,, ..., d,) is then the nthsuccessor of e. Obviously, p(a,, ..., a,) >a, and p(al, ., a,) > p(b,, ..., b,) if (a,, ..., a,) 2 (b,, ..., b,). If every subdomain of an infinite domain D, consisting of the elements preceding a certain element has a cardinal number less than D,,then p(a,, ..., a,) is an element of D, if a,, ..., a, are elements of D,.This is shown by transfinite induction. Indeed, this is obvious for ~ ( 1..., , I), since D, cannot have a last element. It may be true for all m-tuples (a,, ..., a,) preceding a certain m-tuple (d,, .., d,). All these 'p(a,, ..., a,) precede a certain element of D,; for the set of these p(a,, ..., a,) has a lower cardinal number than D,and, according to a well-known theorem of set theory, the elements of any subset of D, which has a cardinal number less than D, must all precede a certain element of D,.Therefore, 'p(d,, ..., d,) is in D, also. ) ..., x,, yl,..., y,J be a wff Let '2i or ( E ~ ,...(~x~,)(y,)...(y,,)~(x,, in Skolem normal form. For the sake of a simple presentation of the proof we shall restrict ourselves to the case in which '2i contains only the dyadic - predicate variables G,, ..., G l . But this is of no consequence; 8 is equivalent to
..
.
Let $ beIa subdomain of a domain D,. is called partially satisif there are propositional functions fiable in D , with respect to Y,, ..., Y l in D, such that for arbitrary a,, ..., a, (but all taken from a),there are elements b,, ..., b,, of D,, all preceding or equal to p(a,, ..., a,), for which 8(a,, ..., a,, b,, ..., 6,) is false by Y,, ...,ul,. We now prove two lemmas.
WFFS WHICH MAY CONTAIN THE SIGN O F EQUALITY
57
Lemma 1 . Let @ be satisfiable in a denumerably infinite domain, or for every finite number p , let there be a finite domain with p or more elements such that @ is satisfiable in that domain. If f? is a finite subdomain of a domain D,,then @ is partially satisfiable in D, with respect to 2. The elements of $t may be d,, ..., dk, enumerated in their right order. There is a finite or denumerably infinite subdomain of D, containing the elements d,, ..., d, such that is satisfiable in that subdomain. There are then dyadic propositional functions Y, ..., Y, in D, and elements b,, ..., b, for every a,, ..., a, taken from the set (a,, ..., d k ) ,such that %(a,, ..., a,, b,, ..., 6,) is false by Y,, ...,Y r . For each m-tuple (a,, ..., a,) we select a special set bl, ..., b,. By a one-to-one correspondence of the elements of D,with themselves (the element d, corresponding to itself), we can find an assignment !Pi, ..., Yi of the aforesaid kind such that the elements b,, ..., b, belonging to (a,, ..., d,) are rp(d,, ..., dl). By a further one-to-one correspondence of the elements of D, by which all elements preceding or equal t o p(d,, ..., d,) and the element d, correspond to themselves, we get an assignment Y,; ..., !P; so that for every bi belonging to (a,, ..., d,, d2), bi y(d,, ..., d,, d2). This procedure is continued and after a finite number of steps we find an assignment for G,, ..., G , such that 8 is partially satisfiable in D, with respect to (al, ..., dk). Lemma 2 . Let 3 be partially satisfiable in D , with respect ' is satisfiable in D,. to any finite subdomain Z of D,;then % We shall assume that rp(a,, ..., a,) is always in D, if %, ..., a, are elements of D,. This is no restriction on the use of the lemma; for there is else a domain D,, with b ' < b which has the cardinal number of D, and is such that all proper subdomains D, of D,,have a cardinal number less than D,,. If 2 is the second element of D,,8 is partially satisfiable in D, with respect to any subdomain of D,consisting of the element < 2 and a finite number of other elements. Let d be an element of D, and let @ be partially satisfiable in D, with respect to any subdomain of D, consisting of the elements
<
<
58
SOME GENERAL THEOREMS
respect to any subdomain of D , containing the elements < d and a finite number of other elements. To prove this, we distinguish two cases. 1) d may have an immediate predecessor d'. According to our supposition, % is partially satisfiable with respect to the elements < d' and a finite number of other elements; therefore, it is partially satisfiable with respect to the elements < d and a finite number of other elements. 2 ) Suppose d to have no immediate predecessor ; let el, ..., e, be arbitrary elements not preceding d. For every d'
<
WFFS WHICH M A Y CONTAIN THE SIGN OF EQUALITY
69
numerably infinite domain, or if for every finite number p there is a finite domain with p or more elements such that is satisfiable in that domain, is satisfiable in every well-ordered infinite domain. If we express this statement in terms of validity instead of satisfiability, we have our theorem TVII. Theorems VI and V I I now yield the result that to determine the domains in which all wffs are valid, we need only investigate the validity for finite and denumerably infinite domains. If a w# i s valid in a denumerably infinite domain, validity exists in all domains with the possible exception of a finite number of finite domains. If a wfl i s not valid in a denumerably infinite domain, it is not valid in any infinite domain, but may be valid (if validity exists at all in some domain) in all or in some finite d o m i n s . For the solution of special cases of the decision problem these theorems are of importance, since they permit the restriction to the domain of the natural numbers and to finite domains of natural numbers when determining the validity of a wff. This results in a considerable facilitation.
a
a
VI SOLUTION O F THE DECISION PROBLEM FOR WFFS WITH SPECIAL PREFIXES 1. Remarks on the selection of special cases of the decision problem In the following, we give a report on special classes of wffs without bound predicate variables for which a solution of the decision problem has been obtained apart from the solution for wffs containing only monadic predicate variables. Such a report cannot be complete in the sense that it comprises all wffs, the validity of which may actually be determined. Every proven mathematical theorem yields the validity of some wff. The relation between mathematical problems and special cases of the decision problem is given by D. Hilbert and W. Ackermann [l],(chapter 111, Q 11). There are certain elementary parts of mathematics, such as elementary algebra, for which even a complete solution of the decision problem has been reached (see C. H. Langford [l, 21, M. Presburger [l], A. Tarski [2], J. C. C. McKinsey [l], W. Smielew [l], Th. Skolem [4]). But in general, the wffs the validity of which is known by mathematics are of a very different character. Some of them have a rather complicated logical structure while the validity of others which are relatively simply constructed is unknown. For a systematic treatment of the decision problem from a logical point of view, it is best to consider classes of wffs which have a common logical structure. It is convenient to assume the wffs to be in prenex normal form. Special classes of wffs may be obtained by confining ourselves: 1) to certain classes of prefixes, 2) to special structures of the matrix, 3) to occurring predicate variables limited as to their number and character. Not every restriction of this kind will lead to classes of wffs for which a complete solution of the decision problem may be taken
SELECTION O F SPECIAL CASES
61
into consideration. For instance, it is useless to try to solve the decision problem for all wffs with a prefix (Exl)... (Ex,)(yl) ... (yJ, since all wffs can be brought into Skolem normal form and therefore, the solution of the problem for these wffs would include a general solution of the decision problem for wffs without bound predicate variables. A general solution of the decision problem for wffs of this type is excluded by the papers mentioned in chapter 11, $ 5 . There are other classes of prefixes such that every wff can be transformed into another one having a prefix of the class. The reduction of all wffs to formulas with a special kind of prefix may be of importance for proving general theorems about wffs, as has been seen by the utility of the Skolem normal form in deriving the general theorems of the previous chapter. We shall only mention some of these reduction theorems, for they generally lend no assistance in the solution of special cases of the decision problem; but they give warning against undertaking too much. Every wff can be reduced t o a corresponding one having the prefix
(Ex)(Ey)(Ez)(u,) ... (u,) (see K. Godel [3]), or (Ex)(Ey)(z,)... (z,)(Eu) (see L. Kalmar [9]), or (Ex)(Ey)(z)(Eu,) ... (Eu,) (see J. Pepis [ 2 , 3]), or
(z)(Ey)(z)(Eul) ... (Eu,) (see W. Ackermann [4]), or
(Ex)(Ey)(Ez)(u) or (Ez)(Ey)(z)(Eu) (see J. Suranyi [l]), or (Ex)(y)(z)(Eu)(Ev) or (x)(Ey)(x)(Eu)(Ew) (see J. Suranyi [Z]). As regards the first four classes of prefixes, no general solution of the decision problem is even possible if the predicate variables occurring are restricted to a dyadic one; for L. Kalmar and J. Suranyi have shown that every wff can also be given such a form (see L. Kalmar [S, 91); L. Kalmar and J. Suranyi [ l , 21). The chief results in the solution of special cases of the decision problem are solutions for special classes of prefixes. These solutions have been given in literature for wffs not containing equality in general, we extend them to wffs with equality. For some of these classes, the solution thereby gets more complicated. Setting aside the cases for which a solution can be reached in a more or less
62
WFFS WITH SPECIAL PREFIXES
trivial way, the author has been trying to give a systematic treatment by reducing the special decision problems to those of the monadic predicate calculus.
Solution for wffs having prefixes consisting solely of universal quantifiers Let the wff be of the form (2,) ... (x,)%(x,, ..., xm), where % contains no quantifiers. For a wfl of this kind, validity need only be determined for domains with 1, ..., m elements. For validity exists in a domain with more than m elements, if and only if it exists in a domain with m elements. If the wfl is valid in a domain with m elements, it is universally valid. Let D, be a domain with k elements (k m) and a subdomain of D,. Further, let the wff be valid in D, and let a,, ...,a, be an arbitrary ordered m-tuple of elements of D p %(a,, ..., a,) is true by any assignment of propositional functions over D, because it is true in Dzby an assignment of propositional functions which have the same values as the functions over Dl, provided only elements of D, are concerned. On the other hand, the wff may be valid in D,,the last domain having in this case exactly m elements. Let b,, ..., b, be an arbitrary tuple of elements of D,.For the valuation of the formula a&,. ..,b,) in D,, only the values of the propositional functions for b, and tuples of bi are of consequence. Since the elements b,, ..., b, are elements (not necessarily the only elements) of a domain with m elements and since validity exists in this domain, %(b,, ..., b,) is true in D, however the assignments for the predicate variables are chosen. The decision problem for wfls with only universal quantifiers mn also be solved in another way, namely by constructing a n equivalent equality formula. Properly spoken, the wff resulting from the given one by placing universal quantifiers for all predicate variables at the beginning of the wff, is equivalent to the equality formula; for the predicate and the individual quantifiers can change their places, and then the predicate variables can be eliminated by applying E25 of IV, $ 2 . 2.
<
PREFIXES CONSISTING OF EXISTENTIAL QUANTIFIERS
63
Solution for wffs having prefixes consisting solely of existential quantifiers Let the wff be of the form (Ex,) ... (Ex,)%(x,, ..., zm)where 9€(xl, ..., xm) contains no quantifiers and no individual variables besides z,,...,xm. A wfl of this kind is universally valid, if it i s valid in the domain with one element. If it is valid in some domain, it i s valid in any domain with a larger n u d e r of elements. Let D, be a subdomain of D, and let the wff bevalidin Dl. If we have an arbitrary assignment Q for the predicate variables in D,, there is a corresponding assignment 52' in D,,namely that one formed by the propositional functions over D,coinciding with those over D,, so far as elements of D, are involved. There exist elements a,, ...,a, of D, such that %(al, ..., a,) is true by Q'. Obviously, %(a,, ..., a,) is true by 52. For the wjfs with only existential quuntifiers not containing equality, the decision problem in the form I I i s solved by use of T I I of V , Q 2. Such a wfl i s either universally valid or validinnodomain at all. Valuation in a domain of one element reveals which of the two cases presents itself. For the wffs containing equality, the domains in which they are valid are not so easily determined. According to V, Q 3, such a wff is either universally valid or valid in no domain at all; or there is a finite number k such that the wff is not valid in domains with less than k elements and is valid in any domain with k or more elements. But hitherto, we have not been able to decide under which of the last two cases the wff falls if the first one is excluded. Nor can we at this point effectively determine the number k if the wff should fall under the third case. I n the following solution of the problem, we shall restrict ourselves to wffs with only monadic and dyadic predicate variables. This restriction is in no way essential. The dyadic predicate variables occurring in a@,, ..., xm) may be G,, ..., G , . We first prove a lemma. Lemma. Let q,, ..., q z ,x,, ..., x1 be functions, the domains and ranges of which are the non-negative integers. They are defined 3.
64
WFFS WITH SPECIAL PREFIXES
by the following simultaneous recursions : x7(074)=4, p,(O,q)=q (r=1, ... Xl(P+l, a) =Fz(P, 1+24);
)
('='>
x7+1(p+1, q)=pr(p+l, 2q) V7(P+17 p)=x,(p+1, 2q) ('= 1,
0; **'>
z-l);
0.
We then assert I and 11. I. Let r,,..., I'z be dyadic propositional functions over a domain D with x7(p,q ) elements which may be natural numbers.
Then there exists a subdomain D, of D with p+q elements a,, ..., aB,b,, ..., b, (written in their natural order) and the following property. Fj(ui, c ) has the same value for all c of D, with ui
<
<
<
PREFIXES CONSISTING OF EXISTENTIAL QUANTIFIERS
65
(a,, ..., a,,,, c,, ..., ci) corresponding t o q~,(p+l,q ) , according to 11. We return to our wff (Ex,) ... (Ex,)%(x,, ..., x,). Let B(xl, ..., x,) be the disjunction of all wffs %(al, ..., a,) where a,, ..., a, are arbitrary variables from the set (x,, ..., x,) taken in any order, with or without repetitions. If (Ex,) ... (Ex,)%(s,, ..., x,) is valid in some domain, (Ex,) .., (Ezm)B(xl,..., 2,) is valid, and conversely. We now construct a third formula with the prefix (Ex,) ... (Ex,) which has only monadic predicate variables. I n B(x,, ..., x,j, we replace every prime formula Gix,x, by Hixp, every prime formula G6xpxq( p< q ) by Kix, and every prime formula Gixpxq( p > q ) by Lizp. B(x,, ..., 2,) is then transformed into a wff E(x,, ..., x,) which contains only the monadic predicate variables Hi, Ki, Ld(i= 1 , . ..,I) and the monadic predicate variables already occurring in B(x,,. ..,x,) The last variables are supposed to be different from Hi, Ki, Li. The following relations hold between (Ex,), ... (Ex,) B(x,, ...,x,) and (Ex,) ... (EX,) &(xl,..., x,). a ) If (Ex,) ... (Ex,)B(x,, ..., x,) is valid in a finite domain with m or more elements, then (Ex,)... (Ex,)@(x,, ...,x,) is valid in this domain also. The elements of this domain be natural numbers. Let @, ..., ds,, Y,, ..., Yt,O,, ..., 0,be an arbitrary assignment for the predicate variables Hi, Ki, Li, and 9 a similar assignment for the other monadic predicate variables. We define dyadic propositional functions I',,..., I', over the domain. For any a and b, Fi(a, b ) has the same value as @&) or !Pi(a)or Oi(b), according as a = b or a < b or a > b. Since (Ex,)... (Exm)B(xl,..., x,) is valid in the domain, there are elements a,, ...,a, such that B(a,, ..., a,) is true by I',, ... r,9. We now take a set c,, ..., c, of elements of the domain such that ci
66
WFFS WITH SPECIAL PREFIXES
(Ex,) ... (Ex,)&(x,, ..., x,) was arbitrary, this wff is valid in the domain. b) If (Ex,) ... (Ex,)&(xl, ..., x,) is valid in a finite domain with k elements (k 2 m), (Ex,) ... (Ex,)%(x,, ..., x,) is valid in a domain with y z ( k ,0 ) elements. Let D be a domain with vl(k,0 ) elements. r,, ..., r,, 9 are assignments in this domain for G,, ..., G, and the monadic predicate variables of B(q, ..., xm). There is then a subdomain Dlof D with k elements such that the value of ri(a, b ) ( j = 1, ..., b) in this domain depends only upon a if a t b , and only upon b if b t a . We define monadic propositional functions !Di, !Pt, Oi(i = 1, ..., 1) over D, such that !Di(a), !Pi(a) and Oi(a) always have the same value respectively, as Td(a,a), Ti(a,b ) for a t b and ri(b, a ) for a t b . Values of ?Piand Oinot determined thereby may be supplied in an arbitrary way. According to our supposition, there are elements a,, ..., a, of D, such that &(%, ..., a,) is true by !Di,Y+,Oi, 9. Let c,, ..., c, be a set of elements of D,such that ci
***7
is valid in D. I n a) and b) we may substitute (Ex,) ... (Ex,)%(x,, ...,x,) for (E.1) ... (Zx,)B(+, ..., x,), since both wffs are valid in the same domains. The problem of determining the domains in which (E.1)
(E~7n)%(x17xm) ..a>
is valid, is now generally solved. (Ex,)... (Ex,)&(x,, ..., xm) is a wff with only monadic predicate variables for which this problem can be solved with the methods of IV, 5 3. Either (Ex,) ... (Ex,)CS(x,, ...,2), is valid in no domain at all,
R E D U C T I O N O F T H E D E C I S I O N P R OBLEM
67
in which case according to a ) , (Ex,) ... (Ex,)iX(x,, ..., xm) is valid in no domain; or there isafinitedomaininwhich (Ex,)...(Exm)E(xl,...,xm) is valid. Let the smallest domain of this kind, which can be determined, ..,xm) have p elements, and let k be Max ( p ,m).Since (Ex,). ..(Exm)E(xl,. is valid in a domain with k elements, (Ex,) ... (Exm)%(xl,...,5,) is valid in all domains with v l ( k ,0) and more elements according to b). To completely determine the domains in which (Ex,)...(Ex,)%(x,, ...,xm) is valid, validity has still to be investigated for domains with 1, 2, ..., v l ( k ,0)-1 elements. This may be done with the methods of I , 5 2. 4.
Reduction of the decision problem for wffs with certain prefixes to that for wffs with simpler prefixes
Before proceeding to the solution of the decision problem for other classes of prefixes it is useful to derive a certain reduction theorem due in the general form stated here to L. Kalmar 141 and used before in a more special form by W. Ackermann [l]. Let % be a wlj in prenex normal form without free individual variables and with the prefix (x,)... (xm)(Eyl)... (Ey,)(z,) ... (zk). The decision problem for iX can be solved if it can be solved for wljs with a prefix (Ey,) (Ey,)(z,) ... (2,). Here, n is the same number as before, while r is arbitrary. If k = 0, r is 0. To exhibit the idea of the proof, it will be sufficient to carry it through for the case that iX contains only monadic and dyadic predicate variables, namely the monadic predicate variables GI, ..., Gp and the dyadic ones H,, ..., H,. iX is transformed into a wff 2'3 in the following way. Every prime formula G,a is replaced by a=xlv Xi85 a=x, v G,a, and every prime formula H,ab by a=x, v b=xl v Y j & a=x, v b=xl Kja & & a=xl v b=x, v L,b & a=x, v b =x, v H,ab. Xi and Y j are propositional variables ; K , and L, are monadic predicate variables (i= 1 , .., p ; j = 1, .. 4 ) . Let @, and !Pi be an arbitrary assignment for Gi and H i and let Q be an arbitrary assignment for the individual variables of the matrix of % in a domain B. The element a of D may be assigned to x1 by Q. Let d i , ri,O,, Aj be assignments for Xi,Y,, K , and L, such that d, and riare the values of @,(a) and Y,(a, a ) , and such that O,(c) and Aj(c)always have the same value
...
.
.
68
WFFS WITH SPECIAL PREFIXES
as Yj(c, a) and Yj(a,c). Any prime formula Gia or Hiab of % then has the same value by Oi, Pi,0 as the corresponding formula of 23 has by Ai, ri,Oi, A$, Oi, Yj, 9. On the other hand, let A i , I'$, @Ii, Ai, dji! Y j ,0 be an arbitrary assignment for Xi, Yi, Ki,Li, G,, Hiand the individual variables of the matrix of 8 ; let the element a be assigned to x, by Q. We define propositional functions dj; and Y; suitable as assignments for Gi and Hi.@:(a)has the value A < ; otherwise, O;(c) always has the same value as d j i ( c ) . !$';(a,a) has the value Ti.Yi(c, a) and Y$!(a, c) have the same value as Oi(c) and Ai(c), if c is different from a. If both c1 and c, are different from a, the value of Y7!(cl,c2) is the same as that of Y i ( c , , cz). Any prime formula of % again has the same value by @,; Y7!, 0 as the corresponding formula of 23 has by A,, Ti, Oi,Ai,dji, Yj, 0. Therefore the wffs 8 and 8 are valid in the same domains. Inthe following, ('a)%(a)maybeanabbreviation - for (a)(a = xlv %(a)) and (E'a)%(a)a similar one for (Ea)(a=x, & %(a). If a wff
*..,Yl&,Z,...Z8) (where @ does not contain the variable 2,) is valid in a domain D (Xl)('X,)
('%)(E'Yl)
-
0
.
(E'Yd'Z,)..-
('zs)@(x2,...,Xm,Y,,
with at least two elements, then it is obvious that tx,) ..f (Xrn)(EYl)
- - a
(Ey7Jfzd
1..
(z,)@(.,,
v . 3 ,
X,, Y1,
--->
yl&,21, ... 2),
is valid in a domain D, which results from D by excluding one element, and conversely. We now transform 8 in a manner such that it becomes a conjunction of wffs of the above kind. '$3 has the prefix (x,) ... (x,)(Ey,) ... (Ey,)(z,) ... (2,) and a matrix CT(xl, ..., x,, ~ 1 .,.., yl&,zl,..., 2,). '$3 is changed into '$3, by replacing CT by CT,. CTl is the conjunction of all possible wffs B(x,, ..., x,, y,, ..., yl&,a,, ..., a,) where a,, ..., ak are variables from the set 21,
zk*
... ('z&
and (2,) ... ( z k ) & get the same Value by any assignment in a domain which has a t least two elements. &, results from 0,by renlacing every wff prime formiila Z ~ = = Xby ~ T and every prime r"orm~t!szi=xl or xl=zi by F and &en by reduction of the ('ZJ
. REDUCTIOh-
O F TIIE D E C I S I O N P R O B L E M
69
8-formula according to 11, $ 3. By this transformation, '$3, becomes B2.B2 is equivalent t o B,, since ('z,) ... ('zJ preceeds 0,. Let %(q, ...,x, y, ..., y,) be ('Q ... ('zkP2(x1,..., x,, yl, ..., ym,zl,...,z k ) . 5D,(xl, ..., x,, yl, ..., y,) is the disjunction of all wffs %(x,, ..., x,, b,, ..., 6,) where b,, ..., 6, are variables from the set x,, y, ..., y., ..., x, y, ..., Y,) and (E'y,) * (E'y?JQ(x,, .-.,x,, (EYl)* * (EY?z)%(~l, y, ..., y,) get the same valuation by any assignment in a domain with a t least two elements. 5D2 results from 9, by replacing every prime formula x1= x1by T and every prime formula y6= x1 or x1= y; by F and by subsequent reduction according to 11, $ 3. (E'y,) ... ... (E'y,)%, and (E'y,) ... (E'ym)B2 are equivalent. The last wff may be abbreviated by E(xl,..., x,). Let Ei(xl,x2,..., x,) be one of the wffs E(xl,c2, ..., c,) where cz, ..., c, are variables from the set z, x2,..., x , . Not every $, of course, contains all the variables xl,..., x,. It is t o be understood that in the following formulas vacuous quantifiers are deleted. For domains having a t least two elements, (xl)... (x,)E(x,, x2,..., x,) (and therefore '$3) get the same value by any assignment as the conjunction of all wffs (xl)('x2) ... ('x,)C$(x,, x2,..., x,). Ei(x,, x2, ..., x,) results from E{(x,, x2,..., x,) by replacing every prime formula x,= x1 by T and every prime formula x1=xior xi = x1 (i # 1) by F and by subsequent reduction according to 11,$ 3. Every wff (xl)('xz)... ('x,)E6(xl,. ..,x,) is equivalent to (x1)('x2) ... ('x,)oli(x,, ..., x,). Each of the last formulas can be given a prenex normal form with a prefix (Xl)('X2)
and a matrix
... (E'Ym)('Zl) ... ('%)
*.. ('%P'Yl)
0&,,..., x,,
y,
*.*
ym,
21,
a * * ,
q.
But Ei does not contain the variable x1; for all the prime formulas xl=xl,",=xi, x,=x,, y i = x l , xl=yi,zi=xl and xl=z6 have been eliminated. Nor does x, occur in other prime formulas ; for regarding the construction of '23, a wff G,xl would only occur as part of xl=xl v G4x1.Likewise prime formulas H,axl, Hjxla,Kix, and Lixl would only occur as terms of a disjunction of which xl=xl is another term. All such prime formulas have disappeared with the elimination of x1=x,.
70
WFFS WITH SPECIAL PREFIXES
Therefore '$3 is valid in a domain having at least two elements, if and only if all the wffs (22)
*.. (.m)(Ey,) .*.( ~ y , ) ( z , )
***
(Z,)Oi(~,,
'*.)
x,, Y l ,
a e . 3
Ya3 z1
*.. 4
are valid in a domain which has one less element. The wffs & contain propositional variables, but these variables can be eliminated according to 11, 0 3. The elimination means only th7h the number of the wffs above is multiplied by 2g,if g is the number of the propositional variables. By applying this reduction several times, we get the following result. A wfl 8 with a prefix (x,)... (xm)(Eyl) ( E y J z J ... (zk)and is valid in a finite domain with at without free i n d i v i d ~variables ~ least m + t elements (t >, l), if and only if a certain finite number of wfls Bi with prefixes (Ey,) ... (Ey,,)(z,) ... (Q, which can be constructed from %, are all valid in a domain with t elements. Here n has not increased while ri m y be greater than k. But if k = 0, all ri are 0. 8 i s valid in a denumerably infinite domain, if and only if all the wfls 8;are valid in such a domain. If for the wffs Bi the decision problem is solved, we get a solution of the problem for % after having investigated the validity of 8 in domains with 1, 2, ..., m elements.
...
5.
Solution for wffs having preiixes such that all the universal quantifiers precede all the existential ones This case of the decision problem as well as the cases treated in Q 2 and 0 3 of this chapter were first solved by P. Bernays and M. Schonfinkel [l] for wffs not containing equality. Let (x,)... (xm)(Eyl)... (Ey,,)%(x,, ..., x,, y,, ..., 9), be the wff. If a wff of this kind is valid in a domain D with at least m elements, it is valid in any larger domain. Let D,be such a larger domain. If we have an arbitrary assignment a,, ...,a,, 5-? for the individual variables x,, ..., x, and for the predicate variables of (Ey,) ... (Ey,)%(x,, ..., x,, y,, ..., y,) in D,, there is a subdomain D,of D, which has the same number of elements as D and which contains the elements a,, ..., a,. Let SZ' be the assignment for the predicate variables in D,consisting of those propositional functions over D, which coincide with the
UNIVERSAL QUANTIFIERS PRECEDING EXISTENTIAL O N E S
71
propositional functions of 9,so far as only elements of D, are concerned. (By,) ... (Ey,)%(a,, ..., a,, y,, ..., y,) is true in D,by 9'. There exist then elements b,, ..., b, of D, such that %(a,, ..., a,, b,, ..., 6,) is true in D, by 9'.Obviously %(a,, ..., a,, b,, ..., b,,) is true in Dl by 0.Since 9 and a,, ..., a, were arbitrary,
(EyJ
***
(Eyn)a(x,,
ea.3
*m,
~
1
9
yn)
is valid in D,. The problem of universal validity for wgs having the prefix above can now be solved. A wfj of this kind i s universally valid if it i s valid in domains with 1 , 2 , ..., m elements. For the wfjs which do not contain the sign of equality, validity in all domains can be determined by use of T I I of V , 6 2 . W e first ascertain whether the w# i s valid in a domain with m elements. If it is, it is universally valid. If not, validity exists at most in domains with 1, 2 , ..., m-1 elements, for which the validity can be determined in the usual way. For the wfls which may contain the sign of equality, the solution of the form 11 of the decision problem can be found by making use of the theorem of 3 4, by which the present case i s reduced to the one treated in 5 3 of this chapter.
VII FURTHER CLASSES O F PREFIXES FOR WHICH THE DECISION PROBLEM CAN BE SOLVED 1. Solution for wffshaving prefixes containing only one existential quantifier The wff has the form
(x,)* * - (x,)(~y)(z,) * * * (%JWx,, ..., x,, y, 21, ..., 2,).
This case of the decision problem, for wffs not containing equality, was first solved by W. Ackermann [l] for the form I1 of the decision problem and independently by Th. Skolem [3] for m=O and the form I of the problem. The subcase m = 0,n = 1 had been treated before by P. Bernays and M. Schonfinkel [l]. This special case is contained in the case treated in 0 2 of this chapter. But as the argumentations used here are much simpler than those used in Q 2 , a separate treatment may be justified. By force of the reduction theorem of 5 4 of the preceding chapter, it is sufficient to give the solution for m=O, i.e. for wffs of the form (Ex)(y,)* * (Yn)Wx,g1, .. Y,). Our treatment of the case is different from that given in the above cited papers inasmuch as we give a reduction of the problem to that for wffs with only monadic predicate variables. Here again, we restrict ourselves to the case where !lj contains only dyadic predicate variables, namely G,, ...,G , , from which the essence of the method is to be recognized. Let E(x, yl, ..., y,) be the conjunction of all wffs B(x, a,, ..., a,) in which a,, ..., a, is a n-tuple selected from the set (x,y, ..., y,). Further, let $(z, y, ..., y,) be the disjunction of all wffs x = y9 and Y,) is yp=yQ. ( P , q= 1, * * . ) n ; P f d . If (Ez)(y,) ... (y,)%Xx, Yl, valid in a domain, (Ex)(y,) ... (y,)($(x, y, ..., y), vE(x,y,, ...,y,)) is valid in the same domain. If the last wff is valid in some domain, the first one is valid in the same domain, provided the domain has J
-..?
PREFIXES CONTAINING O N E EXISTENTIAL QUANTIFIER
73
at least n+ 1 elements. This is easily seen by the construction of
E ( x , ~ 1 -.-, , yn). I n E(x, y, ..., y,), we replace the prime formulas Gixx, Gixy,,
Giypx, Giypyp and Giypyq( P f:4 ) by Hix, KiDx, Lipx, Hiyp and Mi,,x. E(x, y, ..., y,) is thus transformed into D ( x , y, ..., y,) which contains only the monadic predicate variables Hi, K i p ,Lip and Mipq. Let N,, N 2 , N , be three other monadic predicate variables. We now consider the wff which has the prefix (Ex)(y,)... (y,) and t.he matrix is the disjunction of the terms $( x , yl, ..., y,), -of which N,x N2y,v ... v N2y,, N g & N a , v ... vN3y,, N3x & N,y,v ...vN,y,,, -& N,x & N 2 x & G, N,x & N2x, N,x & N3x, N2x & N3x, and D(x, y, ..., y,). We shall abbreviate this wff by $j, while the wff (EX)(YI) (Yn)('$(xt YI,...,y,) v g ( x , !/I, ..., y,)) may be abbreviated by G. We shall prove that the following relations exist between @ and 8. If G is valid in a domain, @ is valid in the same domain. If @ is valid in a denumerably infinite domain, G is universally valid. This suffices to solve the decision problem for the wffs (Ex)(y,) ... (y,)B(x, y,, ..., y,) in the form 11. Since @ contains only monadic predicate variables, it can be determined in which domains it i s valid. If it is valid in a denumerably infinite domain, @ is universally valid, and (Ex)@,) ... (y,)B(x, y,, ..., y,) i s valid in any domain with the possible exception of domains with 1, 2, ..., n+ 1 elements, for which the validity can be determined by the methods of I , 5 2. If $j is not valid in a denumerably infinite domain, it i s either not valid in any domain, in which case G and (Ex)(y,)... (y,)B(x, y,, ..., y,) are not valid in any domain; or @ is valid only in a finite number of finite domains which can be determined, in which case (Ex)(y,) ... (y,,) B ( x , y,, ..., y,) is at most valid in these finite domains. Whether this is the case, can be determined by the methods of I , 5 2. Now for the proof of above assertion. Let G be valid in a domain D. Let Di,Oip, A,,, ripq, II,, 112, 17, be arbitrary propositional functions over D, suitable as assignments for Hi, Ki p , Lip,Mi,@, N,, N2 and N3. If @ were false by this assignment, there would be functions v,, ..., q~,, the domain and the range of which is D such that for every element a of D qIia=a, ppa=Vga, ( p # q ) and - a -
74
FURTHER CLASSES O F PREFIXES
- - - -
%(a,Flu,, cp,,a) are false, and such that I7,a v U2a & I12a v D3a & & F a v I7,a, and one of the formulas 17,a & n2y,a & ... & L12pina, 17,a & I7,cp1u & ... & IT3pna, I7,a & IT1plla & ... & Illp,,a, are true. We define propositional functions Yl- Yt over D . Y4(a, a ) and Qi(a), yi(a,ypa) and @&), Yi(ppa,a ) and 4&), and Yi(vpa,vqa)and ripq(a)have the same value; otherwise the definition of the functions !Piis arbitrary. Such a definitionis consistent, since a # qpa,qpa# piqa, ( p f q ) and as pairs (a, pipa), (Fqb,b ) , and (P)~c,psc) cannot be the same because of the stated properties of 17,)112, 17,. I n that case, @(a,yla, ..., vnu)v &(a,Flu, ..., ynu) would be false by Yl,..., Yc, which contradicts our assumption that @ is valid in D . Therefore, .!$ is true by Di,Clip,Aip, rim, Ll,,112,113,and is valid in D , since the assignment was arbitrary. Let .!$ be valid in the domain D of the non-negative integers; let D, be an arbitrary domain. If @ were not valid in D,, then there would be propositional functions Y1,..., Y l and ordinary functions y l , ..., pi, in D, such that '$(a, Flu, ..., vna) and &(a,yla, ..., pinu) would be false for every a of Dl by Y,, ..., Y,. To every element b of D we let correspond in a unique way an element wb of D,. The element of D, corresponding to the element 0 of D is some arbitrarily chosen, but fixed, element of 0,. If an element b of D is equal to 3 n a + 3 ( i - l ) + k (1 < i n; 0 k 2), wb is Fjoa. We define monadic propositional functions cDi, Oip, ( l i p ,ripq, IT,,112,17, over D . Qi(b) has the same value as Y4(wb,wb) for every element 6 . IIi(b) is true or false depending upon whether b results in the remainder i - 1 by division through 3 or not. @,,(b), Ai,(b), Tipq(b) have the same value respectively as Yi(wb,qnwb),Yi(plpwb,wb), and Yi(Fpwb,Facob)./Let xl, ..., xn be the following functions in D . If b + 1 produces the remainder k by division through 3,
<
< <
xi(b)= 3nb+ 3(i-l)
+ k.
Obviously, wxi(b)= yiwb. For any element b of D , &(cob,F1wb,...,p p b ) is false by Y,, ..., Yl. %(b, Xlb, ..., xmb)is false by Qi, ..., IT3, and the formula which results from the matrix of .!$ by replacing x by b and yl, ..., y,, by Xlb, ..., X,,b is also false. This would contradict the assumption that .!$ is valid in D ;therefore, @ is valid in Dl.
PREFIXES CONTAINING TWO EXISTENTIAL QUANTIFIERS
2.
75
Solution for wffs having prefixes containing only two existential quantifiers which are not separated by universal quantifiers I n this case, the wff has the form (Xl)
... (%)w%’ xm, YlJY2,21, -..,%&I*
(Xrn)(~Y1)(&/2)(%)
The solution of the decision problem was given independently by K. Godel [2, 31, L. Kalmar [4], and K. Schutte [l, 21. Godel and Schutte give the solution for the form I1 of the problem, while Kalmar’s solution is restricted to form I. Taking into consideration the reduction theorem of 5 4 of the preceding chapter, we see that it is sufficient to soIve the problem for wffs of the form (~xl)(Ex,)(Yl). - * ( Y a ) w %
x2, 2 4 1 9
..*Y
Y7J.
The solution of form I of the decision problem is easier to obtain than the solution of form I1 we have given here. We restrict ourselves, as do the cited papers, to wffs which do not contain the equality sign. The method we are following here is in a certain way similar to that used in Q 1 of this chapter inasmuch as we shall reduce the problem to a similar one for the monadic predicate calculus simultaneously making use of some of Godel’s ideas. The idea of the proof can be fully grasped if we exhibit it for the case in which the WEin question contains only one dyadic predicate variable G and only two universal quantifiers. We therefore start from a wff (EXl)(EX,)(Yl)(Y2)~(Xl,x2, Y1,Yz)
which we shall designate by 6. We construct a wff with only monadic predicate variables which stands in a certain relation to 6. The monadic predicate variables occurring in it are
H,Kl,...,K,, L,,L,,
(i=O,
..., 15) Ni,Pi( i = l , ..., 7). I&, Di,k,
etc. are used in the following to designate a disjunction of terms in which i, or i and k, run through all possible values of certain indices. For instance, ITiLixmeans Llxv L2x; (Mix & M+y) means the disjunction of all terms (Mix & M ~ J in ) which i and j
76
FURTHER CLASSES O F PREFIXES
may be independently any of the numbers 0, 1, ..., 15. I n the same way Zi, ZiSk,etc. are used to designate certain conjunctions. Let 01 be a function, the domain and range of which are the natural numbers 1, ..., 7, and which has the property that a(;,cw(j, k)) and 01(ol(j,k),i) are always different from j and k. Such a function exists, as can be immediately shown (a domain with seven elements being the smallest domain in which such a function exists). We select a special function of this kind so that ol always represents this function. The property of 01 stated above includes the case in which always &(i) k ) # i and ~ ( ki ),# k . d,?(k=0, ...) 15; i , i=1, 2) is a truth-value T or F. If k = cO2O c121+ ~~2~+ c 3 2 3 (ci = 0, l ) , then A,,, Ak12, and A,, are T or F in case .so,E ~ c2, , c3 are respectively 0 or 1. 6, yl, ..., y5 are functions, the domains and ranges of which is the set ( 0 , 1 , ..., 15). If k = ~ ~ 2 ~ + ~ ~ 2( ~~ ~+=1)) ~0 ,~then 2 ~ + ~ ~ d(k) = ~ , 2 0+ c221+ ~ , +2cOP. ~ yl, ..., y5 are not further specified except that they satisfy the condition that d k l l ) dYl(k)ll, and dyl(k,ll; Ays(k)ll, and 'y&)ll; Ayl(k)22, 'ya(k)22, and A y s ( k ) l l ; '~,(k)22, Ay,Vc)22, and have the same truth-values. Furthermore, if Akll, Ak12, A, and A,, have the same truth-value, then y,(k)=y,(k), and y,(k) = y,(k). We introduce several abbreviations. Let E ( i ) be the formula which results from %(xl)x2, yl, y2) by replacing Gxlxl, Gx1x2, Gxgl, G x g 2 , G X l Y l , GYl% GYlYl, G X l Y 2 , GYZXl, GY2Y2, Gx2Y1, G Y l X 2 , GX2Y2) G y 2 ~ 2 (, 7 ~ 1 ~ 2and , GY~Y respectively, ~ by dill, d i 1 2 , 4 2 1 , 4 2 2 , Ayl(i)i2,
+
'yl(i)21>
'Y1(i)223
'Yz(i)l27
AY~(i)21, 'YZ(i)22,
Ays(i)121 'Y,(i)21,
'Y,(i)lZ,
AY4(i)21'
and 4 d i ) 2 1 . x2, yl, y2) is an abbreviation for the disjunction of the -formulas - -Ll!/l, 'BLGl, G 2 ~ ~ o i)Y1, ( i , K w y 2 7 MkYl) Mx27 Niyl, NiYB,piY1? piY2) A k l l * Hxl? AM, * HxZ, A ~ l ( k ) 2 2* HYl) dy,(k)22 * Hy2, and xl = x2 & ( A k l l * d,,,) (Ak12 * A<)* % i j k ( ~ l , x2,yl, y2) stands for the disjunction of the formulas 4r(i)12'
ftijk(x1,
"
('1)('2)ftfi~3(k)(~2,
x17
'1, '21,
( Z 1 ) ( Z 2 ) ~ ' i , ( i . i ) y , ( k ) ( 2 1 ,Ylj
'19
'2))
(~1)('2)%a(i. i)ys(k)152' YI, %, ~ 2 ) , and ('1)('2)ftdi, ?)a(i.i)Ydk)(!/l, Y2) %>'2). Let 9 be the disjunction of the formulas (Ex)(L,x & LG), ( ~ 1 ) ( ~ 2 ) 9 i a ( j)ya(kl(xl) i. ~ 2 '1,) '21, ('l)(%)ftja(i.
?)y,(k)(X23 y 2 , '1, '2))
PREFIXES CONTAINING TWO EXISTENTIAL QUANTIFIERS
77
I & ( E x ) ( M p& E(i)), ni*j(Ex)(M,z& M,.), ITtij (Ex)(N,x & N,x), ni*,(Ex)(P,x& Pix), (Ex)(= & ... & K,z), 17$*i(Ex)(K;x& K,x),
(E~l)(Ex,)(Yl)(Y,) 4 j k
aiik(x1, 33, Yl, Y2)7
(Ex,)(Ex,)(EYl)(EY,) 17,ik (%jk(%
and
x2, Y1, Y2)
%ijk(Xl> x2, Y1, Y2)).
b is an #-formula which contains the truth-values T and F . There exist the following (I and 11)relations between CS and 9. 1. If 9is valid in a denumerably infinite domain for arbitrary functions yl, ..., y5, CS is universally valid. Let D be a domain in which CS be false by the assignment @ for G. Then there exist functions q1 and 9, over D,the values of which are elements of D such that for all a and b of D,%(a,b, v,(a,b), y2(a,b ) ) is false by @. We are now going to construct a denumerably infinite domain D‘, the elements of which are non-negative integers. 0 is an element of D‘.If a’ and b’ are elements of D,so are xl(a’, b’) and x2(a’,b’). (xl(a’, b‘) = 2a’+1(2b’+ 1) ; x2(a’,6’) = 2“‘+l(26’+ 1) + 1). The elements generated from 0 by successive applications of x1 and x2 are the only elements of D’.Elements of D’will be usually designated by a’, b’, c’, ..., elements of D by a, b, c, .... We suppose the ordered pairs (a, b ) of elements of D to be enumerated in some way. We introduce the expression: the first ordered pair of D equivalent to an ordered pair (c, d ) of D.By this we understand the first ordered pair (a,b ) of D such that @(a,a ) and @(c, c), @(a,b ) and @(c,d ) , @(b,a ) and @(d, c), @(b,b ) and @(d,d ) have the same truth-value and such that a= b if the values of @(c, c), @(c, d ) , @(d,c), and @(d d ) are the same. TO every ordered pair (a’, b’) of elements of D‘,we let correspond an ordered pair ( a ,b ) of elements of D,which is defined by recursion. a, may be an arbitrary, but nevertheless a fixed element of D. The pair corresponding to (0,0) is the first pair equivalent to (a,,a,). The pairs corresponding to (a’, xl(a’, b’))7 (b’, xl(a’, b’)), (xl(a’,b’), x1(a’, b’)), (a‘, x2(a‘, b’))7 (b‘, x&’, b’)I7 (&’, b’), x2(a’,b’)) (Xl(U‘7 b‘), x2(a’,b‘)) are the first pairs equivalent to (a, vl(a, b ) ) , (6, vl(a, b ) ) , (v,(a, 61, %(a,b ) ) , (a, v2@, b ) ) , (b, v,(a, b ) ) , ( v 2 h b ) , v 2 @ b ) ) , (yl(a, b ) , y2(a,b ) ) , if (a, 6) corresponds to (u’, b’). Otherwise, if
78
FURTHER CLASSES O F PREFIXES
c’
d’, the pair corresponding to (c‘, d’) is the first pair equivalent to (c, d ) if (d, c) corresponds to (d’, c’). We now define monadic propositional functions A , Oi,Yi,St (i= 1, ..., 7), and Y,, Y2,ri(i= 0 , ..., 15))over D’.Ulxl(a’, b’) and Y2x2(u’,L’) are true; otherwise Y, and U, are false. O,(O) is true;
Yi(0) and Ei(0) are false. If Oi(a‘) and O,(b’) are true, Oa(i,i,xl(a‘,b’), Oa(i.,x2(a’, b’h Yixl(a’, b‘), yix2(a’7 b’), Eixl(a’, b’), and Q 2 ( a ’ 6’) , are true. If i # j and if @$(a‘)(Yi(a’), Ei(a’))is true, then @&a’) (Yi(u’),Ej(a’))is false. A(a’) has the same value as @(a,a ) if (a, a ) corresponds to (a’, a’). To every ordered pair (a’, b’) with the corresponding ordered pair (a, b ) we assign that number k (k= 0 , ... ..., 15) for which A,,,, Ak12,A,, and A,, are the values respectively of @(a,a ) , @(a,b ) , @(b,a ) , and @(byb ) . FkxI(a’,b‘) and rkx2(a’, b’) are true if E is assigned to (a’, b’). I n all other cases rk(a’)is false. We define functions y,, ..., y5 over the set (0, ..., 15). If there is a pair (a’, b’) such that k is assigned to it, and if i,, i,, i3, i4, i, are the numbers assigned to (a’, xl(a’, b’)), (a’, x2(a’,b’)), (b’, x,(a’, b’), (b’, x2(a’,b’)), (xda’,6‘)) x2(a’,U), then y,(W = 4, y2(W = i2, ..., y5(k)= i,. This definition is independent of the special pair (a‘, b’) ; for if k is assigned to (a‘, b‘) and to (c’, d’), the ordered pairs of D corresponding to (a’, b’) and to (c’, d’) are the same, and so are the pairs corresponding to (a’, xl(a’, b’)) and (c‘, xl(c’, 67)))etc. On account of the definition of the corresponding pairs, y,, ..., y5 fulfil the conditions imposed on such functions occurring in 9. In so far as the values of y,, ..., y5 are not thereby determined, they are arbitrary. If A , Oi, Yi, Ei,Y, Y, ri are assigned to H , K i , Ni, Pi, L,, L,, Mi, and if the functions y,, ..., y, are defined in the way just described, 9 gets the value P . We have to show that every disjunction term of 9 is false by this assignment. If Ti(a‘)is true, there are elements c‘ and b‘ such that a’=xs(b‘, c‘) and such that i is assigned to (b’, c‘). If ( b , c) is the pair corresponding to (b’, c’), then 8 ( b , c, p,(b, c), p2(b,c)) is false
79
PREFIXES CONTAINING TWO EXISTENTIAL QUANTIFIERS
by the assignment di for C.@(i) results from %(b, c , y,(b, c), y2(b,c)) by replacing every prime formula diab by a certain A,,,. Each such Gab and the pertaining A,,, have the same truth-value; this immediately results from the definition of y,, ..., y5 and the definition of the corresponding pairs. Since @(i) is false, Di ( E x ) ( T p& @ ( i ) ) is false. (Ex) (Y,z & Y 2 x )is false according to the definition of !Pi. (E2)(YiX& Y&, Di*i(Ex)(T,x& Tgx), (Ex)(O,x& ... & (Ex)(s“,x& Eix), and (Ex)( O p & Oix)are false as well with respect to the definitions of ri,Yi, Ei and 04.Riik(a‘,b’, x,(a‘ b‘), x2(a’,b ’ ) ) is false by our assignment if Tkxl(a’,b’), Oi(a‘),and Oi(b‘) are true. Therefore, (E4(Ex2)(g1)(y2) ZikiRigk(xl,x2, g,, y2) is false. If Riik(a’,b’, c’, d’) is false by our assignment, Tk(c’), Tk(d‘), Oi(a’), Oi(b‘), Yi(c’),Yi(d’), Z?(c’), Ei(d’), Y,(c‘), Y2(d’), Oa(j,j)(c’),and Oa)c,j)(d’) are true. There are then elements e‘ and f’ such that c’=x,(e’, f ’ ) , and such that @ ( e l ) , O,(f’) are true. Let 9‘ be x2(e’,f ’ ) ; then Riik(a’,b‘, c’, 9’) is false too. Furthermore, each of the formulas
o,x),
eijic3(k)(b’,a’,
e’), h ( f ’ 7 e’)), ~ l t e ’g’), , ? d e ’ 7 g’)),
x l ( f ’ 3
9ia(i.j)yn(k)(a’,d’,
eicx(4,j)yl(k)(u‘,
c’),
c’,
fhc,j)y.(k)(b’,
c’,
XI(/’,
X2(e‘7
c’)),
c’), xz(f’,c’)),
and ecx(d.j)a(d.j)yp(k)(G’,d‘, xl(c’,9’),x2(c’,g’)) is false too; i.e. %@(a‘,b‘, c’, d’) is false. This means that aja(i. i)y,(k)(b’,d‘,Xl(f‘,g‘),x2(il,g‘)),
( E z ~ ) ( E ~ ~ ) ( % )17ijk ( E Y(%dxl, ~ ) 22, ~
1 ~, 2 & ) % i k ( ~ i , ~ 2 9 ~ ~1 2 , ) )
is false. As all the disjunction terms of 9 are false by our assignment, so is 9. I has now been proved, for we have shown that SD cannot be valid in a denumerably infinite domain for arbitrary functions y,, ..., y5 if (S is not valid in all domains. 11. If 0 is valid in a finite domain with p2 elements, SD is valid in a domain with p elements for arbitrary functions y,, ..., y5. We again prove this in an indirect way. D, may be a domain with p elements. There may exist functions y,, ..., y5 and an assignment A , Oi,Yi, Si, Y, Y2,Ti for H , K i , N;, Pi, L,,L2, Mi such that 9 is false by this assignment. For every element of D, there is then just one i such that @(a)is true. Y, and Y2, and Tj,
80
FURTHER CLASSES OF PREFIXES
Yiand Y i , and Eiand Ei are not true for the same element if i # j. The whole assignment may be designated by 9. The elements of D, may be the numbers 1 , 2 , ..., p . Let D, be a domain, the elements of which are the numbers 1 , 2, ..., p2. Each element a of D, has the form b . p + e ( a ) ( 0 b p - 1; 1 @ ( a ) p ) , so that b+ 1 and @(a)are elements of D,.We define a dyadic propositional function @ over D,.
<
< <
<
a) If e(a)=e(b), @(a,b ) has the same value as A(e(a)).
@) If there is an i, j , k such that &&(a), efb). e(c), e(d)) is false and if c = ( e ( a ) - l ) p + ~ ( c ) and d = ( e ( u ) - l ) p + e ( d ) , then the values of 1) @(a> c ) and 4 , ( k ) 1 2 1 2 ) @(C> a)and 4 ( k ) 2 1 , 3) @.(a,4 and d Y ? ( k ) , 2 , 4) @(4 a ) and 4 ~ 2 1 ,5 ) @(kc ) and 4 3 ~ k ) 1 2 t 6) @(c, b ) and 41(k)21, 7 ) @(b,4 and 4 1 k ) l 2 , 8 ) @(6 b ) and 4 ( k ) 2 1 > 9) @(c,4 and 4 ( k ) l , , 10) @(d,c) and d,l(k,,,are the same.
b ) is a pair of elements of D, for which @(a,b ) is not y ) If (a, c e ( b ) ,then there are indices i ,j,k and eledefined by p ) and if @(a) ments c and d such that Riik(e(a), e ( b ) ,e ( c ) ,e(d))is false by Q and such that c=(e(a)-l)p+e(c) and d= ( e ( a ) - l ) p + e ( d ) . For each such pair we select such an i, j, k , c, d ; @(a,b ) and @(b,a ) then have the values A,,, and dMl, We must show that this definition of @ is consistent, i.e. that the value of @ for a n ordered pair is uniquely determined. If % d e ( a ) e(b), , e ( c ) , e ( 4 ) is false by Q, then oie(a),@,e(b), @,(,.,dc), @a(i,i)e(d),Y l ( e ( c ) ) ,and Y2&) are true. As a(i,j ) # i , j and because of the properties of ul, and Y2,e(a)+e(c), e(a)#e(d), @(b)#@(C), e(b)#e(d), and e ( c )#e(d). a ) and 8) therefore are not contradictory, since they relate t o different pairs. By each of the definitions p l ) , ..., 810) by itself @ is uniquely determined, since for every element e ( c ) and e(d) there is only one k such that r,e(c) and T k ( p ( d ) )are true. It remains to show that definitions Bm) and fin) are not contradictory if m#n. If the value of @(e, f ) is determined by pl), ..., P l O ) , and if O,e(e) and Oie(f) are true, the following relations exist: A) j = a(;, rl); ul,e(f) b e . u',e(f) is true), 82) i = a(j,r2); Ul,e(e), 83) i=4,r3) ; Y,@(f)? 84) i = r4) ; Y,e(e), P 5 ) i=4 r 5 > i) ; ul,e(f), 4
9
PREFIXES CONTAINING TWO EXISTENTIAL QUANTIFIERS
81
86) i = 4 r 6 , i); Yle(e), 87) j = 4 r 7 , 4; Y d f L88) i = &(rg, j) ; Y2e(e), 89) i=i;Y,e(e); Y,@(f), 810) 2* = 3 ;* Y d f ) ; Y,e(e). Since Yland Y, are not true for the same element and since we always have a(s, t ) # s, t ; 01(01(s,t ) ,q ) # s, t , and n(q, &(a, t ) )f s, t, only the definitions 81) and 8 5 ) , 8 2 ) and BS), 83) and 8 7 ) ) and 84) and 88) may apply to the same ordered pair. If 81) and 85) give a definition for the same @(e, f ) , then there are indices i, j, k and elements g, d , h, c such that !&(ee, eg, ef, ed) and Qiik(eh,ee, ef, e c ) are false by 9, and such that f = ( e e - l ) p + e f and f = ( e h - l ) p + e f ; then e(e) = 4 1 1 * 4 2 , 4 c 1 2 * A,,,, A,,, ++A,,, and Yl(W = Y 3 ( k ) and y,(k) =y4(lc). According to 81))the value of @ ( e ,f ) is dYl,,,,,and according to 8 5 ) , Ay,,k)12;but this is the same value. In a similar way, it is shown that 82) and BS), 83) and 8 7 ) , and 84) and 88) are consistent if they apply to the same ordered pair. We now show that (Exl)(Ex2)(y1)(y,)%(x,,x,, yl,y,) is false in D, by the assignment @ for G. Let (a, b ) be an ordered pair of elements of D,. To prove that to such a pair there always exist elements c and d such that '%(a, b, c, d ) is false by @, we distinguish several cases. 1) @(a)= Because 9is false in D,by 9,there are indices i, j, k and elements c and d of D, such that 9&a, eb, ec, ed) is false by 9 and such that c = ( ~ a - l ) p + e c , d=(ea-l)p+ed. Since ea=eb, according to the definition of $ Akl1, A,,,, A;,,, and A,, are all the same truthvalues and this is the value of &a). According to the definition of @, each of the prime formulas of %(a,b, c, d ) with the assignment @ for G has the value of the corresponding formula A,, of G(Ic). Since r&c) is true and since Ui( E x ) ( r c x& @(i))is false, 6 ( k ) is false as is also %(a,b, c, d ) by @. 2 ) Let e(a)
82
FURTHER CLASSES OF PREFIXES
3) Let ea>eb and @(a,b ) be defined according to y ) . Then there are an i, j, k and elements c and d such that $&&b, @a,ec, ed) is false and such that @(b, a ) and @(a,6 ) have the values Akl2 and Aal. Then %{,,(eb, @a,pc, ed) is false too ; that is, there are elements e and f such that e= (ea- l)p+ee, f=(@a-1)p+ef, and such that Rjisck)(ea, eb, ee, ef) is false by Q. %(a,b, e, f)then has the same value as O.(d(k)); i.e. it is false by @. 4) Let @(a,b ) be defined according to P l ) , Then b= (ea-l)p+eb and there are an i, j , k and elements c , d such that ftiik(ea,ec, eb, e d ) is false by 9. Since ec, eb, e d ) is false also, there are elements e and f such that e= (pa-l)p+pe, f = (ea-l)p+pf, and such that 9ia(i,g)yl(k)(ea, eb, ee, e f )is false by 9. As a result of the definition of @, %(a,b, e , f) by @, and O;(y,(k)) have the same value; i.e. %(a,b, e, f ) is false by @. 5 ) Let @(a,b ) be determined by 8 2 ) . Then some formula of the form Rijk(eb, ec, @a,ed) is false by 9, and so are !Xiik(eb,ec, pa, ed), some formula ofthe form j)Yl(k)(eb, ea, ee, e f ) , i)Yl(k)(eb,ea, ee, e f ) and a formula of the form fta(i,i)isy,(k)(~a, eb, eg, eh) where g=(ea-l)p+eg, h=(ea-l)p+eh. %(a, 6 , g , h ) is false by @ because @(6yl(k)) is false. 6) If @(a,b ) is defined according to /?3)-/?10), the argumentation is similar. Thus I1 has been proved. The decision problem for W ~ BS is now solved in the form I I . Since 9 contains only monadic predicate variables and since there are only a finite number of functions yl, ..,, y5, it can be decided whether 6 i s valid in a denumerably infinite domain for arbitrary functions yl, ..., y5. (The truth-values Aiki occurring in 6 are only a convenient means of describing the structure of 6 and can be eliminated). If it is valid in a denumerably infinite domain, E is universally valid. Otherwise, we find functions yl, ..., ys such that 6 i s not valid in a denumerably infinite domain; then we can find a finite d m i n in which this 9 i s not valid and the smallest such domain with k elements. Then 6 i s not valid in domains with k2 or more elements. Whether 6 is valid in the domains with 1 , 2 , ..., k2-1 elements, can be determined by the methods of I , 5 2.
VIII GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
1. Limitation of the range of the method hitherto used For the wffs hitherto treated, the decision problem could be reduced to that for wffs with only monadic predicate variables. All these wffs, as well as the wffs of the monadic predicate calculus, are valid in a denumerably infinite domain if they are valid in any finite domain. Now there is no class of prefixes not included in the classes discussed before for which all the wffs belonging to it have this property. This has been shown by K. Schutte [l]. Let us consider the two formulas, and
(Ez)(y)(Ez)(Gxx v y&
v (Gyz & G)
(Ex)(Ey)(Ez)(u)(Gxx v G G v (Gzy & Gyz & G).
Both these wffs are not valid in a denumerably infinite domain, e.g. in the domain D of the natural numbers. Let @ be the dyadic propositional function over D which has the value T for (a, b ) if a < b, and otherwise the value H. If a and b are arbitrary natural numbers, then all the formulas @(a,a ) , @(a,a+ l ) , @(a+1, b ) & & @(a,b ) are false, i.e. the first formula is not valid in D.If a , b, c are arbitrary natural numbers, then all the formulas @(a,a ) , @(a,a+ l), @(a,b ) & @(b, C) & @(a,c) are false which means that the second wff is not valid in B. On the other hand, both wffs are valid in any finite domain. Let D,be such a domain, and @ an arbitrary dyadic propositional function over Dl. Let us assume that the first wff is false by the assignment @ for G. There is then for every a of D, an element b such that for every c the matrix of the wff is false by @ and for the assignment of a,b, c for x,y, z. For every a we can select such a, b ; call it p(a). @(a,a ) and @(a,Fa) are true €or every a. Let yla, fp,a,y3a, ...
-
84
GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
stand for pa, pya, ppqm, .... Since D, is a finite domain, there are a certain element c and a number n such that pnc=c. Let m be the smallest number such that @(a,p,a) is true for all a, while @(a,prn+,a) is not. Since @(a,p,a)is always true and since @(c, p,c) is false, such a number m exists. Let @(a,yrn+,d) be false; @(pd,prn+,d) & @(d, pm+,d) is true. This means that the matrix of the wff is true by the assignment of d, pd, prn+,d for x,y, 2 , contrary to our assumption. Therefore the first wff is valid in any finite domain. Let us suppose now that the second wff is false by the assignment of @ for G in D,.Then @(a,a)and @(a,b ) & @(b,c) & @(a,c ) are false for all elements a, b, c of D,.Furthermore, for every element a of Dlthere is a d such that @(a,d ) is true. Let pa be such an element. Let ?,a, yza, ... have the same meaning as before. Since D,is a finite domain, there are an element e and a number n such that pne=e. Since @(prne, prn+,e) is true and since is false, @(e, pm+,e) would be true if @(e, pme) were true. Thus @(e, qne) is true, since @(e,ple) is true. This is a contradiction because pne=e. Therefore, the second wff is valid in any finite domain. The result of Schutte indicates that one may produce wffs valid in any finite domain, but not valid in a denumerably infinite domain for every prefix having at least two existential quantifiers separated by a t least one universal one, and for every prefix having at least three existential quantifiers followed (immediately or not) by a universal one. The remaining prefixes are such that they contain only existential quantifiers followed by no universal quantifier, or only two existential quantifiers immediately succeeding each other, or less than two existential quantifiers. These are just the classes of prefixes for which a solution of the decision problem has been given previously and are the only classes for which a solution is known. The method of reduction to the monadic predicate calculus therefore cannot be used to solve the decision problem for further classes of prefixes, at least not in a way similar t o that before.
SOME OTHER CASES
85
Furthermore, the decision problem as a whole has been reduced to that for certain classes of prefixes having only three existential quantifiers, namely to that for the prefixes (Es)(Ey)(Ez)(u), or (Ez)(Ey)(z)(Eu), or (Ex)(y)(z)(Eu)(EvL or (x)(Ey)(z)(Eu)(Ev) (cf. J. Suranyi [I, Z ] ) , so that it is useless trying to find the solution by any method for all wffs having prefixes which contain one of the above prefixes as a part. For the wffs having only two existential quantifiers which do not fall under the Kalmar-Godel-Schitte case, a solution of the problem of validity may be possible, since no statements indicating that this is impossible have been proved. The simplest prefix of this kind is ( E x ) ( y ) ( E z ) For . prefixes of the type (Ez)(y)(Ez)(Eu) or even (Ez)(y)(Ez,)... (Ez,), a general solution has, for the present, not been excluded by a reduction theorem. But in general, the decision problem for prefixes having at least three existential quantifiers must be further specializised if progress in its solution is to be hoped for.
2. Some other cases for which the decision problem has been solved Since the solution of the decision problem as a whole can be reduced to that for certain prefixes and because all prospects for its complete solution have failed, a further division into special classes of those wffs having such prefixes is necessary. For instance, the reduction of trhegeneral decision problem t o that for wffs with mentioned in $ 1 has been shown shown a prefix (Ex)(Eyj(Ez)(u) by Suranyi, if the number of the predicate variables is not limited. Solutions might be tried therefore, if the number of the predicate variables does not exceed a given number, for instance one. No results in this direction have as yet been obtained. Other specializations may be achieved by taking into account only special forms of the matrix. The chief results in this direction are reported below. Another division of the general division problem into special cases is given in the next chapter. J. Herbrand [l] gave a solution for wffs with an arbitrary prefix and a matrix whose conjunctive normal form contains just one conjunction term or a matrix equivalent to such a one. As A. Church
86
GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
[3] remarks, the condition for the matrix may be replaced by a weaker one if the prefix begins with (xl)... (x,). It is sufficient then, that the matrix is (or is equivalent to) a disjunction in which each term is a conjunction of prime formulas or its negations, with at most one of the terms of each such conjunction containing individual variables other than x,, ..., x,. Th. Skolem [3, 71 has shown that the universal validity can ... (Ex,)(yl) ... (y,) if be determined for wffs having a prefix (Ex,) the matrix is such that all prime formulas contain at least m distinct variables. By the same argumentation, the universal validity can be determined for the more general case where every prime formula contains either all of the variables xl,..., x, or at least one of the variables yl, ...,.,y For wffs having a prefix (Ez)(y)(Ez,)... (Ezml-) a single dyadic predicate variable, and a matrix of the form Gxy v '$I@,, ..., zm), W. Ackermann [4] gave a solution of form I1 of the decision problem if m 4 and of form I11 of the decision problem for any m. Though the conditions which characterize these wffs are rather special, the treatment of them is of some interest because this is the only special case solved of form I1 of the decision problem of some generality which includes wffs that are not valid in an infinite domain, although valid in every finite domain. I. Gbgalkine [2] has solved form I11 of the decision problem for wffs having a prefix (Ex)(y)(Ez,)... (Ez,) and a matrix z y v v %(%, ..., zm), '$I this time containing an arbitrary number of dyadic predicate variables. The investigations concerning special cases of the decision problem, setting aside the monadic predicate calculus, nearly all concern wffs in prenex normal form. To make use of the solutions for other wffs, one has to bring them into prenex normal form. This may be done in different ways. To obtain a most favourable prenex normal form or to determine the various possible prenex normal forms, the following device may be adapted, which has been previously described in detail in connection with the wffs of the monadic predicate calculus. We consider the quantifiers whose scopes contain no other quantifiers. If they are universal
<
87
SOME OTHER CASES
quantifiers, we bring its matrix into conjunctive normal form and then contract the scope of the quantifier. It may be split into several quantifiers by using the equivalences (x)(%(x)& 23) ++ (z)%(x)& 23 and ( ~)( %(x)vB) ++(z)%(x) vB, ( x ) ( % ( x&) B(x))++(x)%(x)& (x)%(x). For existential quantifiers, the dual procedure is followed. After this transformation, the next innermost quantifiers are dealt with in the same manner, and so forth. The wff thus arising is put into conjunctive normal form. The validity of the wff for any domain is equivalent to the validity of all conjunction terms. Each conjunction term is then brought into prenex normal form. If there is more than one prenex normal form, we choose one with a prefix in which the maximal number of universal quantifiers is placed at the beginning. This procedure of getting a most favourable prenex normal form may also be applied to wffs which are given in prenex normal form. In the course of these transformations, there may be other simplifications. We illustrate this by the followingexample. Let the wff in question be (Ex)(y)(Ez)(Gxy v Gxz & Gxy v Gxz). It has a prefix for which no general solution of the decision problem is known. By contracting the scope of (Ez), we get
(Ex)(y)((Gzy& G) v (Gxy & (Ez)G%) v
(6 & (Ez)Gxz)v (Ez)(Gxz& GG)). Here the disjunction terms Gxy & 6and (Ez)(Gxz& G G ) may be v
omitted since they get the value F by any valuation. Dealing with (y) in the corresponding manner, we get
(Ez)((y)Gxyv (Ez)Gxz & ( y ) z y v ( E z ) K z & (Ez)Gxz v ( E z ) G x ) . The conjunction term (Ez)Gxz v ( E z ) Gmay be omitted since it is universally valid. Finally, by contracting the scope of (Ex), we get
(E4((Y)GZY
( Y ) Z Y ) v (Ex)((y)Gxy (EZ)G=) v v (Ex)(@)= & (Ez)Gxz)v (Ex)((Ez)Gxz& (Ez)G%). %I
The first three disjunction terms may be omitted as they arenot valid in any domain. The wff is thus equivalent to(Ex)((Ez)Gxz& ( E z ) G ) ,
88
GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
which has the prenex normal form (Ex)(Ez)(Eu)(Gxx& &%). For this prefix the decision problem is solved. Sometimes the introduction of more predicate variables is useful. This may be illustrated by the following example. G. H. von Wright [ 2 , 31 has given a solution of the decision problem for a class of wffs which may be described as follows. Let S&(x, y) be a wff with the free individual variables x, y and without quantifiers. The predicate variables occurring in it are dyadic ones. Let Bk(x) be a wff, the P-constituents of which are of the form (Ey)'&(x, y). Further, let 6 be a wff, the P-constituents of which have the form (Ex)Bk(x). Von Wright has determined the validity of these wffs 6 by independent methods. But by introducing more predicate variables, we can transform the wffs E into a conjunction of wffs having the prefix of VII, $ 2 . Let (Ey)i?l,(x,y), ..., (Ey)%,(x,y) be the different formulas (Ey)'&(x, y) occurring in 6. To each (Ey)$(x, y) we let correspond a monadic predicate variable Ginot occurring in 6. Let 6 become 6' if every (Ey)'&(x,y) is replaced by Gix. The validity of 6 for an arbitrary domain is equivalent to the validity of the following wff 9:
(Ex)(Ey)(z)((G,x & B,(z,z)) v for
84 v (Ex)(Ey)(z)((CT'zx
( G & '2I1(x,y))v
8,o) v (G,x 83.
'2I&>Y))) v 6 ' ;
m 4 )v (G&
( - m ( ~ y ) ( 4 ( ( G& ix
... v
Y)))
fli(Z>
is a prenex normal form of the wff
(X)(GiX
++
( ~ y ) % ( x!, I)).
If we bring 6 into conjunctive normal form, each conjunction term has a form
(ES)Bk,(X)v ... v ( E X ) ! B k m ( X )
v
(.,Bii,(.) v ..*
v (X)Sin(%).
Instead of the last formula, we may write
... v ~
~ ~ v( (x)Bi,(x) x ) ) v ... v ( ~ $ 3(x) ~ or n ( E X ) ( %... ) (zn)(Bkl(x) v * * - v %km(x) v Bil(zl) v ... v Bin(zn))* (EX)(B~,(Z) v
S O M E OTHER CASES
89
Therefore, E’ can be brought into a conjunctive normal form 0;& ... & 0;in which every conjunction term is in prenex normal form and has a prefix (Ex)(zl)... (2,). The validity of 9 means the validity of all wffs 9i which arise from 59 by replacing Q’ by some 6:.Every $Dican be given a prenex normal form with a prefix (Ex)(Ey)(x,)... ( Z J , since the existential quantifiers can be placed first and because their number can be reduced to two by making use of the equivalence between (Ex)%(x)v (Ex)%(x)and (Ex)(%(x) v %(x)). The validity of a wff E is thus reduced to the validity of a finite number of wffs having the Kalmar-Godel-Schutte prefix. The method of producing an advantageous prenex normal form in the way described first (without introducing new predicate variables) leads to a solution of the decision problem only for wffs with a special structure. A. Church [3], among others, mentions the following simple cases in which a solution of the decision problem can be achieved in this way. 1) The P-constituents of the wff in question can be brought into prenex normal form such that their prefixes consist solely of universal quantifiers or solely of existential quantifiers. 2) The P-constituents can be brought into prenex normal form such that their prefixes are all of the form (xl)(x,)(Eyl)(Ey,) or of a form resulting from this by deleting one or more quantifiers. 3) Each P-constituent can be brought into prenex normal form such that its prefix has one of the forms (xl) ... (xm)(Eyl)... (E3,) or (Exl) ... (Ex,)(yl) ... (y,), where n is the same number for each prefix and 0 m n, and such that every prime formula contains all of the variables gl,..., gn.
< <
4) The wff begins with (xl) ... (xm),the scopes of the quantifiers extending to the end of the formula. Every prime formula has at most one individual variable different from xl,..., x,. Indeed, in the first case a prenex normal form with the prefix of VI, 8 5 can be obtained; in the second case a similar one with the prefix of VII, 8 2. The third case can be reduced to the case treated by Skolem and mentioned previously. I n the fourth case,
90
GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
the wff can be treated in the same way as wffs having only monadic predicate variables. Further cases could be added, e.g. the case that each P-constituent has a prefix (zl) ... (~,)(Ey~)(Ey,)(z,) ... (2,) or a prefix which is a part of this prefix, no P-constituent standing under a negationbar. A general characterization of the wffs for which the decidability can be shown in this way seems difficult. But since the procedure by which an advantageous prenex normal form can be obtained is easy to achieve with a given wff, it seems more important to ask what can be done with a wff for which all attempts to obtain one of the favourable prefixes fail. This will be discussed in 5 3.
3. A general theorem about the validity of wffs The following statements concern wffs which may also have free individual variables. WRs containing equality are not considered here. be given in prenex normal form. We consider the Let a wff following alterations which could be effected on a. a) A universal quantifier with which the prefix begins is dropped. b) An existential quantifier with which the prefix begins is dropped, provided that the wff contains no free individual variabIes. c) An existential quantifier somewhere in the prefix is dropped. The variable of the matrix belonging to this quantifier is replaced everywhere by the same free individual variable occurring in a, or this variable is replaced everywhere by hhe variable of a quantifier preceding the existential one. d) The matrix of 2l is put into the form of a disjunction and one or more of the disjunction terms are left out, vacuous quantifiers, i.e. such quantifiers for which there are no more variables in the matrix, being deleted. By any of these transformations, or by a series of such transformations, % becomes a wff %’ which is valid only for domains in which 3 is also valid. If a’ has or can be given a prefix for which the decision problem is solved, we may thereby find domains in which 9.l is valid. Especially, % is universally valid if %’ is.
91
GENERAL THEOREM ABOUT VALIDITY O F WFFS
We give some examples. (1) The wff (Ez)(y)(Ez)(Gzzv
v (Gzz v Gyz & Gzz v Gxy))
is universally valid. For by d), we get (Ez)(y)(Gzxv q y ) which has the other prenex normal form (y)(Ez)(Gxz v q y ) and which proves universally valid by the criterion given for wffs with this prefix. To the last formula we may also apply the transformation c) and get (y)(Gyy v g y ) which is recognized as universally valid since it has a tautologous matrix. (2)
1
(Ex)(y ) (Ez)(Eu)(Gzz v GXy v (Gzx & Gzx) v v (Gxz & Gzu & &)
v (Gxz & Gxu &
z)
is universal1 valid. By applying the transformation c) and replacing
z and u by y, we get
(Ez)(y)(Gxxv z y v (Gzy & Gyz) v (Gzy & Gyy & G)v v (Gzy & Gzy & C y )
which may be recognized as universally valid by the methods given for the prefix (Ex)(y), or which may be further simplified by the v (Gzy & Gxy & By an transformation d) to (Ex)(y)(Gzz v equivalence transformation of the matrix, we get
G).
By a further application of d), we get (Ex)(y)(Gzzv w y ) which has been dealt with above. Sometimes we may not be able to decide the validity of a wff '?2l in this way, but success may be gained if we take a finite disjunction '?2l v % v ... v % instead of 'i?X and bring it somehow into prenex normal form. (3) To give an example for this case also, we consider the wff
VW v Gyy v Gxz v Gzz v (Gzz & G p ) )
(E~)(y)(Ez)(Gxz vG x ~
which we abbreviate (Ez)(y)(Ez)%(x,y, z). Here the universal validity cannot be shown as in example (2). But if we take (-w(y)(Ex)%(z,y, z) v (W(y)(Ez)%(z,y, z ) , for which
(E.)(y)(Ez)(Eu)(v)(Ew)(~(x, y, 2) v
v, 4)
92
GENERAL REMARKS ABOUT FURTHER INVESTIGdTIONS
is a prenex normal form, and transform it by c) into
( E 4 ( y ) ( E z ) ( v ) ( W Yx , z ) v W Y , V ? x)), the matrix becomes a tautology. The question may be raised whether any universally valid wfl can be recognized as such in the last manner by starting from a finite disjunction of the w8.T h e answer i s positive. A theorem of this kind shall be proved, but only for wffs in which the negation-bar stands at most over prime formulas and in which no quantifiers are part of a conjunction term. This is sufficient for all applications since every wff can be given such a form. For instance, a prenex normal form fulfills the condition. To formulate our statement more precisely, we introduce the notion of n-validity. We first construct for every wff 8 a finite set of other wffs determined by 8. A wff of this set may be designated by ( 3 ) though there are usually several wffs (8).We define the wffs ( 3 ) by recurrence from a wff to its parts according to the following conditions. ( 1 ) If Z has no quantifiers, (8) is 8. ( 2 ) ( ( z ) % ( x ) is ) either ( x ) % ( zv) (x)%(x)or ( x ) ( 8 ( z ) ) .
(3) ( ( E x ) Z ( x ) )is either ( E x ) 8 ( x )v (Ez)%(x)or (Ex)(%(x)). (4)
(Z v 93) is (8) v (23).
If we have for instance a wff ( x ) ( E y ) Z ( xy, ) in which 8 ( x ,y ) contains no quantifiers, the wffs ( ( x ) ( E y ) % ( xy,) ) are the wffs (x)(Ey),wx,Y ) ( x ) ( E y ) W x Y, ) , ( x ) ( ( E y ) W zY) , v (EY)WX,Y ) ) , and ( z ) ( E y ) W x Y, ) . A wfl 8 i s called 1-valid if there i s a prenex normal form of 8 which may be turned into a tautology without quantifiers by transformations (a)-(c). ((d) is not used here.) The prenex normal forms of 8 which are used here constitute a definite finite set. After 8 has been transformed in a way such that the negation-bar stands only over prime formulas, and after the variables have been, if necessary, rewritten so that different quantifiers have different variables, the prenex normal forms result
"
GE N E RAL T H E O RE M AB O UT VALIDITY OF WFFS
93
by placing the quantifiers at the beginning in a succession such that any quantifier which was in the scope of another quantifier remains so afterwards. M is called n f 1-valid if one of the wgs (a} is n-valid. We now state the following theorem T V I I I For every universally valid wij (having the special form as regards the position of the negation-bar and as regards the conjunction terms) there is an n such that the w# is n-valid. This of course does not include a solution of the decision problem in form I, since in general we cannot determine the number n. The theorem we deliver here is related, as may be mentioned, t o another one of that kind expressed in a more number-theoretic form. The latter theorem is a corollary of the Godel method of proof for the completeness of the first order predicate calculus (K. Godel [ l ] ) (cf. the generalized metatheorem of A. Church [3]). A proof of our theorem has been given by J. Herbrand [ 1 ] in proving what he calls the property A of universally valid wffs. On the other hand, properties B and G of universally valid wffs also mentioned in his paper and shown t o be equivalent to A , are in close relation to the metatheorem above. We shall not give the proof of Herbrand or any other selfcontained proof here, but we make use of the result of Godel t'hat a certain axiomatic system delivers all universally valid wffs. But no reference is made to the Godel method of proof. Our theorem may be easily established by means of an axiomatic system in which all universally valid wffs can be derived and for which the Hauptsatz of G. Gentzen [ l ] or an equivalent for it is valid. We take an axiomatic system given by K. Schutte [3] which is most appropiate for our purpose. This system has been shown by Schutte to be equivalent to the system which Godel has proved to be complete, and to contain an equivalent of the Hauptsatz. We shall show that the axioms of this system are n-valid and that each rule of inference includes a transition from n-valid wffs to m-valid wffs. The postulates of the system are the following: (1) Axioms are all wffs % v
ff where
'Zt is a prime formula.
94
GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
( 2 ) The rules of inference contain a transition from
(2a) % R v ( r r v B v % to % R v B v % v % , (210) % v ( r r v % to % v % , (2c) % to % V B , (2d) % v % and % v % to i?X v % v % , (2e) (2f)
IX v %
to E v % ,
a(a)v % to
(2g) ‘Ir(ll)v % to
(Eu)%(u)v ’32, and (Eb)%(b) v %.
The system is formulated with free variables. I n (Zg), % must not contain the variable b. The rules (2a)-(2g) are to be so understood that the disjunction terms %R and % may also be missing. Conjunction and the universal quantifier do not appear in the system. % & is interpreted as being an abbreviation for v % ; (x)%(x)is such a one for (Ex)’?&& Let us consider now a wff % which is universally valid, in which the negation-bar stands only over prime formulas, and in which no conjunction term contains quantifiers. If (rr contains a universal quantifier or the sign of conjunction, we eliminate them in the above-mentioned way. % then becomes a wff a’. Because the system of axioms is complete, a proof can be given of a’. We now transform every wff % of the proof into another wff \%3\in which the negation-bar stands only over prime formulas. This can be done in a unique way as described previously in chapter 11. We proceed from the whole wff to its parts by using the fact v 1B/, I(Ex)%(x)lis (Ex)l(rr(x)l, lgl is 131, l m l that 1% v 231 is is /%I & IBI,~ ( ~ u ) % (is u )(/u) l W l , 1 8& BI is 181& IBI,1% & BI is v 1B1, I(u)%(u)[ is (Eu)l%(u)(,till the wff has the desired form. By this transformation, universal quantifiers and the conjunction sign may again appear in the wffs. Obviously, %’ is again transformed into %. The axioms (1) are unaffected by this transformation. Though, as regards the rules (Za), (2b), (2c), (Zf) both premise and conclusion may be altered, the connection of the wffs by these rules remains. In (2e), premise and conclusion are transformed into the
a
(a1
GENERAL THEOREM ABOUT VALIDITY O F WBFS
95
same wff. The wffs formerly connected by (2d) are now related by a transition (2d') from (5 v 0. and 9v 0.t o (0.& 3)v @. Instead of (2g) we have now a transition (Zg') from B(b) v % to (b)113(b) v %. No wff of the transformed proof contains as a part a conjunction with quantifiers in its terms; for the last wff of the proof has no such conjunctions, and the premises of (h), (Zb), (2c), (Zd'), (Zf), and (2g') cannot contain it if the conclusion does not. We show that every wff of the transformed proof is n-valid for some n. For the axioms ( I ) this is evident. They are 1-valid. If YR v (21 v 113 v % is n-valid, then YJl v 23 v (21 v % is n-valid for the same n ; for if n= 1 , Cm v 23 v (21 v % can be given a prenes normal €orm with the same prefix as v (21 v 23 v %. All other steps can be done correspondingly, the prefixes of the corresponding wf€s being the same and the matrices differing only by the arrangement of the disjunction terms. If v (21 v B v \Jt is a+ 1-valid, we have a certain wff v (21 v 23 v \Jt} which is n-valid. We then find a wff (YJl v 113 v 3 v %) differing from the former one by the succession of the disjunction terms. Thus the statement proves correct by induction on n. If (21 is n-valid, % v '23 is n-valid; for if n = 1, v '23 can be given a prefix of which the prefix given to (21 is the first part, the matrix of (21 v 23 containing one disjunction term more than that of (21. This relation between the two corresponding wffs can be preserved by all succeeding steps. If a has been transformed into a tautology without quantifiers, (21 v 23 is transformed into such a tautology by further steps which drop the rest of the quantifiers according to (a)-(c). If n> 1 and if we have a wff (a), a wff ((21 v 23) exists of which (%} is a disjunction term. The statement for n + 1 is thus reduced to that for n. I f B v % v % i s n - v a l i d ,% v % i s n + l - v a l i d ; f o r % v ( 2 1 v % i s o n e of the wffs (a v '%) (or results from it by changing the succession of disjunction terms and doubling such terms without quantifiers). If '9 v Q is m-valid and 23 v (5 is n-valid, ((21 & B) v0: is Max (m, n ) 1-valid. (Remember that and B contain no quantifiers.) If both m and n are 1, (% & B) v (5 v Q is I-valid; for we can give this wff a prenex normal form such that the prefix of B v Q comes
(a
+
96
GENERAL REMARKS ABOUT FURTHER INVESTIGATIONS
first, followed by the prefix of '$3 v Q. The first part of the prefix can be transformed by (a)-(c) in the same way as the prefix of fl v &. After these quantifiers have disappeared, we treat the second part of the prefix and the part of the matrix belonging to it in the same way as @ v Q. Obviously, (% & 23) v 6 v E is then transformed into a tautology without quantifiers. (% & '$3) v Q v CS is one of the wffs ((% & '$3) v 6 ) or differs from such a wff by another succession of disjunction terms and by writing twice some disjunction terms without quantifiers, which evidently has no effect on the property of n-validity. Therefore (a & 23) v 6 is 2-valid. Let us in the general case designate by a wff generated from % by n-fold application of ( ) (n 2 0). If % v Q is m-valid and if 23 v CS is n-valid, a certain wff % v (Q),,-l and a certain wff 23 v (6),-, are 1-valid. Then a wff (%& '$3) v (E),-, v is 1-valid, which shows in the same way as the 1-validity of (% & 23) v v CS before. Consequently, a wff ((21 & 23) v (CS v &)Maax(m,n)-l is 1-valid. This means that ( 3 & 8)v E v & is Max(m,n)-valid.Then (% & '$3) v 6 is Max(m,n)+ 1-valid. Our statement is therefore proved. If %(a) v 92 is n-valid, (Eu)%(u)v % is n-valid. If n = 1, we can give (Eu)%(u)v 92 a prenex normal form such that it can be transformed by (b) or ( G ) into a prenex normal form of %(a) v %, the latter being chosen arbitrarily. If %(b) v 92 is n+ 1-valid, some wff (%(a)) v (92) is n-valid. Supposing the statement to be true for n, we conclude that (Eo)(%(o)) v (%) is n-valid. Since (Eb)(%(b)) v(92) is one of the wffs ((ED)%(b)v %), (&)%(a) v '32 is n+l-valid. If %(a) v % is n-valid, (b)%(b) v % is n-valid. If n = 1 and some prenex normal form of %(b) v % is given, there is a prenex normal form of (b)%(b) v 92 which is the same as the former one except that the universal quantifier (b) is placed at the beginning of the prefix. By transformation (a), this quantifier can be dropped. If %(a) v 92 is n+ 1-valid, (b)%(b) v 3 is n+ 1-valid. This is demonstrated in the same way as the corresponding statement for
(an)
(Ea)%(a)v 9.
This completes the proof of our theorem. The proven theorem may be helpful if the icniversal validity for a claas of a f j s has to be decided. For by separating the wgs which are
GENERAL THEOREM ABOUT VALIDITY OF WFFS
97
n-valid where n is less than a fixed number, the subset of the wgs for which the universal validity i s doubtful is diminished. Sometimes we may even succeed in determining all wffs n-valid for some n. To reduce further the number of these W ~ S other , rules might be useful by which certain wfls are shown not to be universally valid. The following transformations (a)-(y) concerning wffs in prenex normal form are in a certain sense the inverses of the former transformations (b), (c), (d). While transformations (a)-(d) defined a transition from a statement to a stronger statement, (a)-(?) contain a transition to a weaker statement. ( a ) A universal quantifier appearing anywhere in the prefix is changed into an existential one.
(p) A universal quantifier appearing anywhere in the prefix is
dropped. The variable pertaining to it is everywhere replaced by a free individual variable occurring in the wff, or is replaced by a variable belonging to a quantifier preceding the universal one.
( y ) The matrix of the wff is brought into the form of a conjunction, and one or more of the conjunction terms are omitted.
If by (a)-(y) we can transform a wff into another one recognized not to be universally valid, the given wff is not universally valid. Sometimes this method may fail, but we may succeed when starting from a finite conjunction 9l & % & ... & % instead of from %. Another device of finding wffs not universally valid is to determine the wffs which are not valid in a domain with a fixed finite number of elements. Finally, we may construct special propositional functions in the domain of the natural numbers, which assigned to the predicate variables of the wff yield necessary conditions for validity in that domain. Wffs not satisfying these conditions are not universally valid.
IX
THE DECISION PROBLEM FOR WFFS WITH FUNCTIONAL VARIABLES
1. Introduction of wffs with functional variables I n this chapter we give another formulation of the decision problem which may be employed to obtain a classification of special cases different from that mentioned previously. It has been customary to base the logical calculus upon the primitive idea of the predicate or the propositional function. But it would be just as convenient to use the notion of function in the mathematical sense, i.e. of a function whose domain and range are the elements of a certain domain. Such functions will be referred to simply as functions in the following. Though special logical systems have been constructed with the fundamental idea of function, it seems that the decision problem in general for such a functional calculus, apart from special systems with a mathematical interpretation, never has been taken into consideration. For all applications of logic, a functional calculus would render the same service as a predicate calculus. Corresponding t o every monadic propositional function @ over some domain, for instance, we can find a function p over that domain such that for every element of this domain “@(a)is true” and “p(a)=a” are equivalent statements. Likewise, “p(a, b)=u” and “@(a,b ) is true” can be equivalent statements. There are of course many other ways of finding an equivalent expression for “ @ ( a )is true” by means of a function. For instance, if b, and co are two fixed elements of the domain, then there is a function p such that p(a) is always b, or c,, and such that rpa=b, and pa=c, correspond t o “ @ ( a )is true” and t o “ @ ( a )is false”. But the first way seems preferable with respect to the formalization, since we need not introduce special elements of the domain in question and special properties of the functions. For the rest, the method which we choose is not essential for the
INTRODUCTION
99
following. The equivalence between the wffs with predicate variables and the wffs with functional variables will be stated more exactly in that which follows. We now proceed to give the notion of a wfF for the functional calculus. Since several notions of the first chapter are repeated or undergo only a slight alteration, we shall be rather brief in the succeeding explanations. The primitive symbols are the logical constants "$", "v'), "-'), " = " ; the individual variables x,y, x , xI,... ; the functional variables fl, 91,h1, f 2 , h3, ..., the superscript n indicating the n-adic character of the functional variable. There are further existential and universal quantifiers for the individual and the functional variables for which the same (the corresponding) notation is used as before. A term (or more precisely an individual term) is an individual variable or an n-adic functional variable succeeded by n individual variables. a, 'b, C, ..., which were syntactical variables for individual variables before, are now syntactical variables for terms. Syntactical variables for wffs are the same as before. A well-formed formula is a combination of symbols which can be generated by a finite application of the following rules. W'l. A wff is obtained by placing a term before, and another after the sign These are the prime formulas. W'2. The construction of further wffs by use of the signs "&", "v)), "-", and the quantifiers is carried out in the same way, or the corresponding way, as by rules W4-W6 of chapter I. The same applies to the definition of free and bound individual and functional variables. Among the wffs defined in this manner, are included the equality formulas (chapter 111).The superscript of a functional variable is usually omitted. We get an n-adic function in a domain D if we let correspond to each n-tuple of elements of D one element of D , uniquely determined. I n a finite domain, there is only a finite number of n-adic functionsfor every n. Functions are designated by Greek minuscules such as p, x, y , pl, .... Elements of a domain are designated by a, b, C, d, ..., or by the same letters with number indices. A complete assignment for a wff with free individual or functional variables is established in a domain D if an element of D is assigned to every "=)).
100
WFFS WITH FUNCTIONAL VARIABLES
free individual variable, and a function over D with the same n-adic character to every free functional variable occurring in the wff. A complete assignment for a wff without free variables is a vacuous one.
3 ,
Special cases for which the decision problem is solved for wffs with functional variables We shall restrict ourselves here to the problem of validity for wffs in prenex normal form having functional variables with no quantifiers. This corresponds to the decision problem for the wffs of the first order predicate calculus. Special cases of the decision problem are obtained by considering special prefixes or classes of prefixes and by eventually limiting the number of the functional variables occurring in the wffs. Such a special class of wffs would correspond to cIasses of wffs of the 2.
101
SPECIAL CASES
predicate calculus with special matrices. On the other hand, to every class of wffs of the predicate calculus with certain prefixes there correspond here wffs with the same prefixes, but with special matrices. This correspondence of course depends upon how we establish the correspondence between propositional functions and functions. We adhere to the method previously mentioned. Let a wff %(Gl, ..., a,) of the predicate calculus without bound predicate variables be given. Let fl, ..., f k be functional variables, each fi being an n-adic variable if Gi is an n-adic variable. I n %(GI, ..., Gk), we replace every prime formula Gial ... a, by fial ... a,= al, by which %(Gl, ...,Gk)becomes 8(fl, ..., f k ) . The validity of %(G1, ...,Gk) holds for some domain, if the validity of % ( f l , ..., f k ) holds for this domain, and vice versa. On the other hand, let &(fl, ..., f k ) be a wff according to W’1 -W’2 without bound functional variables. Further, let G,, ..., G, be predicate variables, each Gi being an m + 1-adic predicate variable, if fi is an m-adic functional variable. Let %(Gl, ..., Gk) result from E(fl, ..., fk) by replacing any prime formula fia, ... a, = b or b = fial ... a, by G,al ... a,b, and by replacing any prime formula fia, ... a,=/&& ... 6, by (Ec)(Gial ... a,c & Gibl ... b,c). c is an individual variable not occurring in !&(fl, ..., fk). Let 6(Gl, ..., Gk)be the disjunction of all wffs (Ex,) ... (Ex,)(y)Gixl ... zmy, where m varies with i and is the number of the arguments of fi. Let @(G,, ...,G,) may be the disjunction of all wffs
-
(Ex1)... (EX,)(E~)(EZ)(G,X~ ... xrny & Gix1 ... X,Z & y = z), where m is the same number as before. Lastly, let @(Gl, ..., G,) be the disjunction 6(Gl, ..., 4) v @(al,..., Gk)v $(a,, ..., Gk). For any domain &(fl, ...,f k ) and @(G,, ...,Gk)are both valid or both not valid. The proofs, which present no difficulties, are omitted. The foregoing remarks show that special solvable cases of the decision problem for the new wffs correspond to the special cases of the decision problem for the former wffs for which a solution has been given. In the following, we disregard these cases, nothing new appearing in them. Special cases of some generality of the decision problem for the wffs with functional variables are obtained
102
WFFS WITH FUNCTIONAL VARIABLES
by restriction to special classes of prefixes, or by limiting the number of the functional variables, etc. These cases do not correspond to the analogous cases for the wffs with predicate variables and cannot be solved by reference to them. We consider only wffs in prenex normal form without free individual variables.
I. Solution for wfls having prefixes consisting solely of universal quantifiers The wff then has the form (x,) ... (x,)%(x,, ..., x,). Let the functional variables occurring in it be f,, ..., f k , f i being an j,-adic variable. The validity of such a wfj i s equivalent, for any domain, to that of a n equality formula which we shall construct. I n %(x,, ..., x,), let there occur n distinct terms of the form fial ... aii. Terms equally shaped are not counted twice. We replace each such term by one of the variables y,, ..., y,, so that equally shaped terms, and only such, are replaced by the same variable. By this replacement, %(x,, ..., x,) goes over into a wff @(x,, ..., x,, y,, ...,ym). Let fial ... aidand fib, ... b, be two distinct terms of %, beginning with the same functional variable. To each such couple of terms we construct the wff a, = 6, & a2= b2 & ... & aii = 6, & y, = yqr where y, and yq are the variables by which fial ... aji and fib, ... bii have been replaced. Let el,..., Rt be the wffs constructed in this way. Let &(xl, ..., x,, y,, ..., y,) be the wff
Rl v $t2v ... v Rl v B(x,, ..-,x,, y,,
* . a ,
Y,).
Our assertion is: (x,) ... (x,)%(x,, ..., x,) and (x1)
0 . .
(X,)(Yl)
*a.
(Y,)@(X,)
***)
xm, Y1,
***)
YJ
are valid in exactly the same domains. If (2,) ... (x,)'i3(xl, ..., x,) is not valid in a domain D , there is an assignment p, ..., vk for f,, ..., f k and there are elements a,, ...)a, of D such that %(a,, ..., a,) is false by v,, ..., vk. Let the term of '%(x,, ..., x,) which was replaced by y p before receive the value b, by the assignment y,, ..., qk,a,, ..., a,. By the assignment a,, ..., a,, b,, ..., b, for xl, ..., x,, y,, ..., y,, obviously any of the wffs Q,, ..., 9, gets the value F , as does also %(x,, ..., x,, y,, ..., y,) since the
103
SPECIAL CASES
value of each term of the last wff is the same as that of the corresponding term in %(x,, ..., x,). Therefore,
(xi)... (xm)(yl)
(yn)a(X,,
x m , ~ 1 ' * ,* >
Yn)
is not valid in D . Let, on the other hand, &(x,, ..., x,, y,) ...) y), be false by an assignment a,, ...) a,, b,, ..., b, in D. Functions v,, ..., Q)k over D are defined thus: If the term fia, ... aji of %(xl, ..., x,) has been previously replaced by y p and if c,, ..., ci,are the values of a,, ..., a,, by the assignment a,, ..., a, for x,, ... x,, then the value of yi(cl, ..., c,,) is b,. Otherwise, the definition of the functions yi is arbitrary. This definition is consistent, for the wffs j?,, ..., et are false by the assignment a,, ...)a,, b,, ..., b,. Because the valuation of the terms of %(x,, ...)x,) by the assignment y,, ..., P)k, %, ...,a, is the same as that of the corresponding terms of B(x,, ...) x,, y,, ..., yn) by the assignment a,, ...)a,, b,, ..., b,, (x,)... (x,) %(xl, ..., x,) is false by the assignment p,, ..., yk. The translatability of the wffs with functional variables into wffs with predicate variables implies that each of the theorems of chapter V has its analogue here. The theorem concerning the Skolem normal form now takes a specially simple form, the proof of which may be sketched. Corresponding to every wg,one can construct another w8 in prenex normal form with only existential quantifiers, so that both wgs are valid in exactly the same domains. We may assume the wff from which we start to be in prenex normal form and to begin with an existential quantifier. If it should begin with a universal quantifier, we add an existential quantifier at the beginning of the prefix, e.g. ( E x ) , and subjoin the conjunction term x = x to the matrix. x is supposed not to occur in the wff in its original form. Let (Ex,) ... (Ex,) be the sequence of the first existential quantifiers and containing no universal quantifier. ( y ) be the next quantifier; %(x,, ...)x,, y ) the rest of the wff. We replace (Ex,) ... (Ex,)(y)%(x,, ..., xm,y ) by (Ex,)... (Ex,)(Ey)(fx, ... xm=y & %(z,, ..., z,, y ) ) , where f is a new functional variable. We restore the prenex normal form by placing )
104
WFFS WITH FUNCTIONAL VARIABLES
the quantifiers of %(xl,..., x,, y) behind (By)without changing their succession. By a finite repetition of this procedure, we get a wff with only existential quantifiers. I n the following, we shall therefore restrict ourselves to wffs in prenex normal form with only existential quantifiers. This property of the wffs is subsequently assumed without further comment.
11. Solution for wijs having only one monadic functional variable The wff has the form (Ex,) ... (Ex,)%(x,, ..., x,). The only terms occurring in it are x,, ..., x,, fx,, ..., fx,. Instead of
(EX,)* - . (xxm)%(x1> * * . > xm)7 we shall write (Ex,) ... (Exm)%(xl, ..., x,, fx,, ..., fx,). The decision problem shall be treated only in the form I. The wfl is universally valid, if it is valid in the domains with 1 , 2, ..., m+ 1 elements. Let the wff be valid in the domains with 1, ..., m+ 1 individuals. Further, let D be a domain having more than m+ 1 elements and let p be a monadic function over this domain. We shall show that the wff is true in D by v. We take an arbitrary element a of D and designate the elements a , pa, ppa, .,. by voa, pla, p2a, .... We distinguish two cases. 1) There are no numbers p and q such that p > q , ppa=qp and p-q m+l. I n this case, we find a n element b of the set (you,Flu, vza, ...) such that the elements b, vlb, ..., pmb are different from each other. For instance a, as well as any element via, is an element with this property. According to our supposition (Ex,) ... (Ex,) %(xl, ..., x,) is valid in a domain with m+ 1 elements. We shall show that this implies the validity in the domain D. We now consider the domain (b, v,b, ..., v,b) which may by designated by D,. I n this domain, we define a function x by Xvib=vi+,b(l i+ 1 m ) , xp,b= b. Let xoc, xlc, xzc, ... again be abbreviations for c, xc, xxc, .... According to our supposition, there are elements c,, ..., c, in D, such that 'LT(c,, ,.., cm, xc,, ..., xc,) is true. Since the domain D, consists of m+ 1 elements, it has an
<
<
<
105
SPECIAL CASES
element, say xib, which is not identical with one of the elements ..., c,. The definition of x in D, makes it obvious that if '%(a,, ..., d,, xd,, ..., Xd,) is true, then %(xd,, ..., xd,, xxd1, ..., x x d m ) is true for arbitrary d,, ..., d,, since for any elements di and dk, di=dk and xdi=xdk are both true or both false. Therefore, Wxm-jc1, -..,Xm-jCm, xm+l--iC1, * * * ? Xm+l--l .cm ) is true. None of the elements xm+c1, ..., xm+crn is identical with Xmb, since cl, ..., c, were not identical with xjb. We thus have found elements el, ..., em such that %(el, ..., em, Xe,, ..., Xe,) is true, every e, being different from xmb. Since the function x in D,and the function p in D do not differ as regards the elements el, ..., em, %(el, ..., em, pel, ..., pe,) is true in D. This means that (Ex,) ... (Exm)%(xl, ...,x,, px,, ...,px,) is true in D. 2) There are numbers p and q such that p>q, ppa=pqa, and p-q m+ 1. Let p and q be such a pair. We consider the domain D,consisting of the elements p p , pq+,a,..., p,,-,a. We define a function x in D, by ~ p ~ a = p ~ +(q+ , a , 1 if 1 p-I), and xp,-,u=p,,a. The function x for this domain is the same as cp in D as far as elements of D, are concerned. According to our supposition, c,
<
<
EX^)
<
(Exrn)%(Xl,
xm,
*-.,
xxm)
is true in D,;this immediately implies that
(Ex,) *.. (Ezrn)%(Xl> .**,
Xm,
* * * 7
~
m
)
is true in D. Since p was arbitrary, our wff is valid in D.
111. Xolution for W ~ having S prefixa containing only one existential quantifier If ( E x ) is the quantifier, the terms of the wff different from x have a form fx, gxx, hxxx, and so forth. It is easy to see that in this wff the n-adic funct.ions (n >, 2) can be replaced by monadic functions in writing g,x, h,x, ... for gxx, hxxx, .... We may therefore assume the wff to have a form (Ex)(ZL(x, flx, ..., f,x).
106
is equivalent to
WBFS WITH FUNCTIONAL VARIABLES
(fi) -.-(fn)(Ez)Wx,f i Z ,
f24
(Ez)(y1) (y,)%(x, 91,
9n).
The decision problem for this case therefore reduces to that for equality formulas. This solution is obtained by a repeated application of a general elimination theorem corresponding to the elimination theorems E23-E25 of IV, 5 2 . The theorem, or better the theorems, run as follow. E27. Let f be a monadic functional variable occurring in a wff %(x, fx) only in the form fx. %(x, fx) may contain quantifiers (functional and individual ones) and free variables. (f)(Ex)%(x, fx) is then equivalent to (Ex)(y)%(x, y), where y is a new variable. Likewise, let '$3 be a wff in which the dyadic functional variable g occurs only in a form gxa, a being possibly different in the different places. To express this we write '$3 in the form %,(x, gxy). Let E result from '$3 by replacing every term gxa by ha, where h is a new monadic functional variable. E can be written in the form '$3,,(x,hy). (g)(Ex)B,(x,gxy) is then equivalent to (Ex)(h)B,,(x, hy). If (Ex)(y)%(z, y) is false in D by an assignment 9 for its free variables, there is an element b for every element a of D such that %(u, 6 ) is false by a.For every a we can select a b such that a monadic function y is defined over D and such that %(a, pa) is false by D for every a ; then (f)(Ex)%(x, fx)cannot be true by 9. If (f)(Ex)%(x, fx) is false by an assignment 9, there is a function e, over D such that for every u of D, %(a,pa) and therefore (x)(Ey)%(x, y), is true by SZ. This excludes the truth of (Ex)(y)%(x, y) by D. If (g)(Ex)B,(x,gxy) is false in D by an assignment 9, there is a dyadic function y such that !&,(a, yay) is false for every a by 9. Then to every a there exists a monadic function x defined by (y)(xy=yay) such that !&,(a, xy) is false by SZ. (Ez)(h)%Jx,h y ) is then false by SZ. If (Ex)(h)%,(x,hy) is false by 9, there is a function x for every a of D such that BV(a,xy) is false by 12. For every a we select such a function and call it xa. xa defines a duadic function q
SPECIAL CASES
107
for which for all a and b, vab =Xab. Since %Ja, Vay)is always false by Q, so is (g)(Ez)B&, gxy). In general, special cases of the decision problem for the wffs with functional variables are of course not easier to solve than the corresponding cases for the wffs with predicate variables ; but they offer a different trend of investigation. The decision problem can also be formulated for wffs which contain both functional and predicate variables ; it may be advantageous sometimes t o pass to such wfFs. Definition and valuation of such wffs are easily given.
BIBLIOGRAPHY Besides the papers on solvable cases of the decision problem and some other works cited from the text, this list contains the papers on the reduction theory of the decision problem and those original papers in which the impossibility of a general solution of the decision problem was first shown. The numerous works concerning undecidability in special mathematical systems are not included. ACKERMANN, WILHELM(see also Hilbert and Ackermann) : 1. Uber die Erfiillbarkeit gewisser Zahlausdrucke. Mathematische Annalen 100 (1928), pp. 638-649. 2. Untersuchungen iiber das Eliminationsproblem der mathematischen Logik. Math. Annalen 110 (1934), pp. 390-413. 3. Z u m Eliminationsproblem der mathematischen Logik. Math. Annalen 111 (1935), pp. 61-63. 4. Beitrage zum Entscheidungsproblem der mathematischen Logik. Math. Annalen 112 (1936), pp. 419-432. BEHMANN, HEINRICH : 1. Beitrage zur Algebra der Logilr, insbesondere zum Entscheidungsproblem. Math. Annalen 86 (1922), pp. 163-229. 2. Algebra der Logik und Entscheidungsproblem. Jahresbericht DMV 32 (1923), 2. Abt,, pp. 66-67. 3. Entscheidungsproblem und Logik der Beziehungen. Jahresbericht DMV 36 (1927), 2. Abt., pp. 17-18. BERNAYS, PAULund SCHONFINKEL, MOSES(see also Hilbert and Bernays): 1. Zum Entscheidungsproblem der mathematischen Logik. Math. Annalen 99 (1928), pp. 401-419.
CHURCH, ALONZO: 1. An unsolvable theorem of elementary number theory. Amer. Journ. of Math. 58 (1936), pp. 345-363. 2. A note on the Entscheidungsproblem. Journ. of Symbol. Logic 1 (1936), pp. 40-41; Correction ibid., pp. 101-102. 3. Special cases of the decision problem. Revue philos. de Louvain 49 (1951), pp. 203-221. A correction, ibid. 50 (1952), pp. 270-272. CHURCH,ALONZO and QUINE,WILLARDVAN OR-: 1. Some theorems on definability and decidability. Journ. of Symbol. Logic 17 (1952), pp. 179-187.
BIBLIOGRAPHY
109
GEGALKINE, I. : 1. Sur 1'Entscheidungsproblem. Russian with French abstract. Recueil math6matique, Moscou 6 (1939), pp. 185-198. 2. Sur le problbme de la rBsolubilitt5 pour les classes h i e s . Russian with French abstract. Moskovski Gosudarstvenni Universitet, Udenye zapiski, 100 (1946), pp. 155-211. GENTZEN,GERHARD : 1. Untersuchungen uber das logische SchlieDen; I, 11. Math. Zeitschrift 39 (1934), pp. 176-210, pp. 405-431. GODEL, KURT: 1. Die Vollstandigkeit der Axiome des logischen Funktionenkalkiils. Monatsh. fur Math. u. Physik 37 (1930), pp. 349-360. 2. Ein Spezialfall des Entscheidungsproblenis der theoretischen Logik. Ergebn. math. Kolloquium 2 (1932). 3. Zum Entscheidungsproblem des logischen Funktionenkalkiils. Monatsh. Math. Phys. 40 (1933), pp. 433-443.
HILBERT, DAVID und BERNAYS,PAUL: 1. Grundlagen der Mathematik. Vol. I , (1934) ( $ 4, d, e,; $ 5). Vol. I1 (1939), ( 5 3, 5).
HILBERT,DAVIDund ACEERMANN, WILFIELM: 1. Grundziige der theoretischen Logik. 3rd ed. 1949 (Springer) (11, $ 2; 111, $ $ l I , 12). HERBRAND, JACQUES : 1. Recherche5 sup la thhorie de la demonstration. Traveaux de la Soci6t6 des Sciences et des Lettres de Varsovie, C1. I11 math.-phys., 33 (1930), 128 pp. 2. Sur le probkme fondamental de la Logique Mathhmatique. Comptes Rendus des SBances de la Socit5tB des Sciences et des Lettres de Varsovie, C1. 111, 24 (1931). KAL~WAR, L ~ S Z: L ~ 1. Eine Bemerkung zur Entscheidungstheorie. Acta litt. ac sci. Reg. Univers. Hung. Franc. Joseph., Sectio sci. math. 4 (1928/29), pp. 248-262. 2. Ein Beitrag zum Entscheidungsproblem. Ibid. 5 (1930/32), pp. 222-236. 3. Zum Entscheidungsproblem der mathematkchen Logik. Verhandl. Internat. Math. Kongr. Ziirich 1932 (2), pp. 337-338. 4. Uber die Erfiillbarkeit derjenigen Ziihlausdriicke, welche in der Nor-
110
5. 6.
7.
8. 9.
10.
BIBLIOGRAPHY
malform zwei benachbarte Allzeichen enthalten. Math. Annalen 108 (1933), pp. 4 6 g 4 8 4 . 'iiber einen Lowenheimschen Satz. Acta litt. ac scient., math. 7 (1934/35), pp. 112-121. Zuriickfiihrung des Entscheidungsproblems auf den Fall von Formeln mit einer einzigen binkiren Funktionsvariablen. Compositio Mathematica 4 (1936), pp. 137-144. Zur Reduktionstheorie des Entscheidungsproblems. Norsk Mlatematisk Tidsskrift 19 (1937), pp. 121-130. On the reduction of the decision problem. First paper. Ackermann prefix, a single binary predicate. Journ. of Symbol. Logic 4 (1939), pp. 1-9. Contributions to the reduction theory of the decision problem. English with Russian abstract. Acta math. Acad. Sci. Hung. I, 73 (1950), pp. 6 6 7 3 . Contributions to the reduction theory of the decision problem, fourth paper. Acta Math. Acad. Sci. Hung. 11, 1951, pp. 125-142.
K A L M ~LASZL~ R, and SURANYI,JANOS: 1. On the reduction of the decision problem. Second paper. Godel prefix, a single binary predicate. Journ. of Symb. Logic 12 (1947), pp. 65-73. 2. On the decision problem. Third paper. Pepis prefix, a single binary predicate. ibid. 15 (1950), pp. 161-173.
LANaFORD, COOPER HAROLD : 1. Some theorems on deducibility. Annals of Mathematics. 28 (1926/27), pp. 16-40. 2. Theorems on deducibility (Second paper), ibid., pp. 459-471. LOWENHEIM,LEOPOLD : 1. iiber Moglichkeiten im Relativkalkiil. Math. Annalen 76 (1915), pp. 137-148. MCKINSEY,J. C. C.: 1. The decision problem for some classes of sentences without quantifiers. Journ. of Symb. Logic 8 (1943), pp. 61-76.
PEPIS,JOZEF : 1. Beitriige zur Reduktionstheorie des logischen Entscheidungsproblems. Acta Sci. Math. Szeged 8 (1936), pp. 7-41. 2. Untersuchungen iiber das Entscheidungsproblem der mathematischen Logik. Fund. Math. 30 (1938), pp. 257-338. 3. Eine Verfahren der mathematischen Logik. Journ. of Symb. Logic 3 (1938), pp. 61-76.
BIBLIOGRAPHY
111
POST, EMIL L.: 1. Formal reductions of the general combinatorial decision problem. h e r . Journ. of Math. 65 (1943), pp. 197-215.
PRESBURGER, M. : 1. iiber die Vollstandigkeit gamer Zahlen, in welchem tritt. Comptes Rendus du Slaves. Warsaw 1930, pp.
eines gewissen Systems der Arithmetik die Addition als einzige Operation hervorI. Congrbs des Mathematiciens des Pays 92-101.
QUINE, WILLARDVAN ORMAN (see also Church and Quine): 1. On the Logic of Quantification. Journ. Symbol. Logic 10 (1945), pp. 1-12.
S C H ~ T T KURT E, : 1. Untersuchungen zum Entscheidungsproblem der mathematischen Logik. Math. Annalen 109 (1934), pp. 572-603. 2. f i e r die Erfiillbarkeit einer Klasse von logischen Formeln. ibid. 110 (1934), pp. 161-194. 3. Schlul3weisen-Kalkuleder Priidikatenlogik. ibid. 122 (1950) pp. 47-65.
SKOLEM, THORALF : 1. Untersuchungen uber die Axiome des Klassenkalkiils and uber Produktations- und S-ationsprobleme, welche gewisse Klassen von Aussagen betreffen. Skrifter utgit av Vidensk. i Krktiania, I, Math.nat. Klasse 1919, no. 3, 37 pp. 2. Logisch-kombinatorische Untersuchungen uber die Erfiillbarkeit oder Beweisbarkeit mathematischer Siitze nebst einem Theorem uber dichte Mengen. Ibid. 1920, no. 4, 36 pp. 3. Uber die mathematische Logik. Norsk Mat. Tidsskrift 106 (1928), pp. 125-142. 4. Uber einige Satzfimktionen in der Arithmetik. Skrifter Norsk Vid. Akademi Oslo, I mat.-nat. Klasse, no. 7 (1931), 28 pp. 5. Ein kombinatorischer Satz mit Anwendung auf ein logisches Entscheidungsprobleni. Fund. Math. 20 (1933), pp. 254-261. 6. Uber die Erfdlbarkeit gewisser Ziihlausdrucke. Skrifter Norsk Vid. Akademi Oslo, I, Mat.-nat. Klasse, no. 6 (1935), 14 pp. 7. Uber die Erfiillbarkeit von einigen Zahlausdrucken. Vid. Skrifter, Oslo, no. 8 (1935). 8. Ein Satz iiber Zahlausdrucke, Acta Sci. Math. Szeged 7 (1934/35), pp. 193-199. 9. Einige Reduktionen des Entscheidungsproblems. Avh. Vid. &ad. Oslo I, Mat.-nat. Klasse no. 6 (1936), 17 pp.
112
BIBLIOGRAPHY
SURANYI, J h o s (see also Kalmar and Suritnyi): 1. Zur Redulrtion des Entscheidungsproblems des logischen Funktionenkalkiils. Mat. es Fizikai Lapok 50 (1943), pp. 51-74. 2 . Reduction of the decision problem to formulas containing a bounded number of quantifiers only. Proc. Xth Int. Congr. Philos., Amsterdam, I, (1949), pp. 759-762. 3. Contributions to the rcduction theory of the dccision problem, fifth paper. Acta Math. Acad. Sci. Hung. I1 1951, pp. 325ff.
TARSKI,ALFRED: 1. Der Wahrheitsbegriff in den formalisierten Sprachen. Studi aphilosophica, Lemberg 1 (1936), pp. 261-405. 2. Actual. sci. industr. 394, pp. 1-11, Paris 1936. 3. A decision method for elementary algebra and geometry. The Rand Corporation, Santa Monica, California, (1948), 60 pp. TURING,ALANMATHISON: 1. On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. SOC.42 (1936/37), pp. 230-265. A correction, ibid. 43 (1937), pp. 544-546. TRACHTENBROD, B. A.: 1. (Impossibility of an algorithm for the decision problem in k i t e classes). Russian. Doklady Akademii Nauk SSSR, n.s., 70 (1950), pp- 569-572.
VON WRIGHT,G. H.: 1. On the idea of logical truth (I).SOC.Sci. Fennica. Comment. phys.math., vol. 14, no. 4, 1948, 20 pp. 2. On the idea of logical truth (11),ibid., vol. 15, no. 10, 1950, 45 pp. 3. On double quantification. Ibid. vol. 16, no. 3, 1952, 14 pp. W. : 1. Decision problem in group theory. Proc. Xth Int. Congr. Philos., Amsterdam 1948, vol. I , pp. 373-376.
SMIELEW,
INDEX Ackermann, W. 34, 38, 60, 61, 67, 72, 86 assignment 5, 99 Behmann, H. 34, 41 Bernays, P. 34, 41, 70, 72 bound variable 2 Church, A. 4, 23, 86, 89, 93 conjunction 3 conjunction, sign of - 1 conjunctive normal form 19 decision problem 22 Dedekind, R. 55 disjunction 3 disjunction, sign of - 1 disjunctive normal form 20 dyadic functional variable 99 dyadic function 99 dyadic predicate variable 1 dyadic propositional function 4 equaIity, sign of - 1 equality formulas 24 equivalences 12 equivalent 13, 17 elimination theorems 15, 37, 106 existential quantifier 1 free variable 2 function 99 functional variable 99 GBgalkine, I. 86 Gentzen, G. 93 Godel, K. 61, 75, 93 Herbrand, J . 85, 93 Hilbert, D. 34, 41, 60 individual 4 individual variable 1 Kalmar, L. 61, 67, 75 logical constants 1 Lowenheim, L. 24, 34, 50
matrix 21 McKinsey, J. C. C. 60 monadic propositional function 4 monadic predicate variable 1 monadic function 99 monadic functional variable 99 n-adic function 99 n-adic functional variable 99 n-adic predicate variable 1 n-adic propositional function 4 negation 3 negation, sign of - 1 negation-bar 1 normai forms 19, 48 n-validity 93 P-constituent 3 Pepis, J. 61 predicate variable 1 prefix 21 prenex normal form 21 Presburger, M. 60 prime formula 3, 99 primitive symbols 1, 99 propositional function 4 propositional variable 1 quantifier 1 Quine, W. V. 34 rewriting of bound variables 13 satisfiable 8 Schonfkkel, M. 70, 72 Schroder, E. 34, 38 Schutte, X. 75, 83, 93 scope of a quantifier 2 semantic truth-definition 10 S-formulas I5 Skolem, Th. 34, 48, 50, 60, 72, 86 Skolem normal form 48 Smielew. W. 60
114
Puranyi, J. 61, 85 syntactical truth-definition 10 Syntactical variables 3 Tarski, A. 60 tautology, tautologous 19 term 99 term of a conjunction 3 term of a disjunction 3 Trachtenbrod, B. A. 23 Turing, A. 23 universal quantifier 1
INDEX
universal validity 9 vacuous quantifiers 13 validity 8 valuation in arbitrary domains 9 valuation in finite domains 4 valuation of formulas 4, 100 valuation rules 5, 100 variables 1 von Wright, G. IT. 34, 88 well-formed formulas (wffs) 1, 99
