Section : Cours
Avant : Relations
Après : Entraînement

Raisonnements

Il ne s'agit pas de proposer ici une théorie du raisonnement mathématique. Nous allons simplement donner quelques exemples de démonstrations, pour illustrer trois types de raisonnements : par contraposée, par l'absurde et par récurrence. Raisonnement par contraposée
Il consiste, plutôt que de démontrer l'implication $ A\Longrightarrow B$, à démontrer sa contraposée $ (\neg B)\Longrightarrow (\neg A)$. Il est difficile de donner une règle générale d'utilisation de ce raisonnement. Un bon conseil avant de se lancer dans la démonstration d'une implication, est d'écrire d'abord sa contraposée. Avec un peu d'expérience, on arrive vite à sentir laquelle des deux est la plus facile à démontrer. Si le résultat désiré est $ B$, on cherche les conséquences de $ \neg B$ pour arriver aux bonnes hypothèses. Notre premier exemple est un résultat facile, mais très utile.

Proposition 9   Soit $ x$ un nombre réel tel que pour tout $ \varepsilon >0$, $ x\leqslant \varepsilon $. Alors $ x\leqslant 0$.

Démonstration : Nous devons démontrer l'implication :

$\displaystyle \Big(\forall \varepsilon >0 \;,\quad x\leqslant \varepsilon \Big) \;\Longrightarrow\; (x\leqslant 0)\;. $

Ecrivons sa contraposée :

$\displaystyle (x>0)\;\Longrightarrow\; \Big(\exists \varepsilon >0 \;;\quad\quad x> \varepsilon \Big)\;. $

«Si $ x$ est strictement positif, alors il existe $ \varepsilon >0$ tel que $ x> \varepsilon $». C'est vrai : il suffit de choisir $ \varepsilon =x/2$.$ \square$

Comme deuxième exemple, nous allons reprendre un des points de la démonstration du théorème 3.

Proposition 10   Soit $ {\cal R}$ une relation d'équivalence sur un ensemble $ E$. Soient $ x$ et $ y$ deux éléments de $ E$ qui ne sont pas reliés. Alors l'intersection des deux classes d'équivalence de $ x$ et $ y$ est vide.

Démonstration : L'implication que nous devons démontrer s'écrit formellement :

$\displaystyle \neg(x{\cal R} y)\;\Longrightarrow (\mathfrak{cl}_{\cal R}(x)\cap \mathfrak{cl}_{\cal R}(y)=\emptyset)\;. $

Sa contraposée est :

$\displaystyle (\mathfrak{cl}_{\cal R}(x)\cap \mathfrak{cl}_{\cal R}(y)\neq \emptyset)\;\Longrightarrow\; (x{\cal R} y)\;. $

