Explanation about quantifier sequence ∀x∃y and ∃y∀x

Question

I'm learning the science of programming. And there are some quantifier questions I cannot understand, does anyone could explain?

Let $p(u,v) \ ≡ \ v≤u^2 $

Is $(∀x.∃y.p(x,y))$ valid?
Is $(∃y.∀x.p(x,y))$ valid?

Answer 1

$\forall x \ \exists y \ p(x,y)$ ends up saying that for any number $x$ you can find some number $y$ such that $p(x,y)$, i.e. such that $y\le x^2$.

The truth of this statement depends on the domain that you quantify over, though for most 'typical' domain it is true. For example, if the domain is all integers, then given any $x$ you can pick any negative number (or $0$) for $y$ to make this statement true. If the domain is the natural numbers, then the claim is also true, since for any $x$ you can pick $y=0$. And it works for the positive integers as well, since for any $x$ you can pick $y=1$. But, if the domain is, say, $[0.5,2]$, then the claim is false, since with $x=0.5$ you gfet $x^2=0.25$ and now there is no $y$ you can pick from $[0.5,2]$ that is $\le 0.25$

Can you analyze the second statement yourself?

Answer 2

The second one is saying that there is a number y such that, if you square it, it will be bigger than or equal to any number x. We can rule this one out by choosing an x that is bigger than the square of y.

The first one says that for any number x, you can find a number y such that y squared is bigger. This is true even if y is not squared.

Answer 3

I like to use a more concrete example when I illustrate the difference. Let $X$ be the set of men in the world, $Y$ the set of women, and for $x\in X,y\in Y$, let $P(x,y)$ mean "$x$ and $y$ are meant for one another".

$\forall x.\exists y.P(x,y)$ means "For every man, there is a woman who is meant for him." While one can dispute this statement as somewhat old-fashioned, it is a view that many people have and it is hardly controversial.

$\exists y.\forall x.P(x,y)$ means "There exists one woman who is meant to be with every single man in the world." All I can think is poor woman.