Лист за преговор: Construction rigoureuse de l'ensemble des entiers naturels

📋 Plan du Cours

1. Construction de l’ensemble des entiers naturels
2. Axiomes de Peano et modèle de N
3. Définition par récurrence des suites
4. Définition de l’addition et de la multiplication
5. Ordre sur N et propriétés du bon ordre
6. Axiomes de l’ordre et équivalence avec Peano
7. Récurrence simple et principe de propagation
8. Récurrence forte et récurrence double
9. Ordres bien fondés et récurrence bien fondée

📖 1. Construction de l’ensemble des entiers naturels

🔑 Notions clés & Définitions

• Entiers comme ordinaux : Notion d’entier définie en théorie des ensembles via la structure d’ordinal, où chaque entier correspond à un ensemble bien ordonné.
• 0 = ∅ : Définition ensembliste de 0 comme l’ensemble vide, servant de base à la construction de N.
• 1 = ∅ ∪ {∅} : Définition ensembliste de 1 à partir de 0, en ajoutant 0 comme élément à l’ensemble vide.
• 2 = {0, 1} : Représentation ensembliste de 2 comme l’ensemble des entiers précédents, illustrant l’idée {0,1}.
• N plus petit ensemble : Ensemble N défini comme le plus petit ensemble contenant tous les entiers construits, noté N.

📝 Points essentiels

• La construction part de la théorie des ensembles avec 0 = ∅ puis 1 = ∅ ∪ {∅} et ainsi de suite.
• La notion d’entier est reliée aux ordinaux, par exemple 3 = {0, 1, 2}.
• On montre qu’il existe un unique ensemble noté N qui est le plus petit contenant tous les entiers construits.
• La construction vise à obtenir un ensemble N qui servira ensuite de support aux axiomes de Peano.
• L’objectif est de donner une définition rigoureuse de N avant d’étudier ses propriétés (ordre, récurrence, opérations).

💡 Astuce mémo

Ordinal = ensemble des prédécesseurs : 3 = {0,1,2}.

📖 2. Axiomes de Peano et modèle de N

🔑 Notions clés & Définitions

• Axiomes de Peano : Ensemble minimal de propriétés caractérisant les entiers naturels à partir de 0 et d’un successeur.
• Successeur s : Fonction s : N → N  {0} qui associe à chaque entier son entier suivant.
• Modèle des axiomes de Peano : Situation où un ensemble muni de 0 et d’une fonction successeur vérifie toutes les propriétés minimales de Peano.
• Injectivité de s : Propriété selon laquelle deux entiers différents ont deux successeurs différents.
• Clôture par successeur : Condition sur un sous-ensemble A de N : contenant 0 et stable par s, ce qui force A à être tout N.

📝 Points essentiels

• (P0) 0 ∈ N : l’entier de base appartient à N.
• (P1) Pour tout n ∈ N, le successeur s(n) n’est pas égal à 0.
• (P2) La fonction s est injective.
• (P3) Si A ⊂ N contient 0 et est clos par s (n ∈ A ⇒ s(n) ∈ A), alors A = N.
• Proposition 2.1 : s est surjective sur N  {0}, donc pour tout n ≠ 0 il existe m ∈ N tel que n = s(m).

💡 Astuce mémo

P3 = clôture : si A contient 0 et suit le successeur, alors A = N.

📖 3. Définition par récurrence des suites

🔑 Notions clés & Définitions

• Définition d’une suite par récurrence : Construction d’une suite (u_n) à partir d’une valeur initiale u0 et d’une règle d’évolution u_{n+1} = f(u_n).
• Unicité de la suite : Propriété selon laquelle deux suites vérifiant les mêmes conditions initiale et récurrente coïncident.
• Existence du graphe : Approche rigoureuse consistant à montrer l’existence du graphe G(u) = {(n,u_n), n ∈ N}.
• Fonction f : E → E : Fonction qui transforme chaque terme u_n en le terme suivant u_{n+1}.
• Axiome (P3) pour l’égalité : Utilisation de la clôture par successeur pour prouver que deux suites coïncident sur tout N.

📝 Points essentiels

