# logic: order of quantifier with free variables

Take the sentence, "You can't win them all."

This could be logically written as
"For all people, there exists a thing they cannot win at."
$\forall x.\exists y.(\neg win(x,y))$

Now suppose I was lazy and left the x unbound, as in:
$\exists y.(\neg win(x,y))$

Is this equivalent to the previous sentence, or is it interpreted as the different sentence: $\exists y.\forall x.(\neg win(x,y))$
which would mean, "there exists a thing that all people cannot win at?"

In other words, when there are unbound variables, in what order do you put the quantifiers?

• If a variable is unbound, you don't have any quantifier to attribute to the variable, by definition of unbound. The formula $\exists y(\neg \text{win}(x,y))$ is not a statement, A statement, by definition, can't have unbound variables. May 22, 2016 at 19:27
• When there are free variables, they're never implicitly quantified inside existing quantifiers. The formula, with free variables, is implicitly universally quantified. If you were lazy and omitted $\forall x$, people reading the formula $F(x) := \exists y \neg win(x,y)$ would either not know what it means or would think it means $\forall x F(x)$. May 22, 2016 at 22:02
• The interpretation of free variables depends on your logic. Usually, it is the same as universally quantifying over every formula containing the free variable (or equivalently, universally quantifying over every formula in discourse). So $\exists y ~ P(x, y)$ is only the same (in some logics) as $\forall x ~\exists y~ P(x, y)$ if there are no other formulas anywhere containing $x$. May 24, 2016 at 0:26
• @GitGud: By definition, yes a sentence (in first-order logic) cannot have free variables. But most mathematicians don't write sentences. When people write "$(A+B)^2 = A^2 + 2AB + B^2$" there is an implicit quantification, even though I disapprove of leaving out the quantifier, for the reason that it is always restricted. What if $A,B$ are matrices? May 24, 2016 at 4:00

To expand on DanielV's comment, consider that:

1. It is true that $\neg win(x,death) \vdash \exists y\ ( \neg win(x,y) )$.

2. It is false that $\neg win(x,death) \vdash \forall x\ \exists y\ ( \neg win(x,y) )$.

3. If $T \vdash \exists y\ ( \neg win(x,y) )$ and $x$ is not free in any formula in $T$, then $T \vdash \forall x\ \exists y\ ( \neg win(x,y) )$.

Also note that your example is not translated correctly. Unless every thing is a person, you ought to write:

$\forall x \in people\ ( \exists y \in things\ ( \neg winat(x,y) ) )$.

• This answer uses the convention of implicit universal quantification, which is the standard convention in most presentations of first-order logic that permit derivation of formulae with free variables. Other formalizations might not. May 24, 2016 at 3:51
• Thanks for the suggestion. I see why the set notation improves it. So is it assumed that all variables in a logical statement (not necessarily a sentence) must represent the same kind of thing? May 24, 2016 at 17:45
• @jimboweb: Unrestricted quantifiers always range over all objects in the universe. That's rarely what we want, and so either you use restricted quantifiers as I have done or you use additional predicates. The reason I don't use predicates is that natural language reasoning is often better represented by using restricted quantifiers. We say "Everyone here knows what happened." and certainly not "For every thing, if it is a person here then he/she knows what happened.". May 25, 2016 at 2:23

If $\varphi[x]$ is the formula $\exists y(\neg W(x,y))$, introducing a quantifier to bind the free variables of the formula would produce $\forall x\varphi$, which is just $\forall x\exists y(\neg W(x,y))$.

Take the sentence, "You can't win them all." This could be logically written as

"For all people, there exists a thing they cannot win at."
$$\forall x.\exists y.(\neg win(x,y))$$

Better would be:

$$\forall x: [Person(x) \implies \exists y:[Game (y)\land \neg Win(x,y)]]$$

where $$Person(x)$$ means $$x$$ is a person, and $$Game(y)$$ means $$y$$ is a game.

Now suppose I was lazy and left the x unbound, as in:
$$\exists y.(\neg win(x,y))$$

This would probably be interpreted as talking about a single person: There exists a game which person $$x$$ does not win.

Note that

$$\exists y:[Game (y)\land \forall x:[Person(x) \implies\neg Win(x,y)]]$$

suggests that there exists at least one game which everyone loses.

• Thanks for the suggestion. I was under the impression that the general convention holds that later letters in the alphabet (u, v, w...) represent variables, while earlier letters or numbers represent constants. May 24, 2016 at 17:42
• "This would probably be interpreted as talking about a single person." I have seen many sources where a free variable is implicitly existentially quantified. I think our conceptualization of things like numbers leads to that. But I would suggest that $P(x) \implies Q(x)$ is better interpreted as "Every $x$ with property $P$ has property $Q$" rather than as "there is an $x$ such that...". May 24, 2016 at 22:19