$\exists x P(x)\land\exists x Q(x)$ is not logically equivalent to $\exists x(P(x)\land Q(x) )$

10.1k Views Asked by At

The textbook states that the solution is:

Let P(x) be "x is positive" and Q(x) is "x is negative". The domain is integers.

This shows $\exists x P(x)\land\exists x Q(x)$ is True and shows $\exists x(P(x)\land Q(x) )$ is False.

I take this to mean that $\exists x P(x)\land\exists x Q(x)$ is translated into English as "There exist positive integers and there exist negative integers", which is obviously true.

I think that $\exists x(P(x)\land Q(x) )$ means "There exists an integer that is positive and negative" which is False.

Does all this mean what I think it means?

1

There are 1 best solutions below

0
On

You're absolutely right, and the comments to your question are probably more interesting than my answer. Still, I'd like to make the point of scopes.

The scope of a logical connective corresponds to the statements that it connects.

For instance, in $A\lor B$, it should be clear to you that both $A$ and $B$ are in the scope of $\lor$: that's how you evaluate it. Scopes become your first priority as soon as the proposition is a bit more complex. Take $A\lor B\land C$ for example. As you know, this is not a well-formed formula of sentential logic. However, adding parentheses helps you decide whether $(A\lor B)\land C$ or $A\lor(B\land C)$ is meant: the scopes of both connectives are then well-defined.

The same rules apply to quantifiers, both existential and universal.

As you correctly pointed out, it's easy to understand through a simple example how $\exists x Px\land\exists xQx$ and $\exists x(Px\land Qx)$ differ. In the second case, the scope of the existential quantifier is extended to the inside of the brackets: both the $x$ in $Px$ and $Qx$ refer to the same variable $x$, instantiated by the existential quantifier.

On the contrary, in the first case, the scopes of the existential quantifiers are limited by the conjunction, i.e.: $$(\exists x\underbrace{Px}_{\text{scope 1}})\land(\exists x\underbrace{Qx}_{\text{scope 2}})$$ which could as well be rewritten with a new variable to avoid confusion: $$\exists xPx\land\exists yQy$$ To go even further, this is equivalent to: $$\exists x\exists y(Px\land Qy)$$ (This is referred to as Prenex Notation).