How to prove that $ ¬∀x∈A, ¬P(x) \equiv \exists x\in A, P(x) $ using quantifier negation

Question

I'm not needing assistance proving this statement.

$ ¬∀x∈A, ¬P(x) \equiv \exists x\in A, P(x) $

My first approach was to use demorgans laws but I'm having trouble with determining what to do next.

$ ¬∀x(x \in A, ¬P(x)) \equiv ¬\forall x(x \in A \wedge ¬P(x)) $

Answer 1

Quantifier negation is typically stated as:

Quantifier Negation

For any formula $\varphi(x)$:

$\neg \forall x \ \varphi(x) \Leftrightarrow \exists x \ \neg \varphi(x)$

$\neg \exists x \ \varphi(x) \Leftrightarrow \forall x \ \neg \varphi(x)$

But in the case of qualified quantifiers, it would be:

Qualified Quantifier Negation

For any formula $\varphi(x)$ and set $S$:

$\neg \forall x \in S \ \varphi(x) \Leftrightarrow \exists x \in S \ \neg \varphi(x)$

$\neg \exists x \in S \ \varphi(x) \Leftrightarrow \forall x \in S \ \neg \varphi(x)$

If you were given the latter, then what you need to show is trivial:

$\neg \forall x \in A \ \neg P(x) \Leftrightarrow \text{ (Qualified Quantifier Negation)}$

$\exists x \in A \ \neg \neg P(x) \Leftrightarrow \text{ (Double Negation)}$

$\exists x \in A \ P(x)$

So, assuming you were not given the Qualified Quantifier Negation principle, but only the 'normal' one, you will indeed have to rewrite the qualified quantifier as an unqualified quantifier, but as indicated by @Magdiragdag, you didn't do this right.

In general, you have that:

Rewriting Qualified Quantifiers as Unqualified Quantifiers

For any formula $\varphi(x)$ and set $S$:

$\forall x \in S \ \varphi(x) \Leftrightarrow \forall x (x \in S \rightarrow \varphi(x))$

$\exists x \in S \ \varphi(x) \Leftrightarrow \exists x (x \in S \land \varphi(x))$

Applied to your problem, we thus get:

$\neg \forall x \in A \ \neg P(x) \Leftrightarrow \text{ (Rewrite Qualified Quantifier)}$

$\neg \forall x (x \in A \rightarrow \neg P(x) \Leftrightarrow \text{ (Quantifier Negation)}$

$\exists x \neg (x \in A \rightarrow \neg P(x)) \Leftrightarrow \text{ (Implication)}$

$\exists x \neg (\neg x \in A \lor \neg P(x)) \Leftrightarrow \text{ (De Morgan)}$

$\exists x (\neg \neg x \in A \land \neg \neg P(x)) \Leftrightarrow \text{ (Double Negation)}$

$\exists x (x \in A \land P(x)) \Leftrightarrow \text{ (Rewrite Qualified Quantifier)}$

$\exists x \in A \ P(x)$