Prove formula in Predicate Logic

Question

Prove the following

$$ \vdash A \land (\exists x) (B \rightarrow C) \equiv (\exists x)(B \rightarrow (A \land C)) $$

as long as $ x$ not free in $A$.

This is question number 9 chapter 6 in "Mathematical Logic" by Tourlakis. How could i prove it ?

Answer 1

First of all, you must follow the Hint in Ex.9, page 187 : "Translate first to standard notation."

The formulae are written with bounded quantifiers, following Bourbaki's style :

$\vdash A \land (\exists x)_B C \equiv (\exists x)_B (A \land C)$, as long as $x$ not free in $A$.

The formula with the bounded quantifier $(\exists x)_B$ must be rewritten [see page 175] as :

$A \land (\exists x) (B \land C)$;

due to the fact that $x$ is not free in $A$, we may apply Corollary 6.4.3 [page 174] : $\vdash (\exists x)(A \land B) \equiv A \land (\exists x) B$, to get :

$(\exists x)[A \land (B \land C)]$.

Now, we "rearrange" the conjuncts [see Ex 2.4.22, page 74 : $\vdash A \land (B \land C) \equiv (A \land B) \land C$ and $\vdash A \land B \equiv B \land A$ --- use Leibniz] to have :

$(\exists x)[B \land (A \land C)]$,

and this is (in bounded quantifier form) :

$(\exists x)_B (A \land C)$.