Une démonstration du principe de récurrence

Atteindre l'infini à partir de l'existence d'un plus petit nombre

Y. Morel

Document pdf

Le principe de récurrence permet de démontrer un ensemble infini et dénombrable de propriétés. On note par exemple P_n ces propriétés.
Pour démontrer que toutes les propriétés P_n sont vraies, à partir d'un premier entier n₀, on démontre tout d'abord que la première de ces propriétés P_n₀ est vraie (initialisation), ensuite on démontre que cette véracité se propage "de proche en proche": si pour un entier n quelconque P_n est vraie, alors la propriété suivante P_n+1 est aussi vraie.

Le principe de récurrence est celui qui permet alors justement de conclure, à partir de ces deux étapes, que toutes les propriétés P_n, sont vraies, dès le premier n₀, jusqu'à … l'infini.
Ceci est très souvent vu et appris comme un "principe": assez "logique", assez "évident" même …
On peut néanmoins le démontrer, et transformer ainsi ce "principe de récurrence" en "propriété de récurrence".

Une démonstration de ce principe, permettant de démontrer des propriétés P_n pour des entiers n jusqu'à l'infini, repose au contraire sur l'existence d'un plus petit nombre entier dans un ensemble d'entiers:

Propriété

Tout sous-ensemble de N non vide possède un plus petit élément.

Cette propriété admise ici est des plus simples: un sous-ensemble de N est un ensemble de nombres entiers naturels.
Ces nombres sont donc au moins positifs, plus grands que zéro, et peuvent être ordonnés: il y en a nécessairement un plus petit que tous les autres.
Cette nécessité repose sur le fait qu'on manipule ici des nombres entiers, voir la remarque à la fin.

À partir de cette propriété, le principe de récurrence est un théorème:

Théorème:

Soit P₀, P₁, … P_n, … une suite de propositions telles que

P₀ est vraie
pour tout entier n, si P_n est vraie, alors P_n+1 est aussi vraie.

Alors, pour tout entier n≥0, P_n est vraie.

Démonstration:

Supposons au contraire, par l'absurde, que pour un certain entier n, P_n soit fausse.

On note alors A = { k∈N, P_k est fausse} qui est donc un sous-ensemble non vide de N.
D'après la propriété précédente, l'esnemble A admet donc un plus petit élément, que l'on note m, et on a donc

m∈A, ce qui signifie que P_m est fausse
m−1∉A, ce qui signifie que P_m−1 n'est pas fausse, donc est vraie.

Or, on sait que, comme P_m−1 est vraie, la propriété suivante P_m doit aussi être vraie, ce qui est contradictoire.

Ainsi, il n'existe pas d'entier n tel que P_n soit fausse.
En d'autres termes, toutes les propositions P_n sont vraies, donc pour tous les entiers n.

Remarque: Le point clé du principe (ou théorème maintenant) de récurrence est la dénombrabilité: on numérote les propriétés P_n avec les entiers naturels, pour lesquels on a la propriété d'existence du plus petit élément.

Pour les nombres réels, cette propriété est fausse: tout sous-ensemble de R, non-vide, n'admet pas nécessairement un plus petit élément. Par exemple, le sous-ensemble E = ]0;3] n'en admet pas.
0∉E et pour tout nombre réel x∈E, on peut trouver un réel y∈E tel que y<x; on peut par exemple prendre y = x/2.
Ainsi, aucun nombre x de Ene peut être le plus petit élément, on peut toujours en trouver un plus petit.

Voir aussi