2

In my lecture materials on predicate logic I encountered the following equivalence: $$[ \forall x\left( P\left( x\right) \Rightarrow q\right) ] \Leftrightarrow [ \left( \exists x:P\left( x\right) \right) \Rightarrow q]$$ However, I cannot make sense of it. Why is this equivalence true?

I understand the left part to mean the following: for each $x$, if $P(x)$ is true, then $q$. For example, in this picture $P(x)$ is true for $x_3,x_4,x_6$. For those $x$ it is the case of $q$ and for other $x$ it can be either $q$ or not $q$
enter image description here

I understand the right part to mean the following: if there exists at least one $x$ such that $P(x)$ is true, then $q$. For example, in this picture $P(x)$ is true for $x_4$. Thus, there exist at least one $x:P(x)$ and therefore $q$ must be true everywhere.
enter image description here

Now those two situations are obviously not equivalent, so where is my error?

Zyx
  • 786

2 Answers2

1

Note that $q$ is an independent statement. It does not depend on $x$. So it is either true everywhere or false everywhere, in both cases. That means that your first figure is wrong. Also, $P$ is supposed to be the same in the two statements, so it cannot be true for several $x$ values in one case, and only for $x_4$ in the other.

Here is my interpretation of the equivalence: If there exists an $x_i$ such that $P(x_i)$, then the second statement claims $q$. But in the first statement, when the $\forall x$ quantifier hits $x_i$, we have $P(x_i) \Rightarrow q$. So the first statement also claims $q$.

If there are no $x$ such that $P(x)$, then none of the statements make any claim on the truth value of $q$. Thus they are equivalent.

Arthur
  • 199,419
1

A slightly different way to look at this is to consider two cases:

  1. If $q=T$, then we know that $p\Rightarrow T$ is true no matter what the truth value of $p$ is, so the left side of your equivalence becomes $\forall x(T)$ which of course true. Similarly, the right side of your equivalence is true no matter what the value of $(\exists x P(x))$ is so your expression is $T\Leftrightarrow T$.
  2. If $q=F$ then $P(x)\Rightarrow q$ is logically equivalent to $\neg P(x)$ and your left side becomes $\forall x\ \neg P(x)$. The right side is $(\exists x P(x))\Rightarrow F$, which, as before is equivalent to $\neg(\exists x P(x))$ and this is equivalent to $\forall x\ \neg P(x)$, which is just the left side.
Rick Decker
  • 8,718