Commutative quantifiers

Question

If I have a proposition of the form $$(\forall x \in X) (\exists y \in Y) (\forall r \in R) \, P(x,y,r)$$ where at least any number of $X$, $Y$ and $R$ can be the same. Is that logically equivalent to the following?

$$(\forall r \in R) (\forall x \in X) (\exists y \in Y) \, P(x,y,r)$$

where $P(x,y,r)$ is any proposition (possibly an implication). How would I prove it, if it's possible? Properties of quantifiers can't be proven through truth tables, so how would I start to approach this sort of problem?

Answer 1

If I have a proposition of the form $\forall x \in X\ \exists y \in Y\ \forall r \in R\ P(x,y,r)$ where at least any number of Y,X and R can be the same. Is that logically equivalent to $\forall r \in R\ \forall x \in X\ \exists y \in Y\ P(x,y,r)$ ?

No.   The former implies the latter but is not equivalent to it.

---

You have $\forall x\in\mathrm X~~\exists y\in\mathrm Y~~\forall r\in\mathrm R~~P(x,y,r)$ where $P$ is a generic relation.

Now $\exists y~\forall r~\phi$ entails $\forall r~\exists y~\phi$. If something holds for every $r$ of a particular $y$, then something holds for some $y$ of any $r$.

• "There is a column where every row contains a letter", entails that "Every row has a column which contains a letter."

However, the converse is not so.

• "Every row has a column which contains a letter," does not logically entail "There is a column where every row contains a letter."   For instance, when every row may have a distinct column containing its letter, then the first statement is satisfied while the second is not.

So $\forall x\in\mathrm X~~\forall r\in\mathrm R~~\exists y\in\mathrm Y~~P(x,y,r)$ is entailed by the original sentence, but is not equivalent to it.

This can be broken into two steps.

---

$\forall x ~\forall r~\phi$ entails and is entailed by $\forall r~\forall x~\phi$. So the previous statement is equivalent to the desired result.   However the original statement only entails them. $$\forall x\in\mathrm X~~\exists y\in\mathrm Y~~\forall r\in\mathrm R~~P(x,y,r)\\\Downarrow\\\forall x\in\mathrm X~~\forall r\in\mathrm R~~\exists y\in\mathrm Y~~P(x,y,r)\\\Updownarrow\\\forall r\in\mathrm R~~\forall x\in\mathrm X~~\exists y\in\mathrm Y~~P(x,y,r)$$

Answer 2

No, the statements are not equivalent. In general, quantifiers of the same type are commutative ($\forall x \forall y \phi \equiv \forall y \forall x \phi$; $\exists x \exists y \phi \equiv \exists y \exists x \phi$), but quantifiers of two different types are not ($\forall x \exists y \phi \not \equiv \exists y \forall x \phi$).

To illustrate this, consider the simple example:

For all tupperware boxes there is a lid that fits it.

This can be formalized as

(1) $\forall x (Box(x) \to \exists y (Lid(y) \land Fit(y,x)))$

Or, using the abbreviations you made use of in your formula$^1$,

$\forall x \in Box \exists y \in Lid, Fit(y,x)$

Unfortunately, from this we can not conclude that there is a magical lid that fits all tupperware boxes:

(2) $\not \vDash \exists y \forall x (Box(x) \to (Lid(y) \land Fit(y,x)))$

