# Are these two sentences logically equivalent?

What i'm essentially asking is if the following statement is true:

$\forall x \exists y (R(x) \lor Q(y)) :\Leftrightarrow \exists y \forall x (R(x) \lor Q(y))$

where $:\Leftrightarrow$ means that the two statements are logically equivalent.
(sometimes $\vDash$ and it's mirror are used for logical equivalence but can't find the mirrored symbol in mathjax

Edit: I suspect that it is not true but i'm trying to prove it and seems it should be.

## 2 Answers

Yes, the sentence is true — the two sides are equivalent, because both are equivalent to $$\forall x \, R(x) \lor \exists y \, Q(y).$$ If either predicate used both variables this wouldn't be so: in general, $\exists\forall \to \forall\exists$ but not conversely. But here, you can rearrange the quantifiers because:

If $v$ is not free in $p$ then $$\exists v\,(p \lor \varphi(v)) \equiv (p \lor \exists v\,\varphi(v))$$ and $$\forall v\,(p \lor \varphi(v)) \equiv (p \lor \forall v\,\varphi(v)).$$

Nope; but one implication is true: \begin{equation} \exists y\forall x(R(x)\vee Q(y))\to \forall x\exists y(R(x)\vee Q(y)). \end{equation} It's more or less intuitive that this holds: when you have "$\forall x\exists y\dots$" this defines a function: given $x$, exists $x(y)$ such that $\dots$ (You need Choice to define this to be an actual function, so you can well-order the universe and take the least $x$ such that "$\dots$"). So if you have "$\exists y\forall x\dots$" you can define a constant function with output $y$. Therefore you have "$\forall x\exists y\dots$". With this you can see that the other implication is false beacause the function $x(y)$ can take different values.

• Not so: they ARE equivalent, because both are equivalent to $$\forall x\, R(x) \lor \exists y \, Q(y).$$ If either predicate used both variables this wouldn't be so. As you note, in general $\exists\forall \to \forall\exists$ and not conversely. – BrianO Jun 30 '16 at 21:25
• Oooh son of a biscuit, you're totally right; missed that... Thanks! – edgar alonso Jun 30 '16 at 21:56