Showing that $\exists y\forall x\,\phi\rightarrow\forall x\exists y\,\phi$ is universally valid Elsewhere on this site is found a proof that $\exists y\forall x\,\phi\rightarrow\forall x\exists y\,\phi$ is syntactically valid. But I am working on exercise (found in Goldrei, Propositional and Predicate Calculus, 173) to show that the same sentence is semantically valid (i.e., true in all structures), but without using the completeness theorem.
Here's what I have so far. Let $\mathcal{A}$ be a structure with domain $A$. To show that
$$\mathcal{A}\models \exists y\forall x\,\phi(x,y)\rightarrow\forall x\exists y\,\phi(x,y)$$
we need to show that whenever $\mathcal{A}\models \exists y\forall x\,\phi(x,y)$ then $\mathcal{A}\models \forall x\exists y\,\phi(x,y)$. If $\mathcal{A}\not\models \exists y\forall x\,\phi(x,y)$ we are done. So the harder case is when $\mathcal{A}\models \exists y\forall x\,\phi(x,y)$. In that case, there exists some $b\in A$ such that
$$\mathcal{A}\models_{y/b} \forall x\,\phi(x,y)$$ where the subscript $y/b$ means to substitute the free variable $y$ for the element $b$. Then, for all $a\in A$, $$\mathcal{A}\models_{y/b,x/a} \phi(x,y).$$
Now I need to go in the reverse direction to construct $\mathcal{A}\models \forall x\exists y\,\phi(x,y)$. But it seems too easy. There exists a $b\in A$ such that for all $a\in A$,
$$\mathcal{A}\models_{y/b,x/a} \phi(x,y),\quad\mathrm{so}\quad\mathcal{A}\models_{x/a} \exists y\,\phi(x,y),\quad\mathrm{and}\quad\mathcal{A}\models \forall x\exists y\,\phi(x,y).$$
Something seems wrong with that, however. For, using the same line of reasoning, it seems like I could derive $\mathcal{A}\models \forall y\exists x\,\phi(x,y)\rightarrow\exists x\forall y\,\phi(x,y)$ (note the order of the quantifiers) for all structures $\mathcal{A}$, which is certainly not the case
 A: Your reasoning is perfectly fine! I think it is good that you ask why it would go wrong for the converse implication. The problem there is that in $\forall y \exists x \phi(x, y)$ the $x$ might depend on the $y$.
Let's just try to go through the argument and see where it precisely goes wrong. Suppose that $\mathcal{A} \models \forall y \exists x \phi(x, y)$. Then for all $b \in A$ we have that $\mathcal{A} \models \exists x \phi(x, b)$ (see footnote about the notation). Now to actually get to the existential quantifier we need to pick some $b \in A$ so that we can use $\mathcal{A} \models \exists x \phi(x, b)$. Once we have picked that $b$ we can indeed find some $a \in A$ such that $\mathcal{A} \models \phi(a, b)$. The problem is if we now want to "go in the reverse direction", as you call it. We cannot conclude that $\mathcal{A} \models \phi(a, b)$ for all $b$, because we fixed our $b$ earlier! So the $a$ is specific for this $b$, and may not work for another element.
Put differently, in your (correct) solution the first quantifier you strip away is an existential quantifier. So it is fine to just fix some element that you get from that. When trying the same argument for the converse you have to strip away a universal quantifier first. So if you then fix an element, anything that you get after that will depend on that fixed element.

Footnote: I like the notation better where I actually substitute the $b$, but this is of course the same as where you would write $\mathcal{A} \models_{y/b} \exists x \phi(x, b)$
