Different Quantifiers, same variable

174 Views Asked by At

A silly example:

$\exists x (P (x, x)) \leftrightarrow \exists x\forall x (P (x, x))$

Intuition tells me that, because we're dealing with the same variable, the Exists on the right side is of no importance, so that side of the equation would be equivalent to $\forall x (P (x, x))$.

Now, concerning the final result, does the existence of an x that satisfies P implies that all x do? If so, why?

2

There are 2 best solutions below

0
On

"$\exists x \forall x(P(x, x))$" is not a well-formed formula - you're not allowed to overload variables like this, precisely because it leads to ambiguity.

0
On

Although confusing, the nested quantifiers are well formed.   The inner most quantifier binds all occurrences of the entity $x$ within its scope, leaving none free to be bound by the outermost quantifier.

For clarity, the tokens in the statement $\exists x \big(P (x, x)\big) \leftrightarrow \exists x\forall x \big(P (x, x)\big)$ can be alpha-replaced as:

$$\exists x \big(P (x, x)\big) \leftrightarrow \exists y\forall z \big(P (z, z)\big)$$

As you intuited, $\exists y\forall z \big(P (z, z)\big)$ is equivalent to $\forall z\big(P(z,z)\big)$ (if in an unempty domain).   Because iff $\forall z\big(P(z,z)\big)$ is true any $y$ will make it true, and iff $\forall z\big(P(z,z)\big)$ is false, no $y$ can make it true.

So the statement does indeed say, the existence of any entity which satisfies the predicate is equivalent to all entities doing so.

$$\exists x \big(P (x, x)\big) \leftrightarrow \forall x \big(P (x, x)\big)$$

This is equivalent to:

$$\forall x \big(\neg P (x, x)\big) \vee \forall x \big(P (x, x)\big)$$