# Non-trivial example of Quantifiers

1. Aug 2, 2013

### Dragonfall

Can I have a non-trivial example of where $\forall x P(x) \rightarrow \exists x P(x)$ fails?

2. Aug 2, 2013

### CompuChip

No, because it is a true statement.
Assume that $\forall x P(x)$. Let x_0 be arbitrary. Then $P(x_0)$. $\exists x P(x)$. QED.

The only way this can fail is if the universe of discourse is empty, in which case $\forall x P(x)$ is true and $\exists x P(x)$ is false, but I guess this is what you call the trivial case.

3. Aug 2, 2013

### economicsnerd

I don't know much formal logic at all, but under any logic that matches my intuition, $\forall x P(x) \rightarrow \exists x P(x)$ would be true whenever $\exists x$ is true.

4. Aug 3, 2013

### Dragonfall

Then I'm very confused. I thought no-NP languages are decision problems of the form $\forall x P(x)$ and NP languages are $\exists x P(x)$.

5. Aug 5, 2013

### Dragonfall

Wait, I figured it out. Nevermind.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook