QL Trees

In Chapter 9 we saw that the more structured models of QL make reasoning about all possible models rather complex. In SL, where a model was just an assignment of truth values to atomic sentences, reasoning about all models was relatively straightforward: we could simply survey them via truth tables. In QL there isn't really as simple a method for considering claims about validity or satisfiability as the truth table method. So we must rely more heavily on proof systems.

This chapter considers a tree method for QL. Like the tree method for SL discussed in Chapter 5, the QL tree method is a method that attempts to generate an interpretation satisfying a given set of sentences. When it succeeds, it shows a way to satisfy them; when it fails, it shows that they are unsatisfiable. As we did in the initial presentation of trees in Chapter 5, we'll begin by working through a couple of examples at an intuitive level, before laying out the formal tree rules.

10.1 Trees with fixed domains

Let's begin with a simplifying assumption. Let's suppose that we're only interested in models with particular fixed domain sizes. (By the time we get to the formal tree rules later in this chapter, we'll dispense with this assumption, but it's helpful for introducing the general idea.) Let's confine our attention to models that have two members in the UD. Consider whether there are any such models that satisfy the following QL sentences: {∀x(Fx⊃Gx), ¬∃xGx, ∃x(Fx∨Gx)}. To evaluate this question, we put those sentences in the root of a tree.

Let's start by considering the universal claim on line 1. A universal says that each of its instances are true. Since at the moment we are assuming that there are two objects in our UD, let's also assume we have just two names, a and b, corresponding to our two objects. So we can just write down the two instances as a linear development. We also put a check at line 1 to indicate that we've resolved that sentence.

Next let's consider the negated existential at line 2. It says that each instance is false. So it develops into the negation of both instances, and we add a check mark at line 2.

There is one more quantified sentence to resolve, on line 3, but before we do that, let's handle the conditionals on lines 4 and 5. We do these exactly the same way we handled conditionals in SL trees. They each branch into the negation of the antecedent and the consequent; the latter branch closes each time.

Now let's look at line 3. It is an existential claim, so it says that at least one of its instances are true. Again, we're assuming for now that there are only two instances. So we branch into them those two disjunctions at line 10. After that, we apply the approach to disjunctions from SL trees, and the tree closes.

The closed tree indicates that our attempt to find a model satisfying the root has failed. We're not quite in a position to say that we've proven the root entirely unsatisfiable, because we've been assuming for simplicity that we're only interested in models that have two members of the UD. But we've shown at least that it's impossible to satisfy the root with any model with a two-object domain. We'll consider a more generalized procedure soon.

Before moving on to the official tree rules, let's look at one more example that assumes a two-object domain.

Is there any model with a two-object UD that satisfies {∀xFxa, ∀y(Gy⊃¬Fya)}? To find out, we put both sentences in the root of a tree, and continue as before. We start by taking both instances of each universal claim, then process the two conditionals. This tree remains open.

As in SL trees, a completed QL tree with an open branch describes a way of satisfying the root. We're assuming a two-object UD; for simplicity, let's let our objects be the letters 'a' and 'b', and have 'a' be the referent of the QL name a, and 'b' be the referent of the QL name b. We look to the two QL atoms and two negated QL atoms in the branch; they indicate what needs to be included in the extension of each predicate in our model. Since Faa is in the branch, we need to include <a, a> in the extension of F. Since ¬Ga is in the branch, we need for a not to be in the extension of G.

Here is a partial model that suffices to satisfy the root of the above tree:

UD = {a, b}
extension(G) =

extension(F) =

Notice that we've put blanks for two of the cells in the extension of Fxy. That is to indicate that it doesn't matter whether or not <a, b> or <b, b> are included in the extension of Fxy. (This is also why neither Fab, Fbb, ¬Fab, nor ¬Fbb appeared in the open branch.) So the tree method for QL is similar to that for SL in this respect as well. An open branch in a completed tree describes a way to satisfy the root.

10.2 Generalizing the tree method

Trees are supposed to show something about all possible models, not only those with two-object UDs. So we don't want our official tree rules to build in the idea that there are just two objects. For a three-object UD, we'd want our universal statements to develop into all three instances, and we'd want our existentials to branch into the three instances. For a ten-object UD like the one described in Section 9.3, we'd need to give ten instances. For an infinite UD like the set of all natural numbers, we'd need an infinite number of developments. Obviously such rules would be impractical, to say the least. Worse than that, we often won't know at the start of the process what size domain we should be thinking of. So we need a version of the tree rules that is flexible as to domain size.

