Nonintuitve logical equivalence in the predicate calculus

57 Views Asked by At

In the first order predicate calculus as usually constructed the formula $ ((\forall x Ax) \implies B ) $ is logically equivalent to $( \exists x(Ax \implies B))$.

It is not clear to me why these two statements would be equivalent. For example, if Ax is interpreted as 'person x does a good thing' and B is 'a good thing has been done', then the statements "If everyone does a good thing then a good thing has been done' is equivalent to 'there exists a person such that if that person does a good thing then a good thing has been done'. However, these two statement are intuitively not equivalent.

Any ideas on why the predicate calculus should be constructed this way?

1

There are 1 best solutions below

1
On BEST ANSWER

First, we can make a semi-formal argument for their equivalence as follows:

Any universal can be seen as kind of conjunction, that is, if $a,b,c,...$ denote the objects in your domain, then you can think of a universal like this:

$$\forall x \: P(x) \approx P(a) \land P(b) \land P(c) \land ...$$

Likewise, an existential statement is a kind of disjunction:

$$\exists x \: P(x) \approx P(a) \lor P(b) \lor P(c) \lor ...$$

OK, so now:

$\forall x A(x) \to B \approx$

$(P(a) \land P(b) \land P(c) \land ...) \to B \Leftrightarrow$

$\neg (P(a) \land P(b) \land P(c) \land ...) \lor B \Leftrightarrow$

$\neg P(a) \lor \neg P(b) \lor \neg P(c) \lor ... \lor B \Leftrightarrow$

$(\neg P(a) \lor B) \lor (P(b) \lor B) \lor (\neg P(c) \lor B) \lor ... \Leftrightarrow$

$(P(a) \to B) \lor (P(b) \to B) \lor (P(c) \to B) \lor ... \approx$

$\exists x (P(x) \to B)$

Hmm ... ok, but does that make it more intuitive? Not clear. OK, consider this more semantical argument:

Note that $\exists x (A(x) \to B)$ would be true as soon as there is anything that does not have property $A$. For example, say object $c$ does not have property $P$. Then $A(c)$ is false .. but that means that $A(c) \to B)$ is true! And, as such, it is true that $\exists x (A(x) \to B)$ is true. OK ... but what if there is no object lacking property $A$, i.e. what if everything has property $A$? How can $\exists x (A(x) \to B)$ still be true? It must be because $B$ holds. In other words, the only way for $\exists x (A(x) \to B)$ to be false is if everything has property $A$, but $B$ does not hold. But note, that describes exactly the situation that would make $\forall x A(x) \to B$ false. So, the two are equivalent.

So note that the equivalence (whether we showed it semi-formally, or whether we used a more semantical approach) really hinges on the equivalence of $P \to Q$ and $\neg P \lor Q$ ... and that is actually not always very intuitive. Indeed, see the Paradoxes of Material Implication to read about the difficulties of trying to capture English 'if ... then ..' statements with the material implication. So, if the equivalence between $\forall x A(x) \to B$ and $\exists x (P(x) \to B)$ still feels unintuitive, then I would guess that what's behind that is the nature of the material implication, and how that does not quite capture the English conditional, rather than that there is something about the quantifiers that makes this unintuitive.