3
$\begingroup$

Sorry if this is a really dumb question, but...

After reading How to Prove it, I've become a little confused. On page 70, an example stating something similar to this is provided:

$[\exists x P(x) \land \exists x Q(x)]$ and $\exists x [P(x) \land Q(x)]$ are two different things,

and says that for the first statement, there could be a person that makes p(x) true, and there could be a different person that makes q(x) true.

I thought that if we picked an x value, it would apply across the whole statement? What is the purpose of using different variable names if not?

Thanks in advance!

$\endgroup$
  • $\begingroup$ Read back about bounded variables. The formula on the left can be rewritten as $\exists x P(x) \land \exists y Q(y)$. The $x$ in each of the components in $\exists x P(x) \land \exists x Q(x)$ is bounded. They are possibly different $x$'s. $\endgroup$ – Git Gud Jun 18 '14 at 18:38
4
$\begingroup$

The meaning is that the two formulae are not equivalent.

Let $P(x)$ interpreted as "x is Even" and $Q(x)$ interpreted as "x is Odd".

Clearly, in the domain $\mathbb N$ of natural numbers :

[∃xP(x)∧∃xQ(x)] is true : $2$ is an even number and $1$ is an odd number,

while :

∃x[P(x)∧Q(x)] is false : there is no number which is both even and odd.

In this formula the scope of the quantifier $\exists x$ is the whole formula $[P(x)∧Q(x)]$; thus, when you "pick" an $x$, in order to satisfy the formula it is necessary that for that $x$ both $P$ and $Q$ holds.

In the previous formula, the two quantifiers $\exists x$ have different scope : the first one "acts on" $P(x)$ only and the second one on $Q(x)$. Thus, in order to satisfy the formula, we have the "freedom" to "pick" an $x$ for which $P$ holds and a different one for which $Q$ holds.

$\endgroup$
4
$\begingroup$

The formula $\exists x P(x)$ is a single quantified statement, and the value of $x$ is the same value throughout that statement.

The formula $\exists x Q(x)$ also is a single quantified statement, and the value of $x$ is the same value throughout that statement.

The formula $[\exists x P(x) \land \exists x Q(x)]$ is not a single quantified statement. It is the conjunction of two separate quantified statements. Within each of those statements, whatever value of $x$ is used is the same value for the whole statement.

There is actually no reason to use different variable names in the two parts of the conjunction. On the other hand, we can use different variable names if we like, since the variable in each quantified statement is independent of the other.

In other cases, where one quantifier appears inside another quantified statement, for example, $\exists x [\exists y R(x,y)]$, then it actually does matter that the two variable names are different. But in that case, the $\exists y$ is showing up before the "end" of the statement that started with $\exists x$, so the variable $x$ is still "in use" at that point.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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