4
$\begingroup$

Good mornig to all of you. If I have a formula like $( \exists x ) ( P(x) ) \land ( \exists x ) ( Q(x) )$ this means that $x$ is the same? I try to be more clear with an exemple. If I have $\exists x ( x-2=0)$, this is true since $x =2$ satisfies $x-2=0$. If I have $\exists x (x-3=0)$, this is true because $x=3$ satisfies $x-3=0$. But what if I have $\exists x (x-2=0) \land \exists x (x-3=0)$. Is $x$ the same? Can I choose if $x$ is the same or not? Is $\exists x (x-2=0) \land \exists x (x-3=0)$ true or false? Beacause if $x$ has to be the same, then it is false. Thanks.

$\endgroup$
3
  • 2
    $\begingroup$ As they are quantifiers for different statements, they can be different $x$'s $\endgroup$ – Adam Karlson May 10 at 13:06
  • $\begingroup$ @Adam Karlson So the variables can have the same name but I have to think them as two different variables? This means that $\exists x (x-2=0) \land \exists x (x-3=0)$ is true? $\endgroup$ – rookie_of_math May 10 at 13:22
  • $\begingroup$ @rookie_of_math Yes, $(\exists x)(x - 2 = 0) \land (\exists x)(x - 3 = 0)$ is true. $\endgroup$ – frabala May 10 at 14:05
4
$\begingroup$

The issue here is one of scope: parts of a formula where variables refer to the same thing. Scope also shows up in computer science where we can reuse variable names in different subroutines: the same letter refers to something completely different in those different subroutines, and is treated as if it had a completely different letter.

In a formula like $\exists x: (x-2=0) \wedge \exists x: (x-3=0)$ there are two separate variables referred to as $x$. Their scopes are: $$\exists x: \underbrace{(x-2=0)}_\text{scope of first} \wedge \exists x: \underbrace{(x-3=0)}_\text{scope of second}$$

We can associate a variable that isn't free with its quantifier, and each separate quantifier gives a different scope. In order to determine which quantifier a variable goes with, work your way up the parse tree of the formula until you hit a quantifier. If the variable is free its scope is the entire formula*.

*Unless the variable is quantified over within the formula.

$\endgroup$
2
$\begingroup$

They are different variables which just happen to have the same name. The sentence is equivalent to $(\exists x)(x - 2 = 0) \land (\exists y)(y - 3 = 0)$.

If you would want to denote the same variable, you would have to use only one quantifier like so: $$ (\exists x)(x - 2 = 0 \land x - 3 = 0).$$

Note that in this sentence you cannot rename the one of the two occurrences of $x$, while in the previous case you could.


Edit after comment from rookie_of_math:

It is only a coincidence that the two formulas with $\lor$ are "compatible". Still, they are different:

  • In the first case, you can choose two different numbers, test if the 1st number satisfies the first formula, then test if the 2nd number satisfies the 2nd formula.
  • In the second case, you can only choose one number and test it with the 1st and the 2nd formula.

To make the distinction clearer, the solutions to the first formula are:

  • $x = 2$ and $y$ any number
  • $y = 3$ and $x$ any number
  • $x = 2$ and $y = 3$

The solutions for the second formula (with one quantifier) are:

  • $x = 2$
  • $x = 3$

In general, using two quantifiers is different from using one, as the example with $\land$ illustrates better. The question is "What do you want to express?". If you want to talk about only one entity/number, then you should use only one quantifier. If you want to talk about two entities, then you use two quantifiers.

$\endgroup$
3
  • $\begingroup$ OK but I think I'm a little bit confused. I try to explain. If I have $\exists x (x-2=0) \lor \exists x (x-3=0)$, I have a similar formula, I just changed $\land$ with $\lor$, so again I can say that it is equivalent to $\exists x (x-2=0) \lor \exists y (y-3=0)$, like you did. But I know that in this case I can write $\exists x (x-2=0 \lor x-3=0)$. So how is it possible? How are these formuals in this case (the case $\lor$) compatibale each other? $\endgroup$ – rookie_of_math May 10 at 13:40
  • $\begingroup$ @rookie_of_math I've edited my answer. Note that in the formula $(\exists x)(x - 2 = 0 \lor x - 3 = 0)$, again you cannot rename the second occurrence of $x$, just like in the example with $\land$. $\endgroup$ – frabala May 10 at 14:09
  • 1
    $\begingroup$ It may also worth noticing that, analogously, $\forall x(x\geq0)\wedge\forall x(x\leq0)$ and $\forall x(x\geq0\wedge x\leq0)$ are equivalent (indeed, both are flase), while $\forall x(x\geq0)\vee\forall x(x\leq0)$ and $\forall x(x\geq0\vee x\leq0)$ are not equivalent (indeed, the first is false, but the second is true, at least for the real numbers in classical logic). So by the basic principles of how quantifiers work, these are all different, but then some theorems of logic come in to tell us that some of them are nevertheless equivalent. $\endgroup$ – Toby Bartels May 10 at 14:59
2
$\begingroup$

The parentheses after the quantifier indicate the scope of the quantifier: within that scope, all references to the variable being quantified refer to the same object. Outside that scope you can reuse that variable, but it can denote something different.

The same is going on in English expressions, if you think about it. Consider: "Something is big, and something is blue". Sure, I use the very same word "something" twice, but clearly the first "something" can refer to a different something than the second "something"

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.