Can anyone explain why the predicate all
is true for an empty set? If the set is empty, there are no elements in it, so there is not really any elements to apply the predicate on? So it feels to me it should be false rather than true.
Why is predicate "all" as in all(SET) true if the SET is empty?
-
0http://en.wikipedia.org/wiki/Vacuous_truth – 2013-01-03
6 Answers
"All of my children are rock stars."
"If we go through the list of my children, one at a time, you will never find one that is not a rock star."
Do you want the above two sentences to mean the same thing?
Also, do you want
"Not all of my children are rock stars."
to mean the same as
"At least one of my children is not a rockstar"?
Because in the situation that I have no children, the last statement is false, so we would want "all of my children are rock stars" to be true to preserve dichotomy.
-
3Since I wrote this, things have changed. None of my children are rock stars, but they might be some day. – 2018-02-26
It hinges on the Law of the Excluded Middle. The claim itself is either TRUE or FALSE, one way or the other, not both, not neither.
Pretend that I am asserting "For every $x\in S$, property $P(x)$ holds." How could you declare me to be a liar? You would have to produce an element of the set ($S=\varnothing$, in this case) that does not have the property $P(x)$. Only then can you declare my assertion FALSE. Since you cannot do that here, my assertion is TRUE. I essentially spoke the truth by NOT speaking a lie.
-
0(...) But I agree that this is at best tangentially related to vacuous quantification. I jumped in because bodacydo seemed to have problems with the general mode of argument that bwsullivan (for better or worse) brought in. – 2012-09-25
It could be taken the other way, but it's simpler this way.
Say we believe that all rubies are red, and we consider some some collection of rubies, called $R$; say $R$ is all my rubies.
We would like to conclude that all my rubies are red. This seems very reasonable, since all rubies are red. But with your idea, this conclusion might be false! At best we can say that all my rubies are red, if I have any rubies.
This qualification doesn't add anything to the analysis. It doesn't illuminate any subtle point. It just complicates the discussion with an uninteresting special case.
Since the purpose of formal logic is to model plausible reasoning as closely and as simply as possible, we agree to the convention that "all my rubies are red" is deemed to be true even when I have no rubies, so that we don't have to qualify a lot of claims with "… if there are any such rubies".
Another approach: the 'vacuous truth' for $\forall$ is roughly the logical equivalent of an empty product being defined as 1 or an empty sum being defined as 0. Just as we want $\sum_{i=1}^{n+1} a_i = a_{n+1} + \sum_{i=1}^{n} a_i$ (and want this to hold in every case, even the 'base case' where $n=0$) and want $\prod_{i=1}^{n+1} a_i = a_{n+1}\cdot \prod_{i=1}^{n} a_i$, so too we want $\forall x\in (S\cup \{z\})\ P(x) \Longleftrightarrow \bigl(\ (\forall x\in S\ P(x))\ \wedge P(z)\bigr)$ to hold even in the 'base case' where $S$ is empty. You should be able to convince yourself (through some relatively straightforward logical manipulation) that this is requires defining $\forall x\in\emptyset \ P(x)$ to be true for all predicates $P()$.
It kind of makes sense. If I understand correctly, I think you want to prove:
$\forall x (x\in \phi \rightarrow Q)$
where:
$\forall x (x\notin \phi)$
Q is any proposition whatsoever.
Proof: Suppose $y\in \phi$. We want to prove that $Q$ is true for any proposition $Q$ whatsoever. Suppose to the contrary that $Q$ is false.
Applying the definition of $\phi$ to $y$, we obtain the contradiction $y\notin \phi$. Therefore, by contradiction, $Q$ must be true. We have:
$y\in \phi \rightarrow Q$
Generalizing, we obtain, as required:
$\forall x (x\in \phi \rightarrow Q)$
An extension of the comment to bwsullivan's answer:
Suppose for all elements in a set P(x) holds and P(x) doesn't hold, i.e.
$\forall x \in A: P(x) \land \forall x \in A: \neg P(x)$
Suppose $y \in A$
then $P(y)\land \neg P(y)$
a contradiction.
So $\forall y: \neg y \in A$
I.e. $A = \emptyset$
Now if you made $\forall x \in A: P(x) $ or $ \forall x \in A: \neg P(x)$ not true for the empty set, you couldn't conclude this.