two place predicate logic

Question

Im trying to prove following,as lecturer did not have time to go through the proof on the lecture, I wonder how to solve at least the first statement $$(\forall x)(\forall y)L(x, y) ≡ (\forall y)(\forall x)L(x, y)$$ $$(\exists x)(\exists y)L(x, y) ≡ (\exists y)(\exists x)L(x, y)$$ Give an intuitive argument for the validity of the logical equivalences above.

Answer 1

Okay. Lets take a look a the first logical equivalence:

$\forall x\forall y:L(x,y) \equiv \forall y\forall x:L(x,y)$

So.. the "$\equiv$" (equivalent-sign) means exactly the same as the biimplication sign "$\Longleftrightarrow$". So lets assume the left hand side and convince ourself that it implies the right hand side.

1) The left hand side tells us that: regardless which $x$ we choose, all the $y$'s will make the statement L(x,y) true.

So lets look at the right side. If we consider an arbitrary $y_0$, we will have to show that any $x$ will make the statement $L(x,y_0)$ true. To see this we apply the left hand side. Since we know from 1) that regardless which $x$ we choose, all the $y$'s will make the statement $L(x,y)$ true, we know particularly: regardless which $x$ we choose, $y_0$ will make the statement $L(x,y)$ true. (here we use that $y_0$ is part of all the $y$'s.) q.e.d.

Now since this apply for every $x$, and that $y_0$ was arbitrary, we can conclude the right hand side. All in all we have shown that:

$\forall x\forall y:L(x,y) \Longrightarrow \forall y\forall x:L(x,y)$

The proof for the left implication is of course completely analogous. Now lets take a look at the other equivalence:

$\exists x\exists y:L(x,y) \equiv \exists y\exists x:L(x,y)$

So again lets assume the left hand i.e. we know that: there exists minimum one $x_0$, so that there is minimum one $y_0$, that makes $L(x_0,y_0)$ true.

So to prove the right side we have to show the existence of at least one $y_1$ for which at least one $x_1$, makes $L(x_1,y_1)$ true. Now we will apply our assumption. But since our assumption tells us, that at least the pair: $(x_0,y_0)$ makes $L(x_0,y_0)$ true, we can choose our $y_1$ to be $y_0$ and $x_1$ to be $x_0$. q.e.d.

So this was the right implication and the left one is again completely analogous.