## [Principe de L'Induction Mathématique](/fr/node/60960) Définition Principe de preuve fondamental affirmant qu'une propriété P(n) des entiers naturels vaut pour tout n∈ℕ si (i) P(0) est vraie (cas de base) et (ii) pour tout k, P(k)⇒P(k+1) est vraie (fermeture par successeur). Ici il est présenté comme le schéma qui transforme un raisonnement local en une affirmation universelle sur la suite des naturels. ## Principe Principe Si un ensemble S⊆ℕ contient 0 et est fermé par successeur (k∈S⇒k+1∈S), alors S=ℕ ; de façon équivalente, établir un cas de base et une étape de préservation donne une preuve pour tous les entiers naturels. ## Démonstration Démonstration Pour prouver que tout nombre naturel n vérifie n+0=n, établir le cas de base n=0 : 0+0=0, puis supposer pour un k arbitraire que k+0=k et montrer que (k+1)+0=k+1 en utilisant la définition du successeur et l'égalité supposée ; base et étape se combinent pour couvrir tous les n par induction. ## Mauvaise application Mauvaise application Appliquer le schéma sans vérifier un cas de base valide, utiliser une hypothèse d'induction dépendant de davantage d'informations que permis (par ex. supposer P(m) pour m>k lors de la preuve de P(k+1)), ou tenter d'utiliser l'induction ordinaire sur des domaines dépourvus de structure successeur bien définie (ensembles non bien fondés) conduit à des conclusions non valides. ## Conséquence Conséquence Une application correcte convertit une vérification finie (cas de base et étape) en une infinité d'énoncés vrais pour tous les entiers naturels ; elle soutient de nombreuses définitions et preuves en arithmétique, combinatoire et informatique, et engendre des variantes utiles comme l'induction forte et l'induction structurelle. ## Inversion Inversion L'idée inverse est le principe d'existence d'un contre-exemple : trouver un n tel que ¬P(n) réfute l'universalité de P ; conceptuellement, la négation de l'induction produit une réfutation finie plutôt qu'une preuve universelle. Une autre opposition est la descente infinie qui montre l'impossibilité en produisant un contre-exemple toujours plus petit. ## Limite Limite S'applique aux propriétés sur ℕ (ou toute structure inductive de type Peano) munie d'un zéro et d'un successeur ; il ne se transporte pas automatiquement aux ensembles ordonnés arbitraires, aux propositions sur les réels, ni aux domaines sans bien-fondation sans être remplacé par une induction bien-fondée ou structurelle adaptée. ## Tension sémantique Tension sémantique Tension avec l'induction forte et l'induction structurelle : l'induction ordinaire n'autorise que l'hypothèse sur le prédécesseur immédiat tandis que l'induction forte permet d'assumer tous les cas plus petits ; les deux sont équivalents sur ℕ mais diffèrent en méthode, ce qui prête à confusion sur la forme d'induction implicite. ## Synthèse Synthèse Le Principe de l'Induction Mathématique relie une vérification locale (cas de base et étape au successeur) à une assertion globale sur ℕ : vérifier la base et la fermeture par successeur transforme un raisonnement pas à pas en preuve valable pour tout entier naturel, avec des variantes contrôlées selon la structure du domaine.