Le formalisme mathématique

bcpst 1, 27/03/2018

Figure I.1 — Extrait de Principia Mathematica, 1910–1913, A. North Whitehead et B.

Russell

Figure I.2 — Explosion d’Ariane 5, le 4 juin 1996

Les mathématiques modernes forment une science essentiellement formelle.

Tout texte mathématique peut être entièrement énoncé dans un langage conventionnel,
constitué d’un nombre déterminé de symboles, utilisé selon des règles précises. La
vérification syntaxique d’un tel texte est donc une opération purement mécanique.
Toutefois, pour des énoncés courants, une telle vérification est extrêmement fastidieuse.
On se permet donc d’utiliser le langage courant, un certain nombre des symboles
abréviateurs (qui représentent une opération complexe), des méthodes de calcul et
de raisonnement éprouvées (intégration par parties, raisonnement par l’absurde, par
 I — Phrases mathématiques 2

récurrence, etc.) ainsi que des objets courants (entier, opérations usuelles, etc.) sans
chercher à en expliciter complètement la définition.
Il est pourtant essentiel d’avoir quelques notions de ce formalisme, qui constitue les
fondements solides de la science mathématique.

I — Phrases mathématiques
I.1 — Énoncés
On définit tout d’abord un certain nombre de symboles :
– des variables, en nombre infini notées x, y, z, etc.
– des constantes comme 0, 1, etc.
– des prédicats qui rendent compte des relations entre les variables. Par exemple « est
plus petit que » qui est noté ¶, « addition », etc.
– des connecteurs logiques comme « et », « ou », etc.
– et enfin des quantificateurs au nombre de deux : l’un « existentiel » noté ∃ et l’autre
« universel » ∀.

I.2 — Syntaxe
Ces symboles peuvent être employés selon une syntaxe précise qui est constitué à la fois
de règles concernant les objets proprement mathématiques (toute parenthèse ouverte
doit être fermée, le signe × doit être précédé et suivi d’un symbole, etc.), ainsi que des
règles propres à la définition des objets.

Exemple
p
– « 2 = » n’est pas syntaxiquement correcte ;
– « x = ln(−2) » non plus (la syntaxe du symbole ln n’est pas respectée) ;
– « 1 + 1 = 1 » est syntaxiquement correct, quoique fausse ;
– « 2 est un entier pair » ;
– « Cette phrase est écrite avec une faute d’orthographe » (syntaxiquement correct,
mais fausse — j’espère !).

5
X
lim un = = 50
n→+∞
0

Pour bien travailler on doit donc penser à vérifier la syntaxe des énoncés : utiliser une
fonction dans son domaine de définition, vérifier la convergence d’une suite avant
d’écrire le symbole lim, etc.
Beaucoup d’erreurs d’élève sont en réalité des erreurs de syntaxe. Les erreurs de raison-
nement sont souvent plus subtiles et plus difficiles à expliquer.
 II — Logique — Valeurs de vérités 3

Exercice 1 En faisant quelques calculs simples, expliquez pourquoi il est syntaxique-

ment incorrect :
1. de définir un ordre parmi les nombres complexes semblable à celui qui est défini
sur les réels ;
p
2. d’écrire −1 = i ;
3. de définir la racine carrée d’un nombre complexe ;
4. de parler du logarithme népérien d’un nombre complexe.

Solution — 1. Si, par exemple, i ¾ 0, alors i × i ¾ 0, donc −1 ¾ 0.

p p p p p
2. 2 = 4 = −1 −1 4 = i × i × 4 = −2.
p p p
3. i × i = −1, mais cette dernière écriture ne peut être syntaxiquement
correcte.

4
4. Par exemple eiπ /2 = 1, donc on aurait 4 ln(eiπ /2 ) = ln(1) = 0. Or si loga-
rithme est toujours la bijection réciproque de l’exponentielle, on aurait donc
0 = iπ /2.

II — Logique — Valeurs de vérités

II.1 — Assertion, proposition,
Les notions de « Vrai » et « Faux » sont purement conventionnelles. On attribue tout
d’abord à un petit nombre de propositions, nommées axiomes, la valeur de vérité « Vrai ».
Ces axiomes doivent vérifier un certain nombre de propriétés « de bon sens ». Par
exemple, ils ne doivent pas se contredire entre eux, ils doivent être indépendants les
uns des autres (c’est-à-dire qu’on ne peut pas déduire un axiome à partir des autres),
etc
Par la suite, la valeur de vérité des autres phrases mathématiques se déduit des axiomes
à l’aide de règles de calcul logique que nous allons voir.

