0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – BrianO Jun 30 '16 at 21:25
  • $\begingroup$ Oooh son of a biscuit, you're totally right; missed that... Thanks! $\endgroup$ – edgar alonso Jun 30 '16 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.