• Proposition 2.2 : pour tout ensemble E, tout a ∈ E et toute fonction f : E → E, il existe une unique suite (u_n) dans E.
• La suite est caractérisée par u0 = a et pour tout n ∈ N, u_{n+1} = f(u_n).
• Unicité : si (u) et (v) satisfont les conditions, on définit A = {n ∈ N ; u_n = v_n} et on montre que A = N via (P3).
• Pour appliquer (P3), on vérifie d’abord 0 ∈ A car u0 = v0 = a.
• On montre ensuite la clôture : si k ∈ A alors u_{k+1} = f(u_k) = f(v_k) = v_{k+1}, donc k+1 ∈ A.
• Existence : la rigueur passe par l’existence du graphe G(u) ⊂ N × E, ce qui revient à construire la suite.

💡 Astuce mémo

u_{n+1} = f(u_n) : une règle + un départ donnent une suite unique.

📖 4. Définition de l’addition et de la multiplication

🔑 Notions clés & Définitions

• Addition sur N : Opération sur les entiers définie à partir de suites construites par récurrence.
• Multiplication sur N : Opération sur les entiers définie à partir de suites construites par récurrence.
• Suites définies par récurrence : Outil permettant de définir des opérations (addition, multiplication, puissance, factorielle) via une relation de passage au terme suivant.
• Puissance : Opération sur N annoncée comme définissable par le même mécanisme de récurrence que l’addition et la multiplication.
• Factorielle : Opération sur N annoncée comme définissable par récurrence, en cohérence avec la construction des entiers.

📝 Points essentiels

• Le cours annonce que l’addition et la multiplication sont définies via des suites construites par récurrence.
• Les applications mentionnent explicitement addition, multiplication, puissance et factorielle comme exemples de définitions récurrentes.
• Les exercices portent sur la démonstration des propriétés usuelles de l’addition et de la multiplication par récurrence.
• La section relie donc la définition des opérations à la méthode de preuve par récurrence.
• Aucun détail de formule (récurrence exacte) n’apparaît dans l’extrait fourni, mais la méthode de définition est explicitement annoncée comme récurrente.

💡 Astuce mémo

Opérations = suites récurrentes : addition/multiplication suivent la même logique.

📖 5. Ordre sur N et propriétés du bon ordre

🔑 Notions clés & Définitions

• Relation n ≤ m : Relation définie sur N par l’existence d’un décalage additif entre n et m.
• Définition par addition : Idée que n ≤ m signifie que m s’obtient en ajoutant un certain p à n.
• Ordre total : Propriété d’une relation d’ordre où deux éléments sont toujours comparables.
• Bon ordre : Propriété d’un ordre où toute partie non vide possède un plus petit élément.
• Compatibilité avec addition et multiplication : Propriété annoncée selon laquelle l’ordre se comporte bien vis-à-vis des opérations arithmétiques.

📝 Points essentiels

• Définition 2.3 : pour n, m ∈ N, on a n ≤ m s’il existe p ∈ N tel que m = n + p.
• Théorème 2.4 : la relation ≤ est un ordre sur N (réflexive, antisymétrique, transitive).
• Cet ordre est total : pour tous n, m ∈ N, on a n ≤ m ou m ≤ n.
• Cet ordre est un bon ordre : toute partie non vide admet un plus petit élément.
• Proposition 2.5 : N n’admet pas de plus grand élément.
• Proposition 2.5 : toute partie majorée admet un plus grand élément, et il n’existe pas de suite infinie strictement décroissante.

💡 Astuce mémo

n ≤ m ⇔ m = n + p : l’ordre mesure un “reste” p.

📖 6. Axiomes de l’ordre et équivalence avec Peano

🔑 Notions clés & Définitions

• Axiomes O1 O2 O3 : Ensemble de conditions sur un ensemble ordonné (E, ≤) garantissant une structure comparable à celle de N.
• Successeur d’un élément : Pour x ∈ E, le successeur s(x) est le plus petit majorant de x, s’il existe.
• Bien ordonné : Propriété d’un ordre où toute partie non vide admet un plus petit élément.
• Équivalence avec Peano : Résultat reliant les axiomes de l’ordre (O1–O3) aux axiomes de Peano sur (E, 0, s).
• Plus petit élément noté 0 : Dans un ordre bien fondé, l’élément minimal est noté 0 et sert de base à la structure.

