Show $\forall x \exists y F(x,y)$ does not imply $\exists y \forall x F(x,y)$ Show:
$\exists y \forall x R(x,y) \rightarrow \forall x \exists y R(x,y)$
$\forall x \exists y F(x,y)$ does not imply $\exists y \forall x F(x,y)$
How do proofs of this nature usually work? When I try to prove the first one by saying:
$\mathcal{M} \models R(n,m)$ for all $n$ and some $m$ in the domain, so $\mathcal{M} \models \forall x \exists y R(x,y)$, I don't see why the same can't be applied for the second problem with $F(x,y)$. Can someone help me to intuitively understand these operations?
 A: We can draw a table of all truth values of $F$ whose rows correspond to values of $x$ and whose columns correspond to values of $y$. (if it helps, consider a domain such that the universe only has two elements, so this is a $2\times 2$ table)
$\forall x \exists y F(x,y)$ means that every row contains at least one $\top$.
$\exists y \forall x F(x,y)$ means that there exists a column consisting entirely of $\top$.
A: Let the domain of the variables $x$ and $y$ be interpreted as the set of all people and let the statement $F(x,y)$ be interpreted as “$y$ is the mother of $x$.”
Then, $\forall x\exists yF(x,y)$ means that everybody has a mother (duh), while $\exists y\forall x F(x,y)$ means that there is a person who is everybody's mother (utter nonsense).
A: Consider the sentences $\forall x\exists y\ x=y$ and $\exists y\forall x\ x=y$ in a domain with two elements.
A: "does not imply" is almost always proved by a counter-example. Let be $\mathbb{Q}\times\mathbb{Q}$ domain of F(x,y) defined by F(x,y) if only if x=2y.Then, ∀x∃y such that x=2y (obviously) i.e., F(x,y), but there is no y in $\mathbb{Q}$ such that x=2y for all x in $\mathbb{Q}$
A: This is similar to Shaun's answer, however, it uses different software.
One can generate a tree proof for the first one that closes as follows:  

However, for the second one the tree proof does not close allowing a countermodel to be constructed showing it is invalid:

The countermodel specifies a domain with two members, $0$ and $1$. The predicate $F$ is true for the pairs $(0,0)$ and $(1,1)$. It is false for all other pairs, $(0,1)$ and $(1,0)$. That means for all $x$ there exists $y$ such that $Fxy$ is true. So the antecedent is true. However, it is not true that there exists a $y$ such that all $x$ $Fxy$ true. So the consequent is false.
All one has to do to prove invalidity is to find a countermodel showing the antecedent is true while the consequent is false.

Tree Proof Generator. https://www.umsu.de/trees/
A: An informal way to prove these is with the method of analytic tableaux, explained in detail in M. D’Agostino et al.'s "Handbook of Tableau Methods."
You start with the negation of statement you're interested in and apply a systematic search for a contradiction. For example:
,
which closed (i.e. it ends in a contradiction). This is equivalent to a proof in many semantics.
