Raisonnement et Démonstration

Le progrès mathématique a toujours été guidé par les méthodes formelles de la démonstration. Alors que la science s'appuie souvent sur des preuves expérimentales, les mathématiques sont construites sur la certitude de déductions logiques à partir d'hypothèses clairement énoncées. Une démonstration mathématique est un argument rigoureux qui établit la vérité d'un énoncé à partir d'axiomes admis et de résultats déjà démontrés. Elle commence par des suppositions appelées hypothèses, se poursuit par une séquence d'étapes logiques justifiées, et aboutit à une conclusion. Ce chapitre présente le langage fondamental de la logique mathématique et explore les principales méthodes de démonstration requises dans ce cours.

Connecteurs Logiques et Propositions

Proposition

Définition Proposition et Valeur de Vérité

Une proposition est un énoncé qui peut être soit vrai, soit faux, mais pas les deux. On note souvent les propositions par des lettres telles que $p$, $q$ et $r$.

Note

Sauf indication contraire, toute proposition ou tout théorème présenté dans un texte mathématique est affirmé comme étant vrai. Le but d'une démonstration est de justifier cette vérité.

Exemple

$p$ : « Le nombre 9 est un nombre premier. » (Faux)
$q$ : « 3 est un diviseur de 12. » (Vrai)

Négation

Définition Négation

La négation d'une proposition $p$, notée $\neg p$, est la proposition « non $p$ ». La valeur de vérité de $\neg p$ est l'opposé de la valeur de vérité de $p$.

Exemple

$p$ : « L’entier $4$ est un nombre pair. » (Vrai)
$\neg p$ : « L’entier $4$ n’est pas un nombre pair. » (Faux)

Propositions composées

Définition Conjonction

La conjonction de $p$ et $q$, notée $\boldsymbol{p \wedge q}$, est la proposition « $p$ et $q$ ». Elle est vraie seulement si $p$ et $q$ sont toutes les deux vraies.

Exemple

Soit $p$ : « $n$ est un multiple de $2$ » et $q$ : « $n$ est un multiple de $3$ ».
La conjonction $p \wedge q$ est « $n$ est un multiple de $2$ et $n$ est un multiple de $3$ »,ce qui signifie que $n$ est un multiple à la fois de $2$ et de $3$ (par exemple, $n = 6, 12, 18, \dots$).

Définition Disjonction

La disjonction de $p$ et $q$, notée $\boldsymbol{p \vee q}$, est la proposition « $p$ ou $q$ ». Elle est vraie si au moins l'une des deux est vraie. C'est un ou inclusif.

Exemple

Soit $p$ : « $n$ est un multiple de 2 » et $q$ : « $n$ est un multiple de 3 ».
La disjonction $p \vee q$ est vraie si $n$ est un multiple de 2, ou un multiple de 3, ou les deux (par exemple pour $n=2, 3, 4, 6, 8, 9, \dots$).

Proposition Lois de De Morgan

La négation d'une conjonction ou d'une disjonction suit un schéma spécifique connu sous le nom de lois de De Morgan.

Négation d'une conjonction : $\boldsymbol{\neg(p \wedge q) \Leftrightarrow (\neg p \vee \neg q)}$
Pour nier un énoncé « et », on nie chaque partie et on remplace le « et » par « ou ».
Négation d'une disjonction : $\boldsymbol{\neg(p \vee q) \Leftrightarrow (\neg p \wedge \neg q)}$
Pour nier un énoncé « ou », on nie chaque partie et on remplace le « ou » par « et ».

Exemple

Trouver la négation de l'énoncé « $x \le 1$ ou $x > 4$ ».

Correction

Soit $p$ l'énoncé « $x \le 1$ » et $q$ l'énoncé « $x > 4$ ». L'énoncé est une disjonction, $p \vee q$. Nous utilisons la deuxième loi de De Morgan : $\neg(p \vee q) \Leftrightarrow (\neg p \wedge \neg q)$.D'abord, nous trouvons la négation de chaque partie :

La négation de $p : x \le 1$ est $\neg p : x > 1$.
La négation de $q : x > 4$ est $\neg q : x \le 4$.

