Relationship between $\exists$ and $\forall$ and how do they go together with empty set $\{\}$?

Question

I was trying to get a deeper insight into quantifiers. So, as far as I understand, $\forall x : P(x) \rightarrow \exists x : P(x)$, which is a common sense: whenever something is true for all elements of some set, it as well holds for some elements of the same set.

Then I get to the following:

Since empty set contains no elements, $\exists x \in \{\}: P(x)$ is always false regardless of what $P(x)$ states.

But by the definition of the universal quantifier, $\forall x : P(x) \equiv \lnot \exists x : \lnot P(x)$, any universal statement about the empty set statement must be true.

---

Now two questions:

1) I can state that $\exists x \in \{\}: P(x)$, which is false by definition. Than I go crazy and try to restate myself to a $\exists x \in \{\}: \lnot P(x)$, which is also false. Now I got into trouble: both $P(x)$ and $\lnot P(x)$ are false and, as a consequence, both $\forall x \in \{\}: P(x)$ and $\forall x \in \{\}: \lnot P(x)$ are true.

2) But according to the implication I mentioned at the very top, $\forall x \in \{\}: P(x) \rightarrow \exists x \in \{\}: P(x)$ and $\forall x \in \{\}: \lnot P(x) \rightarrow \exists x \in \{\}: \lnot P(x)$.

I am not mathematician and thus probably missing something important. Can someone enlighten me?

Answer 1

The "common sense" statement $$\forall x\ P(x) \to \exists x\ P(x)$$ is FALSE, because the universe may be empty. The OP has a proof already, but lacks the intuition to believe this proof.

Here is a way to build that missing intuition. "Every unicorn has a horn" is a true statement, but "There exists a unicorn that has a horn" is a false statement.

Answer 2

The implication you mentioned at the very top is not true in general: to go from a "$\forall$" to an "$\exists$," we need exactly that the domain be nonempty.

---

Now, there is a subtlety here which can crop up down the road. In first-order logic, we (usually) restrict attention to nonempty structures (= universes of discourse). However, definable subsets may still be empty. E.g. maybe our domain of discourse is "animals," which is a nonempty set, but we happen to be talking about the subset of "fish larger than the moon," which is empty.

So we have the following obnoxious situation in "first-order logic without empty structures":

"$\forall x(\varphi(x))$" does imply "$\exists x (\varphi(x))$," but "$\forall x\in P(\varphi(x))$" does not imply "$\exists x\in P(\varphi(x))$."

This can be made less mysterious by remembering that "$\forall x\in P(\varphi(x))$" and "$\exists x\in P(\varphi(x))$" are shorthand for "$\forall x(x\in P\implies\varphi(x))$" and "$\exists x(x\in P\wedge\varphi(x))$" respectively. Note the difference between "$\implies$" and "$\wedge$," there: we don't have an exact parallel.

This is an unfortunate context of ruling out the empty structure in first-order logic. There are also arguments in favor of ruling out the empty structure; ultimately, you just have to be careful to keep track of which convention you're using and how that affects the meaning of the statements you're looking at.

Answer 3

So, as far as I understand, $\forall x : P(x) \rightarrow \exists x : P(x)$, which is a common sense: whenever something is true for all elements of some set, it as well holds for some elements of the same set.

Except when, as you yourself found out, the set is empty.

The assumption that the domain is not empty is called the Assumption of Existential Import.

Most practical logic systems make this assumption, which is why in most systems you can infer $\exists x \ P(x)$ from $\forall x \ P(x)$.

However, in free logics this assumption is not made, and so in free logics you cannot infer $\exists x \ P(x)$ from $\forall x \ P(x)$.

Now I got into trouble: both $P(x)$ and $\lnot P(x)$ are false and, as a consequence, both $\forall x \in \{\}: P(x)$ and $\forall x \in \{\}: \lnot P(x)$ are true.

Why does this get you into trouble? It is vacuously true that $\forall x \in \{\}: P(x)$ and $\forall x \in \{\}: \lnot P(x)$ are true: Yes, all zero objects from the set have property $P$ ... exactly because there are zero objects. And this is also why all zero objects lack property $P$.

Compare: "Every time I have played the lottery, I won the jackpot!" This is true, I swear! Why? Because I am super lucky? No, it's true because I have never played the lottery. Indeed, it is also true that every time I played the lottery, I didn't win the jackpot. And it is true that every time I played the lottery, pigs started to fly!

Another way to think about it: When I make a claim that something is true for some set of objects, how would you test that claim? Well, you could line up all objects of the set outside the door, have them come in one by one, and see if they have the property. Then, when the line is all cleared, and I haven't found a counterexample to my claim, you would say "Yes, you are right, all objects do have this property". Well, with an empty set, the line is cleared from the very start, and so there cannot be a counterexample, making my claim trivially true.