Prove: [∃xp(x)->∃xq(x)]->∃x[p(x)->q(x)]

Question

$[∃xp(x)\to∃xq(x)]\to∃x[p(x)\to q(x)]$

So I understand that if $∃x(p(x)\to q(x))$ is false then the whole statement would be false since it is an implication. In that case $∀x p(x)\wedge∀x \neg q(x)$. My teacher then said p(x) is always true and q(x) is always false. How did they know that?

Answer 1

It sounds like a semantical argument to show that the formula is valid.

Assume that is not; being a conditional, this amounts to assuming that the antecedent is true and the consequent is false, i.e. $\lnot ∃x[p(x)→q(x)]$ must be true.

But $\lnot ∃x[p(x)→q(x)]$ is equivalent to : $\forall x[p(x) \land \lnot q(x)]$.

$\forall x[p(x) \land \lnot q(x)]$ implies $\forall xp(x) \land \forall x \lnot q(x)$ and this is why your teacher says "$p(x)$ is always true and $q(x)$ is always false".

This in turn implies $\exists xp(x) \land \lnot \exists xq(x)$ that is the negation of $\exists xp(x) \rightarrow \exists xq(x)$.

In conclusion, the assumption that $∃x[p(x)→q(x)]$ is false contradict the assumption that $\exists xp(x) \rightarrow \exists xq(x)$ is true.

Thus, the formula is valid.

Answer 2

The basic idea is to expand and simplify the formula to get an idea what the condition is saying, $\exists x ~ P(x) \land \forall y ~ \lnot Q(y)$ and what the consequence is saying, $\exists z ~ \lnot P(z) \lor \exists w ~ Q(w)$. And since those are tautologically compatible, twice combine a term from the condition and a term from the consequence form an expression like "$a \text{ or } \lnot a$".

$$\begin{array} {rcl} % \bigg( \exists x ~ P(x) \implies \exists y ~ Q(y) \bigg) \implies \bigg( \exists z ~ P(z) \implies Q(z) \bigg) % & & a \implies b \equiv \lnot a \lor b \\ \\ % \lnot \bigg( \lnot \exists x ~ P(x) \lor \exists y ~ Q(y) \bigg) \lor \bigg( \exists z ~ \lnot P(z) \lor Q(z) \bigg) % & & \text{De Morgan's} \\ \\ % \bigg( \exists x ~ P(x) \land \forall y ~ \lnot Q(y) \bigg) \lor \bigg( \exists z ~ \lnot P(z) \lor Q(z) \bigg) % & & \exists x ~ a(x) \lor b(x) \equiv \exists y ~ a(y) \lor \forall z ~ b(z) \\ \\ % \bigg( \exists x ~ P(x) \land \forall y ~ \lnot Q(y) \bigg) \lor \exists z ~ \lnot P(z) \lor \exists w ~ Q(w) % & & \land \text{ distributes over } \lor \\ \\ % \bigg( \exists x ~ P(x) \lor \exists z ~ \lnot P(z) \lor \exists w ~ Q(w) \bigg) & & \exists x ~ a(x) \lor b(x) \equiv \exists y ~ a(y) \lor \forall z ~ b(z) \\ \land \bigg(\forall y ~ \lnot Q(y) \lor \exists z ~ \lnot P(z) \lor \exists w ~ Q(w) \bigg) & & \text{ and De Morgan's} \\ \\ % \bigg( \exists x ~ P(x) \lor \lnot P(x) \lor \exists w ~ Q(w) \bigg) \\ \land \bigg( \forall y ~ \lnot Q(y) \lor \lnot \forall w ~ Q(w) \lor \exists z ~ \lnot P(z) \bigg) \\ \\ % \bigg( \exists x ~ \text{True} \lor \exists w ~ Q(w) \bigg) \\ \land \bigg( \text{True} \lor \exists z ~ \lnot P(z) \bigg) \\ \\ % \bigg( \exists x ~ \text{True} \lor \exists w ~ Q(w) \bigg) % \end{array}$$

Now you might want to apply $\exists x ~ \text{True} \equiv \text{True}$, but that is only the case in a nonempty universe. Actually, that is basically the definition of a nonempty universe. So, to continue, you have to make the non-empty universe assmption:

$$\bigg( \text{True} \lor \exists w ~ Q(w) \bigg) $$

$$\text{True}$$

If you follow this, then I suggest trying to establish the reverse condition, $\bigg(\exists x ~ P(x) \implies Q(x) \bigg) \implies \bigg( \exists y ~ P(y) \implies \exists z ~ Q(z) \bigg)$.