Nested Quantifiers and Infinite Sets

Question

Consider the following Nested Quantifiers:

$\exists x \forall y$ $(x > y)$

where the domain $U$ is a subset of $\mathbb{N}$

If I translate this into english,

There is an $x$, where $x > y$ is true for all $y$.

1. If the set is infinite, then can we possibly conclude that the statement is true?

Since there is always going to be a value $x = y + 1$, but I am confused because the same can be said of the values of $y$. Is there a specific property to consider when dealing with infinite sets? I would love to get some insight as to the general considerations when given an infinite set.

2. Can we use the same element twice to evaluate the truth values?

For example, if the subset was finite and defined by the interval [0, 100].

If $x = 100$ and $y = 100$ then the statement would be evaluated as false as $x$ is not greater than $y$. However, if I am not allowed to set the value of $y$ and $x$ the same, then that statement would be true since I could set $x = 100$ and $y=\{0,...,99\}$. Can we use the same elements twice when evaluating the truth value?

Thanks!

Answer 1

To respond to your first question, the statement certainly isn't true for infinite $U$. You're right that every $y$ has an $x$ that's bigger than it, but the statement requires a single $x$ that's bigger than every $y$. This actually can't be true for any non-empty set of natural numbers, because of the answer to your second question: yes, you can pick the same witness twice. If there were an $x$ that satisfied your formula, it would have to be bigger than everything in the set, not just everything else; in particular, it would have to be bigger than itself.

As for the question you asked in between - "general considerations" when given an infinite set - the major thing to remember is that it's not any different. The rules still work in exactly the same way; with this problem, the difficulty was in the order of quantification, not the size of the sets involved.

Answer 2

One way to make sense of nested quantifiers is to interpret a sentence that contains them as a game between two players.

Player $\exists$ chooses the values of the existentially quantified variables, while Player $\forall$ chooses the values of the universally quantified variables. The choices are made in the order in which the quantifiers appear in the sentence. In case of $\exists x \forall y (x > y)$, $x$ is chosen before $y$. If $(x > y)$ turns out to be true, Player $\exists$ wins, and otherwise Player $\forall$ wins.

The quantified sentence is true if Player $\exists$ has a strategy to win the game no matter how Player $\forall$ chooses the values of the universally quantified variables. Otherwise, the sentence is false.

In our case, regardless of whether the domain is finite or infinite, Player $\forall$ wins by the "copycat strategy," which consists of choosing the same value for $y$ that was chosen for $x$.

If the order of the quantifiers is reversed, as in $\forall y \exists x (x > y)$, the outcome depends on whether the domain contains a maximum element. If it does, Player $\forall$ wins by choosing it. Otherwise, Player $\exists$ wins by adopting the "one-up" strategy.

To summarize, the key points are that the order of the quantifiers matters and choosing the same value for more than one variable is perfectly OK. Going last is typically advantageous, though, as we have seen, it does not always guarantee victory.