1
$\begingroup$

When get general logic statements of vacuous truth, seems that the allowed forms are only for 'all ($\forall$)', and not for 'there exist ($\exists$)'. For example, in wiki, it shows the possible universally quantified statements are:

  • $\forall x:P(x)\Rightarrow Q(x)$, where it is the case that $\forall x:\neg P(x)$.
  • $\forall x\in A:Q(x)$, where the set $A$ is empty.
  • $\forall \xi :Q(\xi )$, where the symbol $\xi$ is restricted to a type that has no representatives.

I dont understand why there is no form constructed by $\exists$, for example:

$\exists x\in A:Q(x)$, where the set $A$ is empty.

In my understanding, this statement is equivalent to say: "if there exist $x\in A$, then $Q(x)$ is true". When $A$ is empty, that means the "there exist $x\in A$" is false, i.e. the $P$ of "$P\Rightarrow Q$" is false, then logically, the statement should be vacuously true.

Could someone tell me where is wrong with this statement?

(I know it's wrong as it is used to show "$\varnothing\not\subset A$ is false instead of vacuous true". See, for example, in discussion: "$X$ is not a subset of $A$", in symbols $X\not\subset A,$ means $\exists x(x\in X\text{ and }x\notin A).$ If $X$ has no elements, this existential statement is not true vacuously, it is simply false.).

$\endgroup$
  • 2
    $\begingroup$ No; $\exists x \in A Q(x)$ is defined as : $\exists x (x \in A \land Q(x))$. If $A$ is empty, the formula is FALSE. Thus, it is not "vacuous" and it is not TRUE. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '18 at 16:30
  • $\begingroup$ "In my understanding, this statement is equivalent to say: "if there exist x∈A, then Q(x) is true". Where are you getting the "if" from? The statement has no IF. The statement reads as: The IS (no "if" about it) an $x \in A$ and for that $x$ $Q(x)$ is true". If $A$ is empty that statement can not be true because no $x \in A$ can possibly exist, much less one where $Q(x)$ is true. $\endgroup$ – fleablood Sep 4 '18 at 16:45
  • $\begingroup$ Consider the natural-language examples: "There is a unicorn which is blue" (= $\exists x\in U: B(x)$) versus "Every unicorn is blue" (= $\forall x\in U: B(x)$). The former is false, since there are no unicorns at all, let alone blue ones; the latter is true (there isn't a counterexample!). Does this help? $\endgroup$ – Noah Schweber Sep 4 '18 at 19:51
  • $\begingroup$ @NoahSchweber Can you say more clear? How to get the form of the counterexample of the latter one and find it is false? This example really confusing me when I thought I am clear. I can also treat "there are no unicorns at all, let alone it is blue" as the counterexample of "Every unicorn is blue". $\endgroup$ – X liu Sep 4 '18 at 21:53
  • 1
    $\begingroup$ @Xliu A counterexample to "Every X is Y" is: an X which is not Y. If I can't find any X at all, I certainly can't find a counterexample to the statement "Every X is Y." $\endgroup$ – Noah Schweber Sep 5 '18 at 0:03
5
$\begingroup$

$\exists x \in A : Q(x)$ means there exists an $x$ that is a member of $A$ and $Q(x)$ is true. If there are no members of $A$ this cannot be true. We don't care about what $Q(x)$ says because $\exists x \in A$ is already false.

$\endgroup$
5
$\begingroup$

On $\exists x\in A:Q(x)$

In my understanding, this statement is equivalent to say: "if there exist $x\in A$, then $Q(x)$ is true"

Your understanding is wrong. Rather, the statement is ”There exists an $x$ such that $x\in A$ and $Q(x)$ is true.

Or in symbols, the long form for $\exists x\in A: Q(x)$ is not $\exists x: x\in A\implies Q(x)$, but rather $\exists x: x\in A\land Q(x)$.

Note that this is in contrast to $\forall x\in A: Q(x)$, which indeed does mean the same as $\forall x: x\in A\implies Q(x)$.

The rule for the $\exists$ quantifier can be derived from the rule of the $\forall$ quantifier as follows: $$\begin{aligned} \exists x\in A: Q(x) &\iff \lnot \forall x\in A: \lnot Q(x)\\ &\iff \lnot \forall x: x\in A \implies \lnot Q(x)\\ &\iff \lnot \forall x: \lnot x\in A \lor \lnot Q(x)\\ &\iff \lnot \forall x: \lnot (x\in A \land Q(x))\\ &\iff \exists x: x\in A \land Q(x) \end{aligned}$$

$\endgroup$
  • 1
    $\begingroup$ @Xliu: I think you mean “when $A$ is empty”, When $A$ is empty, then $x\in A$ is false for all $x$ (that's what “$A$ is empty” means), and therefore for all $x$ we get $False\implies Q(x)$, which is true by the principle of explosion. $\endgroup$ – celtschk Sep 4 '18 at 16:36
  • 1
    $\begingroup$ @Xliu: $\forall x\in A: Q(x)$ is $\forall x: x\in A\implies Q(x)$. Here you have $P\implies Q$ with $P \equiv x\in A$ which for $A$ empty is indeed false. Actually, if you look at the first line of my derivation, you see that $\exists x\in A: Q(x)$ is equivalent to $\lnot \forall x\in A: \lnot Q(x)$. Now $\forall x\in A: \lnot Q(x)$ is vacuously true (still assuming $A$ is empty), thus we have the negation of a vacuous truth. The negation of a truth is, of course, false. $\endgroup$ – celtschk Sep 4 '18 at 17:12
  • 1
    $\begingroup$ @Xliu: Not exactly; the correct statement is: “For all $x$, if $x\in A$, then $Q(x)$ is true”. The “for all $x$” part is important and cannot be omitted, as otherwise $x$ would be a free variable (that is, it would be a statement about some specific $x$, not a statement about all possible $x$). From a formal point of view, it's just a definition. However this definition makes sense, as quite obviously a statement like “all sheep are white” doesn't tell you anything about non-sheep. But if that statement is true, anything that happens to be a sheep must be white. $\endgroup$ – celtschk Sep 4 '18 at 21:06
  • 1
    $\begingroup$ A “$\forall x$” statement is true only if you get a true statement no matter what you insert for $x$. And it's vacuously true only if you get a vacuously true statement no matter what you insert for $x$. So if you have $\forall x:x\in\emptyset\implies Q(x)$, the statement $x\in\emptyset$ is false for each of the possible values for $x$, so you get a vacuous truth. But if you replace $\emptyset$ e.g. with $\{\emptyset\}$, it no longer is vacuously true, as $x=\emptyset$ makes the condition true. The full claim may still hold (namely if $Q(\emptyset)$ happens to be true), but not vacuously so. $\endgroup$ – celtschk Sep 4 '18 at 21:33
  • 1
    $\begingroup$ Well, with “for all $x$” it's another statement; one that says that the statement without “for all” is true for all $x$. And what do you mean with “not always needed”? Those are examples for vacuously true statements; if you remove the “for all”, then you get different statements. Those different statements may still be vacuously true, but they are no longer the same statement. But if all you mean is that there are vacuously true statements that don't use the quantifier, then yes, in that sense the quantifier is not needed. $\endgroup$ – celtschk Sep 4 '18 at 21:51
2
$\begingroup$

At the request of the OP, let me expand on my comments.

It's always a good idea to start with an intuitive picture of what's going on (if such a thing is available). In this case, consider the natural-language examples: "There is a unicorn which is blue" (= $\exists x\in U: B(x)$) versus "Every unicorn is blue" (= $\forall x\in U: B(x)$). The former is false, since there are no unicorns at all, let alone blue ones; the latter is true (there isn't a counterexample!).

Now, let's dive a bit more into the claim that "$\forall x\in U: B(x)$" is true. Certainly if I said "All unicorns are blue," you would respond "But that's silly - there aren't any unicorns at all!" The important point, however, is that silliness is not falsehood. Statements like this - which begin with a quantification over the empty set - are silly, but true. To convince yourself of this, go back to the definition of "$\forall$": a statement of the form $$\forall x:\varphi(x)$$ is false if and only if there is a counterexample - namely, some $x$ for which $\varphi(x)$ fails. Similarly, a statement of the form $$\forall x\in A: \varphi(x)$$ is false if and only if there is a counterexample - namely, some $x$ in $A$ for which $\varphi(x)$ fails. Since there is no unicorn which is not blue, the statement "All unicorns are blue" is true, even though it's silly.

Incidentally, by the same argument, the statement "All unicorns are not blue"is also true. This is in fact a way you can tell that a set is empty: if you prove "All $x\in A$ are $P$" and "All $x\in A$ are not $P$," you can conclude that $A$ is empty, since that's the only way this situation could possibly happen.

$\endgroup$

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.