Soit $ z$ un élément de $ \mathfrak{cl}_{\cal R}(x)\cap \mathfrak{cl}_{\cal R}(y)$ (il y en a au moins un car l'intersection est non vide. Par définition des classes d'équivalence, $ x$ est relié à $ z$, et $ z$ est relié à $ y$. Par transitivité, $ x$ est relié à $ y$.$ \square$ Raisonnement par l'absurde
Il consiste à démontrer une assertion en vérifiant que sa négation conduit à une contradiction avec les hypothèses. Dans certains cas il se distingue mal du raisonnement par contraposée : si $ A$ désigne la conjonction des hypothèses et $ B$ la conclusion, nier $ B$ et aboutir à une contradiction, revient à démontrer $ \neg A$ à partir de $ \neg B$, ce qui est la contraposée de $ A\Longrightarrow B$. Notre premier exemple est dû à Euclide.

Proposition 11   Il existe une infinité de nombres premiers.

Démonstration : Supposons qu'il n'en existe qu'un nombre fini, et soit $ N$ le plus grand d'entre eux. Considérons le nombre $ P=N!+1$. Il est strictement supérieur à $ N$, donc il n'est pas premier, par définition de $ N$. Si on effectue la division euclidienne de $ P$ par un nombre quelconque entre 2 et $ N$, le reste est $ 1$, par définition de la factorielle (produit de tous les entiers de 1 à $ N$). Donc le nombre $ P$ n'est divisible par aucun nombre entre $ 2$ et $ N$ donc par aucun nombre premier : il est donc premier, d'où la contradiction.$ \square$

Voici un autre résultat classique.

Proposition 12   Le nombre $ \sqrt{2}$ est irrationnel.

Démonstration : Un nombre rationnel est le quotient de deux entiers ; un nombre irrationnel n'est pas rationnel. Nous devons donc démontrer que $ \sqrt{2}$ n'est pas le quotient de deux entiers. Supposons le contraire : il existe deux entiers $ p$ et $ q$ tels que $ \sqrt{2}=p/q$. Quitte à simplifier la fraction, nous pouvons supposer que $ p$ et $ q$ n'ont pas de facteur commun. Multiplions par $ q$ et élevons au carré :

$\displaystyle 2q^2=p^2\;. $

Le nombre $ p^2=2q^2$ est pair, donc $ p$ est également pair. Mais si $ p$ est pair, alors $ p^2$ est multiple de $ 4$. Donc $ q^2$ est multiple de $ 2$, donc $ q$ est pair. Mais alors $ 2$ est un facteur commun à $ p$ et $ q$, ce qui est une contradiction. $ \square$

Pour notre troisième exemple, nous revenons encore une fois sur :

Deux classes d'équivalence sont égales ou bien disjointes.
Comparez la démonstration qui suit avec celle du théorème 3 et de la proposition 10. Démonstration : L'assertion $ A$ est l'hypothèse : $ {\cal R}$ est une relation d'équivalence. L'assertion $ B$ est la conclusion, que l'on peut écrire de manière formelle comme suit.

$\displaystyle \forall x,y\in E\;, \quad (\mathfrak{cl}_{\cal R}(x)=\mathfrak{cl... ...y))\vee (\mathfrak{cl}_{\cal R}(x)\cap \mathfrak{cl}_{\cal R}(y)=\emptyset)\;. $

La négation de $ B$ s'écrit :

$\displaystyle \exists x,y\in E\;,\quad (\mathfrak{cl}_{\cal R}(x)\neq \mathfrak... ...dge (\mathfrak{cl}_{\cal R}(x)\cap \mathfrak{cl}_{\cal R}(y)\neq \emptyset)\;. $

Soit encore : il existe deux éléments $ x$ et $ y$ tels que les classes $ \mathfrak{cl}_{\cal R}(x)$ et $ \mathfrak{cl}_{\cal R}(y)$ ne soient ni égales ni disjointes. Si c'est le cas, il existe un élément $ z$ qui est dans l'une et pas dans l'autre, et un élément $ t$ qui est dans les deux. Supposons que $ z$ soit dans $ \mathfrak{cl}_{\cal R}(x)$, mais pas dans $ \mathfrak{cl}_{\cal R}(y)$. Donc $ x{\cal R} z$, donc $ z{\cal R} x$, car $ {\cal R}$ est symétrique. Mais aussi $ x{\cal R} t$ et $ t{\cal R} y$ car $ t$ appartient aux deux classes de $ x$ et $ y$. Donc puisque $ {\cal R}$ est transitive, $ z{\cal R} y$. Donc $ z$ est dans la classe de $ y$, ce qui est une contradiction.$ \square$

Raisonnement par récurrence
Pour démontrer qu'une assertion $ H(n)$ dépendant d'un entier $ n$ est vraie pour tout $ n\in \mathbb{N}$, on démontre :

  1. $ H(0)$ «initialisation »,
  2. $ \forall n\in\mathbb{N} ,\;H(n)\Longrightarrow H(n+1)$ «hérédité».
L'assertion $ H(n)$ est l'hypothèse de récurrence. Il peut se faire qu'elle ne soit vraie que pour $ n\geqslant 1$ ou $ n\geqslant 2$, auquel cas, on la démontre pour la plus petite valeur pour laquelle elle est vraie. Voici la démonstration d'une formule à connaître :

Proposition 13   Pour tout entier $ n\geqslant 1$, la somme des entiers de 1 à $ n$ vaut $ n(n+1)/2$.

Démonstration : L'hypothèse de récurrence est :

$\displaystyle H(n) :\quad\quad\sum_{k=1}^n k = \frac{n(n+1)}{2}\;. $

  1. Initialisation. Pour $ n=1$ :

    $\displaystyle \sum_{k=1}^1 k = 1=\frac{1(1+1)}{2}\;. $

  2. Hérédité. Soit $ n$ un entier quelconque. Supposons que $ H(n)$ est vraie. Ecrivons :

    $\displaystyle \sum_{k=1}^{n+1} k = \left(\sum_{k=1}^n k\right) +(n+1)\;. $

    En appliquant $ H(n)$, on obtient

    $\displaystyle \left(\sum_{k=1}^n k\right) +(n+1)=\frac{n(n+1)}{2}+(n+1)\;, $

    Le membre de droite s'écrit

    $\displaystyle \frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}\;, $

    Nous avons donc démontré que

    $\displaystyle \sum_{k=1}^{n+1} k =\frac{(n+1)(n+2)}{2}\;, $

    c'est-à-dire que $ H(n+1)$ est vraie.
$ \square$

On peut être amené, pour démontrer $ H(n+1)$ à utiliser $ H(m)$ pour $ m\in\{0,\ldots,n\}$, ce qui ne change rien au principe de la récurrence.

$\displaystyle \forall n\in \mathbb{N} ,\; \Big( (\forall m\in\{0,\ldots,n\}\;,\quad H(m) ) \;\Longrightarrow\; H(n+1)\Big)\;. $

Pour deviner quelle est la bonne hypothèse $ H(n)$, on doit souvent essayer plusieurs valeurs successives de $ n$ : $ n=0$, puis $ n=1$, $ n=2$,...  C'est parfaitement inutile pour la démonstration. Attention, ce n'est pas parce qu'une propriété est vraie pour quelques valeurs de $ n$ qu'elle est vraie pour tout $ n$. Voici deux exemples.
  1. Les nombres $ 31$, $ 331$, $ 3 331$,..., $ 33 333 331$ sont tous premiers. Mais $ 333 333 331=17\times 19 607 843$ ne l'est pas.
  2. Pour toutes les valeurs de $ n$ allant de 0 à $ 39$, le nombre $ n^2+n+41$ est premier. Mais le nombre $ 40^2+40+41=41^2$ ne l'est pas.

Section : Cours
Avant : Relations
Après : Entraînement


         © UJF Grenoble, 2011                              Mentions légales