# 7.1: The Rule for Universal Quantification

You have already learned the truth tree method for sentence logic. And now that you have a basic understanding of predicate logic sentences, you are ready to extend the truth tree method to predicate logic.

Let's go back to the basics of testing arguments for validity: To say that an argument is valid is to say that in every possible case in which the premises are true, the conclusion is true also. We reexpress this by saying that an argument is valid if and only if it has no counterexamples, that is, no possible cases in which the premises are true and the conclusion false. When we were doing sentence logic, our possible cases were the lines of a truth table, and in any one problem there were only finitely many lines. In principle, we could always check all the truth table lines to see if any of them were counterexamples. Often the truth tree method shortened our work. But the trees were really just a labor-saving device. We could always go back and check through all the truth table lines.

Predicate logic changes everything. In predicate logic our cases are interpretations, and there are always infinitely many of these. Thus we could never check through them all to be sure that there are no counterexamples. Now truth trees become much more than a convenience. They provide the only systematic means we have for searching for counterexamples.

Everything we learned about truth trees in sentence logic carries over to predicate logic. Someone gives us an argument and asks us whether it is valid. We proceed by searching for a counterexample. We begin by listing the premises and the denial of the conclusion as the beginning of a tree. Just as before, if we can make these true we will have a case in which the premises are true and the conclusion false, which is a counterexample and which shows the argument to be invalid. If we can establish that the method does not turn up a counterexample, we conclude that there is none and that the argument is valid.

We have boiled our job down to the task of systematically looking for a case which will make true the initial sentence on a tree. In sentence logic we did this by applying the rules for the connectives '&', 'v', '~', '⊃', and '='. These rules broke down longer sentences into shorter ones in all the minimally sufficient possible ways which would make the longer sentences true by making the shorter ones true. Since, in sentence logic, this process terminates in sentence letters and negated sentence letters, we got branches which (if they do not close) make everything true by making the sentence letters and negated sentence letters along them true. In this way you should think of each branch as a systematic way of developing a line of a truth table which will make all the sentences along the branch true.

The tree method for predicate logic works in exactly the same way, with just one change: Each branch is no longer a way of developing a line of a truth table which will make all the sentences along the branch true. Instead, a branch is a way of developing an interpretation which will make all the sentences along the branch true. All you have to do is to stop thinking in terms of building a line of a truth table (an assignment of truth values to sentence letters). Instead, start thinking in terms of building an interpretation.

Let's see this strategy in action. Consider the example that got us started on predicate logic, way back in chapter 1:

Everybody loves Eve.        (Vx)Lxe

We begin our search for an interpretation in which the premise is true and the conclusion is false by listing the premise and the denial of the conclusion as the initial lines of a tree:

1     (Vx)Lxe    P
2     ~Lae        ~C

We already know quite a bit about any interpretation of these two sentences which makes them both true. The interpretation will have to have something called 'a' and something called 'e', and '~Lae' will have to be true in the interpretation. '~Lae' is already a negated atomic sentence. We cannot make it true by making some shorter sentence true.

But we can make '(Vx)Lxe' true by making some shorter sentences true. Intuitively, '(Vx)Lxe' says that everybody loves Eve. In our interpretation we have a (Adam) and e (Eve). In this interpretation, in this little novel or story of the way the world might be, we can make it true that everybody loves Eve by making it true that Adam loves Eve and making it true that Eve loves Eve. So we extend the branch representing our interpretation with the sentences 'Lae' and 'Lee':

a, e 1     (Vx)Lxe      P
2     ~Lae         ~C
3     Lae           1, v
4     Lee           1, v
X

And the branch closes! The branch includes both '~Lae' and 'Lae', where the first is the negation of the second. They cannot both be true in an interpretation. We had to include '~Lae' to get an interpretation which makes the conclusion of the argument false. We had to include 'Lae' to get an interpretation which makes '(Vx)Lxe' true. But no interpretation can make the same sentence both true and false. So there is no interpretation which makes lines 1 and 2 true-there is no counterexample to the argument. And so the argument is valid.

Let's talk more generally about how I got lines 3 and 4 out of line 1. Already, when we have just lines 1 and 2, we know that our branch will represent an interpretation with something called 'a' and something called 'e'. We know this because our interpretation must be an interpretation of all the sentences already appearing, and these sentences include the names 'a' and 'e'. Our immediate objective is to make '(Vx)Lxe' true in this interpretation. But we know that a universally quantified sentence is true in an interpretation just in case all its substitution instances are true in the interpretation. So to make '(Vx)Lxe' true in the interpretation we must make 'Lae' and 'Lee' true in the interpretation. This is because 'Lae' and 'Lee' are the substitution instances of '(Vx)Lxel formed with the interpretation's names, 'a' and 'e'.

Notice that I did something more complicated than simply checking line 1 after working on it and putting the annotation '1,V' after lines 3 and 4. The rule for the universal quantifier differs in this respect from all the other rules. The other rules, when applied to a "target" sentence, tell us to write something at the bottom of every open branch on which the target sentence appears. When this is done, we have guaranteed that we have made the target sentence true in all possible minimally sufficient ways. We thus will never have to worry about the target sentence again. To note the fact that we are done with the sentence, we check it.