Définition 2.1 — Proposition logique

Une assertion ou proposition est une phrase syntaxiquement correcte et à laquelle on peut
attribuer une valeur de vérité : « Vrai »(V) ou « Faux » (F).

Il existe donc effectivement plusieurs « mathématiques » selon les axiomes de base

qui sont utilisés. La théorie mathématique courante porte le nom de « théorie des
ensembles de Zermelo-Fraenkel ». Elle se caractérise par l’utilisation intensive de la
notion d’ensembles. Elle a été mise au point les deux mathématiciens Ernst Zermelo et
Abraham Fraenkel à la fin du xixe siècle et au début du xxe. On leur ajoute souvent un
 II — Logique — Valeurs de vérités 4

axiome supplémentaire, l’axiome du choix, encore que les discussions sur la nécessité
d’ajouter cet axiome restent vives.
Les termes « théorèmes », « corollaires », « propositions », « propriétés », « lemmes » dési-
gnent tous des propositions établies comme vraies. L’usage veut que les résultats les
plus importants soient dénommés « théorèmes », que les « corollaires » soient des consé-
quences immédiats d’un théorème. Les « propriétés » sont en général des théorèmes
qui énoncent des propriétés algébriques. Quand aux « lemmes », ce sont des résultats
intermédiaires dans une démonstration un peu étendue.

II.2 — Connecteurs logiques

En partant de plusieurs propositions P, Q, etc. il est possible de construire de nouvelles
propositions : non P, P ou Q, etc. Cette construction permet d’établir la véracité du
résultat en fonction des valeurs de vérités des propositions de départ.

II.2.1 — Négation

Définition 2.2 — non

Soit P une proposition logique. La proposition (non P) est une proposition syntaxiquement
correcte, qui a par définition la valeur de vérité

P non P

V F
F V

II.2.2 — « et », « ou »
À l’intérieur d’un raisonnement, les connecteurs logiques permettent d’envisager diffé-
rentes situations, selon la véracité des assertions qu’ils relient. Ils sont définis de façon
à correspondre aux notions usuelles « et » et « ou ».

Définition 2.3 — et, ou

 II — Logique — Valeurs de vérités 5

Soit P et Q deux propositions logiques. Les propositions (P et Q) et (P ou Q) sont syntaxi-

quement correctes. Elles ont par définition les valeurs de vérité

P Q P et Q P Q P ou Q

V V V V V V
V F F V F V
F V F F V V
F F F F F F

Le connecteur « ou » correspond à un ou inclusif, c’est-à-dire qu’il suffit qu’un des

deux assertions soit vraie. Dans le langage courant, le ou est souvent exclusif : quand on
vous propose « fromage ou dessert », vous ne pouvez peut-être pas prendre les deux...
Les formules de De Morgan 1 explicitent le lien entre non , et et ou .

Théorème 2.4 — Formules de De Morgan

1) « non (P et Q) » à la même valeur de vérité que « (non P) ou (non Q) » ;

2) « non (P ou Q) » à la même valeur de vérité que « (non P) et (non Q) ».

Dém. On dresse les tables des vérités des différentes propositions. ƒ

Exemple
– La négation de « la voiture est bleue ou c’est une Renault » et celle de « mon animal
de compagnie est un chien ou un chat ».
– Donner la négation, pour x ∈ R, de 3 ¶ x ¶ 7.
– Donner la négation, pour x ∈ R, de 3 ¶ x ¶ −7.
– Donner la négation, pour (x, y) ∈ R2 , de

Théorème 2.6 — Commutativité, associativité, distributivité

Soit P, Q et R trois propositions.
• associativité de « et » : P et (Q et R) = (P et Q) et R noté simplement « P et Q et R » ;
• associativité de « ou » : P ou (Q ou R) = (P ou Q) ou R noté simplement « P ou Q ou R » ;
• distributivité de « et » sur « ou » :
P et (Q ou R) = (P et Q) ou (P et R)

• distributivité de « ou » sur « et » :
P ou (Q et R) = (P ou Q) et (P ou R)

1. Auguste De Morgan (27 juin 1806 à Madurai (Tamil Nadu) - 18 mars 1871) est un mathématicien et logicien
britannique, né en Inde. Il fût un excellent professeur, et le fondateur avec Boole de la logique moderne.
 II — Logique — Valeurs de vérités 6