Maintenant, nous les combinons avec un « et » :$$ (\neg p \wedge \neg q) \text{ est } (x > 1) \wedge (x \le 4). $$Ceci peut s'écrire plus simplement comme l'intervalle $\boldsymbol{1 < x \le 4}$.

Implication et équivalence

L’implication formalise la déduction : de $p$ on déduit $q$. Si $p\Rightarrow q$ et $p$ est vraie, alors $q$ doit être vraie.

Définition Implication

Une implication, notée $\boldsymbol{p \Rightarrow q}$, est la proposition « si $p$, alors $q$ ». Elle est fausse uniquement lorsque $p$ est vraie et $q$ est fausse.

Définition Réciproque/Inverse/Contraposée

Pour l'implication $p \Rightarrow q$ :

La réciproque est $q \Rightarrow p$.
La contraposée est $\neg q \Rightarrow \neg p$.
L'inverse est $\neg p \Rightarrow \neg q$.

Exemple

« Si $x=1$ alors $x^2=1$ » est vraie. Sa réciproque « Si $x^2=1$ alors $x=1$ » est fausse (car $x=-1$ convient aussi).

Définition Équivalence

Une équivalence, notée $\boldsymbol{p \Leftrightarrow q}$, est la proposition « $p$ si et seulement si $q$ ». Elle est vraie seulement lorsque $p$ et $q$ ont la même valeur de vérité. C'est la conjonction d'une implication et de sa réciproque : $(p \Rightarrow q) \wedge (q \Rightarrow p)$.

Proposition Équivalence avec la contraposée

Une implication et sa contraposée sont logiquement équivalentes : $\boldsymbol{(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)}$.

Supposons que l’implication « S’il pleut, alors le sol est mouillé. » soit vraie. Comme une implication et sa contraposée sont logiquement équivalentes, on peut en déduire que la contraposée est également vraie :

Implication : « S’il pleut, alors le sol est mouillé. »
Contraposée : « Si le sol n’est pas mouillé, alors il ne pleut pas. »

En revanche, on ne peut pas en déduire que la réciproque « Si le sol est mouillé, alors il pleut. » est vraie. Le sol peut être mouillé pour une autre raison (par exemple, le jardinier l’a arrosé), donc la réciproque n’est pas logiquement équivalente à l’implication de départ.

Quantificateurs

Définition Quantificateurs

Le quantificateur universel $\forall$ signifie « pour tout ». « $\forall x\in E,\;P(x)$ » affirme que $P(x)$ vaut pour tout $x\in E$.
Le quantificateur existentiel $\exists$ signifie « il existe ». « $\exists x\in E,\;P(x)$ » affirme qu’il existe au moins un $x\in E$ tel que $P(x)$ soit vraie.

Exemple

Soit $E = \{1, 2, 3\}$.

$\forall x \in E, x < 4$ est un énoncé vrai, car on a $1<4$, $2<4$ et $3<4$.
$\exists x \in E, x \text{ est pair}$ est un énoncé vrai car $2$ est pair.
$\forall x \in E, x \text{ est impair}$ est un énoncé faux, car $2$ n'est pas impair.

Proposition Négation des quantificateurs

La négation de « $\forall x\in E, P(x)$ » est « $\exists x\in E, \neg P(x)$ ».
La négation de « $\exists x\in E, P(x)$ » est « $\forall x\in E, \neg P(x)$ ».

Exemple

La négation de l’énoncé « Tous les entiers sont pairs »$$\forall n \in \mathbb{Z},\; n \text{ est pair}$$est « Il existe au moins un entier qui est impair »$$\exists n \in \mathbb{Z},\; \neg(n \text{ est pair}) \quad\text{c’est-à-dire}\quad \exists n \in \mathbb{Z},\; n \text{ est impair}.$$

Démonstration écrite

Structure des démonstrations écrites

Méthode Structure des démonstrations écrites

Une démonstration claire et bien structurée suit généralement ces étapes :

