Preuves par l'absurde et contraposée

1. Le Raisonnement par Contraposée

La preuve par contraposée repose sur une équivalence logique fondamentale que nous avons vue dans nos premières leçons : une implication $p\Rightarrow q$ est logiquement équivalente à sa contraposée, $\neg q\Rightarrow \neg p$.

Plutôt que de prouver directement que $p$ implique $q$, nous pouvons donc choisir de prouver que la non-validité de $q$ implique la non-validité de $p$. Cette voie est souvent plus simple lorsque les hypothèses de départ ($p$) sont plus complexes que les conclusions ($q$).

La structure d'une preuve par contraposée pour démontrer $p\Rightarrow q$ est la suivante :

1. Énoncer clairement que l'on procède par contraposition.
2. Formuler la proposition contraposée : "Supposons $\neg q$".
3. Développer un raisonnement déductif à partir de cette supposition.
4. Aboutir à la conclusion $\neg p$.
5. Conclure que, la contraposée étant vraie, l'implication originale l'est aussi.

Le document ci-dessous, que nous avons déjà croisé, définit cette méthode et l'illustre avec un exemple canonique.

L'exemple que vous venez de lire est un cas d'école. Démontrer directement "si $n^2$ est pair, alors $n$ est pair" est malaisé. Partir de $n^2=2k$ pour en déduire la parité de $n$ impliquerait de manipuler une racine carrée, ce qui complique le raisonnement dans $\mathbb{Z}$. En revanche, la contraposée "si $n$ est impair, alors $n^2$ est impair" est triviale à démontrer par calcul direct.

L'image suivante résume parfaitement cette preuve.

2. Le Raisonnement par l'Absurde

Le raisonnement par l'absurde est une technique encore plus générale. Son principe est le suivant : pour prouver qu'une proposition $P$ est vraie, on suppose qu'elle est fausse (on suppose $\neg P$) et on montre que cette supposition mène inévitablement à une contradiction, c'est-à-dire une affirmation qui est logiquement fausse (par exemple, $A\wedge \neg A$, ou $1=0$). Une telle contradiction étant impossible, l'hypothèse de départ ($\neg P$) doit être fausse, ce qui prouve que $P$ est vraie.

Pour prouver une implication $p\Rightarrow q$ par l'absurde :

1. Énoncer que l'on procède par l'absurde.
2. Supposer les prémisses ($p$) vraies ET la conclusion ($q$) fausse. On suppose donc $p\wedge \neg q$, ce qui est la négation logique de l'implication $p\Rightarrow q$.
3. Développer un raisonnement déductif à partir de ces suppositions.
4. Aboutir à une contradiction flagrante (par exemple, contredire une des hypothèses de départ, un axiome ou un théorème connu).
5. Conclure que l'hypothèse $\neg q$ (en présence de $p$) était intenable et que donc $q$ doit être vraie.

La vidéo suivante décompose ce mécanisme avec une rigueur et une clarté remarquables.

La preuve de l'irrationalité de $\sqrt{2}$ est sans doute l'application la plus célèbre du raisonnement par l'absurde. Elle remonte à l'école pythagoricienne et constitue un moment fondateur des mathématiques.

Le document Cours d'analyse (ressource LINK) présente cette preuve à la page 31 (Exemple 4). Je vous invite à la lire attentivement. Vous y verrez que l'hypothèse "$\sqrt{2}$ est rationnel" mène à la contradiction qu'une fraction irréductible a un numérateur et un dénominateur tous deux pairs.

3. Contraposée ou Absurde ?

Bien que proches, ces deux méthodes ne sont pas identiques.

• La preuve par contraposée est très structurée : vous partez de $\neg q$ avec un objectif clair, qui est de démontrer $\neg p$. C'est une forme de preuve directe de l'implication contraposée.
• La preuve par l'absurde est plus ouverte : vous partez de $p\wedge \neg q$ et votre objectif est de trouver n'importe quelle contradiction. La contradiction peut être $\neg p$, mais aussi la négation d'un axiome, ou toute autre affirmation fausse.

Toute preuve par contraposée peut être réécrite comme une preuve par l'absurde. L'inverse n'est pas toujours vrai. En pratique, on privilégie la contraposée lorsque sa structure (partir de $\neg q$ pour arriver à $\neg p$) semble naturelle. On utilise l'absurde pour des problèmes plus "ouverts", où le chemin n'est pas évident.

Pour illustrer davantage, voici une vidéo qui enchaîne des exemples variés des deux types de preuves.

4. Exercice d'application

Mettons en pratique le raisonnement par l'absurde sur un résultat fondamental de l'arithmétique, dont la preuve est attribuée à Euclide.

Énoncé : Démontrez qu'il existe une infinité de nombres premiers.

Je vous guide pour la structure :

1. Méthode : Raisonnement par l'absurde.
2. Hypothèse à réfuter : Il n'existe pas une infinité de nombres premiers. Autrement dit, l'ensemble des nombres premiers est fini.
3. Mise en place : Si cet ensemble est fini, on peut lister tous les nombres premiers : $p_1,p_2,\dots ,p_n$, où $p_n$ est le plus grand de tous les nombres premiers.
4. Votre tâche : Construisez un nouvel entier à partir de tous ces nombres premiers. Montrez ensuite que ce nouvel entier mène à une contradiction. Quelle est cette contradiction ?

Prenez quelques minutes pour y réfléchir avant de lire la solution ci-dessous.

Conclusion

Aujourd'hui, nous avons exploré deux méthodes de preuve indirecte qui sont des piliers du raisonnement mathématique.

Points clés à retenir :

• La preuve par contraposée démontre $p\Rightarrow q$ en prouvant directement $\neg q\Rightarrow \neg p$. C'est un outil de choix lorsque $\neg q$ est une hypothèse de départ plus simple à manipuler que $p$.
• La preuve par l'absurde démontre $P$ en supposant $\neg P$ et en dérivant une contradiction. C'est une méthode puissante et générale, particulièrement utile pour les énoncés d'existence ou d'infinité.
• La rigueur exige de toujours annoncer la méthode de preuve utilisée et de poser clairement les hypothèses initiales avant de commencer le raisonnement.

Ces techniques sont transversales et vous seront utiles dans tous les domaines de l'informatique fondamentale. Dans notre prochaine leçon, nous aborderons une autre technique de preuve essentielle, spécifiquement adaptée aux structures discrètes et aux algorithmes : la preuve par récurrence simple.