Question About Notation Nested Quantifiers.

Question

It's a pretty simple question on nested quantifiers but I didn't see anything about it on my Textbook or on Google so I wanted to give this a shot.

So let's say you have $P(x)$ and $P(y)$ and you have: $\forall x \exists y(P(x) \rightarrow P(y))$

Would this be equivalent to ($\forall x P(x) \rightarrow \exists y P(y)$)?

Looking at this, I want to say no... But I can't think of a counterexample to show that they aren't equivalent.

Answer 1

Both sentences are true in all $L$-structures. So they are, in an uninteresting way, equivalent.

Answer 2

Short answer: They are equivalent.

For this issue we just observe the occurrence of variables inside $∀x∃y(P(x)→P(y))$.

That is, $P(x)$ does not have any occurrence of $y$ in it, $P(y)$ does not have any occurrence of $x$ in it neither. Hence the scope of $∀$ and $∃$ are superfluous in some way, i.e. the above formula is equivalent to $(∀xP(x)→∃yP(y))$.

Answer 3

Both statements are equivalent (as tautologies) if the domain of quantification is non-empty. If it is empty, then your first statement is true, but the second is false.

This is easier to see if you make the domain of quantification explicit as follows:

1. $\forall x:[x\in U \implies \exists y: [y\in U \land [P(x)\implies P(y)]]$

2. $\forall x:[x\in U \implies P(x)] \implies \exists y:[y\in U\land P(y)]$

where $U$ is the domain of quantification.

Suppose $U=\emptyset$

(1) is vacuously true.

To prove (2) is false, we must prove $$\neg[\forall x:[x\in U \implies P(x)] \implies \exists y:[y\in U\land P(y)]]$$ or equivalently $$\forall x:[x\in U \implies P(x)] \land\neg \exists y:[y\in U\land P(y)]]$$

The left side is vacuously true. The right side is true by the obvious contradiction.