Is this equivalent?

Question

Im having a dillema , is

∀x(p(x) -> ∃y n(y))
and
∃x p(x) -> ∃y n(y)

equivalent? it seems at all cases its the same, is it really equivalent?

Answer 1

A universal can be seen as kind of conjunction, that is, if $a,b,c,...$ denote the objects in your domain, then you can think of a universal like this:

$$\forall x \: P(x) \approx P(a) \land P(b) \land P(c) \land ...$$

I write $\approx$, since this is technically not a logical equivalence, but it does capture the semantics of the quantifier. As such, you can 'prove' the following law:

Prenex Laws

Where $P(x)$ is any formula and where $x$ is not a free variable in $Q$:

$$ \forall x \ P(x) \lor Q \Leftrightarrow \forall x (P(x) \lor Q)$$

'Proof':

$$\forall x (P(x) \lor Q) \approx$$

$$(P(a) \lor Q) \land (P(b) \lor Q) \land (P(c) \lor Q) \land ... \Leftrightarrow \text{(Distribution } \lor \text{ over } \land)$$

$$(P(a) \land P(b) \land P(c) \land ...) \lor Q \approx$$

$$\forall x \ P(x) \lor Q$$

With this, we can now prove your equivalence as well:

$$\forall x (p(x) \rightarrow \exists y \ n(y)) \Leftrightarrow \text{ (Implication)}$$

$$\forall x (\neg p(x) \lor \exists y \ n(y)) \Leftrightarrow \text{ (Prenex Law)}$$

$$\forall x \neg p(x) \lor \exists y \ n(y) \Leftrightarrow \text{ (Quantifier Negation)}$$

$$\neg \exists x p(x) \lor \exists y \ n(y) \Leftrightarrow \text{ (Implication)}$$

$$\exists x p(x) \rightarrow \exists y \ n(y)$$

Answer 2

I misread so ignor my comment.

The parenthesis is important.

$\forall x(p(x) \to \exists y n(y))$

Means for every $x$, if $p(x)$ then there exists a y so that $n(y)$. So it might be possible that there are no $x$ so that $p(x)$. But if any $x$ has $p(x)$ being true then there is a $y$ that $n(y)$ is true.

$\exists xp(x) \to \exists y n(y)$ means that if there is any $p$ so that $p(x)$ then there is a $y$ so that $n(y)$.

Those are the same.

Consider $p=$ went to college. And $n$ lives in a pool.

So the first says, for every person, if that person went to college then there is a person who live in a pool. Now maybe nobody went to college and no-one lives in a pool, but if anyone went to college, there's a person living in a pool.

The second says, if there is a person who went to college, then there is someone who lives in a pool. Again maybe nobody went to college and no-one lives in a pool, but if anyone went to college, there's a person living in a pool.

They are equivalent.