Induction structurelle

En mathématiques et davantage en informatique, la définition récursive ou induction structurelle est un procédé de définition conjointe d'un type (classe ou ensemble) et d'objets (éléments) qui le compose au moyen de règles de construction (constructeurs) qui agencent ou structurent ces objets.

L'on peut ainsi définir des nombres, des listes, des arbres, des relations, et plus généralement, toute structure mathématique (langage, système, …). En permettant par le même principe de définir un prédicat total^[pas clair] i.e. qui est défini partout, l'induction structurelle est aussi une méthode de démonstration d'une propriété sur une structure.

Outils mathématiques et informatiques

Les système, langages et logiciels supportant à des degrés divers cette fonctionnalité sont nombreux.

L'un des plus puissants est le calcul des constructions inductives (CIC) et son logiciel Coq.

Caractéristiques

La définition récursives se distingue de la "macro" et de la définition algébrique en cela qu'elle est la seule créatrice d'objets. La « macro » n'est qu'un raccourci de langage (i.e., une notation), alors que la définition algébrique « quotiente » ou contraint et restreint un type préexistant ((en) carier) au moyen d'axiomes. En revanche, la définition inductive engendre ex nihilo ses objets. Les règles de construction sont donc procréatrice.

Ainsi contrairement à l'axiome, les règles de construction d'une récurrence bien fondée ne peuvent créer l'incohérence.

De plus, tout objet appartient à une génération. Dans le cas le plus général, cette génération est un entier ou un ordinal. Le nombre de générations peut donc être ${\displaystyle \omega }$, fini … nulle (types vide) ou ne pas être.

La validité de l'induction découle du caractère bijectif du procédé de procréation :

• injectivité : à construction différente, objet différent ;
• surjectivité : tout objet a une construction.

L'induction structurelle est une généralisation de la récurrence traditionnelle.

Exemples

Les fonctions définies par récurrence structurelle généralisent les fonctions définies par récurrence sur les entiers.

Les listes

Les listes sont définies comme étant

• soit la liste vide [ ],
• soit la liste obtenue par la mise en tête d'une liste ${\displaystyle \ell }$ d'un élément a, ce qui donne a : ${\displaystyle \ell }$.

La fonction length qui définit la longueur d'une liste se définit par induction structurelle :

• length ([ ]) = 0
• length (a : ${\displaystyle \ell }$) = 1 + length (${\displaystyle \ell }$).

La fonction concat qui concatène deux listes ${\displaystyle \ell _{1}}$ et ${\displaystyle \ell _{2}}$

• concat ([ ], ${\displaystyle \ell _{2}}$) = ${\displaystyle \ell _{2}}$
• concat (a : ${\displaystyle \ell _{1}}$, ${\displaystyle \ell _{2}}$) = a : (concat(${\displaystyle \ell _{1}}$, ${\displaystyle \ell _{2}}$))

On peut démontrer par induction structurelle la proposition suivante :

length(concat(${\displaystyle \ell _{1},\ell _{2}}$)) = length(${\displaystyle \ell _{1}}$) + length(${\displaystyle \ell _{2}}$).

Première étape

length(concat([ ], ${\displaystyle \ell _{2}}$)) = length(${\displaystyle \ell _{2}}$) = 0 + length(${\displaystyle \ell _{2}}$) = length([ ]) + length(${\displaystyle \ell _{2}}$)

Deuxième étape La démonstration utilise l'hypothèse d'induction structurelle

length(concat(a : ${\displaystyle \ell _{1}}$, ${\displaystyle \ell _{2}}$)) = length(a : concat(${\displaystyle \ell _{1}}$, ${\displaystyle \ell _{2}}$)) = 1 + length(concat(${\displaystyle \ell _{1}}$, ${\displaystyle \ell _{2}}$))

