Is $\forall x [\exists y\ Q(x,y)\ \lor\ \forall z\ \neg Q(x,z)]$ valid?

Question

Is $\forall x [\exists y\ Q(x,y)\ \lor\ \forall z\ \neg Q(x,z)]$ valid or merely a satisfiable formula?

I would appreciate an explanation as to why, because it seems a bit counter-intuitive to me.

Answer 1

$$\forall x:[\exists y: Q(x,y) \lor \forall z:\neg Q(x,z)]$$

Apply the laws of distribution over quantification; in this case: the universal of a negation is the negation of an existential.

$$\forall x:[\exists y:Q(x,y) \lor \neg\exists z:Q(x,z)]$$

If this isn't clear, we can change the symbols used in each scope as long as the new symbol isn't already used in the same scope.

$$\forall x:[\exists y:Q(x,y) \lor \neg\exists y:Q(x,y)]$$

So: Is this a tautology?

Answer 2

Suppose that exists $x$ such that for all $y$, $\neg Q(x;y)$ and there exists $z$ such that $Q(x;z)$. Then, for this $z$ we have $\neg Q(x;z)$ and $Q(x;z)$ simultaneously. This is a contradiction.