II.2.3 — Implication
La plupart des théorèmes mathématiques s’écrivent sous la forme d’une implication :
« Si (tels et tels objets ont telles et telles propriétés) alors (Q est vrai) ».

Exemple Dans « Soit a et b deux réels. Si a2 + b2 = 0 alors a = 0 et b = 0. » il y a trois

hypothèses ! (Lesquelles ?)
En mathématiques, l’assertion P =⇒ Q se définit à partir des connecteurs précédents.

Définition 2.8 — implique, équivalente

Soit P et Q deux propositions.
• L’assertion « P =⇒ Q » (qui se lit « P implique Q ») est l’assertion « (non P) ou Q »
• L’assertion « P ⇐⇒ Q » (qui se lit « P est équivalente à Q ») est l’assertion « (P =⇒
Q) et (Q =⇒ P) ».

Voyons leurs tables de vérité :

P Q P =⇒ Q P Q P ⇐⇒ Q

V V V V V V
V F F V F F
F V V F V F
F F V F F V

Exemple Vous cherchez à déterminer l’espèce d’une arbre. Pour cela, vous regardez
s’il a des fruits. Vous en trouvez un : c’est une pomme. L’arbre est donc un pommier,
suivant l’implication « Il y a une pomme sur l’arbre, donc c’est un pommier ».
Il est impossible que l’arbre soit autre chose qu’un pommier si on trouve une pomme sur
une de ces branches, ce qui explique la seconde ligne du tableau.
Si nous ne trouvons pas de pommes dans l’arbre, devons nous en déduire que notre
implication est fausse ? Bien sûr que nous. L’arbre peut-être un pommier ou non, bien
que nous ne puissions pas prévoir s’il l’est ou pas. Ainsi les deux dernières lignes du
tableau correspondent bien au sens commun, quoiqu’on ait jamais besoin d’y songer.

Exercice 2 Quelle est la valeur de vérité de des propositions suivantes ?

1. 2 est pair =⇒ 4 est pair ;
2. 2 est pair =⇒ 3 est pair ;
3. 2 est impair =⇒ 3 est pair ;
4. 4 > 1 ⇐⇒ 42 > 1 ;
5. le ciel est bleu ⇐⇒ 2 + 2 = 4.
 II — Logique — Valeurs de vérités 7

Remarque I.1 Remarquez que « faux implique n’importe quoi » et que « faux ⇐⇒
faux »...

II.2.4 — Équivalence, contraposée

Définition 2.10 — Contraposée

La contraposée de l’implication « P =⇒ Q » est « non Q =⇒ non P ».

Théorème 2.11 — Contraposée

Deux contraposées ont la même valeur de vérité.

Dém. Par leurs tables de vérité ƒ

La contraposée de « Il pleut donc je suis mouillé(e) » est « Je ne suis pas mouillé(e)

donc il ne pleut pas ». La contraposée est un bon moyen de démontrer la négation d’une
proposition, comme on le verra par la suite.

Exemple A Montrons la proposition suivante : soit p ∈ N, si p2 est pair alors p est pair.
Raisonnons par contraposée : supposons que p est un entier impair. Comme p est impair,
il existe un entier k tel que p = 2k + 1. Alors p2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 et
nous constatons que p2 est impair. Nous avons donc démontré la contraposée.

Proposition 2.12 — Négation d’une implication

La négation de « P =⇒ Q » est « P et (non Q) ».

Dém. En utilisant les formules de De Morgan ƒ

Exercice 3 Soit f une fonction dérivable de R dans R. Donner la réciproque et la

contraposée des propositions suivantes. Dans chaque cas, donner la valeur de vérité.
1. f est constante =⇒ f est croissante ;
2. f 0 est positive =⇒ f est croissante ;
3. f 0 = 0 =⇒ f est constante ;
4. f admet un maximum en 1 =⇒ f 0 (1) = 0.
 II — Logique — Valeurs de vérités 8

II.2.5 — Raisonnement inductif

En général un théorème énonce qu’une implication est vraie. On l’utilise dans le contexte
du modus ponens. Considérer par exemple le théorème « il pleut donc le sol est mouillé »,
que je note P =⇒ Q avec P « il pleut » et Q « le sol est mouillé ». Bon, aujourd’hui, il
ne pleut pas, donc ce beau théorème ne m’est pas utile.
Mais supposons que P est vrai : il pleut ! Alors je fais le raisonnement suivant

