How do I change ∃x, ∀y, P(x, y) into ∃y, ∃x, P(x, y)? I'm very confused as to how to even begin, any explanation or help would be really appreciated. I understand Universal and Existential Quantifiers but the actual process of proving it is what confuses me.
 A: Hint:


*

*Imagine a huge table/matrix with entries in $p_{x,y} \in \{0,1\}$,
where $x$ determines the row and $y$ determines the column, for example
$$\begin{array}{c|ccc}
  &y_1&y_2&y_3\\\hline
  x_1&p_{x_1,y_1}&p_{x_1,y_2}&p_{x_1,y_3} \\
  x_2&p_{x_2,y_1}&p_{x_2,y_2}&p_{x_2,y_3} \\
  x_3&p_{x_3,y_1}&p_{x_3,y_2}&p_{x_3,y_3}
  \end{array}$$

*Suppose that $$P(x,y) \iff p_{x,y} = 1,$$ then
$\exists x.\ \forall y.\ P(x,y)$ says
\begin{align}
  &\exists x &&\text{ there exists a row such that }\\
  &\forall y &&\text{ for all columns }\\
  &P(x,y)    && \text{ we have }p_{x,y} = 1.
  \end{align}

*On the other hand $\exists y.\ \exists x.\ P(x,y)$ says
\begin{align}
  &\exists y &&\text{ there exists a column such that }\\
  &\exists x &&\text{ there exists a row where }\\
  &P(x,y)    && \text{ we have }p_{x,y} = 1.
  \end{align}

*In other words, given there exists a row full of $1$'s, does a column that contains at least one value $1$ have to exist?

*Observe that for the theorem to work we need an assumption that there is at least one column.


I hope this helps $\ddot\smile$
A: You are given $\exists x\ \forall y\ P(x, y)$. So, writing this in words, we can say that there exists a special value of $x$ such that for all $y$ (no matter what $y$ is chosen), $P(x, y)$ is always going to be true. So lets choose this special value of $x$ and call it $x_0$. Now, no matter what $y$ value you choose, $P(x_0, y)$ is always going to be true. Can you finish the argument from there?