In order to state our rule formally, we need one new bit of formalism. For any QL wff Φ, a constant 𝒸, and variable 𝓍, define Φ[x⇒𝒸] to mean the wff that we get by replacing every occurrence of 𝓍 in Φ with 𝒸. So for example,

Fx[x⇒a] = Fa

For any quantified QL sentence ∀𝓍Φ or ∃𝓍Φ, we call Φ[x⇒𝒶] a substitution instance of ∀xΦ and ∃xΦ, and 𝒸 is called the instantiating constant.

This, more formally, is the same notion we were working with in our discussion of trees for models with two-object UDs. For example:

• Aa ⊃ Ba, Af ⊃ Bf, and Ak ⊃ Bk are all substitution instances of ∀x(Ax⊃Bx); the instantiating constants are a, f, and k, respectively.

• Raj, Rdj, and Rjj are substitution instances of ∃zRzj; the instantiating constants are a, d, and j, respectively.

With this terminology in hand, we can begin with our official tree rules.

10.3 Existentials

This will be our official tree rule for existentials:

Just as Φ stands in for any sentence of QL, the 𝓍 is meant to stand in for any variable, and 𝒶 stands in for any name. The requirement that the name be new means that the name chosen for the substitution instance must be a name that has not appeared anywhere in the tree so far.

What is the rationale for this restriction? The existential claim says that some substitution instance is true, but it doesn't say which one it is. If we knew how many objects we were looking at in the UD, we could make a new branch for each object --- that's what we did in the examples above --- but here we see a different way to model this kind of flexibility. Remember, there is no prohibition in QL of two different names referring to the very same object. So by using an instance involving a new name, we are remaining open-minded about whether it is also a name for some object we've already been discussing.

For example, consider this tree:

The appropriate substitution instance of the existential on line 2 is Fb, not Fa, because a is a name that is already in use. We want to say that something is F, not necessarily that a is. Had we taken the a instance, the tree would have closed, even though the root is satisfiable. Note also that in marking the existential as having been processed, we also make a note of the instantiating constant. That's why there is a b next to the check mark in line 2.

10.4 Universals

Here is the tree rule for universals.

The universal rule, like the existential rule, invites you to take an instance. But unlike the existential rule, we don't limit ourselves to instances with new names. The other major difference is that one can use this rule multiple times. That makes this rule different from all the other tree rules we've seen so far. You're not necessarily finished processing a universal sentence after you've performed the rule once. We mark this by indicating a ∖ instead of a ✓ next to the universal sentence.

Here is an example illustrating the importance of taking multiple instances. Here is a partially completed tree.

The root of this tree is pretty obviously unsatisfiable, but so far, the tree hasn't closed. On line 3 we take the a instance of the universal at line 1, but the tree won't close until we take the b instance as well. We can do so at any time. In this way of developing the tree, we take that instance at line 7, and then the tree will close:

Of course, we could also have taken the b instance at the same time as we took the a instance on line 3, and the tree would have worked just as well. But taking things in this order illustrates that sometimes we can go back to universal claims that have already been considered, to take an additional instance. (Later on, we will see some examples of trees that require this kind of backtracking.)

10.5 Negated existentials

Negated existential claims are quite similar to universals. They say that no instance is true, which is another way of saying that every instance is false. So like the universal rule, the negated existential rule will allow us to take as many instances as we like; this time, we take the instances of the negation of the wff in the scope of the quantifier.

For example, if ¬∃xFx is in the tree, one can use the negated existential rule to develop a tree branch with ¬Fa, ¬Fb, etc.

10.6 Negated universals

Conversely, a negated universal is similar to an existential. It says that not all instances are true, so at least one instance is false. So like the existential rule, we only perform it once (marking it with a check), and ensuring that we use a new name, so as not to assume anything in particular about the instance chosen.

10.7 Whither branching?

When we learned the tree rules for sentential connectives, there was an important distinction between linear rules and branching rules. We retained this when we assumed two-object domains in §10.1, where universal quantifiers had linear rules, and existentials had branching rules. Our new quantifier rules, however, all have the same linear shape. Nothing branches. Why not?

