How is $(∀x)(Px∧Qx)→(∀x)(Px)$ not a tautology?

Question

I read that using the truth tree method (analytic tableaux) “a statement α is tautological just in case any truth tree for ~α closes".

A truth tree for $¬(∀x(Px∧Qx)→∀xPx)$ closes so how this is not a tautology?

Answer 1

The large majority (I think) of logicians use "tautology" to mean truth-functional tautology. So logical truths of first-order logic will not in general be instances of tautologies.

$(\forall x)(Px \land Qx) \to (\forall x)(Px)$ is indeed a logical truth of first-order logic. One way of showing this is that a first-order truth-tree (tableau) starting with the negation of this wff closes.

But this wff is evidently not a truth-functional tautology: it requires more than the rules governing the truth-functional connectives to show that it is a logical truth.

Answer 2

As annoyingly happens in logic, it looks like there's a terminology clash here. The problem is that there are (at least) three notions of "always true" kicking around for first-order sentences. I'll use the terminology I learned for them, but in my experience this can vary from source to source:

• Validities. These are sentences which are always true, semantically speaking: $\varphi$ is a tautology iff $\mathcal{M}\models\varphi$ for every structure $\mathcal{M}$.

• Tautologies. These are sentences which are provable using no nonlogical hypotheses in whatever proof system we're using: $\varphi$ is a tautology iff $\emptyset\vdash\varphi$.

Of course by the completeness theorem we know that validities = tautologies, but this is nontrivial.

Then in a separate, less-pleasant$^*$ bucket we have:

• Truth-functional tautologies. These are the statements whose "propositional projections" (I don't actually know a term for this) are tautologies in the sense of propositional logic. Basically, we forget everything about the sentence in question except for its "top-level" Boolean structure. For example, the propositional projection of $$\forall x(P(x)\wedge Q(x))\rightarrow [\neg \forall x(\neg S(x))\wedge \exists z(R(z,z)]$$ is (up to changing the names of the propositional atoms involved) $$p\rightarrow [\neg q\wedge r].$$

In your example, using the terminology abouve you have a sentence which is a tautology (hence by completeness a validity) but not a truth-functional tautology.

---

$^*$Truth-functional validity for first-order sentences is a pretty pathological notion, at least from a mathematical perspective: two equivalent first-order sentences could have totally unrelated propositional projections. We do have "truth-functional tautology implies tautology," but the converse fails even for very simple sentences (as in your example).