Are these logically equivalent?

26 Views Asked by At

\begin{align} &\forall y(P(y)\rightarrow \forall x(Q(x)\rightarrow R(x,y)))\text{; and,}\\ &\forall x(Q(x)\rightarrow \forall y(P(y)\rightarrow R(x,y))).\\ \end{align}

I think they are. But can you show (or disprove) it?

1

There are 1 best solutions below

0
On

I'm not a logician, but I'd show it as follows.

The negation of first one is $$\exists_y(P(y) \land \exists_x(Q(x)\land\lnot R(x, y))). $$ Now fix an $y_0$ for which it holds. Then $$P(y_0)\land\exists_x(Q(x)\land \lnot R(x, y_0)). $$ Again, fix $x_0$ for which this holds. $$P(y_0)\land Q(x_0) \land\lnot R(x_0, y_0). $$ This is of course equivalent to the negation of the second statement by symmetry.