P vraie
et P =⇒ Q
donc Q vraie

Il faut comprendre que la valeur de vérité de Q n’était pas connue au préalable. Elle a
été déduite de la théorie (ici le théorème P =⇒ Q) et des hypothèses (ici P est vraie).
La « théorie » en question est l’ensemble des résultats du cours, ainsi que les résultats
précédemment établis dans l’exercice.

Exemple À partir de la mini-théorie

– ∀x ∈ R, x + x = 2 × x ;
– ∀x ∈ R+ , , ∀ y ∈ R, x + y ¾ y ;
démontrons le résultat suivant

∀x ∈ R+ , 2× x ¾ x

La démonstration est très simple, mais il est intéressant d’en comprendre la structure.
La mini-théorie fournit deux « théorèmes ». Ceux-ci sont de la forme archi-courante
« Si x vérifie telle propriété alors x vérifie telle autre propriété ». Il s’agit donc d’une
implication logique « P =⇒ Q ».
Ici, supposons donc que x est un réel positif. Appliquons le second théorème dans le cas
particulier y = x (ce qui est possible, puisque x est aussi un réel). On en déduit que
« x + x ¾ x ».
On peut aussi appliquer le premier théorème à x : x + x = 2 × x.
En conclusion « 2 × x ¾ x ».

Exercice 4 Soit E un ensemble et A et B deux sous-ensembles de E. Traduire avec

des quantificateurs les propositions suivantes :
1. A ⊂ B ; 3. E = A ∪ B ;
2. A ⊂ B ; 4. A et B sont disjoints.
 III — Quantificateurs 9

II.2.6 — Négation – raisonnement par l’absurde

Le raisonnement par l’absurde est une méthode de raisonnement assez spectaculaire.
Elle consiste à démontrer une implication en supposant l’hypothèse vraie, la conclusion
fausse puis à raisonner jusqu’à aboutir à une proposition fausse.
En termes logiques, rappelons-nous que « P =⇒ Q » signifie non P ou Q. Sa néga-
tion est donc non (non P ou Q) c’est-à-dire P et non Q. Si on arrive donc à montrer
que cette négation est fausse, alors on sait que P est fausse ou que non Q. Mais P est
vraie (c’est l’hypothèse) donc non Q est fausse, donc Q est vraie !
p
Exemple B — Irrationalité de 2
p
– Démontrons que 2 n’est pas un nombre rationnel.
p
Raisonnons par l’absurde : supposons que 2 est rationnel, c’est-à-dire que l’on peut
p p p
écrire 2 sous forme d’une fraction irréductible : ∃p ∈ N ∃q ∈ N, 2 = et p et q
q
n’ont pas de diviseur commun.
p2
Or 2 = 2 , donc que p2 = 2q2 . Ainsi p2 est pair, donc, d’après l’exemple précédent,
q
p est pair. Donc il existe un entier k tel que p = 2k. Ainsi 4k2 = 2q2 , donc q2 = 2k2 .
On en déduit que q2 est pair, donc q est pair.
Voilà la contradiction : p et q sont tous deux pairs, mais ils ne doivent pas avoir de
diviseur commun.

III — Quantificateurs
Ce sont les quantificateurs qui donnent à la théorie mathématique sa puissance et sa
généralité : c’est la composante réellement abstraite des mathématiques.

III.1 — Prédicat

Définition 3.1 — Prédicat

Un prédicat est une assertion dans laquelle figure un symbole dont la valeur peut être
variable.

La valeur de vérité du prédicat dépend donc de la valeur du symbole.

Par exemple « A est pair » est un prédicat dépendant du symbole A. Pour que cette
assertion soit syntaxiquement correcte, il faut que A soit un objet pour lequel la notion
de « pair » est définie : un entier ou une fonction définie sur R par exemple. Lorsqu’on
remplace x par une valeur (entière) on obtient une assertion : pour x = 2 l’assertion
« 2 est pair » est vraie, pour x = 3 elle ne l’est pas.
De même « x 2 > 1 » est un prédicat sur R, mais pas sur C (il n’y a pas de relation d’ordre
dans C). Si on remplace x par −2 on obtient une assertion, mais si on remplace x par
1 + i on obtient un énoncé qui n’est pas valide syntaxiquement.
 III — Quantificateurs 10

