# Quantifiers (logic)

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 !

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.

• We can even write it without $y$: $\forall x \in \mathbb R, p(x,x+3)$. There is no need of $\forall y$ because $y=x+3$ only have one solution in $\mathbb R$. $y\equiv x+3 \pmod n$ would have been a better exemple. (With $x,y \in \mathbb N or \mathbb Z$, of course) – F.Carette Oct 17 '18 at 11:06
• I think you mean that $\exists x \forall y P(x,\,y)$ implies $\forall y \exists x P(x,\,y)$. – J.G. Oct 17 '18 at 14:01
• Thank you for your answers. In fact, I am going to give you another example which is more related to what I am looking for (because it was a little bit tricky with $\mathbb{R}$). Let $L = \{A \in \mathcal{P}(N) | |A| = 2\} = \{ \{i, j\} \subset N\}$ (where $N \subset \mathbb{N}$ is a finite set). Let $S : L \rightarrow S_{\{i, j\}} = S_{ij} \subset X$ (where $X$ is an arbitrary set) such that we can consider the family of set $(S_{ij})_{\{i, j\} \in L}$. – deeppinkwater Oct 17 '18 at 14:15
• Let $(u_{i})_{i \in N}$ be a family of function such that : $\forall i \in N, u_{i} : \prod_{\{i, j\} \in L} S_{ij} \rightarrow \mathbb{R}$. Now, let $t_{ij} \in S_{ij}$ and $s_{- ij} \in \prod_{\{k, l\} \neq \{i, j\}} S_{kl}$. – deeppinkwater Oct 17 '18 at 14:15
• If I understand what you said, we have the following equivalence : $[\forall \{i, j\} \in L, \forall s_{ij} \in S_{ij}, \forall k \in \{i, j\}, u_{k}(t_{ij}, s_{- ij}) \leq u_{k}(s_{ij}, s_{- ij})]$ $\Leftrightarrow$ $[\forall \{i, j\} \in L, \forall s_{ij} \in X, \forall k \in N, ((s_{ij} \in S_{ij}) \wedge (k \in \{i, j\}) \Rightarrow u_{k}(t_{ij}, s_{- ij}) \leq u_{k}(s_{ij}, s_{- ij})]$ Right ? – deeppinkwater Oct 17 '18 at 14:15

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.

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)$$.