In predicate logic, is it possible to distribute quantifiers

Question

Is possible to establish that $\forall x \,\exists y\,(Fx \rightarrow Gy)$ is logically equal to $\forall x\,Fx \rightarrow \exists y\,Gy$?

If it does not work, why not?

Answer 1

It depends on whether you mean $\;(\forall x\,Fx) \rightarrow \exists y\,Gy\;$ or $\;\forall x\,(Fx \rightarrow \exists y\,Gy)\;$.

The original expression is equivalent to the latter, but not to the former.

Here is a proof, using a sightly different notation, in tiny baby steps: \begin{align} & \langle \forall x :: \langle \exists y :: F(x) \Rightarrow G(y) \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"rewrite $\;p \Rightarrow q\;$ to $\;\lnot p \lor q\;$ -- the latter is usually easier to manipulate"} \\ & \langle \forall x :: \langle \exists y :: \lnot F(x) \lor G(y) \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"$\;\lor\;$ distributes over $\;\exists\;$"} \\ & \langle \forall x :: \langle \exists y :: \lnot F(x) \rangle \lor \langle \exists y :: G(y) \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"leave out quantification over variable $\;y\;$ which does not occur in $\;\lnot F(x)\;$"} \\ & \langle \forall x :: \lnot F(x) \lor \langle \exists y :: G(y) \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;\Rightarrow\;$ -- to achieve our goal"} \\ & \langle \forall x :: F(x) \Rightarrow \langle \exists y :: G(y) \rangle \rangle \\ \end{align}

Answer 2

It is not equivalent. If you just read what the statements are saying it should be clear. The statement

$\displaystyle \forall x\ \exists y\ (f(x) \rightarrow g(y))$

says that for every $x$ there exists some $y$ such that the statement $f(x) \rightarrow g(y)$ is true. The statement

$(\forall x\ f(x)) \rightarrow (\exists y\ g(y))$

says that if $f(x)$ is true for every $x$, then there exists a $y$ for which $g(y)$ is true. Hence the proprositional functions that you need to satisfy are different

Answer 3

You could get the following $\forall x (Fx\rightarrow \exists y Gy)$.