III.2 — ∀, ∃
Les quantificateurs servent à « fermer » une prédicat pour en faire une proposition.
Par exemple « (x + 1)2 − x 2 est pair » est un prédicat que l’on peut fermer par un
quantificateur de la façon suivante : « ∀x ∈ N, (x + 1)2 − x 2 est pai r ».
Ce fermeture permet de transformer le prédicat en une assertion dont on va ensuite
établir la valeur de vérité.

Définition 3.2 — Trois quantificateurs

Soit P(x) un prédicat à une variable x. Ce prédicat a bien un sens lorsque x varie dans un
ensemble donné E. Nous pouvons construire trois nouvelles assertions
– « ∀x ∈ E, P(x) » Cette assertion est vraie dans le cas où le prédicat P(x) est vraie pour
toute les valeurs de la variable x prises dans l’ensemble E ;
– « ∃x ∈ E P(x) » Cette assertion est vraie dans le cas où le prédicat P(x) est vraie pour
au moins une valeur de la variable x.
Elle est définie comme la négation de « ∀x ∈ E non P(x) », soit non (x ∈ E =⇒
non P(x)).
– « ∃!x ∈ E P(x) » Cette assertion est vraie dans le cas où le prédicat P(x) est vraie pour
une unique valeur de la variable x.
Elle est formellement équivalente à « (∃x ∈ E P(x)) et (∀(x, y) ∈ E, [(P(x) et P( y)) =⇒
x = y]).

Par exemple supposons que E est l’ensemble {−1, 0, 4} est que P(x) est le prédicat
(x + 1)2 − x est pair. On peut tester les trois valeurs et se rendre compte que la propriété
est fausse : elle ne marche pas avec 0. On dit que 0 est un contre-exemple.
Toutefois le prédicat P fonctionne avec 0. Ainsi la proposition « ∃x ∈ (−1, 0, 4) , P(x) »
est vraie.
Est-ce que « ∃ y ∈ (−1, 0, 4) , P( y) » est vraie ? Oui, évidemment ! La notation x ne joue
aucun rôle dans la démonstration. Elle n’a été utile que durant la démonstration, mais
n’a pas de sens en dehors. On parle de variable liée.

III.3 — Négation des quantificateurs

Proposition 3.3 — Négation de quantificateurs

1) La négation de « ∀x ∈ E P(x) » est « ∃x ∈ E (non P)(x) ».

2) La négation de « ∃x ∈ E P(x) » est « ∀x ∈ E (non P)(x) ».

On parle dans le premier cas de contre-exemple. Par exemple : « tout les nombres impairs
sont premiers » est nié par le contre-exemple « le nombre impair 9 n’est pas premier ».
 III — Quantificateurs 11

Exercice 5 Quelle est la négation des phrases :

– x < y;
– la fonction f définie sur R est croissante ;
– la fonction f définie sur R est positive ?

Puisque « faux implique n’importe quoi », on a « ∀x ∈ ∅, P(x) » toujours vraie, quelque

soit le prédicat P. Par négation, « ∃x ∈ ∅, P(x) » est donc toujours fausse. C’est pour
cela qu’on prend souvent soin de ne pas faire varier x dans l’ensemble vide.

III.4 — Démonstration avec des quantificateurs

La proposition « ∀x ∈ E, P(x) » est formellement équivalente à « x ∈ E =⇒ P(x) ».
On la démontre donc en faisant l’hypothèse x ∈ E et en démontrant alors la véracité de
P(x).
Un exemple simple : montrer que ∀x ∈ N, (x + 1)2 − x 2 est impair..
Plus subtil. Montrons que

(B) ∀(x, y) ∈ R+ , x 3 + 2x − 3 = 0 et y 3 + 2 y − 3 = 0 =⇒ x = y

Il y a ici quatre hypothèses. Les voyez-vous ?

x 3 + 2x − 3 = 0 et y 3 + 2 y − 3 = 0 =⇒ x 3 + 2x − 3 = y 3 + 2 y − 3
=⇒ x 3 − y 3 = 2( y − x)
=⇒ (x − y)(x 2 + x y + y 2 ) = −2(x − y)
voir ??

=⇒ x − y = 0 ou x 2 + x y + y 2 = −2

Or la seconde proposition est fausse. La première est donc vraie, puisque l’ensemble
doit être vrai. Ainsi

x 3 + 2x − 3 = 0 et y 3 + 2 y − 3 = 0 =⇒ x = y

