Given the equivalence between universal and existance quantifier, gather information from this statement.

Question

Taking into account

$$\forall x: p(x)\iff \lnot \exists x :\lnot p(x)$$ $$\exists x: p(x)\iff \lnot \forall x :\lnot p(x)$$

what information can I gather from $\forall x \exists y : P(x,y)$ ?

Is it true that

$$\forall x \exists y : P(x,y) \iff \nexists x \forall y : \lnot P(x,y)$$

? What are some other equivalences for $\forall x \exists y:P(x,y)$ ?

Answer 1

Yes. This follows from the following two principles:

1. The given equivalences (to replace existentials with universals using negations and vice versa) do hold not just for sentences, but for formulas in general.

2. When you have two equivalent formulas, then if you substitute the one for the other in some larger formula, then the resulting statement is equivalent to the original.

So in this case, we have:

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

But since we also have:

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

We get that:

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

And since

$\neg \neg \forall y \neg P(x,y) \Leftrightarrow \forall y \neg P(x,y)$

we finally get:

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