Énoncé : Énonce clairement la proposition que tu comptes prouver et, si besoin, la méthode que tu utiliseras.
Hypothèses : Énonce explicitement tes hypothèses de départ. Pour une preuve directe, cela revient à supposer la prémisse $p$ de l’implication $p \Rightarrow q$.
Étapes logiques : Présente une séquence de déductions logiques claires, en justifiant chaque étape à l’aide de définitions, d’axiomes ou de théorèmes déjà démontrés.
Conclusion : Énonce la conclusion finale, en la reliant explicitement à la proposition initiale.

Exemple

Preuve directe : la somme de deux entiers pairs est paire.

Énoncé :
Nous prouvons par preuve directe : si $a,b$ sont des entiers pairs, alors $a+b$ est pair.
Hypothèses :
Supposons $a,b$ deux entiers pairs. Par définition d’un entier pair, il existe $k,\ell\in\Z$ tels que$$ a=2k \quad\text{et}\quad b=2\ell. $$
Étapes logiques :
$$\begin{aligned}a+b &= 2k + 2\ell \\ &= 2(k+\ell).\end{aligned}$$Comme $k+\ell\in\Z$, la somme $a+b$ est un multiple de $2$.
Conclusion :
Par définition d’un entier pair, $a+b$ est pair.

Méthode Conseils pour rédiger des démonstrations

Écris d’abord les hypothèses et la conclusion visée ; elles guideront ton chemin. Il peut être utile de remonter à partir de la conclusion sur une feuille de brouillon.
Démonstration en cours : la « main » gauche représente l’hypothèse, la « main » droite la conclusion — elles se rejoignent au milieu.
Utilise un brouillon. Explore librement sur une feuille de brouillon avant de rédiger l’argument final et soigné.
La grande mathématicienne Maryam Mirzakhani travaillant intensément sur un brouillon.
Itère. Recueille des retours, révise, et ne t’attends pas à une démonstration parfaite du premier coup.
Boucle de retours avec Dr. Tariel et un étudiant de la CommeUnJeu Academy.

Introduire une variable

Pour raisonner sur tous les éléments d’un ensemble $E$, on introduit un élément générique par « Soit $x\in E$. » Il représente un élément quelconque pendant toute la preuve.

Méthode Introduire une variable

Soit $x\in E$.
$\vdots\quad\quad \quad\quad$ (raisonner sur $x$)
Par conséquent, l'énoncé vaut pour tout $x\in E$.

Méthodes de démonstration

Démonstration directe (par déduction)

Méthode Démonstration directe

Pour prouver $p \Rightarrow q$, une preuve directe suppose que $p$ est vraie et utilise une suite de déductions logiques pour montrer que $q$ doit aussi être vraie.$$\begin{aligned}&\text{Supposons que } p \text{ soit vraie.} && (\text{Hypothèse})\\ &\quad\vdots\quad && (\text{Étapes logiques})\\ &\text{Donc } q \text{ est vraie.} && (\text{Conclusion})\end{aligned}$$

Exemple

Démontrer que si un entier $a$ divise les entiers $b$ et $c$, alors $a$ divise leur somme $b+c$.

Correction

Soient $a, b$ et $c$ des entiers.
Supposons que $a$ divise $b$ et que $a$ divise $c$.
Par définition de la divisibilité, il existe des entiers $k$ et $m$ tels que$$ b = ak \quad \text{et} \quad c = am. $$Considérons la somme $b+c$ :$$\begin{aligned}b + c &= ak + am \\ &= a(k+m).\end{aligned}$$Par définition, cela signifie que $a$ divise $b+c$.

Preuve par contraposée

Méthode Preuve par contraposée

Pour prouver l’implication $p \Rightarrow q$, on peut plutôt démontrer sa contraposée, logiquement équivalente, $\neg q \Rightarrow \neg p$.$$\begin{aligned} &\text{Supposons que } \neg q \text{ soit vraie.} && (\text{Hypothèse})\\ &\quad\vdots\quad && (\text{Étapes logiques})\\ &\text{Donc } \neg p \text{ est vraie.}&& (\text{Conclusion})\end{aligned}$$

Exemple

Démontrer que si $a^2$ est pair, alors $a$ est pair.

Correction

