Proving logical equivalences in the statements $(∃)(() → ())$ and $(∀)() → (∃)()$

Question

For this I must show that the two statements $(∃)(() → ())$ and $(∀)() → (∃)()$ are logically equivalent. The issue I'm coming up with is that I'm unsure about the proper methods of proving predicate logic. Any help would be appreciated.

Answer 1

It sometimes helps to instead check the negations are equivalent. It also often helps to rewrite any use of $\to$. Let's use both tricks. The first statement is false iff $\forall x(P(x)\land\neg Q(x))$. The second statement is false iff $\forall x(P(x))\land\forall x(\neg Q(x))$.

Answer 2

You say "The issue I'm coming up with is that I'm unsure about the proper methods of proving predicate logic."

Some comments:

1. This type of statement is expressed in "first order logic" (predicate logic) which supersedes propositional logic. There are new inference rules in first order logic that do not exist in propositional logic (simply because propositional logic does not use any quantifiers).
2. In both propositional and first order logic, logical equivalence between $A$ and $B$ can be expressed as $$A \iff B$$ Which means the same thing as $$(A \implies B) \wedge (B \implies A)$$ So the "proper method(s)" of proving logical equivalence between the two statements you have given will be to prove:
   • $$\exists x [ P(x) \implies Q(x) ] \implies \forall x [P(x) \implies \exists x (Q(x))]$$
   • $$\forall x [P(x) \implies \exists x (Q(x))] \implies \exists x [ P(x) \implies Q(x) ]$$
   • So that you can infer $$\exists x [ P(x) \implies Q(x) ] \implies \forall x [P(x) \implies \exists x (Q(x))] $$ $$\wedge$$ $$ \forall x [P(x) \implies \exists x (Q(x))] \implies \exists x [ P(x) \implies Q(x) ]$$
3. That looks like quite a mess! In order to prove those two statements you are going to need to know: how to prove statements of the form $\forall x (L(x))$, $\exists x (L(x))$, and $A \implies B.$ It is not clear from your question if you are totally clear on how to do these, or if you are asking for more specific help on the proof you shared.

Answer 3

You can use basic equivalence principles. The key equivalence in this case is that existentials distribute over disjunctions:

$\exists x (\phi(x) \lor \psi(x)) \Leftrightarrow \exists x \ \phi(x) \lor \exists x \ \psi(x)$

Applying this to your statement:

$\exists x (P(x) \to Q(x)) \Leftrightarrow$

$\exists x (\neg P(x) \lor Q(x)) \Leftrightarrow$

$\exists x \ \neg P(x) \lor \exists x \ Q(x) \Leftrightarrow$

$\neg \forall x \ P(x) \lor \exists x \ Q(x)) \Leftrightarrow$

$\forall x \ P(x) \to \exists x \ Q(x)$

Answer 4

Simply prove each statement from the other, for example

$$\begin{align} &1.\space \exists x (P_x\to Q_x) & \text{(Conditional Proof)}\\ &2.\space \forall x P_x & \text{(Conditional Proof)}\\ &3.\space P_{\alpha}\to Q_{\alpha} & \text{Existential Instantiation of line 1}\\ &4.\space P_{\alpha} & \text{Universal Instantiation of line 2} \\ &5.\space Q_{\alpha}& \text{Modus Ponens on lines 3 and 4}\\ &6.\space \exists x Q_x & \text{Existential Generalization of line 5}\\ &7.\space \forall x P_x \to \exists x Q_x & \text{Conditional Proof on lines 2-6}\\ &8.\space \exists x (P_x\to Q_x)\to (\forall x P_x \to \exists x Q_x) & \text{Conditional Proof on lines 1-7}\\ &9.\space \forall x P_x \to \exists x Q_x & \text{(Conditional Proof)}\\ &10.\space \neg\forall x P_x \vee \exists x Q_x & \text{Conditional Exchange of line 9}\\ &11.\space \neg\forall x P_x & \text{(Conditional Proof)}\\ &12.\space \exists x\neg P_x & \text{Quantifier Negation of line 11}\\ &13.\space \neg P_{\alpha} & \text{Existential Instantiation of line 12}\\ &14.\space \neg P_{\alpha} \vee Q_{\alpha} & \text{Addition of line 13}\\ &15.\space P_{\alpha} \to Q_{\alpha} & \text{Conditional Exchange of line 14}\\ &16.\space \exists x (P_x \to Q_x) & \text{Existential Generalization of line 15}\\ &17.\space \neg\forall x P_x \to \exists x (P_x \to Q_x) & \text{Conditional Proof lines 11-16}\\ &18.\space \exists x Q_x & \text{(Conditional Proof)}\\ &19.\space Q_{\alpha} & \text{Existential Instantiation line 18}\\ &20.\space Q_{\alpha} \vee \neg P_{\alpha} & \text{Addition on line 19}\\ &21.\space \neg P_{\alpha} \vee Q_{\alpha} & \text{Commutation on line 20}\\ &22.\space P_{\alpha} \to Q_{\alpha} & \text{Conditional Exchange on line 21}\\ &23.\space \exists x (P_x \to Q_x) & \text{Existential Generalization on line 22}\\ &25.\space \exists x Q_x \to \exists x (P_x \to Q_x) & \text{Conditional Proof on lines 18-24}\\ &26.\space \exists x (P_x \to Q_x) \vee \exists x (P_x \to Q_x) & \text{Constructive Dilemma lines 10, 17, and 25}\\ &27.\space \exists x (P_x \to Q_x) & \text{Tautology on line 26}\\ &28.\space (\forall x P_x \to \exists x Q_x) \to \exists x (P_x \to Q_x) & \text{Conditional Proof on lines 9-27}\\ &29.\space (\forall x P_x \to \exists x Q_x) \leftrightarrow \exists x (P_x \to Q_x) & \text{Biconditional Implication by lines 8 and 28}\\ \end{align} $$

Which shows their logical equivalence.