Proof using existential quantifier

Question

Prove:

$$\begin{align} \exists x ~:~ \bigg(p(x) &\rightarrow q(x)\bigg) \

How do I go about proving this? Can I distribute the existential quantifier in the first term?

Answer 1

Two relevant laws (whether they are laws of inference or not depends on your logic) would be:

$$A \rightarrow B \equiv \lnot A \lor B \tag{1}$$ $$\exists y ~:~ m(y) \lor n(y) \equiv \exists y ~:~ m(y) \lor \exists y ~:~ n(y)\tag{2}$$

Property (1) may as well be the definition of $\rightarrow$. Property (2) is the result of $\exists$ being a quantified $\lor$.

To your question:

Can I distribute the existential quantifier in the first term?

Let's apply properties (1) and (2) and see:

$$\exists x ~:~ p(x) \rightarrow q(x)$$ $$\exists x ~:~ \lnot p(x) \lor q(x)$$ $$\left(\exists x ~:~ \lnot p(x)\right) \lor \left(\exists x ~:~ q(x)\right)$$ $$\lnot \left(\exists x ~:~ \lnot p(x)\right) \rightarrow \left(\exists x ~:~ q(x)\right)$$ $$\left(\forall x ~:~ p(x)\right) \rightarrow \left(\exists x ~:~ q(x)\right)$$

So you see what happens when you try to distribute the $\exists$ across a $\rightarrow$.

How do I go about proving this?

Simplify your expression.

$$\begin{align} \exists x ~:~ \bigg(p(x) &\rightarrow q(x)\bigg) \\ &\rightarrow\\ \bigg(\exists x ~:~ p(x) &\rightarrow \exists x ~:~ q(x)\bigg)\end{align}$$

Convert $\rightarrow$ to $\lor$:

$$\begin{align} \lnot(\exists x ~:~ \lnot p(x) &\lor q(x)) \\ &\lor\\ \bigg(\lnot \exists x ~:~ p(x) \bigg) &\lor \exists x ~:~ q(x)\end{align}$$

Carry through the $\lnot$ to the leaf terms:

$$\begin{align} (&\forall x ~:~ p(x) \land \lnot q(x)) \\ &\lor \bigg(\forall x ~:~ \lnot p(x) \bigg) \\ & \lor \exists x ~:~ q(x)\end{align}$$

Now you can probably find a counter example. For a counter example, all 3 of the above or cases should be false. The third case: $$\exists x ~:~ q(x)$$ implies that a counter example must have $q(x) = \text{false}$. So to find a counter example for: $$\begin{align} (&\forall x ~:~ p(x)) \\ &\lor \bigg(\forall x ~:~ \lnot p(x) \bigg) \\ \end{align}$$ So your counter examples will be those situations where $p(x)$ is sometimes true and sometimes false, and when $q(x)$ is false. In all other cases the statement is true.