La proposition « ∃x ∈ E, P(x) » est souvent difficile à démontrer, car elle suppose a priori
d’exhiber l’élément x. La plupart du temps, il faut trouver une astuce pour s’assurer
l’existence de x sans avoir à le calculer. Le raisonnement par l’absurde est ici d’une
grande aide. En effet, la négation de « ∃x ∈ E, P(x) » étant « ∀x ∈ E, non P(x) » on
peut se ramener au cas précédent.
La proposition « ∃!x ∈ E, P(x) » nécessite deux étapes de démonstration : d’abord
prouver l’existence de x et ensuite son unicité.

Exercice 6 Dire si les assertions suivantes sont vraies, fausses... ou autre chose.
1. ∀x ∈ R, x2 > 1;
 III — Quantificateurs 12

2. ∀x ∈ N∗ , x2 > 1;
3. ∀x ∈ C, x2 > 1;
4. ∃x ∈ R, x2 > 1;
5. ∃x ∈ R+ , x 3 − 3x + 1 > 0 ;

Exercice 7 Soit a et b deux réels et f une fonction dérivable de ]a ; b[ dans R. Écrire

avec des quantificateurs les propriétés suivantes :
1. f est croissante sur ]a ; b[ ;
2. f 0 > 0.

III.5 — L’ordre des quantificateurs

Certaines assertions dépendent de deux variables. Dans ce cas, chaque variable peut
être liée par un quantificateur. L’ordre des quantificateurs est alors important. Pensez à
la phrase : « pour chaque porte, il existe une clé qui ouvre cette porte » et à « il existe
une clé qui ouvre toute les portes ».
Considérons le prédicat y ¶ x à deux variables réelles x et y. On peut construire
plusieurs assertions à partir de ce prédicat :
– ∀x ∈ R, ∃ y ∈ R, y ¶ x ;
– ∃ y ∈ R, ∀x ∈ R, y ¶ x.
La première est vraie alors que la seconde est fausse (le démontrer).
Dans le premier cas, l’existence de y est toujours assuré, mais x étant donnée, la valeur
de y peut changer.
Dans le second cas, la valeur de y ne peut pas changer parmi tous les x.

Exemple Est-ce que les deux phrases suivantes sont vraies ?

– ∀x ∈ N, ∃ y ∈ N, y ¶ x ;
– ∃ y ∈ N, ∀x ∈ N, y ¶ x.
Notons enfin que des quantificateurs ∀ utilisés ensemble, ou deux ∃ utilisés ensemble
peuvent être permutés. Exemple :
– ∀x ∈ R, ∀ y ∈ R, x 2 + y 4 ¾ 0 ;
– ∃x ∈ R, ∃ y ∈ R, x + y = 1.

Exercice 8 Les énoncés suivants sont-ils vrais ou faux ?

1. ∀x ∈ R+ , ∃ y ∈ R+ , y2 = x ;
2. ∃ y ∈ R+ , ∀x ∈ R+ , y2 = x ;
3. ∃ y ∈ R+ , ∀x ∈ R, xy = x;
4. ∀x ∈ R, ∀ y ∈ R, ∃z ∈ R x = y + z ;
5. ∀ y ∈ R, ∃z ∈ R, ∀x ∈ R x = y + z ;
 V — Raisonnements par récurrence 13

6. ∃z ∈ R, ∀x ∈ R, ∀ y ∈ R x = y + z.

IV — Variables libres, liées

La raison de cette dissymétrie est que lorsqu’on écrit ∀x ∈ R, on pose en quelque sorte la
définition du symbole x. Dans la suite de l’énoncé on ne pourra plus utiliser ce symbole
librement. Ainsi, dans le premier et dans le second énoncé, y peut dépendre de x, alors
que c’est impossible dans le troisième ! On dit que le symbole ∀ « lie » la variable x, ou
encore que la variable x est liée.
Une conséquence étonnante est que l’assertion dans son ensemble ne dépend pas de x.
On aurait aussi bien pu écrire ∀ y ∈ E P( y), ou encore ∀chaise ∈ E P(chaise). Le
symbole x n’a aucun sens à l’extérieur de l’énoncé : le résultat ne peut pas en dépendre !

Exercice 9 Citez d’autres « symboles lieurs ».

V — Raisonnements par récurrence

V.1 — Disjonction des cas
On raisonne par disjonction des cas lorsqu’on doit faire des hypothèses supplémentaires
par rapport à celles de l’énoncé. Il est indispensable d’étudier alors l’hypothèse contraire,
ou d’étudier un ensemble d’hypothèses A1 , A2 , A3 , ..., An telles que l’une d’entre elles
au moins soit vérifiée.

Exemple Démontrer que pour tout réel x il existe un réel y tel que x y + x 2 + y = 1.
On peut commencer un calcul simple

x y + x2 + y = 1 =⇒ y(x + 1) = 1 − x 2

Mais maintenant, on veut pouvoir diviser par x + 1, ce qui n’est possible que si x est
différent de −1. Le raisonnement par disjonction des cas est tout à fait adapté.
Si x 6= −1, alors on trouve y = (1 − x 2 )/(1 + x) = 1 − x. La propriété est donc vraie,
puisque y existe (et d’ailleurs, il est unique).
Si x = −1, alors l’équation devient 0 = 0, qui est vraie quelque soit y. La propriété est
vraie : toutes les valeurs réelles de y conviennent.
En conclusion, quelque soit la valeur de x, il existe un réel y tel que etc.
 V — Raisonnements par récurrence 14

V.2 — Raisonnement par récurrence

Le principe de base du raisonnement par récurrence est souvent mal compris, alors qu’il
est en fait très simple. Soit à démontrer un prédicat H(n) dépendant d’une variable
entière n, variant dans N (ou, mutatis mutandis dans N∗ , N \ {0, 1}, etc.). Il s’agit en
fait de démontrer une infinité de proposition

H(0) H(1) H(2) ··· H(n − 1) H(n) H(n + 1) ···

La méthode la plus naturelle consiste à fixer n dans N et à démontrer directement H(n).

Exemple Démontrons que

n(n + 1)
∀n ∈ N 1 + 2 + 3 + ··· + n =
2
Pour cela on écrit la somme dans les deux sens, et on somme :

Sn = 1 + 2 + 3 + · · · + n
Sn = n + (n − 1) + · · · + 1

par somme 2Sn = (n + 1) + (n + 1) + · · · + (n + 1) = n(n + 1)

n(n + 1)
donc Sn =
2
Lorsque cette méthode semble trop difficile à mettre en œuvre, on peut essayer de se
simplifier la vie. Pour cela, on va démontrer H(n) en faisant une hypothèse supplémen-
taire, à savoir que H(n − 1) est vraie. Si on y parvient, alors on aura démontré la suite
d’implications

H(0) =⇒ H(1) =⇒ H(2) =⇒ · · · =⇒ H(n−1) =⇒ H(n) =⇒ H(n+1) =⇒ · · ·

Cela signifie-t-il que toutes les propositions sont vraies ? Évidemment non, car il nous
manque une information : que la première proposition de la chaîne, à savoir H(0) est
aussi vraie. En résumé,

Théorème 5.3 — Principe de récurrence simple

Soit une assertion H(n), où n ∈ N.
– Si H(0) est vraie ;
– si, pour tout n ∈ N, on a « H(n) =⇒ H(n + 1) » vraie ;
– alors « ∀n ∈ N, H(n) » est vraie.

On peut bien sûr commencer à un rang autre que 0.

 V — Raisonnements par récurrence 15

Exemple Soit (un )n∈N une suite telle que

1 − un
u0 = 1/2∀n ∈ N, un+1 =
n
Montrer que ∀n ∈ N un > 0.

Récurrence à deux pas On a parfois besoin d’une version plus puissante de la récurrence

Théorème 5.5 — Principe de récurrence double

Soit une assertion H(n), où n ∈ N.
– Si H(0) et H(1) sont vraies ;
– si ∀n ∈ N∗ , « (H(n − 1) et H(n)) =⇒ H(n + 1) » ;
– alors « ∀n ∈ N, H(n) » est vraie.

Ici on établit une chaîne d’implications un peu plus compliquée, et c’est pour cela qu’il
est nécessaire de démontrer aussi H(1). Sans cela, la seconde hypothèse ne suffirait pas
à démontrer H(1).

Exemple Soit (un )n∈N une suite telle que

u0 = 1 u1 = 2 ∀n ∈ N, un+2 = un+1 + 2un

Montrer que ∀n ∈ N un = 2n .

Récurrence forte Voici la version la plus puissante de la récurrence, que j’utiliserai

parfois dans le cours.

Théorème 5.7 — Principe de récurrence forte

Soit une assertion H(n), où n ∈ N.
– Si H(0) est vraie ;
– si pour tout k entre 0 et n H(k) est vraie alors H(n + 1) est vraie ;
– alors « ∀n ∈ N H(n) » est vraie.

Une déduction est une suite de formules telle que chaque formule A apparaissant dans
cette suite vérifie l’une des conditions suivantes :
– A est l’un des théorèmes déjà démontrés (ou un des axiomes) dans lequel les variables
sont remplacées par des formules ;
– il existe deux formules précédant A qui sont de la forme B =⇒ A et B ; on dit alors
que A est obtenue par modus ponens (déduction logique) entre ces deux formules. On
représente une déduction en écrivant les formules ligne par ligne et en adjoignant
un commentaire à chaque ligne pour expliquer comment la formule correspondante
a été obtenue.
 V — Raisonnements par récurrence 16

V.3 — Définition
Dans cette perspective formelle, une définition est une manière de résumé en un mot
une propriété plus ou moins complexe.
Un exemple typique de définition est

Définition 5.8 — Un intervalle de R est un ensemble I vérifiant la propriété

∀(x, y) ∈ I 2 , ∀z ∈ R, x < z < y =⇒ z ∈ I

Définition 5.9 — Fonction croissante

Soit I un intervalle de R et f une fonction de I dans R.
On dit que f est croissante sur I si et seulement si

∀(x, y) ∈ I 2 , x ¶ y =⇒ f (x) ¶ f ( y)

Il faut bien comprendre que

– l’expression française « f est croissante sur I » est un raccourci pour la formule ma-
thématique précédente. C’est cette formule qui a un véritable intérêt dans les raison-
nements !
Ainsi, une excellente habitude au début d’une question consiste à écrire les définitions
en langage mathématique.
– l’intervalle I est ici essentiel ! Il n’est pas équivalent de dire qu’une fonction est crois-
sante sur R, sur R+ ou sur [ 0 ; 1 ]. Il arrive qu’on parle simplement d’une « fonction
croissante », mais c’est une facilité de langage à éviter.
– Cette définition peut très bien ne rien définir ! En général, une définition est assor-
tie d’un exemple explicite d’objet vérifiant la propriété, ou bien d’une preuve de
l’existence d’un tel objet.
On parle de caractérisation lorsqu’on énonce une propriété qui est équivalente à la
définition. Au fond cette propriété aurait pu être prise comme définition, c’est une
« redéfinition ». Mais parfois on ajoute un petit quelque chose...

Théorème 5.10 — Caractérisation des fonctions dérivables croissantes

Soit I un intervalle de R et f une fonction dérivable de I dans R.
f est croissante sur I si et seulement si f 0 ¾ 0.

Au cours d’une démonstration il est assez fréquent de rencontrer plusieurs niveau

d’implication. Démontrons par exemple la proposition suivante :
« (A) L’équation x 3 + 2x − 3 = 0 admet une unique solution dans R+ . »
 V — Raisonnements par récurrence 17

Une manière de procéder consiste à supposer connues deux solutions de l’équation puis
à montrer qu’elles sont égales. Ainsi l’énoncé (A) est équivalent à l’énoncé (B) suivant

(B) ∀(x, y) ∈ R+ , x 3 + 2x − 3 = 0 et y 3 + 2 y − 3 = 0 =⇒ x = y

Vous êtes bien d’accord que si nous démontrons l’énoncé (B), alors nous avons démontré
l’énoncé (A) ? Or (B) est une implication. Pour le démontrer, nous allons supposer vrai
le coté gauche de l’implication et montrer que le côté droit est vrai.

x 3 + 2x − 3 = 0 et y 3 + 2 y − 3 = 0 =⇒ x 3 + 2x − 3 = y 3 + 2 y − 3
=⇒ x 3 − y 3 = 2( y − x)
=⇒ (x − y)(x 2 + x y + y 2 ) = −2(x − y)
voir ??

=⇒ x − y = 0 ou x 2 + x y + y 2 = −2

Or la seconde propostion est fausse. La première est donc vraie, puisque l’ensemble
doit être vrai. Ainsi

x 3 + 2x − 3 = 0 et y 3 + 2 y − 3 = 0 =⇒ x = y

Résumons nous : pour démontrer le résultat (A), nous avons remarqué qu’il était équi-
valent à l’implication (B), nous avons ensuite démontré l’implication (B).
En apprenant à suivre méthodiquement les implications et les équivalences vous serez
capables de comprendre les démonstrations les plus compliquées ! Retenez que vous
pouvez immédiatement remplacer une proposition par une proposition logiquement
équivalente, et retenez surtout que cette petite gymnastique est très utile !