TRUTH TREE RULES IN RELATIONAL LOGIC
In Statement Logic the Truth Tree Method is a decision procedure: it will always give us a decision whether a given argument is valid or invalid. Every tree will be complete: that is, will either be closed or contain at least one complete open path.
As we saw in the previous section, in Predicate Logic we need to modify the definition of completeness of trees to incorporate effectively complete paths in trees:A truth tree is complete if and only if either (i) every path is closed, or (ii) there is at least one open path that is either complete or effectively complete.
With this modification, the method will also be a decision procedure in Predicate Logic, but only provided it is restricted to arguments involving predicates with only one individual—the unary or monadic predicates. That is, in Monadic Predicate Logic every tree will be complete: i.e., either all its paths will close, or at least one of the open paths will be either complete or effectively complete. Unfortunately, however, when we turn to arguments involving predicates with more than one individual—relational or polyadic predicates—the method of truth trees no longer guarantees a decision on whether an argument is valid. This is because the trees associated with some arguments in relational logic there are open paths in trees that do not even become effectively complete. As we shall see, this occurs when we have to decompose certain quantifications over more than one variable—for instance,. j j __
________________________________ j________ j In such cases our demand that
or
be instantiated with “all the names appearing in the argument” can never be met, and the tree becomes infinite.
First let’s prove that any totally connexive relation R is also reflexive:
All the paths close, so the sequent is valid. Again, the truth tree method yields a very economical proof. One point worth mentioning is that we interpret the V rule as automatically licensing many applications in the same line, i.e., as analogous to our telescoped quantifier rules. The same goes for multiple existential quantifications: we may do repeated applications of
in the same line, provided we are careful to use different names for each application.
As another example, let’s investigate whether a symmetric relation can be irreflexive, that is whether
Here we have a tree with one path remaining open. But it is effectively complete—the only name occurring on previous lines is i, and we have found an instance, iRi, that makes the premise true and the conclusion false. So the sequent is invalid.
But, as mentioned, the Truth Tree Method does not always yield results for relational arguments, since sometimes the tree never meets the condition of becoming effectively complete. Consider the following example: from the fact that everyone has a mother 
On line 6, we could not get -∣iMu to obtain a contradiction with iMu because the rule -∣V requires us to instantiate with a letter that has not been used already: hence the instance iMj. But since the expression on line 1 is a universal quantification, we may use it again, this time taking j as an instance. But then when we apply 3 on line 8 we again need a different letter, this time k, giving kMj. Again, there are no restrictions on -∣3, so we can use ê as an instance on line 9. But then when we apply -∣V on line 10 we will again need a new letter. This process will repeat indefinitely, and we will never arrive at a contradiction, nor at a path that is effectively complete. The sequent is definitely invalid; but we cannot prove this using truth trees.
23.2.2