(Usually, the case is rather that there are alwyays somehow more lids than tupperware boxes, but still you can't find a suitable lid for all your boxes...)

So $\forall x \exists y \phi \not \vDash \exists y \forall x \phi$. This can be shown by providing a simple model that satisfies that first but not the second formula.

The reverse direction does hold: If there were a magical lid that is compatible with all tupperware boxes, then of course every tupperware box would have a matching lid.

So $\exists y \forall x \phi \vDash \forall x \exists y \phi$. You can prove this by making an argument about about how quantified formulas are satisfied semantically, or by a formal proof in some system like natural deduction for predicate logic, employing soundness of this system.

That (1) $\not \vDash$ (2) but (2) $\vDash$ (1) means that (2) is a stronger statement: Any situation in which (2) holds is one where (1) is also true, but there are situations in which (1) is true but (2) is not, because (2) is a stronger constraint on the valid models.

The same reasoning now applies to your formula that involves three quantifications: While it is okay to swap the order of $\forall x$ and $\forall r$, moving $\forall r$ in front of $\exists y$ is not. This makes for a weaker statement: Saying that for all $r \in R$ we can find some $y \in Y$ that satisfies $P(x,y,r)$ is a less strict requirement and will hence have models that don't satisfy the original stronger claim that there must be a particular $y \in Y$ that works for all $r \in R$.

Since $\forall r \in R \forall x \in X \exists y \in Y ,P(x,y,r) \not \models \forall x \in X \exists y \in Y \forall r \in R ,P(x,y,r)$ but $\forall x \in X \exists y \in Y \forall r \in R ,P(x,y,r) \models \forall r \in R \forall x \in X \exists y \in Y ,P(x,y,r)$, if you are convinced that your second formulation does the job, you can use this one, and all the models that were compatible with your first formalization will also be permitted by your second formalization. But they are not logically equivalent: Depending on what you want to describe/to which models you want to restrict yourself to with your proposition, your second formalization might be too weak, in that it in addition permits models that would contradict the first formalization - at least it is in the general case. (I would have to get a better understanding of your predicate to be able to tell whether your second, weaker version is still strong enough for what you want to express).

---

To show that the two formulas are not equivalent, consider a simple model:

$$\mathfrak{A} = \langle \mathcal{A}, \mathcal{I} \rangle$$ with $$\mathcal{A} = \{x1, y1, y2, r1, r2\}$$ $$\mathcal{I}(X) = \{x1\};\\ \mathcal{I}(Y) = \{y1, y2\};\\ \mathcal{I}(R) = \{r1, r2\};\\ \mathcal{I}(P) = \{\langle x1, y1, r1 \rangle, \langle x1, y2, r2 \rangle\}$$

$\mathfrak{A} \models \forall r \in R \forall x \in X \exists y \in Y P(x,y,r)$ (your second formalization): For each r and for each thing in x (there is just one, to make things simpler) we can find find some element y that goes in the triple: For $r1$, we have $y1$, and for $r2$, we find $y2$.
But $\mathfrak{A} \not \models \forall x \in X \exists y \in Y \forall r \in R P(x,y,r)$ (your first formalization), because for our one $x$, there is no thing in $Y$ that works for all the $r$.

Since there is a model that satisfies the second but not the first formula, they are not equivalent.

---

$^1$ Technically, $\forall x \in X \exists y \in Y \phi$ is not a syntactically valid first-order formula, but it's a very common abbrevation for $\forall x (x \in X \to \exists y (y \in Y \land \phi))$. I'm using this latter explicit syntax to hopefully give a better understanding of why a formula is or is not satisfied by a model.

Answer 3

ADDED LAST

The final word is that lemontree's answer was right and mine was wrong; I have left the original in place below.

A good example of the in-equivalence, is to let the domains of discourse $X$, $Y$, and $R$ be the reals, and consider the proposition $P(x,y,z)$ to be $$ (x=0) \vee ((y \in \Bbb Q) \wedge (|y-\sqrt{2}| \lt |x|) \wedge (|ry-r\sqrt{2}| \lt |rx|)) $$ Then the first statement $\forall x\left( \exists y \forall r P(x,y,r) \right)$ reads in English as "for any given real non-zero $x$ there exists some rational $y$ such that for all real $r$ the absolute difference between $y$ and $\sqrt{2}$ is less than $|x|$ (and when both sides of that inequality are multiplied by $R$ it still holds). This is obviously true, since arbitrarily good rational approximations to $\sqrt{2}$ can be found.

But the second statement $\forall r\left( \exists y \forall x P(x,y,r) \right)$ reads "for every real $r$, there exists some rational $y$ such that for any arbitrary non-zero $x$ the absolute difference between $y$ and $\sqrt{2}$ is less than $|x|$ (and another clause)." That is obviously not true, because there is no rational approximation to $\sqrt{2}$ that is closer than any arbitrarly chosen $x$.

Thus the two statements are not logically equivalent.

---

ORIGINAL ANSWER

In a logic system that allows Skolemization, you can apply this second-order equivalence (see https://en.wikipedia.org/wiki/Skolem_normal_form): $$ \forall x\left( R(g(x)) \vee \exists yR(x,y)\right) \Longleftrightarrow \exists f\forall x \left( R(g(x)) \vee R(x,f(x))\right) $$ where $f(x)$ is a function that maps $x$ to $y$.

Our application of this is a specialization which is a considerable simplification: Let $R(g(x)) = F$ (False) and $F(x,f(x)$ be $\forall r P(x,f(x),r)$. Then the equivalence reads $$ \forall x\left( \exists y \forall r P(x,y,r) \right) \Longleftrightarrow \exists f\forall x \left( \forall r P(x,f(x),r)\right) $$ Here I have omitted the domain designations, that is, $\forall x$ means $\forall x \in X$ and $\exists y$ means $\exists y \in Y$.

And now we can commute $\forall x \forall r$ because an axiom says that $\forall x \forall r\, P$ is identical to $\forall r \forall x\, P$, thus $$\exists f\forall x \forall r P(x,f(x),r) \Longleftrightarrow \exists f\forall r \forall x P(x,f(x),r) \Longleftrightarrow \forall r\left( \exists y \forall x P(x,y,r) \right) $$

---

Added later:

OMG, I didn't have to go into this detail, because (assuming the Skolem_normal_form page is correct) they give an example that is precisely the case in the problem! To quote:

As an example, the formula $\forall x \exists y \forall z P(x,y,z)$ is not in Skolem normal form because it contains the existential quatifier $\exists y$. Skolemization replaces $y$ with $f(x) \ldots$ and removes the quantification over $y$. The resulting formula is $\forall x \forall z P(x,f(x),z)$. $\ldots$ The formula obtained by this transformation is satisfiable if and only if the original formula is.

(Emphasis mine). So we can now go over to $\forall x \forall z P(x,f(x),z) \equiv \forall z \forall x P(x,f(x),z)$ and from there, use the "if and only if" property to go to the equivalent $\forall z \exists y \forall x P(x,y,z)$

The use of the function $f(x)$ might imply that this reasoning depends on having the axiom of choice.

---

To extend/use the @lemontree example:

Let $P(x,y,r)$ be "lid $r$ fits every tupperware that is in the same house ($x$) as this tupperware box $y$.

Then the question becomes whether these statements are identical:

• For all houses, there is some lid that fits every tupperware in the house.
• For every tupperware, there exists some lid that fits (it and) every tupperware in the same house.

I claim they are logically equivalent.