The Undecidibility of Polyadic QL
 

Let's attempt a truth-tree for the following argument:

which is the translation of:

We set the truth tree up with the premise and the negation of the conclusion:

and apply rules for moving negations inside:

Now we instantiate our two universally quantified wffs. Since there are no constants on the tree, we have to begin with a new constant, and so we'll use "a".

We have instantiated our two universally quantified wffs with "a". Now we have to instantiate the two existentially quantified wffs, our last two on the current version of the tree. But for existential wffs, we must pick constants not already on the path. So we'll need new constants for each:

Are we done? NO! We have to instantiate our universally quantified wffs with every constant on the path, and now we have two new constants on the path, "b" and "c". So we have to go bak to the two universally quantified wffs and reinstantiate them each with "b" and "c".

And now we have four new existentially quantified wff, and so we need to instantiate them with new constants not already on the tree:

But now we have new constants on the tree, and so we have to instantiate our two universally quantified wffs with them. But last time we did that, it led to our writing down new existentially quantified wffs, which require us to introduce new constants, which then have to be instantiated universally, which leads to new existentials, and so on. So what we clearly have here is a never-ending tree.

What we have just demonstrated is the undecidability of Polyadic QL. There is an argument (indeed there are many) for which there is not a step-by-step procedure for determining whether an argument is valid in a finite number of steps. (Actually, we've only demonstrated that the truth-tree method is undecidable. It takes a little more work to generalize from the truth-tree method to any method.)

The undecidability of Polyadic QL is an important metatheoretical result. When you take your next logic course, you will study undecidability and other metalogical properties in more detail. Until then, you'll have to settle for this Undecidability Exercise.