Les entiers naturels

ℕ est primitif : il est décrit par les axiomes de Peano.

Axiome¶

Axiome Les entiers naturels¶

L'ensemble ℕ des entiers naturels contient 0, et tout entier n a un successeur S(n), qui n'est jamais 0. Deux entiers qui ont le même successeur sont égaux, et toute partie de ℕ qui contient 0 et qui est stable par successeur est ℕ tout entier : c'est le principe de récurrence.

Addition et ordre¶

Définition Addition des entiers naturels¶

L'addition est définie par récurrence sur le second terme : n + 0 = n et n + S(m) = S(n + m).

Définition Ordre sur les entiers naturels¶

n ≤ m quand on peut passer de n à m en ajoutant un entier naturel : n ≤ m ⟺ (∃k ∈ ℕ, m = n + k).

Récurrence, plus petit et plus grand élément¶

Corollaire Principe de récurrence simple¶

Soit P(n) une propriété dépendant de n ∈ ℕ telle que P(0) soit vraie et ∀n ∈ ℕ, P(n) ⟹ P(n + 1). Alors P(n) est vraie pour tout entier naturel n.

Démonstration.

On considère A = {k ∈ ℕ | P(k)}. 0 ∈ A, et A est stable par successeur, car n + 1 est le successeur de n.

D'après l'axiome de Peano, A = ℕ : P(n) est vraie pour tout n.

Théorème Plus petit élément¶

Toute partie non vide de ℕ admet un plus petit élément.

Démonstration.

Soit A une partie de ℕ sans plus petit élément. Montrons par récurrence sur n que la propriété « aucun entier k avec k ≤ n n'est dans A » est vraie.

Pour n = 0 : si 0 ∈ A, alors 0 serait le plus petit élément de A, car 0 est inférieur à tout entier naturel.

Si c'est vrai pour n et si n + 1 ∈ A, alors n + 1 serait le plus petit élément de A, car les éléments de A sont tous supérieurs à n, donc à n + 1. C'est donc vrai pour n + 1.

Ainsi aucun entier n'est dans A : A est vide.

Théorème Plus grand élément¶

Toute partie non vide et majorée de ℕ admet un plus grand élément.

Démonstration.

Soit A une partie non vide et majorée de ℕ. L'ensemble de ses majorants est une partie non vide de ℕ : d'après le théorème du plus petit élément, il a un plus petit élément m.

Supposons m ∉ A. Comme A n'est pas vide, il contient un a avec a ≤ m et a ≠ m, donc m > 0. Alors tout a ∈ A vérifie a ≤ m − 1 : m − 1 serait un majorant plus petit que m, ce qui est impossible.

Donc m ∈ A : m est le plus grand élément de A.

Théorème Principe de récurrence, sans Peano¶

Une autre présentation de ℕ ne part pas des axiomes de Peano, mais prend comme axiome la propriété du plus petit élément. Le principe de récurrence devient alors un théorème, démontré ainsi.

Soit P(n) une propriété dépendant de n ∈ ℕ telle que P(0) soit vraie et ∀n ∈ ℕ, P(n) ⟹ P(n + 1). Alors, pour tout entier naturel n, P(n) est vraie.

Démonstration.

Supposons la conclusion fausse : il existe n₀ tel que ¬P(n₀).

On considère alors A = {k ∈ ℕ | ¬P(k)}.

0 ∉ A et d'autre part A est une partie non vide de ℕ (n₀ ∈ A).

D'après l'axiome du plus petit élément, A admet un plus petit élément k₀, et k₀ > 0, donc k₀ − 1 ∉ A.

Donc P(k₀ − 1) est vraie. Or ∀n ∈ ℕ, P(n) ⟹ P(n + 1), donc P(k₀) est vraie.

C'est une contradiction.

Parties de ℕ¶

Définition Les entiers naturels non nuls¶

ℕ^* est l'ensemble des entiers naturels non nuls : ℕ^* = {n ∈ ℕ | n ≠ 0}.

Définition Les entiers naturels positifs¶

ℕ₊ est l'ensemble des entiers naturels positifs. Tout entier naturel est positif, donc ℕ₊ = ℕ.

Définition Les entiers naturels strictement positifs¶

ℕ₊^* est l'ensemble des entiers naturels strictement positifs, c'est-à-dire non nuls : ℕ₊^* = ℕ^*.