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

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

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

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

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

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

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 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

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.