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.
6 Answers
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.
-
$\begingroup$ Okay that's pretty interesting argument. But why doesn't it work the other way around? -- Pretend that I'm asserting "There exists an
x∈Ssuch thatP(x)doesn't hold." How could you declare me to be a liar? You would have to produce an element of the set (S=∅, in this case) that does have the propertyP(x). Since S is the empty set, you can't convince me that there is anxsuch thatP(x)holds, therefore my assertion is true. ... I'm easily getting lost in logic. $\endgroup$– bodacydoSep 25, 2012 at 21:48 -
2$\begingroup$ If you're asserting "there exists such-and-such" and I declare you to be a liar, it is your job to show me an actual something and defend the proposition that this particular something is a such-and-such. Someone claiming $\exists$ is a liar by default (just as someone who claims $\lor$ is), whereas someone claiming $\forall$ is right unless his opponent can find a counterexample (just as someone who claims $\land$ can relax until his opponent names one of the conjuncts that he claims is false). $\endgroup$ Sep 25, 2012 at 21:53
-
$\begingroup$ @HenningMakholm Suppose I claim that there is a well-ordering of the reals, and you declare me be to a liar ... $\endgroup$ Sep 25, 2012 at 22:03
-
1$\begingroup$ @PeterSmith: Then you make a call upon your good friend Axiom of Choice, and he goes out into his back room and does something magical whereupon he returns with a something that you then present to me. I have no idea how he does it. $\endgroup$ Sep 25, 2012 at 22:12
-
$\begingroup$ @HenningMakholm Indeed! :-) The serious point, though, is that issues pro or contra a constructivist reading of disjunction/existentials are one thing, and issues about the treatment of vacuous quantifiers surely something else. $\endgroup$ Sep 25, 2012 at 22:23
"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.
-
18$\begingroup$ Congratulations on your children's success! $\endgroup$ Sep 25, 2012 at 22:11
-
4$\begingroup$ Thank you, they have all topped the charts and become pop icons! All of them. $\endgroup$– 2'5 9'2Sep 26, 2012 at 2:23
-
6$\begingroup$ Since I wrote this, things have changed. None of my children are rock stars, but they might be some day. $\endgroup$– 2'5 9'2Feb 26, 2018 at 15:13
-
1$\begingroup$ @user599310 Empty sums, empty products, empty conjunctions. All the same. Let me start with an empty sum. People often think of $\sum_{i=1}^n{x_i}$ as $x_1+\cdots+x_n$. Imho this is flawed for lacking symmetry. It has $n$ operands but only $n-1$ operators. I suggest thinking of it as "add $x_1$, add $x_2$, ..., add $x_n$. So it's the operator: ${}+x_1+x_2+\cdots+x_n$. Reach a value (instead of an operator) by applying it to $0$: $0+x_1+x_2+\cdots+x_n$. So when the summation is empty, you just have $0$. Continued below. $\endgroup$– 2'5 9'2Nov 1, 2020 at 19:51
-
1$\begingroup$ An empty conjunction is the same, with "true" as the base instead of $0$, since "true" is the identity operand for conjunction. Assuming for now $X$ has a finite $n$ elements, "$\forall x\in X, P(x)$" is the same as $\bigwedge_{i=1}^nP(x_i)$, which under what I outline above, is nicely interpreted as $``\text{true}\wedge P(x_1)\wedge P(x_2)\wedge\cdots\wedge P(x_n)"$. And if $n=0$, that's just "true". $\endgroup$– 2'5 9'2Nov 1, 2020 at 19:54
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.
∀x∈S(R(x))is true, then allx∈Smust haveR(x)true. Since there is no suchxfor empty setS, the statement∀x∈S(R(x))is false. ... What happened? $\endgroup$