Prenex form with two same variables versus equivalence

33 Views Asked by At

The statement ∃x(P(x) ∨ Q(x)) is logically equivalent to ∃xP(x) ∨ ∃xQ(x) according to the solution from this quiz (Question 3)

But converting ∃xP(x) ∨ ∃xQ(x) to it's prenex form would result in ∃x∃y(P(x) ∨ Q(y)) according to the rewrite rules described here (item 3).

Is ∃x(P(x) ∨ Q(x)) logically equivalent to ∃x∃y(P(x) ∨ Q(y))? How can I show that?

1

There are 1 best solutions below

0
On

$\def\fitch#1#2{\begin{array}{|l}#1\\\hline#2\end{array}}$

If you accept that $$\begin{align}\exists x~(P(x)\vee Q(x))&\iff (\exists x~P(x))\vee(\exists x~Q(x))\tag 1\\(\exists x~P(x))\vee(\exists x~Q(x))&\iff (\exists x~P(x))\vee(\exists y~Q(y))\tag 2\\(\exists x~P(x))\vee(\exists y~Q(y)) &\iff \exists x~\exists y~(P(x)\vee Q(y))\tag 3\end{align}$$

Then it follows that $$\exists x~(P(x)\vee Q(x))\iff \exists x~\exists y~(P(x)\vee Q(y))\tag {4}$$


You seem to have trouble with (1) so here's a skeleton for a proof by cases

$${\fitch{\exists x~(P(x)\vee Q(x))}{P(a)\vee Q(a)\\\fitch{P(a)}{~\\~}\\\fitch{Q(a)}{~\\~}\\(\exists x~P(x))\vee(\exists x~Q(x))}\\\fitch{(\exists x~P(x))\vee(\exists x~ Q(x))}{\fitch{\exists x~P(x)}{~\\~\\~}\\\fitch{\exists x~Q(x)}{~\\~\\~}\\\exists x~(P(x)\vee Q(x))}\\\exists x~(P(x)\vee Q(x))\iff (\exists x~P(x))\vee(\exists x~ Q(x))}$$