logic: order of quantifier with free variables

486 Views Asked by At

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?

3

There are 3 best solutions below

3
On BEST ANSWER

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) ) )$.

0
On

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))$.

2
On

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.