But the rule for the universal quantifier is not like this. First, in applying the rule to a universally quantified sentence, we have to search the branch on which the target sentence appears for names. Then, at the bottom of every open branch on which the target sentence appears, we must instantiate the target sentence with each name which occurs along that branch. To help keep track of which names have already been used to instantiate the target sentence, we list them as we use them.

You might think that when we have thus accounted for all the names on the branch we are done with the target sentence and can check it. But you will see that new names can arise after first working on a universally quantified target sentence. In such a case we must come back and work on the universally quantified sentence again. Because we must recognize the possibility of having to return to a universally quantified sentence, we never check the sentence as a whole. Instead, we list the names which we have thus far used in the sentence, because once a universally quantified sentence has been instantiated with a given name, we never have to instantiate it with the same name again.

Here is a summary statement of our rule:

Rule V: If a universally quantified sentence (Vu)(. . . u . . .) appears as the entire sentence at a point on a tree, do the following to each open branch on which (Vu)(. . . u . . .) appears. First, collect all the names s1, s2, s3, . . . that appear along the branch. (If no name appears on the branch, introduce a name so that you have at least one name.) Then write the substitution instances (. . . s1 . . .), (. . . s2 . . .), (. . . s3 . . .), . . . at the bottom of the branch, and write the names s1, s2, s3, . . . to the left of (Vu)(. . . u . . .). Do not put a check by (Vu)(. . . u . . .).

Several facets of this rule bear further comment. First, in working om a universally quantified sentence on a given branch, you only need to instantiate it with the names along that branch. If the same universally quantified sentence occurs along a second branch, that second branch calls for use of the names that occur along that second branch. This is because each branch is going to represent its own interpretation. Also, when instructed to write a substitution instance, (. . . s . . .), at the bottom of an open branch, you do not need to write it a second time if it already appears.

Next, the rule instructs you to write all of the substitution instances, (. . . s1 . . .), (. . . s2 . . .), (. . . s3 . . .), . . . at the bottom of every open path. But if the path closes before you are done, of course you can stop. Once a path closes, it cannot represent a counterexample, and further additions will make no difference. Thus, in the last example, I could have correctly marked the path as closed after line 3, omitting line 4. You can make good use of this fact to shorten your work by choosing to write down first the substitution instances which will get a branch to close. But don't forget that if the branch does not close, you must list all the substitution instances.

Finally, listing the names used to the left of (Vu)(. . . u . . .) is a practical reminder of which names you have already used to instantiate (Vu)(. . . u . . .). But this reminder is not foolproof because it does not contain the information about which branch the substitution instance appears on. In practice, this isn't a difficulty because in almost every problem your substitution instance will appear on all branches. Indeed, when a universally quantified sentence appears on a branch it never hurts to introduce a substitution instance formed with a name which had not otherwise appeared on that branch.

Let me illustrate how the rule applies when no name appears on a path. At the same time, I will show you how we will write down counterexamples:

A                    1              A           P
~(Vx)Bx               2       ~~(Vx)Bx      ~C
a3            (Vx)Bx      2, ~~
4              Ba          3, V

Invalid. Counterexample: D = {a}; Ba & A

'A' is an atomic sentence letter which we make true in the counterexample. 'A' is not a name. So when we get to line 3 and need to instantiate '(Vx)Bx' with all the names in the interpretation we are building, we find that we don't have any names. What do we do? Every interpretation must have at least one thing in it. So when applying the rule V to a universally quantified sentence on a branch which has no names, we have to introduce a name to use. This is the only circumstance in which the V rule tells us to introduce a new name. Any name will do. In this example I used 'a'.

Notice how I indicated the counterexample to the argument provided by the open branch. The counterexample is an interpretation which makes everything along the branch true. You read the counterexample off the open branch by listing the names which occur on the branch and the atomic and negated atomic sentences which occur along the branch. The rules have been designed so that these shortest sentences make true the longer sentences from which they came, which in turn make true the still longer sentences from which they came, and so on, until finally everything along the open branch is true.

Exercise

7-1. Use the truth tree method to test the following arguments for validity. In each problem, state whether or not the argument is valid; if invalid, give a counterexample.

a) (Vx)(kx & Jx)                    b) (Vx)(Fx ⊃ Gx)                    c) (Vx)(Cx ⊃ Ix)
Ka                                     ~Ga                                    Ch v Ih
Fa

d) A ⊃ (Vx)Mx                        e) (Vx)(Bx ⊃ Cx)                    f) (Vx)(Ne ≡ Px)
A                                        (Vx)Bx                                      Pg
Mg & Mi                                  Ca & Cb

g) (Vx)(Kx v Ax)                      h)  (Vx)(Dx v Gx)                    i) (Vx)(Sx ≡ Tx)
~kj                                     (Vx)(Dx ⊃ Jx)                          Sb v ~Ta