1
$\begingroup$

I am working through a problem on implications, and I have confused myself. I wish to state the contrapositive of:

$$\forall n\in \mathbb{Z}, \exists k \in \mathbb{N}, \ n \mid 12k+5 \wedge n \mid 18k+1 \implies n=17$$

My issue is with the nested quantifiers. Does the existential quantifier belong to the hypothesis, and therefore the contrapositive is:

$$\forall n\in \mathbb{Z}, n \ne 17 \implies \forall k \in \mathbb{N}, n \nmid 12k+5 \vee n \nmid 18k+1$$

Alternatively, if the existential quantifier does not belong to the hypothesis, then the contrapositive should be:

$$\forall n\in \mathbb{Z}, \exists k\in \mathbb{N}, \ n \ne 17 \implies n \nmid 12k+5 \wedge n \nmid 18k+1$$

These are two VERY different statements, and both might be the wrong one. What is the right answer here, and why?

$\endgroup$
2
  • $\begingroup$ I know the contrapositive of a conditional $P \to Q$ is $\neg Q \to \neg P$. But I have never seen the contrapositive defined for a quantificational statement. Were you given a definition for that? $\endgroup$
    – Bram28
    Oct 5 '20 at 14:08
  • $\begingroup$ See Prenex Normal Form: $\forall n \exists k (\phi(n,k) \to \psi (n))$ is equivalent to : $\forall n [\forall k \phi(n,k) \to \psi (n)]$ $\endgroup$ Oct 5 '20 at 14:12
1
$\begingroup$

The logical form of your first statement is

$$\tag{1} \forall n \in \mathbb{Z} \, \exists k \in \mathbb{N} ((n \mid 12k+5 \wedge n \mid 18k+1) \implies n=17)$$

The contrapositive of such a formula (obtained by reversing the arrow and negating its antecedent and consequent) is

$$\tag{2}\forall n \in \mathbb{Z} \, \exists k \in \mathbb{N} (n \neq 17 \implies (n\not \mid 12k+5 \lor n \not\mid 18k+1))$$

which is logically equivalent to

$$\tag{3}\forall n \in \mathbb{Z} (n \neq 17 \implies \exists k \in \mathbb{N} (n\not \mid 12k+5 \lor n \not\mid 18k+1))$$

Note that both your proposals for the contrapositive are wrong, because they are not logically equivalent to $(2)$ or $(3)$. In your last formula you use $\land$ instead of $\lor$, and in your previous formula you use $\forall$ instead of $\exists$.


Another way to see this is considering the following formula, which is logically equivalent to $(1)$

$$\forall n \in \mathbb{Z} (\forall k \in \mathbb{N} (n \mid 12k+5 \wedge n \mid 18k+1) \implies n=17)$$

The contrapositive of such a formula (obtained by reversing the arrow and negating its antecedent and consequent) is exactly $(3)$.


The logical equivalences used above are: \begin{align} P \to Q &\equiv \lnot Q \to \lnot P &&\text{(contrapositive)} \\ \lnot (P \land Q) &\equiv \lnot P \lor \lnot Q &&\text{(De Morgan)} \\ \exists x (P \to Q) &\equiv (\forall x P) \to Q &&\text{(contravariance of the antecedent)} \\ \exists x (Q \to P) &\equiv Q \to (\exists x P) &&\text{(covariance of the consequent)} \end{align} where, in the last two equivalences, $x$ does not occur free in $Q$.

$\endgroup$

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.