4
$\begingroup$

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 !

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – F.Carette Oct 17 '18 at 11:06
  • 1
    $\begingroup$ I think you mean that $\exists x \forall y P(x,\,y)$ implies $\forall y \exists x P(x,\,y)$. $\endgroup$ – J.G. Oct 17 '18 at 14:01
  • $\begingroup$ 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}$. $\endgroup$ – deeppinkwater Oct 17 '18 at 14:15
  • $\begingroup$ 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}$. $\endgroup$ – deeppinkwater Oct 17 '18 at 14:15
  • $\begingroup$ 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 ? $\endgroup$ – deeppinkwater Oct 17 '18 at 14:15
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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