Show that $(\forall y)(\exists x): \phi (x,y) \to (\exists x) (\forall y) :\phi(x,y)$ does not hold

Question

I want to show that $(\forall y)(\exists x): \phi (x,y) \to (\exists x) (\forall y) :\phi(x,y)$ does not hold using rules of inference but I keep getting stuck. I understand that various examples can be given to disprove this but I cannot understand how this can be proved wrong using inference rules. Could anyone explain how this statement does not hold using rules of inferences?

Answer 1

Using formal rules of inference you can only show that something does follow from something else ... you cannot use them to show that something does not follow. So, you are trying to do the impossible.

Answer 2

Proof using the Rules of Inference

Problem: Prove that $(\forall y)(\exists x): \phi (x,y) \implies (\exists x) (\forall y) :\phi(x,y)$ is false.

Proof: Suppose that $(\forall y)(\exists x):\phi(x,y)$ is true. Using Universal Instantiation, we know that $(\exists x):\phi(x,y_0)$ is true, where $y_0$ is taken to be some arbitrary value. Now we have to consider two distinct situations. First, we can have the case where we assign the same $x$ to all possible values of $y$ in order to make $\phi(x,y)$ true, or we can have the case where for two distinct values of $y$ we assign to distinct values of $x$ in order to make $\phi(x,y)$ true.

Case $1:$ Assume that we assign the same $x$ to all values of $y$ such that $\phi(x,y)$ is true. Let $a$ be that value of $x.$ Then $\phi(a,y_0)$ is true, using Existential Instantiation. Using the Universal Generalization, we conclude that $(\forall y):\phi(a,y)$ is true, since $y_0$ is an arbitrary value. By the Existential Generalization, we deduce that $(\exists x)(\forall y):\phi(x,y)$ is true. Therefore, in this case $(\forall y)(\exists x): \phi (x,y) \implies (\exists x) (\forall y) :\phi(x,y)$ is true.

Case $2:$ Now, assume that for distinct values of $y$ we assign distinct values of $x.$ Suppose that $\phi(x_0,y_0)$ is true and $\phi(x_1,y_1)$ is also true, where $x_0 \neq x_1$ and $y_0 \neq y_1.$ Further, assume that $(\exists x) (\forall y) :\phi(x,y)$ is true. Let’s derive a contradiction. Since $(\exists x) (\forall y) :\phi(x,y)$ is true, using the Existential Instantiation, we deduce that $(\forall y):\phi(b,y)$ is true for some value $a.$ Hence, it is true, using the Universal Instantiation that both $\phi(b,y_0)$ and $\phi(b,y_1)$ are true. Which is a contradiction. Therefore, $(\exists x) (\forall y) :\phi(x,y)$ is false, which implies that $(\forall y)(\exists x): \phi (x,y) \implies (\exists x) (\forall y) :\phi(x,y)$ is false.

Since there is a case where $(\forall y)(\exists x): \phi (x,y) \implies (\exists x) (\forall y) :\phi(x,y)$ fails, we deduce that $(\forall y)(\exists x): \phi (x,y) \implies (\exists x) (\forall y) :\phi(x,y)$ is false. $\square$

---

A side note on the Logic of the proof

This was the final step that I use in the proof to conclude that this statement is false.

$$\big[ \text{Hypothesis} \implies \text{Conclusion} \big] \iff$$ $$ \iff \big[(\text{Case $1$}) \vee (\text{Case $2$}) \implies \text{Conclusion}\big] \iff$$ $$\iff \big[ (\text{Case $1$} \implies \text{Conclusion}) \wedge (\text{Case $2$} \implies \text{Conclusion})\big].$$

---

An alternative method of proving

We could also have proved this without using rules of inference, which would have simplified the proof. We could have proved it by showing that the statement is false for some particular case, i.e., by presenting a counter-example.

Suppose that $A = \{1,2,3\}$ and that $\phi(1,1),$ $\phi(2,2),$ $\phi(3,3)$ are all true and for other combination of $(x,y)$ we have that $\phi(x,y)$ is false. It clearly doesn’t exists some $x$ such that for all $y$ we have $\phi(x,y)$ true. So the statement $(\forall y)(\exists x): \phi (x,y) \to (\exists x) (\forall y) :\phi(x,y)$ is not true, regarding our definition of conditional statement.