Existential quantifier before/after the implication sign gives different contrapositives.

Question

Notice that the existential quantifier for p is after the implication in the first statement, while it is before the implication in the second statement. And if you take the contrapositive for both those statements, in the first statement, the existential quantifier is negated to the universal quantifier. However, in the second statement, we can keep it as it is, as to not include it in our implication statement.

Since the contrapositives of the two statements are different, it seems to me that the original two statements are also different. However, when I try to explain the original two statements in plain English, I find myself uttering just the same sentences for both. Apparently it seems to me that I am making some logical mistake in my thinking process. Any help in identifying my mistake is appreciated.

Answer 1

Not correct: if $x$ is not free [free means: not quantified] in $\alpha$, then:

$(\alpha \to \exists x \beta) \leftrightarrow \exists x (\alpha \to \beta)$.

In your case $p$ is the $x$ and it is not free, simply because it does not occur at all, in $\forall n ( \text {Comp}(n) \to \ldots)$.

You have to take care about the "contrapositive: the first one will be:

$\forall n (\forall p \lnot R(n,p) \to \lnot \text {Comp}(n))$

and the second one will be:

$\forall n \exists p (\lnot R(n,p) \to \lnot \text {Comp}(n))$.

But we have also that, if $x$ is not free in $\alpha$:

$(\forall x \beta \to \alpha) \leftrightarrow \exists x (\beta \to \alpha)$.

Thus, the two "contraposed" versions are equivalent, and this is consistent with the fact that also the two original formulas are.

---

Intuitively, $\exists$ acts as a (potentially infinite) disjunction: $\exists n (n = 0)$ means: $(0 = 0) \lor (1 = 0) \lor (2 = 0) \lor \ldots$

This fact explains, intuitively again, why $\exists$ freely "distribute" over $\lor$; i.e. $\exists x (\alpha \lor \beta) \equiv (\exists x \alpha \lor \exists x \beta)$.

Thus, usig the equivalence between $p \to q$ and $\lnot p \lor q$, we can rewrite: $\exists x (\alpha \to \beta)$ as follows:

$\exists x (\lnot \alpha \lor \beta)$.

Now we can "distribute" the leading quantifier, getting:

$\exists x \lnot \alpha \lor \exists x \beta$.

But if $x$ does not occur free in $\alpha$ (for simplicity, we can assume that it does not occur at all) we have that $\exists x \lnot \alpha$ has the same meaning of $\lnot \alpha$, and thus we have again the new equivalent formula:

$\lnot \alpha \lor \exists x \beta$,

and finally, restoring $\to$:

$\alpha \to \exists x \beta$.