Quantifier order confusion

Question

I wondered, if $\forall x\, \exists y\, R(x,y)$ is equivalent to $\exists y\, \forall x\, R(x,y)$.

If $R(x, y) = (x < y)$ then the answer would appear to be no.

In the first case, for all $x$, does there exist a $y$ such that $x < y$? Sure, just pick $y = x + 1$.

In the second case, it says there exists a $y$ such that $x < y$ holds for all $x$. But any $x$ that is greater than or equal to $y$ would make this false.

So it seems that the order of the quantifiers matter, but then we have this proof:

∃x ∀y R(x, y)                                 [Hypothesis]

Let c be a constant such that ∀y R(c, y)
    ∀y R(c, y)    

    Given constant d:
        R(c, d)                               [∀ elim]
        ∃x R(x, d)                            [∃ intro]

    ∀y ∃x R(x, y)                             [∀ intro]

∀y ∃x R(x, y)                                 [∃ elim]

Here it seems to imply we can swap the order if we start out with an exists quantifier coming first?

In other words is it true that:

$\forall x\, \exists y\, R(x,y) \not\rightarrow \exists y\, \forall x\, R(x,y)$ (how would we actually prove this?)

But:

$\exists y\, \forall x\, R(x,y) \rightarrow \forall x\, \exists y\, R(x,y)$

Answer 1

$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline #2\end{array}}$

Okay, now, that was a valid derivation for that implication, but to introduce equivalence you also need to derive the converse; which you cannot do.

$$\fitch{}{\fitch{\exists x\forall y~xRy}{\fitch{[c]~\forall y~cRy}{\fitch{[u]}{cRu\\\exists x~xRu}\\\forall y~\exists x~xRy}\\\forall y~\exists x~xRy}\\\exists x~\forall y~xRy\to\forall y~\exists x~xRy\\\fitch{\forall y~\exists x~xRy}{\fitch{[u]}{\exists x~xRu\\\fitch{[c]~cRu}{...\text{cannot introduce the universal at this point}}}\\\ldots\text{cannot conclude the }\exists\forall\text{ statement}}\\\ldots\text{unable to derive the converse statememt}}$$

Now, there are interpretations of the relation $R$ for which the converse will be true, but it is not so in general.  

Rather than fallaciously declaring it proven to be a not-implication ($\vdash a\nrightarrow b$), we should correctly state that it is not proven to be an implication ($\nvdash a\to b$).

Answer 2

If $\exists y\, \forall x\, R(x,y)$ then this means there is an $R$-maximal element, for example if $R$ is $\leq$ then this would mean there is a maximal element. Then sure, given an $R$-maximal element, then for any $x$ there is a $y$ $R$-greater than $x$, namely the $R$-maximal element. Think of the set $\{1,2,3\}$ ordered by $\leq$. There is an $\leq$-maximal element, namely $3$, and for any $x \in \{1,2,3\}$ we have $x \leq 3$. So yes

$\exists y\, \forall x\, R(x,y) \rightarrow \forall x\, \exists y\, R(x,y)$ is true.

In the other case, just because for every $x$ we have a $y$ which is $R$-greater than $x$, this doesn't imply there is an $R$-maximal element. Think of the set $\{1,2,3,..\}$ ordered by $\leq$. Given any $x$ I can find a $y$ greater than $x$, namely $x+1$, but still the set $\{1,2,..\}$ has no maximum. So yes

$\forall x\, \exists y\, R(x,y) \not\rightarrow \exists y\, \forall x\, R(x,y)$ is correct as well.

Answer 3

Yes, what you said is correct: the order of the quantifiers matters. The only thing you miss is probably the fact that the proof you cited is not a proof of equivalence: in fact, the deductions are true if read from top to bottom, and not from bottom to top. In fact, the problematic step is that $∀y\ R(c, y) \implies R(c, d)$ but the converse is not true.