Negate nested quantifiers in predicate logic.

Question

I was wondering how the distribution of the negation works on a nested quantifier, taking into consideration the equivalent formulations.

This is what I mean. I have this sentence:

$\forall x(Ax\rightarrow\exists y(Bxy\wedge\neg Ay)).$

This is, following the equivalent sentence forms rule $(\forall x(P\rightarrow Q)\equiv\neg\exists x(P\wedge\neg Q))$, equal to

$\neg\exists x(Ax\wedge\neg\exists y(Bxy\wedge\neg Ay))$

It becomes,

$\neg\exists x(Ax\wedge\forall y(Bxy\rightarrow Ay)).$

Is it legitimate to pose the subformula $\exists(Bxy\wedge\neg Ay)$ as “Q” in the meta-formula $\forall x(P\rightarrow Q)$? Is, thus, the reasoning correct?

Thanks.

Answer 1

Yes, this is correct. The equivalence $\forall x(P\rightarrow Q)\equiv\neg\exists x(P\wedge\neg Q)$ is valid no matter what $P$ and $Q$ are, so they can be any formula you want.

Answer 2

Four quantifier rules to remember:

Negating Unrestricted Quantfiers

$\neg\forall x: P(x) \space \equiv\space \exists x: \neg P(x)$

$\neg\exists x: P(x)\space \equiv \forall x: \neg P(x)$

Negating Restricted Quantifiers

$\neg\forall x \in S: P(x) \space \equiv \space \exists x\in S: \neg P(x)\space $

$\neg\exists x \in S: P(x) \space \equiv \space \forall x\in S: \neg P(x)$

Fun Fact

For any set $S$ and any proposition $Q$, we have $\exists x: [x\in S \implies Q]$. (See Drinker's Paradox)