Théorie > Fondements > Techniques élémentaires de preuves

Preuve par contraposition

Nous avons vu dans le chapitre sur la logique que la proposition $P \Rightarrow Q$ à laquelle nous nous intéressons est équivalente à $\lnot Q \Rightarrow \lnot P$. Une preuve par contraposition consiste à démontrer que l'on a $\lnot Q \Rightarrow \lnot P$. On utilise cette méthode lorsque l'hypothèse $P$ semble difficile à exploiter ou lorsqu'on ne voit pas comment il sera possible de parvenir à la thèse $Q$.

Exemple : Soit $m \neq 0$ et $f : \mathbb{R} \to \mathbb{R}$ la fonction définie par $f(x) = mx+n$. Montrer que si $x \neq y$, alors $f(x) \neq f(y)$.

Lorsque l'hypothèse ou la thèse contient une négation comme c'est le cas ici ($\neq$ est la négation de $=$), la preuve par contraposition est souvent une option. Pour cet exemple, supposons que l'on a $f(x) = f(y)$ et montrons qu'alors $x = y$. On a
$$mx + n = my+n,$$ d'où
$$m(x-y) = 0$$ et, comme $m \neq 0$, on a $x = y$ comme espéré.