Nous allons prouver la contraposée : « Si $a$ est impair, alors $a^2$ est impair. »
Supposons que $a$ soit un entier impair.
Il existe alors un entier $k$ tel que $a=2k+1$.$$\begin{aligned} a^2 &= (2k+1)^2\\ &= 4k^2+4k+1\\ &= 2(2k^2+2k)+1.\end{aligned}$$Donc $a^2$ est de la forme $2m+1$ et est donc impair.
Puisque nous avons prouvé la contraposée, l’énoncé initial est vrai.

Preuve par exhaustion

Une démonstration par exhaustion (ou par cas) consiste à décomposer un énoncé en un nombre fini de cas distincts et à prouver que l'énoncé est vrai pour chacun de ces cas. Il est crucial de montrer que les cas choisis couvrent toutes les possibilités.

Méthode Preuve par exhaustion

Pour prouver une proposition $P$, identifie un ensemble fini de cas $\{C_1, C_2, \dots, C_n\}$ qui soient exhaustifs (couvrent toutes les possibilités).

Prouver que $P$ est vraie pour le cas $C_1$.
...
Prouver que $P$ est vraie pour le cas $C_n$.

Exemple

Démontrer que pour tout entier $n$, $n(n+1)$ est pair.

Correction

Soit $n$ un entier.

Cas 1 : $n$ est pair.
Il existe un entier $k$ tel que $n=2k$. $$ \begin{aligned} n(n+1) &= 2k(2k+1)\\ &= 2[k(2k+1)]. \end{aligned} $$ Donc $n(n+1)$ est pair.
Cas 2 : $n$ est impair.
Il existe un entier $k$ tel que $n=2k+1$. $$ \begin{aligned} n(n+1) &= (2k+1)((2k+1)+1)\\ &= (2k+1)(2k+2)\\ &= 2\left[(2k+1)(k+1)\right]. \end{aligned} $$ Donc $n(n+1)$ est pair.

Donc $n(n+1)$ est pair.

Réfutation par contre-exemple

Pour prouver qu'un énoncé universel est faux, il suffit de trouver un seul cas pour lequel il ne s'applique pas. Par exemple, pour prouver que l'énoncé « Tous les élèves de ma classe sont des garçons » est faux, il suffit de trouver une élève qui est une fille. En notation logique, dire que « $\forall x\in E,\;P(x)$ » est faux revient à dire que « $\exists x\in E,\;\neg P(x)$ » est vrai.

Méthode Réfutation par contre-exemple

Pour réfuter l'énoncé « $\forall x\in E,\;P(x)$ », il suffit de trouver un élément $c \in E$ pour lequel $P(c)$ est faux. Cet élément $c$ est appelé un contre-exemple. Autrement dit, on montre que l’énoncé existentiel « $\exists x\in E,\;\neg P(x)$ » est vrai.

Exemple

Réfuter « Tous les nombres impairs sont des nombres premiers. »

Correction

Contre-exemple : $9$ est impair mais n’est pas premier (car $9 = 3 \times 3$).

Preuve par équivalence

Pour prouver $p\Leftrightarrow q$, on peut montrer séparément $p\Rightarrow q$ et $q\Rightarrow p$, ou transformer $p$ en $q$ par équivalences successives.

Méthode Preuve par équivalence

Pour prouver $p \Leftrightarrow q$, deux méthodes sont possibles :

Double implication :
1. Prouver le sens direct : supposer que $p$ est vraie et montrer que $q$ doit être vraie ($p \Rightarrow q$).
2. Prouver le sens réciproque : supposer que $q$ est vraie et montrer que $p$ doit être vraie ($q \Rightarrow p$).
Chaîne d'équivalences : partir de l'énoncé $p$ et construire une suite d'énoncés logiquement équivalents qui se termine par $q$. $$ p \quad \Leftrightarrow \quad s_1 \quad \Leftrightarrow \quad s_2 \quad \Leftrightarrow \quad \dots \quad \Leftrightarrow \quad q. $$

Exemple

Pour $n\in\Z$, les énoncés suivants sont équivalents :$$n \text{ est pair} \;\Leftrightarrow\; n^2 \text{ est pair}.$$

($\Rightarrow$) Supposons que $n$ soit pair. Il existe alors $k\in\Z$ tel que $n = 2k$. Ainsi$$n^2 = (2k)^2 = 4k^2 = 2(2k^2),$$donc $n^2$ est pair.
($\Leftarrow$) Supposons que $n^2$ soit pair. D’après le résultat démontré plus haut (« Si $a^2$ est pair, alors $a$ est pair »), on en déduit que $n$ est pair.

