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?

  • $\begingroup$ But they are ... $\endgroup$ – Hagen von Eitzen Apr 15 at 16:41
  • $\begingroup$ @Hagen von Eitzen the two statements are intuitively equivalent to you? Can you explain how if possible $\endgroup$ – David Warren Katz Apr 15 at 16:42
  • $\begingroup$ "If I have completed all of my tasks, I can go home" is the same as "There is a task (namely the last one I complete) such that if that task is completed, I can go home". The only "trap" is perhaps that it may not be clear beforehand, which task it is. In my example, if my tasks are 1) to order new pencils and 2) to read a report, I can neither say (equivalently to the first staement) "When I have ordered the pencils, I can go home" nor "When I have read the report, I can go home" (though I can say one of these after the other task has been completed). (cont'd) $\endgroup$ – Hagen von Eitzen Apr 15 at 16:52
  • $\begingroup$ (cont) But note that I expressly used "when" instead of "if" to express a temporal development. This just makes it clear that perhaps one often intuitively understands "if" in real life also to have at least some temporal, or in fact even causal connotation. $\endgroup$ – Hagen von Eitzen Apr 15 at 16:54
  • $\begingroup$ It may be worth noting that this statement is not constructively valid. (The right to left entailment is though.) In my experience, most of the classical tautologies that people find non-intuitive are not constructively valid. (The principle of explosion is perhaps the best example of a constructively valid law that people find non-intuitive.) $\endgroup$ – Derek Elkins Apr 15 at 18:29

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.

  • $\begingroup$ I strongly dislike describing $\forall$/$\exists$ as a "kind of conjunction/disjunction". This "intuition" doesn't generalize to non-classical contexts, and even in a classical context it takes some care to state it in a way that isn't misleadingly incorrect (as opposed to just technically incorrect). $\endgroup$ – Derek Elkins Apr 15 at 20:18

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.