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?



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.


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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.