prenex normal equivalence challenges in math

Question

consider

these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.

Answer 1

Now I give an answer without using provable equivalences on Enderton, page 121 and page 130. Main formula is equivalent to $$(\neg\exists x\varphi(x))\vee(\forall x\exists y\psi(x,y))$$ and this is also equivalent to $$(\forall x\neg\varphi(x))\vee(\forall x\exists y\psi(x,y))$$ but we have: $$\forall x\exists y\psi(x,y))\leftrightarrow\forall z\exists y\psi(z,y))$$ so Main formula is equivalent to $$(\forall x\neg\varphi(x))\vee(\forall z\exists y\psi(z,y))$$ Since neither x is free in $\psi(z,y)$ nor y and z are free in $\neg\varphi(x)$. So we can move quantifiers on prefix of formula and thus we have: $$(\forall z\forall x\exists y(\neg\varphi(x)\vee\psi(z,y)))\leftrightarrow(\forall x\forall z\exists y(\varphi(x)\rightarrow\psi(z,y)))$$ and both of them are prefix normal

Answer 2

I'll use Enderton's system (see Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)).

We start with :

$\exists x \varphi(x) \rightarrow \forall x \exists y \psi(x,y)$;

the first step is to change the second bound $x$ to $z$, in order to avoid problems with "clashing" quantifiers :

(A) -- $\exists x \varphi(x) \rightarrow \forall z \exists y \psi(z,y)$.

We need some provable equivalences; see Enderton, page 121 and page 130 :

(Q2A) -- $\vdash (\alpha \rightarrow \forall x \beta) \leftrightarrow \forall x (\alpha \rightarrow \beta)$, if $x$ does not occur free in $\alpha$

(Q2B) -- $\vdash (\alpha \rightarrow \exists x \beta) \leftrightarrow \exists x (\alpha \rightarrow \beta)$, if $x$ does not occur free in $\alpha$

(Q3A) -- $\vdash (\forall x \beta \rightarrow \alpha) \leftrightarrow \exists x (\beta \rightarrow \alpha)$, if $x$ does not occur free in $\alpha$

(Q3B) -- $\vdash (\exists x \beta \rightarrow \alpha) \leftrightarrow \forall x (\beta \rightarrow \alpha)$, if $x$ does not occur free in $\alpha$.

Starting from (A), we apply first (Q2A) with $\forall z$ to get :

$\forall z(\exists x \varphi(x) \rightarrow \exists y \psi(z,y))$,

then we apply (Q3B) with $\exists x$ to get :

$\forall z \forall x(\varphi(x) \rightarrow \exists y \psi(z,y))$,

and finally we apply (Q2B) with $\exists y$ to get :

$\forall z \forall x \exists y(\varphi(x) \rightarrow \psi(z,y))$.

Of course : $\forall z \forall x \alpha \vdash \forall x \forall z \alpha$ [see Enderton, page 118]; thus, the last formula is equivalent to :

(B) -- $\forall x \forall z \exists y(\varphi(x) \rightarrow \psi(z,y))$.

Now we apply the following equivalence : $\vDash_{TAUT} (\alpha \rightarrow \beta) \leftrightarrow (\lnot \alpha \lor \beta)$ to (B) to get :

$\forall x \forall z \exists y(\lnot \varphi(x) \lor \psi(z,y))$,

and again we "switch" the two initial quantifiers to get :

(C) -- $\forall z \forall x \exists y(\lnot \varphi(x) \lor \psi(z,y))$.