Logic question about equivalency...

Question

How one can show that the following are equivalent...?

$$\forall x \exists y(P(x)\to Q(x))$$

and

$$\neg \exists x \forall y\neg(P(x)\to Q(x))$$

Answer 1

Let $\phi(x,y)$ be a predicate.

To prove that $\forall x \exists y\phi(x,y) \iff \neg \exists x \forall y\neg\phi(x,y)$, first assume that $\forall x \exists y\phi(x,y)$ is true and try to prove that $\neg \exists x \forall y\neg\phi(x,y)$ is true and afterwards assume that $\neg \exists x \forall y\neg\phi(x,y)$ is true and try to prove that $\forall x \exists y\phi(x,y)$ is true.

$\Longrightarrow:$ Suppose $\forall x \exists y\phi(x,y)$ is true and argue, hoping to find a contradiction, that $\neg \exists x \forall y\neg\phi(x,y)$ is false. Then there exists $a$ such that $\forall y\neg \phi(a,y)$. By assumption it is also true that $\exists y\phi(a,y)$, this means that there exists $b$ such that $\phi(a,b)$. Now since $\forall y\neg \phi(a,y)$ is true, it is true in particular for $b$, that is $\neg\phi(a,b)$. Thus $\phi(a,b)\land \neg \phi(a,b)$, a contradiction.

For the other direction I leave you with just a layout.

$\Longleftarrow :$ Suppose $\neg \exists x \forall y\neg\phi(x,y)$ is true. You want to prove that $\forall x \exists y\phi(x,y)$ is true, so take an arbitrary element in the universe $a$ and your thesis becomes $\exists y\phi(a,y)$. Suppose this is false and prove that $\forall y\neg \phi(a,y)$. Find a contradiction.

Answer 2

In classical logic, the following methods of transforming a formula yield an equivalent formula.

1. Introduce a double negation.

2. Move a negation through a quantifier, replacing that quantifier with its opposite ($\forall$ becomes $\exists$ and vice versa).

Thus, the following are equivalent.

• $\forall x \exists y P(x,y)$
• $\forall x \exists y \neg \neg P(x,y)$
• $\forall x \neg \forall y \neg P(x,y)$
• $\neg \exists x \forall y \neg P(x,y)$

By the transitivity of equivalence, the result of interest follows.