2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ $\forall x.Px \to \exists x.Px$ isn't true in an empty domain. You said "whenever something is true for all elements of some set, it as well holds for some elements of the same set"...unless there is nothing for that "some" to refer to. $\endgroup$
    – DanielV
    Apr 18 '18 at 19:27
  • 1
    $\begingroup$ You can't infer that $P(x)$ and $\neg P(x)$ are both false from their existential quantification being false, is where you go awry. And the $\forall\to\exists$ implication only holds in non-empty domains. Logicians just don't usually care about empty domains. $\endgroup$ Apr 18 '18 at 19:33
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Makes sense to me, however I still kind of confused with question #1: by stating $\exists x \in \{\}: P(x)$ and right after $\exists x \in \{\}: \lnot P(x)$ I get both $\forall x \in \{\}: P(x) \land \lnot P(x)$... is it also a regretful "side-effect" of the empty set? $\endgroup$
    – Zazeil
    Apr 18 '18 at 19:35
  • $\begingroup$ @SerejaBogolubov I think you've gotten things mixed up a bit: it's not that "$\exists x\in\emptyset: P$" and "$\exists x\in\emptyset: \neg P$" are both true, but rather that they're both false. So the things you're stating should be "$\neg\exists x\in\emptyset: P$" and "$\neg\exists x\in\emptyset: \neg P$" (in your comment above you don't have the "$\neg$" out in front). That said, yes, this is a consequence of the emptyset - but I wouldn't call it regrettable, I quite like it. $\endgroup$ Apr 18 '18 at 19:41
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ But does it mean that I can state both: every unicorn does have a horn, and at the same time, every unicorn does NOT have a horn? By question #1 in the OP? $\endgroup$
    – Zazeil
    Apr 18 '18 at 19:31
  • 3
    $\begingroup$ @SerejaBogolubov Yes. Both statements are true! Just like: every time I have played the lottery, I won the jackpot! ... this is true exactly because I have never played the lottery. Indeed, it is also true that every time I played the lottery, pigs started to fly! $\endgroup$
    – Bram28
    Apr 18 '18 at 19:32
  • 3
    $\begingroup$ Every unicorn is purple, and also every unicorn is white. $\endgroup$
    – vadim123
    Apr 18 '18 at 19:32
3
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.