$\forall x(P(x) \rightarrow Q(x))\stackrel{?}{\equiv}\neg\exists x(P(x) \rightarrow \neg Q(x))\stackrel{?}{\equiv}\neg\exists x(P(x) \wedge\neg Q(x))$

78 Views Asked by At

Statement $1$: The statement $\forall x(P(x) \rightarrow Q(x))$ reads "For all $x$, if $P(x)$, then $Q(x)$".

Statement $2$: The statement $\neg\exists x(P(x) \rightarrow \neg Q(x))$ reads "There does not exist an $x$ such that if $P(x)$, then not $Q(x)$".

Statement $3$: The statement $\neg\exists x(P(x) \wedge \neg Q(x))$ reads "There does not exist an $x$ such that $P(x)$ and not $Q(x)$".

When I think about these statements by only considering their meaning, I can't seem to come up with any distinctions between their meaning. I can use De Morgan's Law to show that statements $1$ and $3$ are logically equivalent. However, I am unable to show that statement $2$ is equivalent to the other two.

Could someone explain the difference in the meaning between statement $2$ and the other statements, perhaps with an example?

1

There are 1 best solutions below

1
On

We can work with the different equivalent transformations of the formulas.

We agree that 1 and 3 are equivalent and 3 says that "there is no object $a$ such that $P(a)$ and $\lnot Q(a)$".

But this is consistent with: "for some $b$, $\lnot P(b)$ and $Q(b)$".

Consider 2 now: it is equivalent to $¬∃x(¬P(x) \lor ¬Q(x))$ and to $∀x(P(x) ∧ Q(x))$

But this is not consistent with "for some $b$, $\lnot P(b)$ and $Q(b)$".


Example: 1 may be "for every x, if x is Male, than it is Human" that is the same as "there is no x that is Male and not Human", which is True.

Thus, 2 will be "there is no x such that if x is Male, than x is not Human", which is False because it amounts to "for every x, x is a Male and it is Human" (there are Women).