Order of quantifiers and reversing variables

Question

I have few doubts on existential and forall quantifers:-

1) Out of quantifiers and implication ($\rightarrow$), which one has the higher precedence ? Rosen book and wikipedia have different answers to this question.

2) What is the associativity of implication operator ($\rightarrow$) ? Is it from right to left?

3) ($\forall x \forall y \space P(x, y)) \rightarrow (\forall x \forall y \space P(y, x))$.

$(∃x∃y \space P(x,y)) \rightarrow (∃y∃x \space P(y,x))$.

Are both the statements always true if $x$ and $y$ are from same domain?

4) I know that $\forall x \forall y \space P(x, y) \equiv \forall y \forall x P(x, y)$ is true, but how is it true? Is it true for $∃x∃y \space P(x,y) \equiv ∃y∃x \space P(x,y)$ also?

Answer 1

For the 3rd and 4th question, an informal way to understand these, notice that an existential can be seen as kind of disjunction, that is, if $a,b,c,...$ denote the objects in your domain, then you can think of an existential like this:

$\exists x \: \varphi(x) \approx \varphi(a) \lor \varphi(b) \lor \varphi(c) \lor ...$

I use $\approx$ since this is technically not a logical equivalence, but if you really want to prove the above equivalence, you'd need to go into formal semantics, and that might be a bit to much to ask for a binner in logic. But, what you would be doing there does follow this basic idea, so let's just leave it more informal.

So, with this 'equivalence', you can show (or at least informally understand) an equivalence like $\exists x \exists y \ P(x,y) \Leftrightarrow \exists y \exists x \ P(x,y)$ as follows:

$\exists x \exists y \ P(x,y) \approx$

$\exists y \ P(a,y) \lor \exists y \ P(b,y) \lor \exists y \ P(c,y) \lor ... \approx$

$(P(a,a) \lor P(a,b) \lor P(a,c) ...) \lor (P(b,a) \lor P(b,b)\lor ...) \lor (P(c,a) \lor P(c,b) \lor ...) \lor ... \Leftrightarrow$

$P(a,a) \lor P(a,b) \lor P(a,c) ... \lor P(b,a) \lor P(b,b) \lor ... \lor P(c,a) \lor P(c,b) \lor ... \Leftrightarrow$

$P(a,a) \lor P(b,a) \lor P(c,a) ... \lor P(a,b) \lor P(b,b) \lor P(c,b) ... \lor P(a,c) \lor P(b,c) ... \lor ... \approx$

$\exists x P(x,a) \lor \exists x P(x,b) \lor \exists x P(x,c) \lor ... \approx$

$\exists y \exists x \ P(x,y)$

So, you see that we can swap two existentials if they are next to each other basically because the $\lor$ is associative and commutative.

Likewise, by thinking a universal like this:

$\forall x \: \varphi(x) \approx \varphi(a) \land \varphi(b) \land \varphi(c) \land ...$

you can understand why two universals that are next to each other can be swapped, since the $\land$ is both associative and commutative.

As a general equivalence principle:

Swapping Quantifiers of Same Type

$\forall x \forall y \ P(x,y) \Leftrightarrow \forall y \forall x \ P(x,y)$

$\exists x \exists y \ P(x,y) \Leftrightarrow \exists y \exists x \ P(x,y)$

Now, I note that in 3) you asked:

$(∃x∃y \space P(x,y)) \rightarrow (∃y∃x \space P(y,x))$

So here you not only swap the quantifiers, but you also swap the role of the variables in the formula. Well, that always works, because variables are just dummy place-holders, so of course you always have:

Swapping Bound Variables

$\forall x \ \varphi(x) \Leftrightarrow \forall y \ \varphi(y)$

$\exists x \ \varphi(x) \Leftrightarrow \exists y \ \varphi(y)$

And in particular you therefore have:

$\exists x \exists y \ P(x,y) \Leftrightarrow$

$\exists z \exists y \ P(z,y) \Leftrightarrow$

$\exists z \exists x \ P(z,x) \Leftrightarrow$

$\exists y \exists x \ P(y,x)$

In fact, this also works with mixed quantifiers, e.g.:

$\forall x \exists y \ P(x,y) \Leftrightarrow$

$\forall z \exists y \ P(z,y) \Leftrightarrow$

$\forall z \exists x \ P(z,x) \Leftrightarrow$

$\forall y \exists x \ P(y,x)$

Finally, swapping variables in a formula typically results in a statement that is not equivalent, but there are cases where it does remain equivalent:

Swapping Role of Variables

$\forall x \forall y \ P(x,y) \Leftrightarrow \forall x \forall y \ P(y,x) $

$\exists x \exists y \ P(x,y) \Leftrightarrow \exists x \exists y \ P(y,x) $

And these we can derive from the earlier principles, e.g.:

$\forall x \forall y \ P(x,y) \Leftrightarrow \text{ (Swapping Quantifiers)}$

$\forall y \forall x \ P(x,y) \Leftrightarrow \text{ (Swapping Bound Variables)}$

$\forall x \forall y \ P(y,x)$

Answer 2

1. There is unfortunately no universally observed conventions. Different traditions that give different answers. If you're in doubt which convention your readership will be employing, either explain your convention up front or disambiguate fully using parentheses.

2. This also differs from tradition to tradition.

3. Yes, these are always true. You can get from the antecedent to the succedent by exchanging the order of two quantifiers of the same kind (which is allowed, as per 4) and then renaming the bound variables.

4. I don't understand the question -- which kind of answer to "how" something is true do you expect? It is "very" true or "certainly" true or just plain true true?