If we had $\exists x [\text{PLAY}(x) \rightarrow \text{CLIMB}(c)]$, is this equal to $\exists x [\text{PLAY}(x)] \rightarrow \text{CLIMB}(c)$ as the scope of the quantifier does not contain $\text{CLIMB}$ in either case? Does this therefore mean that they have the same truth value, that: there is some $x$ which has the proposition $\text{PLAY}$, and if this is true, then there is some $c$, which has the proposition $\text{CLIMB}$?
Asked
Active
Viewed 735 times
3 Answers
4
Suppose $x$ does not exist, i.e. the domain from which $x$ is drawn is empty. The first proposition is false, but the second is true.
Clarifying, as requested in the comments:
If $x$ does not exist, then $\exists x$ always fails. In the first proposition, that causes the whole proposition to be false. In the second one, it only causes the premise to be false, which makes the whole proposition vacuously true.
vadim123
- 82,796
-
Under the usual interpretation of quantifier logic, the "universe of discourse: is nonempty, so that $\forall xP(x)$ implies $\exists xP(x).$ Thus the second statement is stronger than the first one. – bof Feb 10 '16 at 18:47
-
@bof: that seems like a bad convention. Then you constantly need to check whether the sets you're quantifying over are in fact nonempty or not. – Qiaochu Yuan Feb 10 '16 at 18:55
-
So, why is this the case? If x does not exist, why is it that the two have different truth outcomes? – Regina Phalange Feb 10 '16 at 19:18
2
The first sentence does not imply the second one. Consider an interpretation where $c$ does not climb; in this case the first sentence says that there is someone who does not play, the second sentence says that no one plays.
On the other hand, the second sentence implies the first one (under the usual assumption that the domain is nonempty). This becomes clearer if we eliminate the confusing implications in favor of conjunctions, disjunctions, and negations: $$\exists x[P(x)\rightarrow C(c)]\iff\exists x[\neg P(x)\vee C(c)]\iff\exists x\neg P(x)\vee\exists xC(c)\iff\exists x\neg P(x)\vee C(c);$$ $$\exists xP(x)\rightarrow C(c)\iff\neg\exists xP(x)\vee C(c)\iff\forall x\neg P(x)\vee C(c).$$
bof
- 78,265
0
$\text{ and }$ factors out of $\exists$, while $\text{ or }$ factors out of $\forall$:
$$\exists x ~:~ \bigg(y \text{ and } f(x) \bigg) = y \text { and }\bigg(\exists x ~:~ f(x)\bigg)$$
$$\forall x ~:~ \bigg(y \text{ or } f(x) \bigg) = y \text { or }\bigg(\forall x ~:~ f(x)\bigg)$$
Also, $\text{ and }$ factors out of $\forall$, while $\text{ or }$ factors out of $\exists$ if they are within another quantifier:
$$\frac \forall \exists z ~:~ \dots \exists x ~:~ \bigg(y \text{ or } f(x) \bigg) \dots = \frac \forall \exists z ~:~ \dots y \text { or }\bigg(\exists x ~:~ f(x)\bigg) \dots $$
$$\frac \forall \exists z ~:~ \dots \forall x ~:~ \bigg(y \text{ and } f(x) \bigg) = \frac \forall \exists z ~:~ \dots y \text { and }\bigg(\forall x ~:~ f(x)\bigg) \dots $$
$$\exists x ~:~ \bigg(\text{Play}(x) \implies \text{Climb}(c)\bigg)$$ $$\exists x ~:~ \bigg(\text{ not }\text{Play}(x) \text{ or } \text{Climb}(c)\bigg)$$
So here you can see that since the $\text{or}$ is within a $\exists$ which itself is not within another quantifier so you are stuck. But as it turns out, if you have defined anything anywhere else in your logic, that is equivalent to wrapping the expression in a quantifier.
Presumably, $c$ is defined somewhere. So you can proceed with factoring:
$$\bigg(\exists x ~:~ \text{ not }\text{Play}(x) \bigg)\text{ or } \text{Climb}(c)$$ $$\text{ not }\text{ not }\bigg(\exists x~:~ \text{ not }\text{Play}(x) \bigg)\text{ or } \text{Climb}(c)$$ $$\text{ not }\bigg(\forall x ~:~ \text{Play}(x) \bigg)\text{ or } \text{Climb}(c)$$ $$\bigg(\forall x ~:~ \text{Play}(x) \bigg) \implies \text{Climb}(c)$$
So
$$\exists x ~:~ \bigg(\text{Play}(x) \implies \text{Climb}(c)\bigg) \text{ is equivalent to } \bigg(\forall x ~:~ \text{Play}(x) \bigg) \implies \text{Climb}(c)$$
if they are within another quantifier, which is the case if anything is defined .
DanielV
- 23,556