In chapter 2 I introduced the idea of an interpretation for a predicate logic sentence, that is, of a case which determines the truth value for closed sentences of predicate logic. In the definition of chapter 2 I required that every object in the domain of an interpretation have at least one name, I included this requirement because with it I could give a sim- , ple and intuitive truth definition for existentially and universally quantified sentences: I said that an existentially quantified sentence is true in any interpretation just in case at least one of its substitution instances is true in the interpretation. And I said that a universally quantified sentence is true in an interpretation just in case all of its substitution instances are true in the interpretation.
Requiring every object to have a name may have been expedient for teaching fundamentals, but ultimately the requirement is unsatisfactory. Our system of logic should be able to deal with situations in which some objects go unnamed. So henceforth, by an interpretation for predicate logic, I will mean exactly what I meant in chapter 2, except that I will no longer require every object to have a name. I also will streamline the definition somewhat by counting atomic sentence letters as Zero Place Predicates:
D20: An In&rprehtion consists of a nonempty domain of objects, a list of names, and a list of (zero place, one place, two place, and in general many place) predicates. The list of names may be empty, but there must be at least one predicate. For each name, the interpretation specifies the object in the domain which is named by that name; and for each predicate the interpretation specdies its truth value if it is a zero place predicate (an atomic sentence letter), or the objects in the domain of which the predicate is true if it is a one place predicate, or the ordered lists of objects of which the predicate is true if it is a two, three, or many place predicate. If a predicate is not true of an object or ordered lit of objects, it is false of that object or list of objects.
This definition allows us to consider situations in which there are objects without names in the object language. But it makes hash of my definition of truth in an interpretation for quantified sentences.
Before we begin, precision requires a comment on notation. Remember that '(3u)P(u)' is an expression of the metalanguage ranging over closed existentially quantified sentences, with u the existentially quantified variable. Ordinarily, P(u) will be an open sentence with u the only free variable, which is the way you should think of 'P(u)' while getting an intuitive grasp of the material. But strictly speaking, '(3u)P(u)' ranges over closed existentially quantified sentences, the s-substitution instances of which are P(s), the expressions formed by substituting s for all free occurrences of u in P(u)-if there are any free occurrences of u. This detail accommodates vacuously quantified sentences, such as '(3x)A1, as discussed in exercise 3-3.
To work toward new truth definitions for the quantifiers, let's think through what we want these definitions to do. Intuilively, (3u)P(u) should be true in an interpretation iff there is some object in the domain of the interpretation of which the open sentence, P(u), is true. When all objects in the domain had names, we could express this condition simply by saying that there is at least one name, s, in the interpretation for which the substitution instance, P(s), is true in the interpretation. But now the object or objects in virtue of which (3u)P(u) is true might have no names, so this strategy won't work.
We can get around this problem by appealing to the fact that, even if the interpretation we are considering does not include a name for the object we need, there will always be another interpretation which does have a name for this object and which is otherwise exactly the same.
In more detail, here is how the idea works. Suppose we have an interpretation, I, and a sentence (3u)P(u). Intuitively speaking, (3u)P(u) is true in I when I has an object, o, of which, intuitively speaking, the open sentence P(u) is true. We cannot say that (3u)P(u) is true of o by saying that o has a name, s, in I such that P(s) is true in I. We are considering an example in which o has no name in I. But we get the same effect in this way: We consider a second interpretation, If, which is exactly like I. except that in I' we assign o a name. We can always do this, because if I 422 Interpretations, Soundness, and Completeness for Predicate Logic 15-1. Interpretations 223 is one interpretation, we get a second interpretation, 1', which has exactly the same domain of objects, the same list of predicates, the same specification of what is true of what, but which differs from I only by assigning the name s to object o.
We do also have to require that s not be a name which occurs in (3u)P(u). If, in going from I to If, we move a name from one object to another, and this name occurs in (3u)P(u), we may disturb some other aspect of the truth conditions for (3u)P(u). Some new terminology will help in transforming this intuitive idea into a precise definition:
D21: I, is an s-Variant of I iff I, assigns the name s to some object in its domain and I. differs from I at most by having name s or by assigning s to a different object.
With the help of the idea of an s-variant, we can say
D22: (3u)P(U) is true in interpretation I iff, for some name, s, which does not appear in (3u)P(u), there is an s-variant, I., of I in which P(s) is true. 1
EXERCISE 15-1. Give an example of a sentence and an interpretation which shows that D22 would not work as intended if it did not include the requirement that s not appear in (3u)P(u).
The truth definition for the universal quantifier works in exactly the same way, except that we use 'all s-variants' instead of 'some s-variant'. We want to specify the conditions under which (Vu)P(u) is true in I. Intuitively, the condition is that P(u) be true of all objects in I. We capture this idea with the requirement that P(s) be true in all s-variants of I:
D23: (Vu)P(u) is true in interpretation I iff, for some name, s, which does not appear in (Vu)P(u), P(s) is true in all s-variants of I.
EXERCISE 15-2. Give an example of a sentence and an interpretation which shows that D23 would not work as intended if it did not include the requirement that s not appear in (Vu)P(u).
I hope you will find these new truth definitions for quantifiers to have some plausibility. But they are a bit abstract and take some getting used to. The only way to become comfortable with them is to work with them. We can get the needed practice, and at the same time lay the groundwork . for the next sections, by proving some basic lemmas.
Consider a predicate logic sentence, X, and an interpretation, I. Now consider some name which does not occur in X. If we reassign the name to some new object in the interpretation, this should make no difference to the truth value of X in I. X does not constrain the referent of the name in any way. The same thing goes for a predicate symbol not occurring in X. Intuitively, X and the unused predicate have no bearing on each other. So what the predicate is true of (or the truth value of a zero place predicate) should make no difference to the truth or falsity of X:
L25: Let X be a sentence and I and I' two interpretations which have the same domain and which agree on all names and predicates which occur in X. Then X is true in I iff X is true in 1'.
By 'agreeing on all names and predicates which occur in X', I mean that, for each name which appears in X, I and I' assign the same object to that name, and for each predicate appearing in X, I and I' specify the same truth value or the same collection of objects of which the predicate is true. For names and predicates not appearing in X, I and I' may make different assignments.
We prove L25 by induction on the number of connectives in X. For the basis case, consider an atomic X and an I and I' with the same domain which agree on all names and predicates in X. An interpretation explicitly provides the truth values in terms of the extensions of the used predicates and names (e.g., 'Pa' is true in I just in case the thing named 'a' is in the extension which I assigns to 'P'). Since I and I' agree on the predicates and names in X, they assign X the same truth value.
For the inductive case, assume, as inductive hypothesis, that L25 holds for all X with n or fewer connectives and all I and I' agreeing on X, as before. We must separately consider each of the connectives. For example, suppose that X has the form Y&W. Then X is true in I iff both Y and W are true in I. But since Y and W both have fewer connectives than X, we can apply the inductive hypothesis to conclude that Y is true in I iff Y is true in 1'; and W is true in I iff W is true in 1'. Finally, Y and W are both true in I' iff X (=Y&W) is true in It, which is what we need to show in this part of the argument.
EXERCISE 15-3. Carry out the inductive step of the proof of L25 for the other sentence logic connectives, modeling your proof on the example just given for '82.
Now assume that X has the form (3u)P(u). The ideas are not hard, but keeping everything straight can be confusing. So let's introduce some further terminology: For I' I will write I(X) to remind us that I(X) is an interpretation with the same domain as I and just like I so far as names and predicates in X are concerned, but differing arbitrarily from I on other predicates and names. In considering the case of X = (3u)P(u), instead of writing out I((3u)P(u)), I will write just I(P). Finally, I will write I(P,s) for an otherwise arbitrary interpretation agreeing with I on domain, on P, and on s.
So suppose that (3u)P(u), I, and I(P) have been given. Suppose that I makes (3u)P(u) true. Definition D22 then tells us that there is a name, s, not appearing in (3u)P(u), and an s-variant of I, I,, where P(s) is true in I,, Now we change I,. We keep 1,'s assignment of s and of all the names and predicates in (3u)P(u), and we change everything else to look just like I(P). The resulting interpretation, I(P,s), is an s-variant of I(P). Furthermore, the inductive hypothesis applies to tell us that, since P(s) is true in I,, P(s) is true in I(P,s). D22 applies to these facts to yield the conclusion that (3u)P(u) is true in I(P).
I have shown that if (3u)P(u) is true in I, it is true in I(P). But exactly the same argument works in the reverse-direction-if I(P) agrees with I on all vocabulary in (3u)P(u), then I agrees with I(P) on this vocabulary. So we may conclude that (3u)P(u) is true in I iff it is true in I(P), as was to be shown. (I did not use an iff in the chain of inferences in the previous paragraph because doing so makes it harder to keep clear about the existential ~uantifiers, 'there is an s' and 'there is an I,'. I will avoid certain 'iffs' in the proof of the next lemma for the same reason.)
EXERCISE 15-4. Carry out the inductive step of the proof of L25 for the universal quantifier.
Let's move on to another very intuitive fact, but one which is a bit tricky to prove. Consider a sentence of the form R(s,t), a perhaps very complex sentence in which the names s and t may (but do not have to) occur. Let I be an interpretation in which s and t refer to the same object. Then it should not make any difference to the truth of R(s,t) in I if we replace any number of occurrences of s with occurrences oft or occurrences of t with occurrences of s. In I, s and t are just two different ways of referring to the same thing. R(s,t) says something about this thing, and how one refers to this thing should not make any difference to the truth of R(s,t) in I. (At this point it would be a good idea to review the discussion of extensional semantics in section 9-2.)
L26: Let R(s,t) be a closed sentence in which the names s and t may occur. Let I be an interpretation in which the names s and t refer to the sameobject. Let R'(s,t) arise by replacing any number of instances of s by t or instances oft by s. then R(s,t) is true in I iff R1(s,t) is true in I.
I have stipulated that s and t do not have to occur in R(s,t) to cover the important case in which all occurrences of s in a sentence P(s) get replaced by occurrences of t.
EXERCISE 15-5. Begin the proof of L26 by carrying out the basis step and the inductive step for the sentence logic connectives.
The complications in the inductive step for L26 call for writing it out in some detail. In what follows, take care to understand what I mean by 'r = s'. 'r' and 's' are metavariables over names. So 'r = s' means that the name picked out by 'r' is identical to the name picked out by 's', that is, that r and s are the same name. 'r = s' does not mean the object referred to by the name picked out by 'r' is the same as the object referred to by a different name picked out by 's'.
Now let's assume (inductive hypothesis) that L26 holds for all R(s,t) with n or fewer connectives. And let's consider the case of R(s,t) with the form (3u)Q(u,s,t). R1(s,t) is then the sentence (3u)Q1(u,s,t). Let interpretation I be given with names s and t having the same referent. In outline, the argument runs as follows:
(1) Suppose that I makes (3u)Q(u,s,t) true. (Assumption)
(2) Then there is a name, r, and an r-variant, I, of I, such that I, makes Q(r,s,t) true. (By (1) and D22)
(3) Suppose that r f s and r f t. (Assumption, to be discharged)
(4) Then I, makes Qf(r,s,t) true. (By the inductive hypothesis applied to (2) and (3))
(5) Then I makes (3u)Qf(u,s,t). (By D22 applied to (4))
I want to be sure you understand step (4) and the role of step (3). First, you might have thought that D22 guarantees (3). But that happens only if both s and t actually occur in (3u)Q(u,s,t). Since we want out proof to cover, for example, a sentence in which just t occurs and in which we replace all occurrences oft with occurrences of s, we have allowed that s and t don't have to occur. Next, remember that to apply the inductive hypothesis to switch around the names s and t, we need to be considering an interpretation in which s and t both refer to the same object. By assumption, I is such an interpretation. But in step (4) we need this to be 426 Inkrjnutatiar, Soundness, and Cmnpkteness for Predicate Logic 15-1. Interpretations 227 true of I,. If r # s and r # t, we're OK. According to D22, I, arises from I by at most reassigning r to a new referent. When r # s and r # t, s and t still have their mutual referent, so the inductive hypothesis can be applied.
To get ready to discharge the assumption (3), let's see what can go wrong if (3) fails. Let's suppose that r = s. In this case, when we apply D22 to make I, out of I, we might have the situation pictured for I, in figure 15-1.
In I, s and t both refer to the object 0,. We apply D22, which says that there is an r-variant, I,, of I, differing at most from I by assigning a new referent, which I'm calling 'oi, to r (or is an object which makes the existential quantification true). But if r = s, this means assigning r, that is, s, to the object or, which in general will be distinct from q. So in I, we may not have available the condition that s and t have the same referent, the condition needed to apply the inductive hypothesis.
To get around this difficulty I will argue by cases. Case 1: Neither s nor t actually occurs in (3u)Q(u,s,t). Then there is nothing to prove, since there are no occurrences of s and t to switch around. Case 2: s and t both occur in (3u)Q(u,s,t). D22 requires that r not occur in (3u)Q(u,s,t). So in this case r # s and r # t, we have assumption (3) available, and the proof (1)-(5) can proceed.
Case 3: t but not s actually occurs in (3u)Q(u,s,t). (The case in which s but not t occurs is the same.) To remind us that s occurs vacuously, I will put parentheses around s, like this: (3u)Q(u,(s),t). If, in this case, r happens by luck to be distinct from s, the proof (1)-(5) applies. So I will also assume that r = s. In this case we have the situation for I, pictured in figure 15-1, and the inductive hypothesis will not apply because s and t no longer have the same referent. In addition, we won't be able to apply
D22 in step (5). When r = s, r, that is, s, will get put in for occurrences oft when we exchange Q(r,(s),t) for Q1(r,(s),t). Then when we try to apply D22 to reform the existential quantification, the u will get put into the wrong places.
To resolve these difficulties, I must accomplish two things. I must show that I can pick another name, r', with r' # s and f t, and assign r' to 0,. Then I must reassign s as a name of q. If I do these two things, then s and t will again have the same referent, so that I can apply the inductive hypothesis in step (4); and I will again be using a name, r' # s and # t, so that D22 will unproblematically apply in step (5).
Once this problem is clearly explained it is easy to solve, with the help of lemma L25. I pick a new name, r', not occurring in Q(r,(s),t), # s and # t. L25 tells us that Q(r,(s),t) has the same truth value in a new interpretation, I,., that it had in I,, where I,, is just like I, except that r' has been assigned as an additional name of or. Next I apply the inductive hypothesis to Q(r,(s),t) and the interpretation I,,. In I,,, r' and r (that is, s) both name or. So the inductive hypothesis allows me to replace all occurrences of r with r'. I now have Q(rl,(s),t) true in I,,, with s not actually occurring in Q(rl,(s),t). Consequently, I can again apply L25 to tell me that Q(rl,(s),t) is also true in 13, an interpretation just like I,, except that s has been reassigned to 0,. At this point 13 is an rt-variant of I, r' # s and C t, and s and t are both referents of ot so that I can carry out steps (4) and (5) of the foregoing proof using 13, instead of I,,.
We are almost done. I have shown that if I makes (3u)Q(u,s,t) true, then I makes (3u)Q1(u,s,t) true. But the argument works in exactly the same way in the opposite direction. So we have shown that I makes (3u)Q(u,s,t) true iff it makes (3u)Q1(u,s,t) true, completine: this Dart of - " the proof of L26.
EXERCISES 15-6. In a more advanced logic text, this sort of informal proof would be written up much more briefly. I have spelled it out in some detail to help you learn how to read and study such a proof. To further practice study of an informal proof and to appreciate better how complicated it really is, formalize the proof as a natural deduction. Use 'Mod(1,X)' for 'X is true in 1', '(3r)' for 'There is a name, r', '(31,)' for 'There is an r-variant, I,, of 1', and so on. I suggest that you formalize the initial proof (1)-(5), with the undischarged assumption of step (3), being sure to make explicit the tacit appeal to 3E. Then fill in the full argument explained in the discussion which follows (1)-(5). The most efficient natural deduction may have a significantly different organization than the informal presentation, 228 Int+ekrrionr, Soundness, and Completeness for Predicate Logic which was designed to help you see what is going on as opposed to presenting the argument in as few steps as possible. Students of truth trees may also have fun doing this argument as a truth tree proof, although this is less helpful in exposing the structure of the informal argument in English.
15-7. Carry out the inductive step of the proof of L26 for universally quantified sentences. You may do this most efficiently by commenting on how to modify the proof for the case of existentially quantified sentences.
Now that I have shown you how to proceed with this kind of argument, I am going to ask you to prove the rest of the lemmas we will need. When not otherwise specified, P(u) can be any open sentence with u the only free variable, I any interpretation, and so on.
Lemmas L27 and L28 show that the truth definitions for the quantifiers are equivalent to conditions which, superficially, look stronger than the definitions:
L27: Let s be any name not appearing in (3u)P(u). Then Mod[I,(3u)P(u)] iff there is an s-variant, I., of I such that Mod[I,, P(s)J.
L28: Let s be any name not appearing in (Vu)P(u). Then Mod[I,(Vu)P(u)] iff Mod[I,,P(s)] for all s-variants, I., of I.
EXERCISE 15-8. Prove L27 and L28. Apply L25 and L26 to D22 and D23. You will not need to do an induction.
L29: -(Vu)P(u) is logically equivalent to (3u)-P(u) and -(3u)P(u) is logically equivalent to (Vu)-P(u). 15-8. Prove L27 and L28. Apply L25 and L26 to D22 and D23. You will not need to do an induction.
EXERCISE 15-9. Prove L29. Remember that logical equivalence is the semantic notion of having the same truth value in all interpretations. You will not need to use induction. Instead, simply apply L27 and L28.
When you have finished your proof of L29, look it over and find the places at which you used, as informal logical principles applied in the metalanguage, just the negated quantifier rules which you were proving as generalizations about the object language! It is a noteworthy, and perhaps disturbing, fact that we cannot prove anything about the object language formulation of logic without assuming logical principles at least as strong in the metalanguage. What, then, do we gain in the process? Pre- - cision and clarity.
L30: Suppose that Mod[I,P(s)]. Then Mod[I,(3u)P(u,s)], where P(u,s) arises from P(s) by substituting u for any number of occurrences of s in P(s).
L31: Suppose that Mod[I,(Vu)P(u)]. Let I' differ from I only in assignment of names not occurring in (Vu)Pu, and let s be any name in 1'. Then Mod[I1,P(s)].
Note that in L31, s may be a name appearing in (Vu)P(u). L31 is a generalization of the principle that all substitution instances of a universally quantified sentence are true, a generalization we will need in the following sections.
EXERCISES 15-10. Prove L30. You will use L26 and D22 and no induction. 15-1 1. Prove L31, using L25, L26, and L28. The fact that s may appear in (Vu)P(u) may give you trouble in this problem. The trick is not to use the name s for the s-variant in D23. Use some other name, t, which does not appear in (Vu)P(u) and then apply L25 and L26 to s and t.
L32: Let I be an interpretation in which every object in its domain has a name. Then
a) Mod[I,(3u)P(u)J iff Mod[I,P(s)J for some name, s, that appears in I.
b) Mod[I,(Vu)P(u)] iff Mod[I,P(s)] for all names, s, that appear in I.
L32 simply says that the truth definitions for quantifiers given in chapter 2 work in the special case in which all objects in an interpretation's domain have names.
EXERCISE 15-12. Using any prior definitions and lemmas from this section that you need, prove L32.
We are now ready to extend our previous proofs of soundness and completeness for sentence logic to predicate logic. Most of the real work has been done in the lemmas of this section and in Koenig's lemma from 230 Znterpntationr, Soundness, and Compkteness for Predicate Logic 15-2. Soundness and Completeness for Trees 231 chapter 14. I am only going to outline the proofs and ask you to fill in the details. In the next three sections I will only treat predicate logic without identity or function symbols, and 1 will treat only finite sets of sentences in the completeness proofs
Contributors and Attributions
Paul Teller (UC Davis). The Primer was published in 1989 by Prentice Hall, since acquired by Pearson Education. Pearson Education has allowed the Primer to go out of print and returned the copyright to Professor Teller who is happy to make it available without charge for instructional and educational use.