Order of parameters in quantified predicates

Question

I'm studying up for my midterm in Discrete Math and I've been looking at sample questions and their solutions. There is one I don't really understand and I was hoping someone could help me out.

2. Let the domains of x and y be the set of all integers.
Compute the Boolean values of the following quantified predicates:

  All x, Exist y, (x^2 < y)
  Exist y, All x, (x^2 < y)
  Exist x, All y, (x^2 >= y)
  All y, Exist x, (x^2 >= y)

Solution:
  All x, Exist y, (x^2 < y) = T
  Exist y, All x, (x^2 < y) = F
  Exist x, All y, (x^2 >= y) = F 
  All y, Exist x, (x^2 >= y) = T

I'm not really sure if I'm understanding this or not. The first solution appears to say there exists one integer that is greater than every integer squared? I guess that makes sense on a per-integer basis, but the second solution appears to say the same thing, in a different order, but is false.

I know there's more here that I'm just not seeing. Would somebody mind explaining the nature of the problem and solutions? It would mean a lot, thanks!

Answer 1

$\forall x.P$ means that every possible value of $x$ will make $P$ true.

$\exists x.P$ means that there is a value of $x$ that will make $P$ true. One such value is enough, but there has to be at least one.

Usually each variable is restricted to some domain. For example, since this is a discrete math course, can we stipulate that $x$ and $y$ represent integers?

Now consider, the sentence, "For $x = 4,$ there is a value of $y$ that satisfies $x^2 < y.$" Is that true?

How about, "For $x = 17,$ there is a value of $y$ that satisfies $x^2 < y$"?

In fact, we could set $x$ equal to any integer, and there would still be a value of $y$ that satisfies $x^2 < y.$ So the statement, "There is a value of $y$ that satisfies $x^2 < y,$" which we can write as $\exists y.(x^2<y),$ is true for all $x.$ And that is what $\forall x.\exists y.(x^2<y)$ says.

Now consider the sentence, "If $y = 4,$ every possible integer $x$ satisfies $x^2 < y.$" Is it true?

How about, "If $y = 17,$ every possible integer $x$ satisfies $x^2 < y$" ?

In fact, is there any value to which we can set $y$ so that $\forall x.(x^2<y)$ (that is, so that every possible integer $x$ will satisfy $x^2 < y$)? No, there is not. The statement $\exists y.\forall x.(x^2<y)$ asserts that there is such a value of $y,$ so that statement is false.

Answer 2

The first quantified predicate $\forall x \, \exists y \, (x^2 < y)$ means: "If you pick any real number $x$ and square it, then I can find a real number $y$ that is bigger than it". Indeed, this is true. Given any $x \in \mathbb R$, just take $y = x^2 + 1$.

The second quantified predicate $\exists y \, \forall x \, (x^2 < y)$ means: "I can think of a real number $y$ that is bigger than the square of any real number $x$ that you pick.". Indeed, this is false. Given any $y \in \mathbb R$, if you pick $x = \sqrt{|y|}$, then $x^2 = ||y|| = |y| \geq y$.

---

In general, the order of different types of quantified variables matters because the second variable is allowed to depend on the first. Indeed, the second variable is often a function of the first variable. This concept is very important to understand, particularly when doing $\epsilon$-$\delta$ proofs in real analysis.