Does swapping the quantifiers change meaning for the following case?

238 Views Asked by At

Case 1: $\exists x\forall y\;.\; P(x,y)$

Case 2: $\forall x\exists y\;.\; P(x,y)$

I have tried to write them and convince myself of an answer:

Case 1: There exists an $x$ for every $y$ such that $P(x,y)$ holds.

Case 2: For every $x$, there is a $y$ such that $P(x,y)$ holds.

As I currently interpret it, these both mean the same. Could someone indicate whether I have thought about this correctly? I know that if I had taken case 2 to be $$\forall y\exists x\;.\; P(x,y)$$then the meaning changes. What if it is only the quantifiers that are swapped, and variables remain in the same place? All help appreciated.

1

There are 1 best solutions below

1
On

Case 1 means that a single $x$ exists that makes $P(x,y)$ true for all $y$. This $x$ is the same for all $y$: this information is found in the order of the quantifiers, where we wrote $\exists x$ such that $\forall y$.

Case 2 means that given any $x$, we can find a $y = y(x)$ such that $P(x,y)$ is true. The choice of $y$ depends on the $x$ we started out with, this information is given by the quantifiers written in the order $\forall x$ $\exists y$.

A concrete example might help, let's look at the definition of a converging sequence: $(a_n)_{n \in \mathbb{N}}$ converges to $L$ iff $\forall \varepsilon >0$, $\exists n_0 \in \mathbb{N}$ such that $\forall n\geq n_0$, $|a_n - L| < \varepsilon$. The order of the quantifiers matters, here the $n_0$ depends on the choice of $\varepsilon$. This makes sense, if I make the distance between $a_n$ and $L$ very small ($\varepsilon$), then the term of the sequence $n_0$ starting from which all elements of the sequence are within a distance $\varepsilon$ of the limit $L$ will increase. Swapping the order of $\exists n_0$ and $\forall \varepsilon$ wouldn't make sense anymore.

(edit: fixed a typo, thanks Andreas)