Raisonnement par l'absurde

Le raisonnement par l'absurde repose sur l'idée que si une supposition mène à une absurdité logique, cette supposition doit être fausse (par exemple $1=0$). On peut résumer la forme logique ainsi : si supposer $\neg p$ conduit à une contradiction, alors $p$ doit être vraie.

Méthode Raisonnement par l'absurde

Pour prouver qu'une proposition $p$ est vraie par l'absurde :$$\begin{aligned} &\text{Supposons que } \neg p \text{ soit vraie.} && (\text{Hypothèse})\\ &\quad\vdots\quad && (\text{Étapes logiques menant à une contradiction, par exemple } 1=0)\\ &\text{Contradiction ! Donc l’hypothèse } \neg p \text{ est fausse.} && \\ &\text{Ainsi, } p \text{ doit être vraie.}&& (\text{Conclusion})\end{aligned}$$

Exemple

Démontrer par l'absurde que le nombre de nombres premiers est infini.

Correction

Supposons qu'il n'existe qu'un nombre fini $n$ de nombres premiers, que nous notons $p_1, p_2, \dots, p_n$.
Tout entier positif strictement supérieur à 1 est soit un membre de cette liste, soit divisible par un membre de cette liste.
Soit $N = p_1 \times p_2 \times \dots \times p_n + 1$. Remarquons que :

$N > p_k$ pour tout $k=1, \dots, n$.
Donc $N$ n'est pas un membre de la liste.
Si nous divisons $N$ par n'importe quel $p_k$, $k=1, \dots, n$, alors le reste est $1$.
Donc $N$ n'est divisible par aucun $p_k$.

Ceci contredit notre supposition selon laquelle tout entier strictement supérieur à 1 est dans la liste ou divisible par un nombre premier de la liste. Notre supposition est donc fausse, et il existe une infinité de nombres premiers.

Raisonnement par récurrence

Le raisonnement par récurrence est une technique puissante utilisée pour démontrer qu'une proposition $P(n)$ est vraie pour tous les entiers $n$ à partir d'une certaine valeur de départ. C'est analogue à faire tomber une rangée de dominos : si tu peux faire tomber le premier, et que tu sais que chaque domino fera tomber le suivant, alors tous les dominos finiront par tomber.

Méthode Le principe du raisonnement par récurrence

Pour prouver par récurrence qu'une proposition $P(n)$ est vraie pour tous les entiers $n \ge n_0$ :

Initialisation : prouver que $P(n_0)$ est vraie.
Hérédité :
- supposer que $P(k)$ est vraie pour un entier arbitraire $k \ge n_0$ (hypothèse de récurrence) ;
- en utilisant cette hypothèse, prouver que $P(k+1)$ doit aussi être vraie.

Exemple

Démontrer par récurrence que pour tout entier $n \ge 1$,$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$

Correction

Soit $P(n)$ la proposition$$P(n) : \quad 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$pour tout entier $n \ge 1$.

Initialisation ($n=1$) :\$$0.2em]À gauche, on a $1$. À droite,$$\frac{1(1+1)}{2} = \frac{2}{2} = 1.$$Donc $P(1)$ est vraie.\$$0.4em]
Hérédité :
Supposons $P(k)$ vraie pour un certain entier $k \ge 1$, c’est-à-dire$$1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}.$$Nous devons montrer que $P(k+1)$ est vraie :$$1 + 2 + 3 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2}.$$En partant du membre de gauche de $P(k+1)$ :$$\begin{aligned}1 + 2 + \dots + k + (k+1)&= \left(1 + 2 + \dots + k\right) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \quad &&\text{(d’après l’hypothèse de récurrence)}\\ &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2}.\end{aligned}$$Ainsi, $P(k+1)$ est vraie.

Comme $P(1)$ est vraie et que $P(k) \Rightarrow P(k+1)$ pour tout entier $k \ge 1$, d’après le principe de récurrence, $P(n)$ est vraie pour tout entier $n \ge 1$.