Quantifiers (logic)

Question

I have a question about quantifiers in logic.

I know that we can switch the quantifiers "$\forall$" between them (e.g., $\forall x \in X, \forall y \in Y, p(x, y) \Leftrightarrow \forall y \in Y, \forall x \in X, p(x, y)$), the quantifiers "$\exists$" between them and that we cannot do this for two quantifiers "$\exists$" and "$\forall$" (e.g., we just have : $\exists x \in X, \forall y \in Y, p(x, y) \Rightarrow \forall y \in Y, \exists x \in X, p(x, y)$)

My problem is the following, if I take for example the proposition :

$\forall x \in \mathbb{R}, \forall y \in \{z \in \mathbb{R} | z = x + 3\}, p(x, y)$,

the set to which $y$ belongs depends of $x$ right ? In this case, it does not make any sense for me to switch the two quantifiers "$\forall$" here (because $x$ has to be defined "first").

You could say that it's not a problem because we can switch the two "$\forall"$ in the previous proposition, but then, if we take :

$\exists y \in \{z \in \mathbb{R} | z = x + 3\}, \forall x \in \mathbb{R}, p(x, y)$,

We cannot switch "$\forall$" and "$\exists$" and again, it has no sense for me...

(I have the feeling that it is simply not a good way to write it and that obviously, we have to define $x$ first, but I'm not 100% sure...)

Can you enlight me ? Thank you !

Answer 1

In this case, the use of set theory symbols seems to complicate things.

Assume for simplicity $\mathbb R$ as domain; in this way, we can simply write $\forall x$.

What does it mean : $∀y ∈ \{ z \mid z=x+3 \}$ ? It simply means : $y=x+3$.

Thus, the formula will be : $\forall x \forall y \ (y=x+3 \to p(x,y))$.

In this case, we have no issue with the swap of the two quantifiers.

---

Regarding the second example, things are different.

In general, we cannot swap $\forall$ and $\exists$.

More specifically : $\exists x \forall y P(x,y)$ implies $\forall y \exists x P(x,y)$, but not vice versa.

Consider the following counterexample :

$\forall m \exists n (m < n)$

holds in $\mathbb N$ (it is enough to consider $m+1$), while :

$\exists n \forall m (m < n)$

does not.

Answer 2

Long story short, you are right!

the set to which $y$ belongs depends of $x$ right ? In this case, it does not make any sense for me to switch the two quantifiers $\forall$ here (because $x$ has to be defined "first").

That's it, if $x$ and $y$ are independant, you can switch the $\forall$ quantifiers, if they're not, you can't.

The reason behind this, as explained with your exemple in Mauro ALLEGRANZA's answer, is that it can be written:

$$\forall x \in \mathbb X, \forall y \in \mathbb Y_x, p(x,y)$$

Which is the same as writting:

$$\forall x \in \mathbb X, \forall y \in \mathbb Y, (y\in \mathbb Y_x \implies p(x,y))$$

Now you can see that $x$ and $y$ don't play symetrical roles.

Answer 3

One way of analyzing $\forall$ and $\exists$ is to imagine an array in Cartesian coordinates of white and black squares, where white at $(x,y)$ represents $p(x,y)$ and black at $(x,y)$ represents $\not p(x,y)$. Then "$\exists y: \forall x: p(x,y)$" means "There is a row consisting entirely of white squares", and "$\forall x: \exists y:p(x,y)$" means "Every column has a white square". If there is a row of white squares, then every column has a white square (whatever square in that column is in the all-white row), but every column having a white square doesn't mean there's a white row: the white squares could be in different columns.

Also $\forall x: \forall y \in S_x: p(x,y)$ can be interpreted as "Each column has a subset defined by $S_x$ for which all the squares are white." But taking, for each column, a subset of that column is equivalent to simply taking a subset of the entire Cartesian plane to begin with. For instance, in your example, we can word it as "Every square for which $y=x+3$ is white". If we want to, we could write this in a symmetric manner as $\forall y \in \mathbb{R}, \forall x \in \{z \in \mathbb{R} | y = x=z + 3\}, p(x, y)$.