📝 Points essentiels

• Axiome (O1) : (E, ≤) est bien ordonné et admet donc un plus petit élément noté 0.
• Axiome (O2) : tout élément de E admet un successeur s(x).
• Axiome (O3) : tout élément non nul est le successeur d’un autre élément.
• Le cours indique que N satisfait ces trois axiomes de l’ordre.
• Réciproquement (Proposition 2.6) : si (E, ≤) vérifie O1, O2, O3, alors (E, 0, s) vérifie les axiomes de Peano.
• La définition de s(x) repose sur l’ensemble des majorants de x : s(x) est le plus petit de ces majorants.

💡 Astuce mémo

O1 bien ordonné donne 0 ; O2 donne un successeur ; O3 dit que tout non-0 vient d’un successeur.

📖 7. Récurrence simple et principe de propagation

🔑 Notions clés & Définitions

• Récurrence simple : Principe où la vérité d’une propriété se propage de n à n+1 à partir d’un rang initial n0.
• Propriété H(n) : Énoncé dépendant de l’entier n, dont on cherche à établir la validité pour tous les n ≥ n0.
• Hypothèse initiale H(n0) : Point de départ de la récurrence : la propriété est vraie au rang initial n0.
• Implication H(n) ⇒ H(n+1) : Condition de propagation : si la propriété est vraie à n, elle l’est aussi à n+1.
• Conclusion pour tout n ≥ n0 : Résultat final : la propriété est vraie pour tous les entiers à partir du rang initial.

📝 Points essentiels

• Théorème 3.1 : si H(n0) est vraie et si pour tout n ≥ n0 on a H(n) ⇒ H(n+1), alors H(n) est vraie pour tout n ≥ n0.
• La forme logique donnée est (H(n0) ∧ ∀k ≥ n0 (H(k) ⇒ H(k+1))) ⇒ ∀n ≥ n0 H(n).
• La récurrence simple ne demande qu’un pas de progression entre n et n+1.
• Le cours précise que H(n) porte sur un entier n et que n0 est un entier de départ.
• La conclusion porte sur tous les entiers supérieurs ou égaux à n0, pas seulement sur une suite finie.

💡 Astuce mémo

Départ + pas : H(n0) et H(n)→H(n+1) ⇒ H partout après n0.

📖 8. Récurrence forte et récurrence double

🔑 Notions clés & Définitions

• Récurrence forte : Variante où l’étape de preuve à n+1 peut utiliser la validité de la propriété pour tous les rangs ≤ n.
• Récurrence double : Variante de récurrence mentionnée comme alternative, traitée sur une feuille de TD dans le cours.
• Propriété P(n) : Énoncé dépendant de n utilisé dans la récurrence forte pour établir une conclusion pour tous les entiers.
• Conjonction P(0) ∧ ... ∧ P(k) : Hypothèse cumulative utilisée dans la récurrence forte : la propriété est vraie pour tous les indices jusqu’à k.
• Étape k+1 : Conclusion intermédiaire de la récurrence forte : à partir des cas ≤ k, on obtient P(k+1).

📝 Points essentiels

• La récurrence forte est donnée par Proposition 3.2 : si P(0) et si (P(0) ∧ P(1) ∧ · · · ∧ P(k)) ⇒ P(k+1), alors P(n) pour tout n ∈ N.
• Le cours réécrit l’idée via Q(n) = P(0) ∧ P(1) ∧ · · · ∧ P(n) pour organiser la preuve.
• La condition porte sur tous les k ∈ N, pas seulement sur un intervalle limité.
• La récurrence double est renvoyée à une feuille de TD (aucun énoncé n’est fourni dans l’extrait).
• La récurrence forte permet d’utiliser plusieurs hypothèses antérieures simultanément, via la conjonction jusqu’à k.

💡 Astuce mémo

Forte = “tous les ≤ k” servent pour prouver “k+1”.

📖 9. Ordres bien fondés et récurrence bien fondée