= (par hypothèse d'induction structurelle) 1+ length(${\displaystyle \ell _{1}}$) + length(${\displaystyle \ell _{2}}$) = length(a:${\displaystyle \ell _{1}}$) + length(${\displaystyle \ell _{2}}$)

Les arbres binaires

Considérons les arbres binaires définis ainsi :

• ${\displaystyle \Box }$ pour l'arbre vide,
• B${\displaystyle _{1}}$ ${\displaystyle \bullet }$ B${\displaystyle _{2}}$ pour un arbre non vide ayant pour sous-arbre gauche B${\displaystyle _{1}}$ et pour sous-arbre droit B${\displaystyle _{2}}$.

On peut définir la fonction taille (le nombre de nœuds internes de l'arbre binaire) :

• taille(${\displaystyle \Box }$) = 0
• taille(B${\displaystyle _{1}}$ ${\displaystyle \bullet }$ B${\displaystyle _{2}}$) = taille(B${\displaystyle _{1}}$) + taille(B${\displaystyle _{2}}$) + 1

Principes

Considérons une structure définie par des constructeurs ${\displaystyle f_{1},...,f_{n}}$ d'arité ${\displaystyle a_{1},...,a_{n}}$. Les constructeurs d'arité 0 sont des constantes.

Définition par induction structurelle

La définition par induction structurelle d'une fonction ${\displaystyle g}$ s'écrit pour chaque constructeur ${\displaystyle f_{i}}$

• ${\displaystyle g(f_{i}(x_{1},..x_{a_{i}}),y_{1},...y_{n})=E_{i}(g(x_{1}),...,g(x_{a_{i}}),y_{1},...,y_{n})}$

où ${\displaystyle E_{i}}$ est une expression qui dépend de i'. On remarque que si ${\displaystyle f_{i}}$ est une constante, la définition est celle d'un cas de base:

• ${\displaystyle g(f_{i},y_{1},...y_{n})=E_{i}(y_{1},...,y_{n})}$

Raisonnement par induction structurelle

Le schéma de démonstration qu'une propriété P est valide sur toute une structure se présente sous la forme d'une règle d'inférence pour chaque constructeur ${\displaystyle f_{i}}$

${\displaystyle {\frac {P(x_{1})...P(x_{a_{i}})}{P(f_{i}(x_{1},...,x_{a_{i}}))}}}$

Il faut donc faire une démonstration d'« hérédité » pour chaque constructeur.

Le cas des entiers naturels

Le cas des entiers naturels est celui où il y a deux constructeurs: 0 d'arité 0 (donc une constante) et succ (autrement dit +1) d'arité 1. La récurrence traditionnelle se réduit donc à une récurrence structurelle sur ces deux constructeurs.

La coinduction

Grossièrement la coinduction étend l'induction en offrant la possibilité d'omettre les éléments initiaux (le jardin d'éden).

Par exemple, omettre la liste vide, transforme la liste en flux ((en) stream). : Un flux de trucs est un truc qui s'ajoute à flux de trucs.

Bibliographie

• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Reading Mass, Addison-Wesley, 2001, 2nd éd., 521 p. (ISBN 0-201-44124-1)
• (en) R.M. Burstall, « Proving Properties of Programs by Structural Induction », The Computer Journal, vol. 12, n^o 1,‎ février 1968, p. 41–48 (DOI 10.1093/comjnl/12.1.41, lire en ligne)
• Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1985 (lire en ligne)
• Horst Reichel, Structural induction on partial algebras, Akademie-Verlag, 1984
• Jason Filippou, « Structural Induction », 7 mai 2016
• Rozsa Peter, Über die Verallgemeinerung der Theorie der rekursiven Funktionen für abstrakte Mengen geeigneter Struktur als Definitionsbereiche, Symposium International, Varsovie (septembre 1959) (Sur la généralisation de la théorie des fonctions récursives à des ensembles abstraits avec, comme domaines, des structures adaptées).

Voir aussi

• Forme de Backus-Naur
• Type récursif
• Définition par récurrence
• Ordre bien fondé
• Raisonnement par récurrence
• Récurrence transfinie
• Terme (logique)