0
$\begingroup$

I need help proving $\exists x:[D(x)\implies Q]$ for arbitrary unary predicate $D$ and proposition $Q$.

I think it should be possible since I have been able to prove a set-theoretic version: $\exists x: [x\in D \implies Q]$ for arbitrary set $D$ and proposition $Q$, but I don't see how to translate it into a purely FOL proof.


EDIT

On further consideration, the FOL version is clearly not true in general. Consider, for example, the case of $\forall x: D(x)$ being true and $Q$ being false.

The set-theoretic version, however, is obviously true if the universal set does not exist. Since every set would then exclude something, we must then have some $x$ such that $x\notin D$. Introducing disjunction, we have $x\notin D \lor Q$ or equivalently $x\in D \implies Q$. Generalizing, we have $\exists x:[x\in D\implies Q]$.

The two, seemingly equivalent statements are at odds with one another. Is this not a problematic?


FOLLOW-UP

It is not problematic at all. You simply have more ways to prove things, more tools with set theory. In set theory, you can construct subsets and quantify over sets. Both of these tools are essential to the resolution of the Paradox of the Universal Set, which in turn is essential to prove $\exists x:[x\in D\implies Q]$. There is no equivalent of these tools available in FOL. This leaves $\exists x:[D(x)\implies Q]$ unprovable in FOL.

$\endgroup$
  • 1
    $\begingroup$ If $Q=\bot$ then isn't that just $\exists x : \neg D(x)$? If so, then shouldn't $D(x) := \top$ contradict your statement? (This doesn't work in set theory, since such a set would be the universal set). Or do I misunderstand something? $\endgroup$ – Ian Mar 12 '15 at 3:31
  • $\begingroup$ @Ian Sorry, I don't follow your argument, but the set-theoretic proof is based on the non-existence of the universal set. Since every set must exclude something, we must have some $x$ such that $x\notin D$. Introducing disjunction, we have $x\notin D \lor Q$ or equivalently $x \in D \implies Q$. Generalizing, we have $\exists x:[x \in D \implies Q]$. $\endgroup$ – Dan Christensen Mar 12 '15 at 3:48
  • $\begingroup$ That doesn't work for predicates, for they can be always true. $\endgroup$ – Matt Samuel Mar 12 '15 at 3:56
  • $\begingroup$ @Ian Hmmmm... The FOL version is not true in general. It is false if $\forall x:D(x)$ is true and if $Q$ is false. Is this what you were getting at? The two versions are at odds with one another. Isn't this problematic? Is this Russell's Paradox for FOL? $\endgroup$ – Dan Christensen Mar 12 '15 at 5:42
  • $\begingroup$ Or does this demonstrate some inconsistency in set theory??? Must we accept the existence of a universal set? What do the experts say? $\endgroup$ – Dan Christensen Mar 12 '15 at 5:57
2
$\begingroup$

Regarding :

$\exists x [D(x) \to Q]$ --- (*)

we cannot prove it in FOL, because it is not valid.

Consider a false proposition $Q$, like : $\forall y(y \ne y)$ and consider as $D(x)$ the unary predicate $\exists y(y = x)$.

Thus, the formula above is :

$\exists x [\exists y(y = x) \to \forall y(y \ne y)]$

which is false in any not-empty domain $D$, because the conditional : $\exists y(y = x) \to \forall y(y \ne y)$ has a true antecedent and a false consequent.


Added

Your example in set theory can be rewritten as $x \in \emptyset$ as the false proposition $Q$ :

$\exists x [x \in D \to x \in \emptyset]$.

But this is not the same as (*) above; in first-order set theory, all variables are individual variables "ranging" over the "universe" of sets and $\in$ is a binary predicate.

Thus, the formal counterpart of the last formula is :

$\exists x [\in(x,d) \ \to \ \in(x,\emptyset)]$;

of course, $\in(x,\emptyset)$ is always false, and we can prove that $\forall y \exists x (x \notin y)$ (i.e. there is no "universal" set).

This implies :

$\forall y \exists x [x \notin y \lor x \in \emptyset]$,

i.e.

$\forall y \exists x [x \in y \to x \in \emptyset]$.

In conclusion, the fact that the last formula is a theorem of set theory implies that it is true in every model of the axioms of set theory. This does not imply that the formula is valid, i.e. true in every interpretation.

$\endgroup$
  • $\begingroup$ I came to the same realization an hour before your posting. (See my comments on original.) The interesting thing now is that the set theoretic version seems to be at odds with the FOL. Is this not problematic? $\endgroup$ – Dan Christensen Mar 12 '15 at 14:24
  • $\begingroup$ I agree the FOL formula is not provable (see my edit). But I am not sure how to reconcile it with the seemingly equivalent but provable set-theoretic formula. $\endgroup$ – Dan Christensen Mar 12 '15 at 14:50
  • $\begingroup$ It's about the domain of discourse. $\exists x (x\in D \to y\in \varnothing)$ is false when $D$ is universal. But is we deny that there can be a universal set, then it is never false. $\endgroup$ – Graham Kemp Mar 12 '15 at 23:13
  • $\begingroup$ Similarly $\exists x(D(x)\to \bot)$ is false in domains of discourse where $D(x)$ is universal but true if we discuss another domain where $D(x)$ is not universally true (eg. move from discussing $\exists x(x\geq 0 \to \bot )$ for natural numbers, to integers). $\endgroup$ – Graham Kemp Mar 13 '15 at 0:10
1
$\begingroup$

Take the statement $\;\exists x (D(x) \to Q)\;$ where $x$ is not free in $Q$ .

$$\begin{array}{l}\exists x\;(D(x)\to Q) \\ \quad\Updownarrow (\text{implication equivalence}) \\ \exists x\;(\neg D(x) \vee Q ) \\ \quad\Updownarrow (\text{distribuition }\exists\text{ over }\vee) \\ \exists x\;\neg D(x) \;\vee\; \exists x\; Q \\ \quad\Updownarrow (x \text{ is not free in }Q) \\ \exists x\; \neg D(x) \;\vee\; Q \\ \quad\Updownarrow (\text{dual negation}) \\ \neg\forall x\; D(x)\;\vee\; Q \\ \quad\Updownarrow (\text{implication equivalence}) \\ \big( \forall x\; D(x) \big) \;\to\; Q \end{array}$$

Thus the statement is not a tautology.   It is falsified iff $D(x)$ is universally true but $Q$ is false.

For instant, if $U$ is the universal set (if we don't deny its existence), then $\exists x( x\in U \to y\in \varnothing)$ is false, while for any $A: A\subset U$, then $\exists x( x\in A\to y\in \varnothing)$ is true because $x\in A$ is not universally true for a strict subset of the universal set (by definition).

But if we do deny the existence of a universal set then the one case were the statement is false never occurs. $\forall x(x\in D)$ is always false for any $D$.

$\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.