Decidability and Essential Undecidability Hilary Putnam The Journal of Symbolic Logic, Vol. 22, No. 1. (Mar., 1957), pp. 39-54. Stable URL: http://links.jstor.org/sici?sici=0022-4812%28195703%2922%3A1%3C39%3ADAEU%3E2.0.CO%3B2-U The Journal of Symbolic Logic is currently published by Association for Symbolic Logic.
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at http://www.jstor.org/journals/asl.html. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission.
JSTOR is an independent not-for-profit organization dedicated to and preserving a digital archive of scholarly journals. For more information regarding JSTOR, please contact
[email protected].
http://www.jstor.org Sun Jun 17 04:46:37 2007
THE JOURNAL OF SYMBOLIC LOGIC
Volume 22, Number 1, March 1957
DECIDABILITY AND ESSENTIAL UNDECIDABILITY HILARY PUTNAM
1. There are a number of open problems involving the concepts of decidability and essential zcndecidabi1ity.l This paper will present solutions to some of these problems. Specifically: (1) Can a decidable theory have an essentially undecidable, axiomatizable extension (with the same constants) ? 2 (2) Are all the complete extensions of an undecidable theory ever decidable ? We shall show that the answer to both questions is in the affirmative. In answering question ( I ) , the decidable theory for which an essentially undecidable axiomatizable extension will be constructed is the theory of the successor function and a single one-place predicate. It will also be shown that the decidability of this theory is a "best possible" result in the following direction! the theory of either of the common diadic arithmetic functions and a one-place predicate; i.e., of addition and a one-place predicate, or of multiplication and a one-place predicate, is undecidable. 2. Before establishing the main result, it is convenient to give a simple proof that a decidable theory can have an axiomatizable (simply) undecidable extension. This is, of course, an immediate consequence of the main result; but the proof is simple and illustrates the methods that we are going to use in this paper. For this purpose, we select the theory of the successor function (call Received October 4, 1956. 1 The terminology of this paper is that of Undecidable theories, Tarski, Mostowski, and Robinson, North Holland Publishing Co., Amsterdam (1953). This work will be cited as "U.T.". A solution to problem (1) has erroneously been announced by Myhill (Solution of a problem of Tarski's, this JOURNAL, vol. 21 (1956), pp. 49-51). Actually Myhill has solved a related problem; but an answer to (1) does not follow from what he proves, as he asserts. (Cf. section 7., below). (Except for section 7) attention in the present paper is confined to theories with a finite number of constants. Kreisel has previously solved problem (1) for theories which use an infinite number of constants. A statement of Kreisel's proof appears in his review of the article by Myhill just cited; see Mathematical reviews, vol. 17, no. 8 (Sept. 1956), p. 815. 2 This is easily seen to be a reformulation of a problem in U.T., p. 18. (Cf, the discussion below). From now on, when the term 'extension' is used, 'with the same constants' will be understood. 3 This problem was suggested by G. Kreisel whose interest and infectious enthusiasm have led me to work on these questions.
40
HILARY PUTNAM
it 'R'). This theory is d e ~ i d a b l e .If~ t o R we adjoin two new individual constants, a and b,5 and no new axioms, we obtain another theory R'. A sentence of R' is valid only if its universal generalization with respect to a and b is valid in R;'so R' is likewise decidable. In the terminology of U.T., R' is an inessential extension of R. Let us define 0 as a, 1 as S(a) ("the successor of a"), 2 as S(S(a)), etc. And finally, let us construct a theory L by adding to R' the following axioms : where m,, m,, m,, .. . run through the membership of some set of positive integers which is recursively enumerable but not recursive (for the sake of definiteness, let us take the set of Godel numbers of theorems of quantification theory). We now claim: THEOREM1. L is recursively axiomatizable, and (simply) undecidable. Proof : i) L is axiomatizable: we have given a recursively enumerable set of axioms for L. But, according to Craig's theorem6 every theory that can be axiomatized with a recursively enumerable set of axioms can be axiomatized with a recursive set of axioms. So L is axiomatizable in the sense of U.T. (recursively axiomatizable) . ii) L is undecidable: it suffices to show that b f ~ z is not a theorem of L unless it is an axiom; in other words, if n does not belong to the set {m,, m,, m,, . . .), then b=n is consistent with all the axioms bfm,. For if b=n were inconsistent with the axioms of L, b=n wocld have to be inconsistent by itself (since it entails all of those axioms), so -(b=n) would be a theorem of R', and (x)-(x=n) would be a theorem of R', which is absurd. iii) L is not essentially undecidable: for if n is any integer not in (m,, m,, m,, . . .), the theory obtained by adding b=n as sole new axiom to R' U.T., p. 64. Also, a decision method for the elementary theory of the successor function and an arbitrary one-place predicate is given in section 3. below. This can, of course, be used t o decide sentences of R. Logical signs are used as names of themselves throughout the present paper, and not in their object-language use. Craig's method is as follo~vs(012 axiomatizability witl2in a system, this JOURNAL, vol. 18 (1953) pp. 30-32): let {A,, A,, . . . } be a recursively enumerable but not recursive set of axioms for a theory T. Replace each axiom A i b y the conjunctions whose members are Ai repeated 9 t times, for each n such t h a t n is the number of a proof t h a t A, belongs to the set {A,, A,, . . . } (or rather t h a t the Godel number of A i belongs t o the corresponding recursively enumerable set of integers). The recursiveness of the new axiom set follows from the fact that the set of pairs (n, A) such t h a t A belongs t o {A,, A,, . . . } and n is the number of a proof t h a t this is the case (in a suitable formalism) is recursive.
DECIDABILITY AND ESSENTIAL UNDECIDABILITY
41
is a consistent extension of L, by the remark just made; and this theory is decidable because it is a finite extension of R' and R' is decidable. q.e.d. Thus we have that a decidable theory may have an undecidable and axiomatizable extension: for R' and L are two theories that stand in just this relation to one another.
3. In this section we shall establish the decidability of a certain simple theory G: this will serve as a basis for showing, in the next section, that a decidable theory (an inessential extension of G) may have an axiomatizable and essentially undecidable extension. G is the theory of the successor function and a single one-place predicate; i.e., G has a single monadic operator S, and a single monadic predicate P. The variables of G have arbitrary integers as values; S(x) means "the successor of x"; and P designates an arbitrary class of integers. A sentence of G is valid if it is true under this unterpretation (for all values of P). For convenience, let us also introduce into G the symbol P r for "the predecessor of x." Evidently P r is definable in terms of S as follows: Instead of S(x) we shall henceforth write x+ 1 ; and likewise x+2 for S(S(x)),x-1 for Pr(x), etc. Since Pr(S(x))=x=S(Pr(x)), we can write x, and not (x+ 1)- 1 ; ~ $ 5 ,and not (x+7)-2; etc. Also, we can "transpose," i.e., rewrite x+3=y-2 as x+5=y or x=y-5, etc. The decision method for G will be given in four lemmas. We choose the decision problem for satisfaability as being a convenient form for our purposes. To introduce a terminology and notation we shall employ from now on: P(x)P(x+l)P(x+2) will be written simply P P P , and similarly in similar cases. A formula like PPP (with n terms) will be called a 3-series (n-series). Our procedure in Lemma 1 is in part a variant of a decision procedure for monadic quantification theory invented by Behmann : following him we introduce the special symbols (3x)"( . . .) for "there are at least n x's such that ( . . .)," and (3x)"'(. . .) for "there are exactly n x's such that ( . . .)." LEMMA1 : Every closed formula of G can be effectivelyreduced to. T or 1 7 or to a disjunction of formulas of the forms: a) ~ ( 3 x ) C
(where C is an n-series)
T and 1 ("tee" and "eet") are Quine's symbols for truth and falsity (Methods of logic, Harvard (1950)). They are always eliminated by elementary reduction techniques; or else the whole formula reduces to T or 1. The logical notation in the
-
present paper follows Quine (e.g., in using juxtaposition for conjunction; in using both and - for negation), except that more dots than are strictly necessary for punctuation are sometimes used to facilitate reading. Following U.T., identity is included in each elementary theory as a logical constant.
42
HILARY PUTNAM
b)
(3x)"C (where C is an n-series) (3x)""C ,, ,, conjunctions8 of formulas of kinds a)<) (with C's of the same length) d) in which no two C's are the same. C)
'8
1,
8,
-
Example : ( ~ x ) ( P ( x ) Pl)P(x+2)). (x+ (%)l(P(x)F(x+ 1)P(x+2)).(gx)Z'(P(x)P(x+ 1) P(x+2)) is a formula of the form d). (With n=3.) Proof: Let a closed formula F of G be given. By employing Behmann's proceduresa for monadic quantification theory, we confine each quantifier to a conjunction of prime formulass containing only the variable of quantification and no identity formulas. In detail: The formula F is first written in prenex normal form. The last quantifier in the initial string of quantifiers will be either (3xn) or - ( ~ x ~ ) N .I n the latter case, the second 'N' is considered as part of the matrix; and (in either case) the matrix is put in disjunctive normal form. The existential quantifier (3xn)is then distributed through the disjunction, say as (3xn)Blv (Ixn)B, v . . . . Also, (3x,)B, is replaced by Bi whenever xn does not occur in Bi. And quantifiers are confined, i.e., (3x,)Bi is rewritten as (3xn)Ci.Diwhere Ci is the conjunction of all the prime formulas in Bi containing x,. Thus the quantifier (3x,) now stands only in front of conjunctions of prime formulas, each one of which contains the variable x,. Certain of these formulas (3xn)C, may contain variables y other than x, (in identity formulas). If (3xn)Cican be brought (e.g., by "transposing") into the form (3xn)(xn=y+m.C'(xn)), where y is any variable other than xn, the whole quantification is eliminated, and one writes instead C1(y+m). Otherwise, y must occur in a negated identity formula, and (3xn)Ci has the form (3xn)(xn#y+m.C'(xn)). I n this case we write instead: (4)
c'(y+m) (3xn)(c'(xn))v C'(Y+ m )( 3 ~ n ) ~ ( C ' ( ~ n ) ) *
If there is a variable other than x, in the scope of one of the resulting quantifications, the procedure is repeated. In repeating, (3xn)"(xn#y. CH(xn))would be replaced by
In this way,1° the quantifier (3x,) is confined to conjunctions of prime In the sequel, a single formula will also be called a "conjunction" (with one member). sa Bez:vage tur Algebva der Logrk, insbesondere t u m Entscheidungsproblem, Mathematische Annalen, vol. 9 , pp. 1-36. "Prime formulas" are formulas o f the forms P(x+m), P(x+m), x+m=y+n, x+m f y +n, where m, 11, may be positive, negative, or zero. 10 I f the procedure eventuates in a formula o f the form (3x)"(x# y ) , this is reduced to T. Formulas o f the forms ( 3 x ) ( x = y + m ) and x=x+m are also eliminated.
DECIDABILITY AND ESSENTIAL UNDECIDABILITY
43
formulas containing only the variable x,, and no identity formulas. The same procedure is then applied to the remaining quantifiers in turn. Finally, the formula is placed in disjunctive normal form, and we insure that no formulas of the form (%,)"C occur (with m> I ) by replacing such formulas by (6) ( ~ X , ) C v (3x,)l'C v ( 3 ~ ~v ). .~. v' (ax,)"-l'c. I n this way we obtain a disjunction
where each B, is a conjunction of quantifications of the forms ( g x , ) ~ , (3xj)"C, (3xj)"'C; and where C is a conjunction of formulas of the forms P(x,+n) and P(x,+n). In short, the B, have the form
To get the B, into the form given in the statement of the lemma, we have to put the C's into n-series form. This is done as follows: A term occuring in one of the B, may be of the form x-m. But (3x)(C'(x+ml)C"(x+m2). . .C'k)(x+mk))(3x)(C'(x)C"(x+m,-ml) . . . C(k)(x+mk-ml)); where C(i) is P or P and m l S m , l . . . Lm,; - e.g., (3x)(~(x-3)P(x+7))( 3 x ) ( P ( x ) f j ( x +10)). A constant is added or subtracted in this way in each of the B, to insure i) that no "negative" terms appear (i.e., we may have terms of the form x+m, where m is a positive integer, but not x-m). ii) that the variable of quantification (which will henceforth be written as x) appears as a term once in every B, (without any "plus" or "minus"). Next, it may happen that some "in between" terms are missing from a B,. E.g., (3x)(P(xe3)P(x+7)) has been rewritten as ( 3 4 (P(x)P(x+ lo)), but the intervening terms x+ 1, x+2, . . . , x+9, are now missing. This is remedied by replacing (3x)(P(x)P(x+ lo)) by (3x)(P(x)P(x+ l)P(x+ 10)) v (&)(P(x)P(x+ l)P(x+ 10)). In this way the missing terms are brought in one by one: if we have instead (3x)"(p(x)P(x+ lo)) we write first (3x)"(P(x)P(x+ 1)P(x+ 10) v P(x)P(x+ l)P(x+ lo)) and then we use :
Finally, we may assume that no two C's are the same: otherwise (8) can be trivially simplified. E.g., (3x)"'C implies (3x)"C if m 2 n, and
44
HILARY PUTNAM
the weaker formula may be dropped; and (3x)*'C is inconsistent with (3x)"'C if mf n, and (8) may be reduced to I. This completes the proof of Lemma 1. Since a disjunction is satisfiable if and only if one of the disjuncts is satisfiable, we have a general decision method provided we can find a decision method for formulas of the form (8), where the C's are as described in Lemma 1. Let us make a list of all the n-series (for the given n) not exclzlded by the negative existential quantifications in (8) ; i.e., of all the n-series except C,, C,, etc. (If there are no negative existential quantifications in (9), this list will comprise all the 2" n-series for the given n). The members of this list will be called the permissible n-series. For the sake of an example, suppose n=5, and that the following is the list of permissible 5-series :
PPPPP
PPFPP
PPPHP
PPPPP
PFPPP
BPPPP
PPPPP
PPPPP.
We now proceed to reduce this list in the following way: Suppose integers n, n + l , . . ., n+4 realize PPPPP.loa Then n + l , n+2, . . ., n+5 must realize either PPPPP or PPPPH. We will express thus by saying that (a) in the list above can be succeeded only by (b) or (g). Similarly, we will say that (d) can be preceded only by (c) (since PPPPP is not permissible); and that (h) cannot be preceded by anything at all, although it can be succeeded by (a). Formally, C, can precede C, (C, can succeed C,) only if C, and C, are both permissible, and C, is obtained from C, by deleting the final P or P and prefixing an initial P or P. We express these relations in the following diagram:
Branches going up from an element in the diagram indicate which
.
l o a "Integers n , n+ 1, n+2, . . n+4 realize PPPPP" if and only if t h e integer n satisfies the formula PPPPP; i.e., if and only if P(n)P(n+l)P(n+2)P(n+3)P(n+4) is true. - And similarly in similar cases.
DECIDABILITY AND ESSENTIAL UNDECIDABILITY
45
permissible 5-series can precede i t ; branches going down indicate which can succeed it. Now we reduce the list and the diagram by casting out any 5-series (n-series) that cannot be preceded (no "branches going upJ') or cannot be succeeded (no "branches going down"). Thus we obtain as our reduced diagram :
But in the reduced diagram, (a) cannot be preceded. So we apply the reduction procedure again (as often as is still possible), obtaining in our example :
Since no further reduction is possible, (b), (c), (d), (e), (f), and (g) comprise our final reduced list. (Henceforth this will be called simply the 'reduced list .') The meaning of the reduction procedure should be evident. If the statement that only the n-series in the original list are realized is true (and this is the statement made by the conjunction of the negative existential quantifications in (8)), then the stronger statement that only the n-series in the reduced list are realized must likewise be true. For if (h), say, were realized it would have to be preceded by something or other; and since it cannot be preceded by any permissible 5-series, this would falsify the statement in question. Certain corollaries are immediate: for instance, if the reduced list is empty, or if one of the Cy', Ci: is not in the reduced list, then (8) is not satisfiable. Moreover : LEMMA 2: If there are no formulas of forms b) or c) in a conjunction of formulas as described in Lemma 1, and the reduced list is not empty, the conjunction is satisfiable. Proof: Choose some n-series from the reduced list (say (b), in our example) and interpret P with respect to the integers 1, 2, . . ., n so that this n-series is realized (so that 1, 2, 4 belong to P, 3, 5, to P ) . Since this nseries can be succeeded by some element in the list (in fact, by (c)),we can extend the interpretation to n + 1 so that 2,3, . . . , n+ 1 realize this n-series
46
HILARY PUTNAM
(in the example, by letting 6 belong to P). Thus we can always go one step further "to the right." Likewise, if we have interpreted P so that some integers m, m+ 1, . . ., m+n- 1 exemplify a permissible n-series C, and we have not yet extended the interpretation to m- 1, we simply pick an n-series D that can precede C, and make m- 1 either P or p, - whichever will cause m- 1, m, . . . , m+n-2 to realize D. Thus we can always go one step further "to the left." Hence P can be interpreted in such a way that every integer is assigned either to P or to p , and only n-series in the reduced list are realized. q.e.d. (In fact by the time we have assigned membership in P or in p to the integer 2"+n we must have realized some permissible n-series twice; at the earliest place where this happens, the sequence is made periodic.) LEMMA3 : I f there are formulas of the form b) in a conjunction of formulas as described in Lemma 1, but none of the form c), then the formula is generally satisfiable if and only if it is satisfiable over the integers 1, 2, . . . , m, mI ;(2"+1)kb2"+n+l, in such a way that only C's in the reduced list are realized. (Here k is the sum of the n, in sub-formulas of the form (3%)
niC;c.) Proof: Suppose the formula (8), minus quantifications of the form (3x)"l'C;"", to be satisfied. Since each C? is realized n, or more times in the whole series of integers, there must be some finite subseries (say from m to m+k) such that each Cp is realized n, or more times in the subseries, and only C's in the reduced list are realized in the subseries. Conversely, if there is a finite series (an interpretation of P with respect to some finite sequence of integers 1, 2, 3, . . . , m) which satisfies these conditions, then we can satisfy these conditions in the whole series of arbitrary integers. To do this it is only necessary to extend the interpretation of P to m + l , m+2, etc.; and to - 1, -2, etc. But this can always be dope, as remarked above. Thus we can confine our attention to fipzite sequences of integers (and interpretations of P with respect to these). Let k=Cn,. We wish to show i
that it is sufficient to consider finite series with not more than (2"+ 1)k2"+n+ 1 elements. To prove this, suppose there is a finite series 1, 2, . . . , m which satisfies the conditions, under a certain interpretation of P. From this sequence, it must be possible to pick out (for each i) n, occurrences of CYi (i.e., n, sets of n successive integers which realize C;'). Call these designated occurrences of C;'. (There may also be other, non-designated occurrences of some C:'; but what is important is that we designate exactly n, occurrences of C;'.) We may drop all the integers to the left of the first designated occurrence of any n-series in 1, 2, . . . , m; and also all the integers to the right of the last designated occurrence, and the resulting series will still satisfy the
DECIDABILITY AND ESSENTIAL UNDECIDABILITY
47
conditions. (It will no longer begin with 1, in general, but this can easily be remedied by "renaming" the first integer 'l', etc.) Thus we can always obtain a new series which begins and ends with a designated occurrence. Suppose that between two successive designated occurrences there is a "repetition," i.e., some C, occurs twice. Then we may drop all the CJs between the two occurrences of C,, and also drop the second of the two occurrences, and all conditions are still satisfied. E.g., if we have:
(the C's stand for successive n-series, not for integers, and the asterisks indicate designated occurrences), we may put instead :
and each C is still a possible successor for the preceding C. Also, if the designated occurrences are of C1 and C, respectively (as in the example), we may suppose that no occurrence of either C, or C, appears between the two designated occurences, for similar reasons. Thus, between the two designated C's we will have a series of a t most 2"-2 C's. So given any finite sequence which satisfies the conditions, we obtain a series which contains at most 2"-2 C's between each pair of designated occurrences; hence, a series with at most (k-1)(2"-2)+k, or (2"-l)k-(2"-2) C's. Hence the series contains (2"-l)k-(2"-2)+ (n- 1) integers. q.e.d. Now we shall consider the last case; there are affirmative quantifications of the form (31x)"i'CYi'. In this case, cast ail the CY1' out of the reduced list. Call the result the 'special list.' We now reduce the special list in two different ways : 1) Cast out any element in the special list which cannot be succeeded by any element in the special list. (This is to be done as many times as possible, but an element is not cast out simply because it cannot be Preceded by any element in the list.) Let the elements thus obtained be El, E,, . . . , E,. 2) Cast out any element in the special list which cannot be preceded by any element in the special list. (This is to be done as many times as possible, but an element is not cast out simply because it cannot be succeeded by any element in the list.) Let the elements thus obtained be Dl, D,, . . . , DL. If the first list (El, . . . , E,) is empty, no infinite endless series (of C's in the reduced list) is possible that does not contain some Cyi'. If the second list (Dl, . . . , DL) is empty, no infinite beginningless series (of C's in the reduced list) is possible that does not contain some CY1'. In either case, there must be infinitely many occurences of some of the CTs' if only C's in the reduced list are realized, and (8) is unsatisfiable.
48
HILARY PUTNAM
If neither list is empty, then we state: LEMMA4 : If there are formulas of the form c ) in a conjunction of formulas as described in Lemma 1 , then the formula is generally satisfiable if and only if it i s satisfiable over the integers 1 , 2, . . . , m, m s (2"- l)r+2"+n- 1, i n such a way that only C's in the reduced list are realized, and the integers 1 , 2, . . . , n realize one of the Di, and the integers m-n+ 1, m-n+2, . . . , m realize one of the E,. (Here r i s the sum of the n , and mi in sub-formulas of the forms (ax)"tC:i and (3x)"*'CYi.) Proof: Suppose the formula (8) to be satisfied. Since each C:' is realized a t least ni times, and each Cri' is realized exactly mi times in the whole series of integers, there must be some finite subseries (say from m to m+k) such that each Cyi' is realized ni or more times in the subseries, and each CY8'is realized exactly mi times in the subseries, and only C's in the reduced list are realized a t all. Moreover, no C r i occurs to the "left" or "right" of this subseries. But we have seen that it is possible to have a n endless series (which uses only C's from the reduced list) in which the Cyi' do not occur, only if none but (some or all of) E,, . . . , E, are realized in the series. And it is possible to have a similar series without beginning, only if none but Dl, . . . , DL are realized in it. Thus the integers m- 1, m, . . ., m+n-2 must realize one of the Di ; and similarly m+ k- (n-2), . . . , m+ k+ 1 must realize one of the E,. Therefore, the whole series m- 1 , m, . . . , m+k+ 1 is a finite series of the kind whose existence is asserted in the Lemma. (It does not begin with 1 , in general, but as before this can be remedied by "renaming" m-1 'l'.) Let r=Cn,+Cm,. We wish to show that we can confine our attention i
t
to series with (2"- l)r+2"+n- 1 elements. The argument exactly parallels the argument in the preceding case; this time we will have r + 2 designated occurrences (the Crl, the Cyi', the initial D, and the final E,); and, since we can "condense" asin (15)-(16), we can once again assume that there are at most 2"-2 C's between any two designated C's. Thus our decision method is complete. If P can be interpreted with respect to 1 , 2, . . . , m, m s (2"- l)r+2"+n- 1 , so that the conditions stated in the Lemma are satisfied, we can "continue to the left" and without ever using any C,"I', since this finite series begins ~ v i t ha D,; we can "continue to the right" from the final Ei in similar fashion. And if none of the possible interpretations of P with respect to 1 , 2, , .,., (2"- l)r+2"+11-- 1 satisfies the conditions; (8) is not satisfiable, q.e.d. THEOREM 2. G is decidable. Prooj: Immediate from Lemmas 1-4.
Since G is decidable, it is of course axiomatizable (the set of valid sen-
DECIDABILITY AND ESSENTIAL UNDECIDABILITY
49
tences could be taken as the set of axioms, since these are recursive). For our present purposes, we could use instead of G the theory of one permutation and one one-place predicate. This theory has a single monadic operator, f , a single monadic predicate, P, and the following axioms:
(17)
(i) (x)(3y)(x=f(y))
(ii) (4(y)(f(x)= f ( y ) 2 x=y). Since any model for this theory is isomorphic to the system of arbitrary integers (when f is identified with S), or to the integers modulo m,or is a sum of such models, the decision method just given for G is easily extended to this theory. This yields an example of a finitely axiomatized and decidable theory from which (by the method given in the next section) an essentially undecidable theory can be obtained by simply adding a recursive set of additional axioms. The decision method given also applies if there are any number of oneplace predicates. The major modification required is in the definition of 'n-series': if the formula being tested for satisfiability has m one-place predicates, then an n-series is a possible character of n successive integers with respect to these predicates. E.g., if there are two predicates, PI, P,, then PlP2(x)P,H,(x+ 1) PlP2(x+ 2) is one of the 2mn=64 3-series. 4. Let us construct an inessential extension of G (to be called G') by adding the single individual constant b and no new axioms. To obtain an essentially undecidable extension of G' we make use of the fact that there are disjoint recursively enumerable sets that cannot be separated by any recursive set; i.e., there are a, b such that anb=A, but such that for no recursive set c is it the case that a c c while b n c = A. (Trachtenbrotll has even shown that the following two sets constitute such a pair: the Giidel numbers of theorems of quantification theory, and the Godel numbers of formulas that fail in at least one finite domain.) Let {m,, m,, . . .) and {n,, n,, .. .) be two such sets, and define 0 as b, 1 as S(b), etc.; then we obtain a theory H by adding to G' the axioms:
(18)
(i) P(mi) (ii) P(ni)
(i = I ,2, (i = I, 2,
..j . . .). ,
THEOREM 3. H is axiomatizable and essentially zlndecidable. Proof: (i) The axiomatizability of H follows again from Craig's theorem. (ii) H is consistent (bearing in mind that the sets {m,, m,, . . .) and {n,, n,, . . .) are disjoint). l 1 0 rekursivnoj olde'limosli,Doklady Akaddmii Nauk USSR, vol. 88 (1953), pp. 953-956.
50
HILARY PUTNAM
(iii) H is essentially undecidable. For, assume some consistent extension D of H is decidable. Then the set of integers n such that P(n) is a theorem of D is recursive (call it k) ; k contains all the mi, because P(mi) is an axiom of H (for i = 1, 2, . . .) and D is an extension of H ; and k does not contain any of the n,, because P(ni) is an axiom of H (for i = 1, 2, . . .) and D is a consistent extension of H. Thus k is a recursive set separating {m,, m,, . . .) and {n,, n,, . . .); which is impossible, since these were chosen as inseparable sets. q.e.d.
5. Let us now turn to the question: whether the decidability of G is a "best possible" result.12 Since the theory of the successor function and any number of one-place predicates is decidable, we consider next the theory of addition and a single one-place predicate. Let us call this theory K ; K has a single diadic function symbol and a single monadic predicate P as its extra-logical constants. The variables are interpreted as ranging over positive integers; P stands for an arbitrary set of integers. A sentence of K is valid if it is true under this interpretation (for all values of P). THEOREM 4. K is undecidable. Proof: I t is known that one can formulate an essentially undecidable and the diadic relation and finitely axiomatizable theory in terms of Sq(x?y) (read: "x is the square of y").13 We shall show that it is possible to define Sq(x, y) in terms of and the particular monadic predicate P(x) ("x is a square"). Thus there is an essentially undecidable and finitely axiomatizable theory T with the primitives and P . Since P stands for an arbitrary set of integers in K, all valid sentences of K must remain true when P is interpreted as this predicate. Therefore T is compatible with K, and K is undecidable.14 The following is a possible definition of Sq(x, y) in terms of P : we first define x < y and u= 1, thus
+
+
+
+
and then define
\+'hat (21) says is that x is a square and that the difference between x and the next larger square is 2y+ 1. This is satisfied only if x=y2. q.e.d. l 2 At the referee's suggestion, I stress the informal character of this question. The terms 'immediately stronger,' 'just weak enough,' etc., a t the beginning of section 6. are also used informally. 1 3 U.T., esp. pp. 77-80. l 4 By Theorem 6 of U.T. (given below in section 7.)
51
DECIDABILITY AND ESSENTIAL UNDECIDABILITY
K is undecidable even if the variables are interpreted as ranging over arbitrary integers instead of just positive integers. For a possible definition of Pos(x) ("x is a positive integer") in terms of and P applied to arbitrary integers is
+
(In words: "x is the sum of four squares, and x does not satisfy 2x=x." and P This is true only if x is a positive integer.) Thus the theory of relativized to positive integers can be interpreted in the theory of and P for arbitrary integers; therefore so can the essentially undecidable and finitely axiomatizable theory T referred to above. Instead of K we might have considered M; the theory of multiplication and a single one-place predicate Q. The argument for the undecidability of M is parallel to that for K. Here we use as our finitely axiomatizable and essentially undecidable theory a subtheory of the theory of multiplication and the particular one-place predicate "is an integer of the form 2"'." With this particular interpretation for Q we define B ("is a power of 2"), thus:
+ +
(23) B(x) = d l (y)((3z)(y.z=x) 3 (Y. x=x) v ( 3 ~ ( Q)( 4 . (34('w.~t=y))). In words: "for every y, if y divides x, then y= 1 or y is divisible by some w such that Q(w)." (If x is a power of 2, then every divisor of x is either 1 or is itself divisible by 2; and Q(2).) We establish a correspondence between the integers and the powers of 2, thus: n corresponds to 2", addition to multiplication, and P (i.e., "is a square") to Q. This correspondence is clearly an isomorphism: nt+2", P(?z)= Q(2"). Thus the truth-value of any ~ e t 2 n+met2n.2m=2n+m, ~ , sentence of the essentially undecidable and finitely axiomatizable theory T mentioned above is unaltered when addition is replaced throughout by multiplication, P by Q, and the quantifiers are relativized to B. In this way there results an essentially undecidable and finitely axiomatizable theory in the vocabulary Q.
6 . To recapitulate: we have now shown that G is decidable, and that G', an inessential extension of G, possesses the essentixlljr undecidable, axiomatizable extension H. However, we could not have used in place of G either of the theories immediately stronger (i.e., hl or K ) ; for these are undecidable, though not essentially so. Thus the peculiarity of G : that, although decidable, it possesses an essentially undecidable and axiomatizable extension, - depends on G being just weak enough. If G lacked some notation for expressing the integers (the successor function) or some one-
52
HILARY PUTNAM
place predicates, we could not form H; on the other hand, any obvious strengthening of G (beyond bringing in more one-place predicates) seems to yield an undecidable theory. We turn now to a kind of "converse" of this problem: instead of seeking decidable theories with undecidable extensions, we will seek an undecidable theory all of whose complete extensions are decidable. Let N be the following theory: there are no extra-logical constants; and the axioms are (i = 1, 2, . . .). (24) (gx)""(x = x ) As before (3x)"i (x=x) means "there are exactly mi x's such that x=xJ'; and we assume that {m,, m,, .. .) is some recursively enumerable but not recursive set. THEOREM 5. N is undecidable; and all its complete extensions are decidable. Proof : (i) N is axiomatizable. By Craig's theorem. (ii) N is consistent: let N, be the theory with the following single axiom (where n is any integer not in {m,, m,, . . .)): (25) (3x)"'(x =x) . N, is clearly consistent: and N, is an extension of N, since (25) implies each of the axioms (24). Thus N is consistent. (iii) N is undecidable. For (jx)"'(x=x) is not a theorem unless it is an axiom; i.e., unless n belongs to the set {m,, m,, . . .). And this is not a recursive set. (iv) Every complete extension of N is decidable. By Behmann's method we can decide any sentence of any complete extension C of N provided we know the truth-values of all sentences of the following kinds:
"(X =X) (a) (3%) (b) (3x)"'(x=x) Thus each complete extension is completely characterized by giving one number : the number of individuals (co,or some finite number). This information enables us to assign a truth value to sentences of kinds (a)-(b); and hence (since the method referred to can be used to express any sentence of C as a truth-function of these15) to any sentence of C. 7. In U.T. the following theorem is stated (p. 18): 'Theorem 6. Let T, and T, be two compatible theories such that every constant of T, is also a constant of T,. If T, is essentially undecidable and finitely axiomatizable, 15 The method is in fact contained in the proof of Lemma 1 of section 3.; the only modification is as follows: formulas of the form ( 3 ~ ) ~ ( x #are y ) not reduced to T (as in fn. 10 above), but are instead replaced by ( 3 ~ ) ~ + l ( x = x ) .
DECIDABILITY AND ESSENTIAL UNDECIDABILITY
53
then TIis undecidable, and so is every subtheory of TIwhich has the same constants as TI.' Tarski goes on to remark (p. 19): 'From the point of view of applications, it would be important to know whether Theorem 6 can be improved by assuming that T, is an arbitrary axiomatizable theory (which may not be finitely axiomatizable). We could answer this question affirmatively if we knew that every essentially undecidable theory which is axiomatizable has an essentially undecidable subtheory which is finitely axiomatizable.' However, the question has in fact a negative answer (cf. Theorems 2 and 3 above). Myhill has provided an example of an essentially undecidable, axiomatizable theory without a finitely axiomatizable, essentially undecidable, subtheory. Myhill erroneously claims that this answers Tarski's question. I t does not: for the finitely axiomatizable subtheories of the theory constructed by Myhill are undecidable, though not essentially so. To show that the answer to Tarski's question is in the negative, one must construct an axiomatizable and essentially undecidable theory with a decidable subtheory which uses all of the constants. As remarked above (fn. l ) , Kreisel has previously solved this problem for theories with an infinite number of constants. Indeed, the use of an infinite number of constants materially shortens the argument. The following proof is my own, but the idea is related t o that used by Kreisel: Take as the decidable theory D, monadic quantification theory with an infinite set of individual constants a,, a,, a,, . . . , and an infinite set of predicate constants PI, P,, P,, . . . . Let T(e, m, x) be the recursive predicate: "m is the number of a proof (in a suitable formalism) that x belongs to the recursively enumerable set whose Godel number is e." As the essentially undecidable extension E take the theory with the following axioms: I. P,(an) (for each i, n, such that the recursively enumerable set with the Godel number i contains the integer n). 11. (x)(P,,,(x) 3 -Peji(x)) (for all i, j ; where e , is the Godel number of the following recursively enumerable set: the set of all n such that (3m)(T(i, m, n) . (m')(T(j, m', n) 3 m' > m)).) E is axiomatizable, by Craig's theorem. And every recursive set is definable in E. For let R be a recursive set of positive integers, and let i and j be Godel numbers of R and R respectively: then e,, is also a Godel number of R, and eji is a Godel number of E.Whenever n belongs to R, Pef,(an)is an axiom of E ; and whenever n does not belong to R, Pe,((an) is also an axiom of E, and therefore -Pe,,(an) is a theorem of E, by axiom 11. But a theory in which every recursive set of positive integers is defined is essentially undecidable.16 To show this, let Sb(x) be the Godel substitution '6 In U.T. only the weaker statement is given (p. 49) that a theory is essentially undecidable if every recursive function is definable in it.
54
HILARY PUTNAM
function : that is, the recursive function whose value for any n is the number of the formula that results when a, is put for the variable 'x' throughout the formula whose number is n. Now suppose that a consistent extension F of E were decidable. Let Prov(x) be the recursive predicate: x is the number of a theorem of F. Then -Prov(Sb(x)) is also a recursive predicate, and is therefore defined in E and hence in F, say as P,. The formula P,(x) has a number, say h. And the formula P,(a,) isprovable in E and hence in F if the integer h has the property -Prov(So(h)), and disprovable if it does not: i.e., the formula is provable if and only if it is not provable, which yields a contradiction. PRINCETON U N I V E R S I T Y
http://www.jstor.org
LINKED CITATIONS - Page 1 of 1 -
You have printed the following article: Decidability and Essential Undecidability Hilary Putnam The Journal of Symbolic Logic, Vol. 22, No. 1. (Mar., 1957), pp. 39-54. Stable URL: http://links.jstor.org/sici?sici=0022-4812%28195703%2922%3A1%3C39%3ADAEU%3E2.0.CO%3B2-U
This article references the following linked citations. If you are trying to access articles from an off-campus location, you may be required to first logon via your library web site to access JSTOR. Please visit your library's website or contact a librarian to learn about options for remote access to JSTOR.
[Footnotes] 1
Solution of a Problem of Tarski John Myhill The Journal of Symbolic Logic, Vol. 21, No. 1. (Mar., 1956), pp. 49-51. Stable URL: http://links.jstor.org/sici?sici=0022-4812%28195603%2921%3A1%3C49%3ASOAPOT%3E2.0.CO%3B2-U 6
On Axiomatizability Within a System William Craig The Journal of Symbolic Logic, Vol. 18, No. 1. (Mar., 1953), pp. 30-32. Stable URL: http://links.jstor.org/sici?sici=0022-4812%28195303%2918%3A1%3C30%3AOAWAS%3E2.0.CO%3B2-Q
NOTE: The reference numbering from the original has been maintained in this citation list.
