Logic. Does RHS imply LHS?

Question

Does RHS implies LHS here: $\exists x[P(x)\land\neg Q(x)] : \neg \forall x[P(x) \to Q(x) ]$

I know that LHS implies RHS and I could prove it. However, I think that RHS does not imply LHS, but I cannot think of counter example.

Answer 1

They are equivalent, because $¬∀x \ [P(x) \to Q(x)] \equiv ∃x \ ¬[P(x) \to Q(x)]$, by De Morgan's laws for quantifiers.

In turn, we have $\lnot (Px \to Qx) \equiv \lnot(\lnot Px \lor Qx)$ by Material implication.

Then applying propositional De Morgan's laws we get :

$\lnot (Px \to Qx) \equiv (Px \land \lnot Qx)$.

---

For a Natural Deduction derivation of the propositional equivalence :

1) $\lnot (Px → Qx)$ --- premise

2) $Qx$ --- assumed [a]

3) $Px \to Qx$ --- from 2) by $\to$-intro

4) $\bot$ --- from 1) and 3)

5) $\lnot Qx$ --- from 2) and 4) by $\to$-intro, discharging [a]

6) $\lnot Px$ --- assumed [b]

7) $Px$ --- assumed [c]

8) $Qx$ --- from 6) and 7)

9) $Px \to Qx$ --- from 7) and 8) by $\to$-intro, discharging [c]

10) $\bot$ --- from 1) and 9)

11) $\lnot \lnot Px$ --- from 6) amd 10) by $\to$-intro, discharging [b]

12) $Px$ --- from 11) by Double Neg

13) $Px \land \lnot Qx$ --- from 5) and 12) by $\land$-intro

14) $\lnot (Px \to Qx) \to (Px \land \lnot Qx)$ --- from 1) and 13).

---

15) $(Px \land \lnot Qx)$ --- premise

16) $Px$ --- from 15) by $\land$-elim

17) $\lnot Qx$ --- from 15) by $\land$-elim

18) $(Px \to Qx)$ --- assumed [a]

19) $Qx$ --- from 16) and 18) by $\to$-elim

20)$\bot$ --- from 17) and 19)

21) $\lnot (Px \to Qx)$ --- from 18) and 20) by $\to$-intro, discharging [a]

22) $(Px \land \lnot Qx) \to \lnot (Px \to Qx)$ --- from 15) and 21).

The equivalence follows from 14) and 22) by Bi-conditional introduction.

---

---

Now we can "embed" the derivation above into the quantificational part. For the RHS to LHS :

1) $\lnot \forall x \varphi$ --- premise

2) $\lnot \exists x \lnot \varphi$ --- assumed [a]

3) $\lnot \varphi$ --- assumed [b]

4) $\exists x \lnot \varphi$ --- from 3)

5) $\bot$ --- from 2) and 4)

6) $\varphi$ --- from 3) and 5) by Double Negation, discharging [b]

7) $\forall x \varphi$ --- from 6) by $\forall$-intro

8) $\bot$ --- from 1) and 7)

9) $\exists x \lnot \varphi$ --- from 2) and 8) by Double Negation, discharging [a].

Answer 2

$\neg \forall x [Px \to Qx] \equiv \exists x \neg [Px \to Qx] \equiv \exists x [Px \wedge \neg Qx]$