13.1: Introduction

There are no new rules for QT. However, note these points:

1.   Resolve only main operators.

      There may be a bit of work involved in getting each quantifier out to the right place.

2.   Counterexamples must be tested.

3.   Validity, tautology, and contradiction are the same for QT as for MQT.

4.   We're going to abbreviate ("y) as (y).

13.2: QT-Trees

Here's a very simple example:

1.     ($x)(y) xRy             P

2.     ~ ($x)($y) xRy          NC

3.     (x) ~ ($y) xRy          2, QN

4.     aRa                     1, EI

5.     ~ ($y) aRy              3, UI

6.     (y) ~ aRy               5, QN

7.     ~ aRa                   6, UI

8.     X                       4, 7

As you can see, it's perfectly normal. The hard parts are in getting the quantifiers into main operator positions as you proceed through the tree, choosing the appropriate constants for UI and EI. That's just a matter of practice and becoming familiar with the way trees work.

13.3: Counterexamples in QT

Find finite counterexamples by reference to an open tree. Here are the steps to follow.

A.     Construct a tree

B.     Find a path that will not close. Extract a purported counterexample (PCX) as follows:

         1.     Count the different individual constants in the PCX.

                 That is the number of elements in the counterexample world.

         2.     Set up one table for each set of n-place predicates (n = 1, 2, 3, ...) that occur.

         3.     Fill in the tables from the formulae in the selected open path (there may be blank spaces.)

         4.     Eliminate quantifiers from all the formulae involved and

                 calculate their truth values in the PCX.

         5.     If calculations are incomplete because of blanks in the tables,

                 try creating some appropriate table values to get a CX.

         6.     Is this a counterexample?

                 Yes: OK

                 No: Have another look at the tree and try something else.

A problem for QT-trees is that they can generate counterexamples that are unnecessarily large.

1.  One way to avoid this is to try counterexamples in one-item worlds first. (But if there is no singleton counterexample that doesn't mean that the formula is a tautology or the argument valid.)

2.  If you still have no luck then try eliminating quantifiers for a world with two items - if that's not too hard.

3.   If you can't do any of that then you're better off with a tree.

13.4: Taming Wild Arguments with QT

This section just has some tricky examples. Read them and understand their trickiness.

13.5: Infinite Counterexamples

We have hinted from time to time that there may be invalid arguments with no finite counterexamples. Here is an example of one such.

       (x)($y)xSy

       (x)(y)(z)((xSy & ySz) É xSz)

       (x)~xSx

       ----------------------------

       ($x)(y)ySx

The tree for this begins thus:

1.     (x)($y)xSy                    P

2.     (x)(y)(z)((xSy & ySz) É xSz)  P

3.     (x)~xSx                       P

4.     ~($x)(y)ySx                   NC

5.     (x)~(y)ySx                    4, QN

6.     ~(y)ySa                       5, UI to a

7.     ($y)~ySa                      6, QN

8.     ~bSa                          7, EI to b

9.     ($y)bSy                       1, UI to b

10.    bSc                           9, EI to c

       .

       .

       .

The tree won't close because EI will continue to add new elements. A few attempts will probably convince you that no finite counterexample exists.

To come up with infinite counterexamples it  helps to think of an interpretation of an argument. In the case above there is a natural numerical interpretation that we can see in the following dictionary:

Universe  = natural numbers: 1, 2, 3, ...

xSy = s is smaller than y.

The argument in English therefore runs as follows:

Every number is smaller than some number or other.

If one number is smaller than a second, and the second is smaller than a third, then the first is smaller than the third.

No number is smaller than itself.

-------------------------------------------------

There is a number than which all numbers are smaller.

The conclusion is that there is a largest number. We can see that the premisses in a finite world are inconsistent, and the conclusion true; but in an infinite world the premisses can be consistent but the conclusion is then false.

Other interpretations are appropriate for finding counterexamples by analogy for other arguments. The process of finding these are:

1.     Set out a universe of discourse.

2.     Give an appropriate interpretation to each predicate letter.

3.     Let each individual constant refer to some item in the universe.

4.     Let each propositional letter stand for some statement that is known to be either true or false.

5.     Translate the formulae into English.

If the interpretation gives a genuine counterexample for an argument, then the premisses will be true and the conclusion will be false.