Is there a scenario for when changing the order of different quantifiers in a nested quantifier retain the original meaning?

Question

I was exploring the difference in meaning of a proposition when changing the order of two different quantifiers in a nested quantifier. I've been sitting here playing around with various scenarios and doing a bit of research, but I'm unable to come to a decisive answer. Does changing the order of different quantifiers always change the meaning of a logical proposition?

There was two scenarios I was exploring:

1. Not changing the order of Quantifiers but keeping the order of the variables (e.g. For all x there exists a y ,changed to, For all y there exists an x)

2. Changing both the order of the quantifiers and the variables (e.g. For all x there exists a y ,changed to, There exists an x for all y)

If anyone could give me a scenario or a reasoning as to why it's not possible, that would be amazing. Thanks in advance.

Answer 1

The variables in the quantifier might not appear in the statement at all. For example, $\forall x \exists y \phi$ and $\exists y \forall x \phi$ are equvialent if $x$ and $y$ don't appear in $\phi$.

Answer 2

Your question is very subtle, and it's great that you are thinking about these things. I think your question deserves a serious answer, and I hope this serious answer isn't too long and detailed to be helpful.

The short answer to your question is

no two of them have the same meaning.

There are very few cases where different expressions have the exact same meaning. One of these rare exceptions is that “For every $x$, $P(x)$ is true” has the same meaning as “For every $y$, $P(y)$ is true”. (And similarly “For some $x$…”, “For some $y$…”.) The name of the variable in the formula is completely arbitrary and doesn't affect the meaning of the expression. An example closer to the expressions you were talking about is that “For every $x$ there is some $y$ such that $P(x,y)$ is true” has the same meaning as “For every $y$ there is some $x$ such that $P(y,x)$ is true”. (Here “$P(x,y)$” should be understood to represent some claim about $x$ and $y$, for example “$x+1>y$”.) All we've done is to change the names of the two variables, which doesn't change the meaning.

Not including this sort of renaming, there are three possible ways to rearrange $$0.\qquad \forall x.\exists y.P(x,y),$$ the two you suggested, and a third:

$$ 1.\qquad\forall y.\exists x.P(x, y) \\ 2.\qquad\exists x.\forall y.P(x, y) \\ 3.\qquad\exists y.\forall x.P(x, y) $$

(The “$\forall$” and “$\exists$” signs are standard notation for “for all” and “there exists”.)

These four all express different meanings, four different claims about the behavior of $P$. For a single particular $P$, each one is either true or false. For example, when $P(x, y)$ is “x < y”, the original claim (0) is true, and so is (1), but (2) and (3) are false. But even though (2) are (3) are both false we can't conclude that they have the same meaning. “The moon is made of green cheese” and “Pinocchio is the president of Ghana” are both false, but don't mean the same thing. (2) says $\exists x.\forall y. x<y$ and (3) says $\exists y.\forall x. x<y$, and these still mean different things.

---

Ethan Bolker's suggestion is an interesting example. Ethan suggests we consider $P(x, y)$ to be “$x+y=2$”. Does $$\exists x.\forall y.x+y=2$$ mean the same as $$\exists y.\forall x.x+y=2?$$ I'd argue no. This is formally the same as my $x<y$ example of the previous paragraph. The expression “$x+y$” doesn't mean the same as “$y+x$” any more than the expression “$x<y$” means the same as “$y<x$”. It happens to be the case that the numeric value of $x+y$ is always the same as that of $y+x$, but that doesn't imply that the expressions have the same meaning; if it did there would be no reason to state or prove the commutative property of addition, since “$x+y = y+x$” would be inane.

Now we could ask a different question than the one you did ask: is there a single specific $P$ for which all of those expressions are logically equivalent, that is, both true or both false? And here Ethan Bolker's suggestion does work: when $P(x, y) = “x+y=2”$, all four are true. But the meanings are still different, they just happen to have the same truth value, like the claims about Pinocchio and the moon.

---

One way to show that (1) has a different meaning from the original statement (0) is by observing that when $P$ is “$x^2=y$”, the original statement is true, but (1) is false (at least if you understand $\forall x$ to mean “for all integers $x$” or “for all real numbers $x$"). If (1) had the same meaning as (0), it would have to be true whenever (0) was true, and for that particular choice of $P$, it isn't.

Similarly when $P$ is “$x^2=y$”, (2) and (3) are false, so can't mean the same as (0).

Could (2) and (3) perhaps mean the same thing? No, because when $P(x,y)$ is “$x^2\ne y$”, item (2) is false but item (3) is true (just take $y=-1$).

Similarly you can find specific $P$ for which (1) is true and (2) is false, or (1) is true and (3) is false. So none of these could have the same meaning.

In contrast, $\forall x.\exists y.P(x,y)$ and $\forall y. \exists x. P(y,x)$ have the same truth value for every possible $P$, which justifies the claim that they do have the same meaning. David Lui's example is of this type.

I hope this was more helpful than confusing. Welcome to Math SE.

Answer 3

Does changing the order of different quantifiers always change the meaning of a logical proposition?

No. Adding to David Lui's example:

e.g. For all x there exists a y, changed to For all y there exists an x

$$∀x∃y(Px → Py) \equiv ∀y∃x(Px → Py);$$

e.g. For all x there exists a y, changed to There exists an x for all y

$$∀x∃y(Px → Py) \equiv ∃x∀y(Px → Py);$$

switching around ∃y and ∀x $$∀x∃y(Px → Py) \equiv ∃y∀x(Px → Py).$$

Answer 4

Given

(i) ∀x∃y[P(x,y) ↔ P($\neg x$,y)]

We have that

∀x∃yP(x,y) ↔ ∃y∀xP(x,y)

Proof:

Assume: ∀x∃yP(x,y)

Pick ÿ s.t. ∀xP(x,ÿ)

by (i) pick γ s.t.

∀x[P(x,γ) ↔ P($\neg x$,γ)]

In particular,

[P(ÿ,γ) ↔ P($\neg ÿ$,γ)]

If x = ÿ then P(x,γ)

If x = $\neg ÿ$ then P(x,γ) holds

It follows that

∀x(P(x,γ) holds.

thus,

∃y∀xP(x,y)

Assume: ∃y∀xP(x,y)

Then Pick ÿ s.t. ∀xP(x,ÿ)

So ∀x∃yP(x,y)

Answer 5

Counter Example

1. $\forall x \in N: \exists y \in N: y\gt x$

2. $ \exists y \in N:\forall x \in N: y\gt x$

(1) says that, for every $x\in N$, there exists $y\in N$ such that $y\gt x$. (true)

(2) says that, there exists number $y\in N$ that, for every $x\in N$, we have $y\gt x$. (false)