In SL, and for QL models where finite domains were specified in advance, we used branching to represent the particular possible ways one could satisfy the formula above. For some interpretation ℐ to satisfy P ∨ Q, either ℐ(P) = 1 or ℐ(Q) = 1. If we assume there are only two objects, a and b, then in order for ℐ to satisfy ∃xFx, ℐ must either have a in the extension of F or have b in the extension of F. So we can branch the tree to represent those two possibilities.

But if we do not assume anything in particular about the UD, we can't just list all the possible ways to satisfy an existential (or a negated universal). We'd need as many branches as there are objects in the UD. So instead we just take one instance, but give it a new name, which may or may not be co-referential with another name we've already considered. The novelty of the name is playing the functional role of branching.

10.8 The other development rules

So far this chapter we've introduced four tree development rules for QL: we have rules for universals, existentials, negated universals, and negated existentials. There are nine more resolution rules, but they are all familiar: they are the same nine resolution rules given in Chapter 5. We'll use all the same resolution rules for conjunction, negated conjunction, disjunction, negated disjunction, conditional, negated conditional, biconditional, negated biconditional, and double negation as we did before. They were introduced in Chapter 5.

10.9 Branch closure rules

Our branch closure rules also remain unchanged. A branch closes if and only if it contains some sentence Φ along with its negation, ¬Φ. We mark closed branches with an ×.

10.10 Tree completion rules

The completion rules, however, require a modification. The SL tree completion rule, given in §5.6, said that a branch was complete if every sentence, other than atoms and negated atoms, has been resolved. In the QL tree system we need for our tree completion rules to take account of the fact that some sentences need to be acted on multiple times. The universal rule, for example, lets one take whatever instance one likes; we need our completion rules to ensure that we've taken enough instances.

For example, this should not count as a completed tree:

Our universal rule can be processed multiple times. This tree has only taken the a instance of (Fx⊃Ga); if it also took the b instance, the tree would close:

We don't want this tree to count as complete until it's taken both the a and the b instance. The universal says that every instance must be true; we don't ensure that this is satisfied if only some instances have been taken.

If we knew how many names our model used, we could simply require that every instance be taken. But we don't know in advance how many names our models are going to use. QL trees construct their interpretations as they go. (Remember that resolving existentials and negated universals involves introducing new names.) Here is the requirement we want: we require that we've taken the instance corresponding to every name in the branch. If, after taking an instance or two, we go on to introduce a new name within the same branch, that branch isn't complete until we've taken that instance as well. Once again, this is why we use the ∖ instead of a . We can't be sure that we're finished with that line until we've done the rest of the tree.