🔑 Notions clés & Définitions

• Ordre bien fondé : Ordre où il n’existe aucune suite infinie strictement décroissante.
• Suite strictement décroissante : Suite (a_n) telle que chaque terme est strictement plus petit que le précédent selon l’ordre.
• Bon ordre : Propriété où toute partie non vide possède un élément minimal (plus petit élément).
• Élément minimal : Élément a ∈ A tel qu’il n’existe pas dans A d’élément strictement plus petit que a.
• Équivalence bien fondé et bon ordre : Résultat reliant deux notions d’ordre lorsque l’ordre est total.

📝 Points essentiels

• Définition 3.3 : l’ordre ≤′ est bien fondé s’il n’existe pas de suite infinie strictement décroissante dans E.
• Proposition 3.4 : si l’ordre est total, alors bien fondé ssi bon ordre.
• La preuve utilise l’absence de suite décroissante pour montrer que bon ordre implique bien fondé.
• La réciproque se fait par contraposé : si un ordre total bien fondé n’est pas bon, on construit une suite décroissante.
• La construction suppose l’existence d’un sous-ensemble non vide A sans plus petit élément, puis on choisit x0 ∈ A et on construit x1, x2, ... avec x_{i+1} < x_i.
• Définition 3.5 : a ∈ A est minimal si aucun élément de A n’est strictement plus petit que a, et en ordre partiel il peut y avoir plusieurs minimaux.

💡 Astuce mémo

Bien fondé = pas de descente infinie ; bon ordre = chaque non-vide a un minimal.

📊 Tableaux de synthèse

Équivalence ordre bien fondé et bon ordre

⚠️ Pièges & confusions fréquents

1. Confondre la définition de n ≤ m (existence de p avec m = n + p) avec une comparaison “directe” sans addition.
2. Penser que (P3) dit seulement que s est injective : (P3) est une propriété de clôture qui force A = N.
3. Croire que l’unicité de la suite par récurrence se prouve sans utiliser (P3) : le cours construit A = {n ; u_n = v_n} puis applique (P3).
4. Mélanger “bon ordre” et “bien fondé” : ils coïncident seulement quand l’ordre est total (Proposition 3.4).
5. Oublier que la récurrence forte utilise une hypothèse cumulative (P(0) ∧ ... ∧ P(k)), pas seulement P(k).
6. Penser que “élément minimal” signifie “plus petit élément” en tout cas : en ordre partiel, il peut y avoir plusieurs éléments minimaux.

✅ Checklist Examen

1. Savoir reconstruire N à partir de la théorie des ensembles (0 = ∅, 1 = ∅ ∪ {∅}, et l’idée d’ordinal comme ensemble des prédécesseurs).
2. Connaître les axiomes (P0)-(P3) de Peano et comprendre la clôture par successeur (P3).
3. Savoir énoncer la surjectivité de s : tout n ≠ 0 s’écrit n = s(m).
4. Savoir énoncer la proposition de définition par récurrence d’une suite : u0 = a et u_{n+1} = f(u_n) donnent une unique suite.
5. Savoir définir l’ordre sur N : n ≤ m ⇔ ∃p ∈ N, m = n + p.
6. Savoir énoncer les propriétés de l’ordre sur N : ordre total, bon ordre, pas de plus grand élément, toute partie majorée a un plus grand élément, pas de suite infinie strictement décroissante.
7. Connaître les axiomes de l’ordre (O1)-(O3) via bien ordonné, existence de successeur, et “tout non nul est successeur”.
8. Savoir énoncer la récurrence simple : H(n0) vraie et H(n) ⇒ H(n+1) pour n ≥ n0 implique H(n) pour tout n ≥ n0.
9. Savoir énoncer la récurrence forte (Proposition 3.2) avec l’hypothèse conjointe P(0) ∧ ... ∧ P(k) ⇒ P(k+1).
10. Savoir définir “ordre bien fondé” et énoncer l’équivalence avec “bon ordre” quand l’ordre est total (Proposition 3.4).
11. Savoir définir “élément minimal” et comprendre la différence avec “plus petit élément” en ordre partiel.