Démonstration - Théorème de récurrence

Définition

Soient ($\mathbb{N}$,$\leq$) l’ensemble des entiers naturels muni de la relation d’ordre usuelle notée $\leq$, $A(n)$ une assertion définie $\forall n \in \mathbb{N}$ et $n_0 \in \mathbb{N}$ un entier naturel fixé.

• Si $A(n_0)$ vraie
• Si $\forall n \geq n_0$, $A(n)$ vraie $\Rightarrow A(n+1)$ vraie.

Alors $\forall n \geq n_0$, $A(n)$ vraie.

Démonstration

Une correction de cette démonstration a été proposé par Christophe Haro ici : Théorème de récurrence faible La démonstration ci-dessous est donc à prendre avec des pincettes.

Soit $\mathbb{N}_{0} = \{n \in \mathbb{N} \ | \ n \geq n_0\}$ pour simplifier la notation.

Montrons ce théorème par l’absurde.

Soit $P \subseteq \mathbb{N}$ tel que $P = \{n\in \mathbb{N}_0 \land n \leq n_0 \ | \ A(n) \ \text{vraie}\}$. Montrons que $P = \mathbb{N}_0$.

Supposons que $\bar{P}^{\mathbb{N}_0} \neq \emptyset$ ($\bar{P}^\mathbb{{\mathbb{N}_0}}$ est le complémentaire de $P$ dans $\mathbb{N}_0$).

Alors il existe un plus petit élément $p \in \bar{P}^{\mathbb{N}_0}$.

Comme $n_0 \in P$, nécessairement, $n_0 \notin \bar{P}^{\mathbb{N}_0}$, donc $p\geq 1 + n_0$.

Si $1 + n_0$ vous perturbe, remplacez $n_0$ par 0, cela devrait vous aider.

Il était important de vérifier que $p-1 \geq n_0$ pour savoir si $p-1 \in {\mathbb{N}_0}$.

$p$ étant défini comme le plus petit élément de $\bar{P}^{\mathbb{N}_0}$, $p - 1 \notin \bar{P}^{\mathbb{N}_0}$ donc $p-1 \in P$.

Nous pouvons donc dire que $A(p-1)$ est vraie. Par l’ordre usuel sur $\mathbb{N}$, $A(p)$ l’est aussi.

Nous ne pouvons avoir $p\in P$ et $p \in \bar{P}^{\mathbb{N}_0}$ : Contradiction

Nous avons donc bien $P = \mathbb{N}$ et donc le théorème de récurrence !