A wff is resolvable if it is the kind of wff that gets a check mark upon processing it. (That's everything except for atoms, negated atoms, universals, and negated existentials.) A wff is general if it is a universal or a negated existential. Here is our new tree completion rule:

A branch is complete if and only if either (i) it is closed, or (ii) every resolvable sentence in the branch has been resolved, and for every general sentence and every name a in the branch, the a instance of that general sentence has been taken. A tree is complete if and only if every branch in that tree is complete.

10.11 Resolution order

As in the SL tree system, the rules do not indicate any particular resolution order. But --- also as in the SL system --- some strategies are going to be more efficient than others. In fact, given the increased complexity of our rules and the fact that some resolutions introduce new names, it is even more important, from an efficiency perspective, than it used to be to employ sensible strategies. It is still a good idea to do linear rules before branching rules, and when possible, to perform a branching rule when you can see that one branch will close right away. Now, we can use similar strategies to take instances from general sentences in a strategic way. If you're not sure which instance to take first, look a step ahead and see if one of the instances will close a branch.

Here is a simple tree illustrating the point. Let's consider whether Gb ⊃ ∀x¬Fx and ∃xFx entail ¬Gb. We begin by putting the first two sentences and the negation of the third in the root of a tree:

Ordinarily, it is efficient not to branch too early. But in this case, if we look ahead a step, we can see that resolving the conditional on line 1 will close one branch immediately. So that's a good place to start.

From here we have three choices to consider: lines 2, 3, and 4. Line 3 pretty obviously won't get us anywhere interesting, so let's consider either the existential at line 2 or the universal at line 4. It's usually a good rule of thumb to do the new instances first --- that way we'll have more information when we make decisions about which instances to take for the general rules. So let's take the a instance of line 2.

Now we turn our attention to the universal at line 4. We can take whatever instance we want. Let's be intelligent about it. The b instance wouldn't do anything interesting; Fb won't interact with that ¬¬Gb in any helpful way. But the a instance will close the tree. So we take that one.

Planning ahead can help make your trees more efficient. The general principle you should keep in mind is, if you have a choice for what resolvable sentence to resolve, or what instance of a general sentence to take, make a choice that will allow you to close branches more quickly.

10.12 Infinite trees

In the SL tree system, every development of the tree took us closer to a completed tree, because we checked sentences above as resolved, and wrote simpler sentences in one or two branches below. SL trees are guaranteed to be completed in a finite number of steps --- they will either close, or they will reach a point where everything resolvable has been resolved.

Because of the way our QL system works, it is possible for trees to continue indefinitely without closing. General sentences require that instances be taken for all names in the branch; but the rules for existentials and negated universals require that new names be introduced. Often, we can introduce the new names before dealing with the general instances, as in this completed tree:

In this tree, we introduce the name a for the existential, then take the instance for the one and only name in the branch for the universal, and the tree is complete. But things won't always be so simple. Consider a tree with this single sentence in its root: ∀x∃yRxy. In this case, we must begin by performing the universal rule, as our one and only sentence is a universal. This rule allows us to take an instance with any name. Ordinarily, we use the names that already exist in the branch, but since there are no names, we'll just take the a instance from the start, putting that instance --- an existential --- on line 2.

To resolve that existential, we must use a new name. So on line 3, we take the b instance from line 2.

This tree has not closed, but note that it is not complete. We haven't taken the b instance of the universal on line 1. When we do so, we will find ourselves with another existential on line 4; it in turn requires an instance involving a new name, and the process will continue indefinitely.

As the pattern makes clear, this tree will never close, but it will also never be complete. It will just keep taking instances of an existential with new names, then taking those instances of the universal, which in turn require a new existential, and so on. (Eventually we will run out of letters, but we have subscripts available too, so we'll never run out of names.) Because the tree will never close, its open branch is describing a model that satisfies the root, but the model suggested is an infinite one. Line 3 tells us that <a, b> should be in the extension of R; line 5 says that <b, c> should too. There is a clear pattern that tells us what R's extension must be like:

extension(R) = {⟨a, b⟩, ⟨b, c⟩, ⟨c, d⟩, ⟨d, e⟩…}

Or we can represent it graphically, thus:

The blanks indicate that it doesn't matter whether those pairs fall under the extension of R or not.

What this suggests is that if one had a UD comprising an infinite list of objects, with each object related via R to the next item in the list, this model would satisfy the root of the tree. For example, suppose that our UD were the set of all natural numbers, and that we interpreted Rxy as x + 1 = y. For every number x, there is a number y that is equal to x + 1.

Note, however, that this is only one of many possible ways to construct a model meeting the constraint described. In fact, we don't necessarily require that our UD be infinite. Our tree ended up using an infinite number of names, but there's no rule requiring that each name be assigned to a unique object.

The extension of R requires that certain pairs be included. Note that it doesn't require that any pairs be excluded. There are no 0s in the chart above. The blanks mean it doesn't matter whether you include them. A model that included every ordered pair in the extension of R would be an example of the kind of model indicated:

Once we put it this way, we can see that the R predicate needn't draw any distinctions between the various objects in the domain. Each object could be the same, as far as R is concerned. So we could even offer a simpler model, with a UD comprising a simple object that is R-related to itself.

UD = {a}
extension(R) = {⟨a, a⟩}

When a tree continues indefinitely, the root is satisfiable; you can describe a model for it using an infinite domain, taking advantage of the pattern indicated by the infinite branch; or you can often find a way to simplify it into a model with a finite UD.

Let's consider another example of an infinite tree. This time, we'll use names with subscripts. Everything is straightforward up until line 6; at line 7, we need to go back and take a second instance of line 2, and the infinite cycle begins.

If we continued drawing the tree, we'd take the a₄ instance of the universal at line 2 on line 15, then introduce a new name by resolving that universal. The tree will continue forever, again with a clear pattern. Lines 5, 9, 13, etc. tell us that for every integer i, Ra₁a_i=0. Lines 6, 10, 14, etc. tell us that for every i > 1, Ra_ia₁=1. Or in chart form:

This chart describes the extension of R that, as part of a model with the infinite UD {a₁, a₂, a₃, ...}, would satisfy ∃x∀y∃z(¬Rxy & Rzx). As in the previous example, we do not need an infinite model to satisfy this sentence; the extension of R here can be collapsed into a finite one. In the previous example, our extension required no distinctions between any of the objects; here, we do have some required differences. Ra₁a₁ = 0, but Ra₂a₁ = 1. So our model is treating a₁ and a₂ differently. But it requires no further distinctions than that. Every object after a₂ can be the same as a₂, as far as this model is concerned. So a two-object model would also suffice to satisfy this sentence. Here is a graphical representation of the denotation for R:

UD = {a₁, a₂}
extension(R) = {⟨a₂, a₁⟩}

The reasoning involved in collapsing models with infinite domains into finite ones centrally involves reasoning about what distinctions are required: do we need to suppose that the objects named are different objects, or can we treat it as a case of multiple names for the same thing. In Chapter Chapter 12, we'll foreground this kind of question in more detail, and introduce a way to talk about it in QL.

Note that, for purposes of answering questions about entailment, you needn't go through the reasoning that allows you to move from infinite models to finite ones that would serve just as well. The tree method, most fundamentally, is a question about whether there is any possible model of the root. If a tree continues infinitely, then it is answering that question: yes, there is an infinite model for it. It's not necessary, for the question of whether there is any model satisfying the root, to determine whether there is a finite model that does so.

10.13 Common student errors

Using old names

The most frequent errors for trees in QL involve ignoring the restrictions on names involved in taking instances. Particular sentences (existentials and negated universals) require a new name --- if the name appears anywhere in the branch at the time the existential is taken (including below it), it is not suitable for substitution via these rules.

For example, this tree is a mistake:

Line 3 here is fine; but at line 4, this tree takes the b instance of the existential on line 3, even though b appeared in line 2. The existential rule requires a new name. The correct version of this tree will remain open. (It will extend infinitely.)

Main Connectives

Always work on the main connectives. If you have a sentence like ∀x∃y¬Ryx & (Fa⊃Fb) don't use the universal rule. This sentence is a conjunction, so you must perform the conjunction rule on it. That will give you a universal, at which point you can take an instance.

Practice Exercises

Part A Use a tree to test whether the following sentences are tautologies. If they are not tautologies, describe a model on which they are false.

1. ∀x∀y(Gxy⊃∃zGxz)

2. ∀xFx ∨ ∀x(Fx⊃Gx)

3. ∀x(Fx⊃(¬Fx⊃∀yGy))

4. ∃x(Fx∨¬Fx)

5. ∃xJx ≡ ¬∀x¬Jx

6. ∀x(Fx∨Gx) ⊃ (∀yFy∨∃xGx)

Part B Use a tree to test whether the following argument forms are valid. If they are not, give a model as a counterexample.

1. Fa, Ga, ∴ ∀x(Fx⊃Gx)

2. Fa, Ga,∴ ∃x(Fx & Gx)

3. ∀x∃yLxy,∴ ∃x∀yLxy

4. ∃x(Fx & Gx), Fb ≡ Fa, Fc ⊃ Fa, ∴ Fa

5. ∀x∃yGyx, ∴ ∀x∃y(Gxy∨Gyx)

Part C Translate each argument into QL, specifying a UD, then use a tree to evaluate the resulting form for validity. If it is invalid, give a model as a counterexample.

1. Every logic student is studying. Deborah is not studying. Therefore, Deborah is not a logic student.

2. Kirk is a white male Captain. Therefore, some Captains are white.

3. The Red Sox are going to win the game. Every team who wins the game will be celebrated. Therefore, the Red Sox will be celebrated.

4. The Red Sox are going to win the game. Therefore, the Yankees are not going to win the game.

5. All cats make Frank sneeze, unless they are hairless. Some hairless cats are cuddly. Therefore, some cuddly things make Frank sneeze.