3
$\begingroup$

For example if I have $$\forall a \in A \forall b_2 \in B \forall b_1 \in B((a,b_1)\notin R \lor (b_1, b_2)\notin R)$$ is is the same as

$$\forall b_2 \in B \forall b_1 \in B \forall a \in A ((a,b_1)\notin R \lor (b_1, b_2)\notin R)$$

and other variations thereof? Is this true in general? I ask because I think it is the same thing since there is not a "dependency" between these 3 variables but I might be wrong.

$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

Universal quantifiers if not separated by other types of quantifiers (existential for example) are interchangeble IF they do not depend on each other.

Example where the exchange is possible: $$\forall a \in A,\, \forall b \in B : p(a,b) = T$$ $$\forall b \in B,\, \forall a \in A : p(a,b) = T$$

Example where the exchange cannot be performed:

$$\forall a \in A,\, \forall b \in (B \setminus \{a\}) : p(a,b) = T$$

in the second example you can observe that the second universal quantifier depends on the first since the set $(B \setminus \{a\})$ does not contain the element chosen by the first universal quantifier.

indeed like you said in your proposition the universal quantifiers are all togheter and they are independent so you can swap them the way you like.

$\endgroup$
5
  • 2
    $\begingroup$ Note that if we "de-relativize" the quantifiers above - that is, replace "$\forall x\in X(\varphi(x))$" with "$\forall x(x\in X\rightarrow\varphi(x))$" - then we can perform the latter exchange: "$\forall a\in A\forall b\in (B\setminus\{a\})(p(a, b))$" derelativizes to "$\forall a\forall b(a\in A, b\in B\setminus \{a\}\rightarrow p(a, b))$," and this is equivalent to "$\forall b\forall a(a\in A, b\in B\setminus \{a\}\rightarrow p(a, b))$." So this example of nonexchangeable quantifiers is more a consequence of the syntactic form of proposition used; (cont'd) $\endgroup$
    – Noah Schweber
    Aug 4, 2016 at 16:36
  • 2
    $\begingroup$ by contrast, swapping different types of quantifier, or swapping universals across an existential (e.g. going from "$\forall a\exists b\forall c$" to "$\forall c\exists b\forall a$") or vice versa, is genuinely impossible. $\endgroup$
    – Noah Schweber
    Aug 4, 2016 at 16:36
  • 1
    $\begingroup$ you are absolutely correct. this was meant to be an example to guide the user of the post when he is doing quick manipulations, and i think you'll agree that it's not always productive (for the sake of writing concise and clear mathematical propositions) to perform such operations. Moreover i already mentioned in my answer that swapping U.Q that are separed by an E.Q. is impossible. anyway a +1 for you :) $\endgroup$
    – Frank
    Aug 4, 2016 at 16:41
  • 2
    $\begingroup$ Yes - my comments were aimed at the OP, not at you. Your answer is of course completely correct, I just thought it would be useful to the OP to see how there can be different obstacles to quantifier swapping (and you're absolutely right, in general derelativizing is really messy and not a thing you actually want to do). $\endgroup$
    – Noah Schweber
    Aug 4, 2016 at 16:43
  • 2
    $\begingroup$ @Noah in dependent type theory, the quantifiers may be truly dependent such that we cannot write the type of the second variable without depending on the first; it is not always possible to "de-relativize" as in typeless set theory. $\endgroup$
    – lily
    Aug 4, 2016 at 16:46
3
$\begingroup$

Yes, you can permute universal quantifiers. You can also permute existential quantifiers - "$\exists x\exists y\varphi(x, y)$" is equivalent to "$\exists y\exists x\varphi(x, y)$".

You cannot, however, swap different types of quantifiers: e.g. "$\forall x\exists y(x<y)$" and "$\exists y\forall x(x<y)$" mean very different things!

EDIT: Another thing you can't do is swap similar quantifiers across a different kind of quantifier: "$\forall x\exists y\forall z(p(x, y, z))$" is not the same as "$\forall z\exists y\forall x(p(x, y, z))$". (For example, take $p(x, y, z)$ to be the formula "$y>x$ and not ($y>z>x$);" only one of the sentences above is true in the integers with the usual ordering!)

$\endgroup$
2
$\begingroup$

Yes, universal quantification expressions are always equivalent for whichever order you chose for the quantifiers.

To see why this is true, consider the interpretation of a sentence $\forall a\in A \forall b\in B f(a,b)$. This is true iff $\forall b\in B f(a,b)$ is true for whichever $a$, which in turn is true iff $f(a,b)$ is true for whichever $a$ and $b$. Going the other way, we realize that then $\forall b\in B \forall a \in A f(a,b)$ is true iff $\forall a\in A \forall b\in B f(a,b)$ is true.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .