Is $\forall xP(x) \vee \neg \forall yP(y)$ a tautology in FOL?

96 Views Asked by At

I am claiming that $$\forall xP(x) \vee \neg \forall yP(y)$$ is a tautology, since if we denote $\varphi = \forall xP(x)$ and we know that $(\varphi \vee \neg\varphi)$ is a tautology in propositional logic and is equivalent to our given formula then the given formula is a tautology.

However, my text says that it is not a tautology.

I can't find a way to show that this formula is indeed not a tautology.

1

There are 1 best solutions below

2
On BEST ANSWER

$$\forall xP(x) \vee \neg \forall yP(y)$$

The given formula has truth-functional form $$A∨¬B,$$ so is not a (propositional-logic) tautology. Because it is equivalent to $$\forall xP(x) \vee \neg \forall xP(x),$$ it certainly is a first-order validity. You might call it a "first-order tautology".

While some FOL texts consider "validity" and "tautology" synonymous, your textbook is using a strict definition of "tautology" referring specifically to propositional-logic tautologies.