Quantifiers and variable link

Question

I have asked a professor about the difference between the two expressions, he said the following:

$\forall x, \exists y, \; p(x,y)$: y is linked to x

$ \exists x,\forall y, \; p(x,y)$: y is not linked to x

can you elaborate more on this?

Answer 1

I’ll start with the second statement, as I think it makes more sense that way.

$\exists x, \forall y, P(x,y)$ means that for all $y$ there exists such an $x$ that the predicate $P(x,y)$ is true. That is, unless otherwise specified, your $y$ variable can take any value within the universe, whereas for $x$ we only consider one particular value. Of course, there could more than one $x$ that would satisfy the expression, but the question is about existence, not uniqueness.

Example: $$\exists x\in \Bbb{N} , \forall y\in \Bbb{N} ,x \leq y $$

The first statement, on the other hand, means that for any one $x$ in the universe we can find a particular $y$ that will make $P(x,y)$ true.

Example: $$\forall x\in \Bbb{N} , \exists y\in \Bbb{N} , x < y $$