2
$\begingroup$

Writing $(\forall a)(\forall b)(\forall c)(\forall d)\cdots$ means for every $a, b, c, d, \cdots$

And writing $(\exists a)(\exists b)(\exists c)(\exists d)\cdots$ means there is/are some $a, b, c, d, \cdots$

So I think changing the order shouldn't change anything right? If so in a formula of the form $(\exists a)(\exists b)(\cdots)$ do they both have the same scope?

While $(\exists x)(\forall y)$ and $(\forall x)(\exists y)$ are different since they mean: there is some $x$ that is such that for every $y$.. and for every $x$ there is some $y$ that is such that.. respectively correct?

$\endgroup$
2
2
$\begingroup$

They are, which is why you sometimes see expressions such as $\exists x,\,y$ or $\forall x,\,y$. Indeed, $$\exists x\exists y\phi(x,\,y)\iff\exists y\exists x\phi(x,\,y).$$

$\endgroup$
0
$\begingroup$

As J.G. points out, we indeed have:

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

and we also have:

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

And this generalizes to any number of existentials or universals. That is, you can reorder a sequence of existentials (universals) in any way you want, e.g.:

$$\exists x\exists y \exists z \ \phi(x,y,z)\Leftrightarrow \exists y\exists z\exists x \ \phi(x,y,z)$$

You might also be interested in knowing that with such a sequence of quantifiers of the same type, you can (instead of switching the quantifiers) switch the use of the variables as quantified by those quantifiers in the 'body' of the statements. For example:

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

$$\forall x\forall y \forall z \ \phi(x,y,z)\Leftrightarrow \forall x\forall y\forall z \ \phi(y,z,x)$$

Being able to swap the use of the variables is of course due to the fact that variables are just 'dummies', and can therefore be replaced by other variables. That is, we have

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

And therefore we can do:

$$\exists x\exists y\ \phi(x,y)\Leftrightarrow \exists x\exists z\ \phi(x,z)\Leftrightarrow \exists y\exists z\ \phi(y,z)\Leftrightarrow \exists y\exists x\ \phi(y,x)\Leftrightarrow \exists x\exists y \ \phi(y,x)$$

Now, as you realized, once we start to mix quantifier types, the equivalences no longer hold. That is we have:

$$\exists x\forall y\ \phi(x,y)\color{red}\not \Leftrightarrow \forall y\exists x \ \phi(x,y)$$

Also, the fact that just because you have multiple quantifiers of the same type doesn;t mean that you can swap them ... if there is a quantifier of a different type between them, it also doesn't work. For example:

$$\exists x\forall y \exists z \ \phi(x,y,z)\color{red}\not \Leftrightarrow \exists z\forall y\exists x \ \phi(x,y,z)$$

However, for uninterrupted subsequences of quantifiers of the same type, it still works. For example, we do have:

$$\forall x\exists y \exists z \ \phi(x,y,z) \Leftrightarrow \forall x \exists z \exists y \ \phi(x,y,z)$$

$$\exists x\forall y \forall z \exists w \ \phi(x,y,z,w)\Leftrightarrow \forall x\forall z\forall y \exists w \ \phi(x,y,z,w)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.