# 8.4: Infinite Trees

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

8-4. INFINITE TREES

So far, truth trees have provided a mechanical means for testing arguments for validity and sentences for consistency, logical truth, logical contradiction, or logical equivalence. But if logic were a purely mechanical procedure it could not have enough interest to absorb the attention of hundreds of logicians, mathematicians, and philosophers. However, in one way, the truth tree method is not purely mechanical.

Let's test the sentence '(Vx)(3y)Lxy' for consistency. That is, let's look for an interpretation which makes it true:

d, c, b, a, 1 Wx)(3y)Lxy S 42 (3y)Lay 1, V 3 Lab 2, 3, New name J4 (3y)Lby 1, V 5 Lbc 4, 3, New name J6 (3x)Lcy 1, V 7 Lcd 6, 3, New name 1

34 More on Truth Trees for Predicate Logic 8-4. Injinite Trees 135

The tree starts with the universally quantified sentence '(Vx)(3y)Lxy'. At this point the tree has no names, so I pick a name, 'a', and use it to instantiate 1, giving 2. Line 2 is an existentially quantified sentence, so I must instantiate it with a new name, 'b', giving line 3. But having the new name, 'b', I must go back and make 1 true for 'b'. This produces 4, again an existentially quantified sentence, which calls up the new name, 'c'. Now I must go back once more to 1 and instantiate it with 'c', producing the existentially quantified 6 and the new name, 'd', in 7. I am going to have to return to 1 with 'd'. By this time you can see the handwriting on the wall. This procedure is never going to end! The tree is just going to keep on growing. What does this mean? What has gone wrong?

Your immediate reaction may be that the troublesome new name requirement has clearly gummed up the works. The tree keeps on growing without end only because we keep needing to use a new name each time the existentially quantified sentence comes up. It's the new name from the existentiall; quantified sentence which has to be used to instantiate the universally quantified sentence which produces a new existentially quantified sentence which . . . and so on.

On the other hand, we know that without the new name requirement, the method will not always do its job. So what should we make of this situation?

First, let us understand what this infinite tree represents. It represents an interpretation with infinitely many names. The tree goes on forever, and corresponding to it we have a domain, D = {a,b,c,d, . . .}, and a specification that Lab & Lbc & Lcd & . . . . In other words, each object bears the relation L to the next.

Perhaps you have noticed that we can simplify the interpretation by supposing that there really is only one object to which all of the infinitely many names refer. This gives an interpretation in which there is only one thing, a, such that 'Laa' is true. In this interpretation it is true that for each thing (there is only one, namely a) there is something (namely a itself) such that Laa.

This is the last straw! you may well be saying to yourself. The new name requirement horribly complicates things, in this case by unnecessarily making the tree infinite. In this case the requirement prevents the method from finding the simplest interpretation imaginable which makes the original sentence true!

In fact we could rewrite the rules so that they would find this simple interpretation in the present case. But then the new rules would have some analogue of the new name requirement, an analogue which would provide a similar difficulty in some other problem. Let us say a bit more specifically what the difficulty comes to. In the infinite tree we have seen, it is very easy to tell that the tree will go on forever. And it is easy to figure out what infinite interpretation the infinite tree will provide. But in more complicated problems it will not be so easy. The rub is that there can be no mechanical way which will apply to all cases to tell us, in some limited number of steps, whether or not the tree will eventually close. - There will always be cases in which, even after thousands of pages, we will still not know whether the tree will close in just a few more steps or whether it will go on forever.

One can show that this problem, or some analogue of it, will come up no matter how we write the rules of logic. Indeed, this is one of the many exciting things about logic. The rules can be mechanically applied. But logic will always leave room for insight and ingenuity. For in difficult problems the mechanical rules may never tell you whether the tree will eventually close. In these cases you can find out only by being clever.

Unfortunately, we must stop at this point. But I hope that all of you have been able to get a glimpse of one of the ways in which logic can be exciting. If you continue your study of logic beyond this course, you will come to understand why and how the problem of infinite trees is really a very general fact about all formulations of predicate logic, and you will understand the essential limitations of predicate logic in a much more thorough way.

EXERCISES

8-5. Test the following sentences to determine which are logical truths, which are contradictions, and which are neither. Show your work and state your conclusion about the sentence. Whenever you find a counterexample to a sentence being a logical truth or a contradiction, give the counterexample and state explicitly what it is a counterexample to.

8-6. Use the truth tree method to test the following sets of sentences for consistency. In each case, state your conclusion about the sets of sentences, and if the set of sentences is consistent, give a model. 136 More on Td Treesfor Pwdhtc Logic

8-7. Use the truth tree method to determine which of the following are logically equivalent. Give counterexamples as appropriate. and Wx)Px & Wx)Qx and (3x)Px & (3x)Qx and Wx)Px v Wx)Qx and (3x)Px v (3x)Qx and (3x)Px 3 Wx)Qx and (Vx)Px 3 (3x)Qx and Wx)Px 3 Wx)Qx and (3x)Px 3 (3x)Qx (3y)Wx)ky and (3x)Bx & Wy)Hy

8-8. Are the following arguments valid? If not, give a counterexample. (All cats are animals. Therefore all tails of cats are tails of animals.)

CHAPTER SUMMARY EXERCISES Here are items from this chapter for you to review and record in summary: a) Contradiction b) Truth Tree Test for Contradictions c) Logical Truth d) Truth Tree Test for Logical Truth e) Logical Equivalence f) Truth Tree Test for Logical Equivalence g) Consistency h) Model i) Truth Tree Test for Consistency j) Three Permissible Truth Tree Shortcuts k) Infinite Trees 8-4. I* Trees 137

8.4: Infinite Trees is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.