Quantificateurs imbriqués dans une implication et sa contrapositive

Question

Je travaille sur un problème sur les implications, et je me suis confondu. Je souhaite énoncer le contrapositif de:

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

Mon problème concerne les quantificateurs imbriqués. Le quantificateur existentiel appartient-il à l'hypothèse, et donc le contrapositif est:

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

Alternativement, si le quantificateur existentiel n'appartient pas à l'hypothèse, alors le contrapositif devrait être:

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

Ce sont deux déclarations TRÈS différentes, et les deux peuvent être la mauvaise. Quelle est la bonne réponse ici et pourquoi?

Answer 1

La forme logique de votre première déclaration est

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

La contrapositive d'une telle formule (obtenue en inversant la flèche et en annulant son antécédent et conséquent) est

$$\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))$$

qui est logiquement équivalent à

$$\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))$$

Notez que vos deux propositions pour le contrapositif sont fausses, car elles ne sont pas logiquement équivalentes à $(2)$ ou $(3)$. Dans votre dernière formule que vous utilisez$\land$ au lieu de $\lor$, et dans votre formule précédente, vous utilisez $\forall$ au lieu de $\exists$.

---

Une autre façon de voir cela consiste à considérer la formule suivante, qui est logiquement équivalente à $(1)$

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

Le contrapositif d'une telle formule (obtenu en inversant la flèche et en niant son antécédent et son conséquent) est exactement $(3)$.

---

Les équivalences logiques utilisées ci-dessus sont: \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} où, dans les deux dernières équivalences, $x$ ne se produit pas gratuitement dans $Q$.