Is $\exists x\exists yP(x,y) \to\exists x\exists yP(y,x)$ valid?

Question

Consider

$$\exists x\exists yP(x,y) \to\exists x\exists yP(y,x).$$

Is the above statement valid? Please explain why.

I thought is is valid and that I could write $\exists x\exists yP(y,x)$ as $\exists y\exists xP(x,y)$ and if $\exists x\exists yP(x,y)$ is true then there must exist a $y$ for an $x$ too, and thus $\exists x\exists yP(y,x)$ is also true but the answer given is invalid.

Answer 1

Yes, of course. $\exists x\exists y P(x,y)$ means $P(a,b)$ for some $a$ and $b.$ This is an inference rule sometimes called existential instantiation. Then setting $y=a$ and $x=b$ we can infer $\exists y\exists xP(y,x)$ by existential generalization. Less formally, both of these sentences just say that the predicate $P$ is true for some input. The names of the variables used aren't relevant.

Answer 2

Yes.

Suppose otherwise. Then

$$\exists x\exists yP(x,y)\tag{1}$$

is true while

$$\exists x\exists yP(y,x)\tag{2}$$

is false.

From $(1)$, we have some $a$ in the domain such that

$$\exists yP(a,y),\tag{3}$$

which, in turn, gives some $b$ in the domain such that

$$P(a,b).\tag{4}$$

Now $(2)$ being false means that, for any $c$ in the domain, we have $\lnot\exists yP(y,c)$, so, letting $c=b$, we get

$$\lnot\exists yP(y,b).\tag{5}$$

But then $(5)$ is equivalent to saying that, for any $d$ in the domain, we have $\lnot P(d,b)$, so, letting $d=a$, we get

$$\lnot P(a,b).\tag{6}$$

But now $(4)$ contradicts $(6)$.

Hence the result.

Answer 3

Yes. Here is, for instance, a Gentzen-style proof.

$\cfrac{\cfrac{\cfrac{\cfrac{\cfrac{P(a,b)\vdash P(a,b)}{P(a,b)\vdash\exists yP(y,b)}\vdash\exists}{P(a,b)\vdash\exists x\exists yP(y,x)}\vdash\exists}{\exists yP(a,y)\vdash\exists x\exists yP(y,x)}\exists\vdash}{\exists x\exists yP(x,y)\vdash\exists x\exists yP(y,x)}\exists\vdash}{\vdash\exists x\exists yP(x,y)\rightarrow\exists x\exists yP(y,x)}\vdash\rightarrow.$

And here is a Hilbert-style one.

1. (Ax) $P(a,b)\rightarrow\exists yP(y,b);$

2. (Ax) $\exists yP(y,b)\rightarrow\exists x\exists yP(y,x);$

3. (1+2+Syllogism rule) $P(a,b)\rightarrow\exists x\exists yP(y,x);$

4. (3+$\exists$-rule) $\exists yP(a,y)\rightarrow\exists x\exists yP(y,x);$

5. (4+$\exists$-rule) $\exists x\exists yP(x,y)\rightarrow\exists x\exists yP(y,x).$