Show $\forall x \exists y F(x,y)$ does not imply $\exists y \forall x F(x,y)$

Question

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?

Answer 1

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).

Answer 2

"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}$

Answer 3

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$.

Answer 4

Consider the sentences $\forall x\exists y\ x=y$ and $\exists y\forall x\ x=y$ in a domain with two elements.

Answer 5

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.