Natural Deduction First Order Logic $∃y∀x(P(x) ∨ Q(y))↔∀x∃y(P(x) ∨ Q(y))$

Question

I'm working on some of my logic exercises for my end term exam in Predicate Logic. One of these exercises is "Show with natural deduction that $\vdash ∃y∀x(P(x) ∨ Q(y))↔∀x∃y(P(x) ∨ Q(y))$"

I'm getting the part that shows you can do $∃y∀x(P(x) ∨ Q(y)) \vdash ∀x∃y(P(x) ∨ Q(y))$. It's the other way around I'm not able to do. I'm getting stuck introducing the Universal Quantifier whilst having them as a free variable.

Where I'm getting stuck

I know this isn't correct/possible, but I cannot figure out how it should be done...

Is there anyone who is able to solve it? Or is it simply not possible?

Thanks in advance!

Answer 1

Hint

It must be derivable, due to the fact that it is valid (in classical logic).

We may check it with two equivalences :

$\exists x \ (\alpha \lor \beta(x)) \equiv (\alpha \lor \exists x \beta(x))$, if $x$ is not free in $\alpha$

and (this one holds only in classical logic) :

$\forall x \ (\alpha \lor \beta(x)) \equiv (\alpha \lor \forall x \beta(x))$, if $x$ is not free in $\alpha$.

Thus, starting from :

$∃y∀x(P(x) ∨ Q(y))$

we can get, by the second equivalence above : $∃y(∀xP(x) ∨ Q(y))$ and then, using the first one we get the equivalent :

$(∀xP(x) ∨ ∃yQ(y))$.

Now we re-apply the second equivalence to get :

$∀x(P(x) ∨ ∃yQ(y))$

and finally :

$∀x∃y (P(x) ∨ Q(y))$.