Sedrikov

Induction et CoInduction

L'induction et la coinduction sont des concepts de structure que l'on retrouve dans les notions de (co)récurrence, et (co)récursion pour définir des objets (pas nécessairement) infinis, mais surtout dont la structure contient des motifs identiques à des échelles différentes (un peu comme les objets fractals).

Les notions liées à la (co)induction sont:

• structurelles (structure (co)inductive)
• fonctionnelles (fonctions (co)inductives)
• probatoires (preuve par (co)induction)

Les fonctions et les preuves sont traitées simultanément en vertu de la correspondance de Curry-Howard.

La coinduction étant un peu plus technique, elle n'est que survolée dans l'aperçu.

Aperçu

Un cas concret: les dominos

On se donne un jeu de dominos que l'on pose verticalement les uns derrière les autres afin de déclencher une réaction en chaîne (effet domino).

(P)Pour s'assurer que tout le monde tombera quand on poussera le premier domino, il faut s'assurer que tout domino qui tombe entraine le suivant dans sa chute.

Cet énoncé manque quelque peu de formalisme:

• "Que veut dire premier?"
• "Que veut dire suivant?"
• "Comment s'assurer que cet énoncé est valide?"

En fait tel quel, (P) n'est valide que dans le cas inductif, dans un cas coinductif, il n'est plus valide.

Pour être plus formel nous allons dire que tout domino est:

• (A)soit un domino particulier $O$ (le "premier")
• (B)soit le domino suivant un domino $D$ défini, $S(D)$ (le "suivant")

Cette définition est inductive si elle vérifie la propriété selon laquelle on peut passer de tout domino au premier en un nombre fini d'étapes.

Toutes les définitions de dominos ne vérifient pas cette propriété, on pourrait très bien autoriser à un domino $D_{a}$ d'être le successeur de $D_{b}$ qui serait successeur de $D_{c}$ qui serait successeur de $D_{a}$; on aurait alors une boucle, et aucun de ceux ci ne tomberaient quand $O$ serait poussé; ou encore avoir une infinité de dominos de suite auquel cas un domino $D_{\omega +1}$ pourrait ne jamais tomber.

L'ensemble inductif est le plus petit des ensembles vérifiant (A) et (B); le coinductif est le plus grand; il existe d'autres formulations que l'on trouvera par la suite.

Les dominos sont des entiers

Une autre façon de voir ces dominos est simplement de leur associer un entier:

• $O$ devient $D_{0}$
• si $D$ devient $D_{n}$, alors $S(D)$ devient $D_{n+1}$

Ceci définit une fonction $\pi$.

On a alors $\pi (O)=D_{0}$, $\pi (S(O))=D_{1}$, $\pi (S(S(O)))=D_{2}$, etc...

Et réciproquement à tout domino indicé par un entier je peux lui associer un domino dans la représentation initiale (si j'en ai assez):

• $D_{0}$ devient $O$
• si $D_{n}$ devient $D$, alors $D_{n+1}$ devient $S(D)$

Ceci définit une fonction $\rho$ et $\pi \circ \rho =id$.

Les dominos "sont" donc des entiers.

En fait ce n'est pas étonnant puisque tout entier est:

• (A')soit $0$
• (B')soit $1+(n)$, le successeur de l'entier $n$

de manière inductive (axiomatique de Peano).

Lien avec la récurrence

Après cette description de la structure des dominos, il faut être en mesure de l'utiliser, c'est à dire pouvoir définir des fonctions et des preuves sur ces structures.

Etant donné un ensemble $E$ (à au moins deux éléments), il existe une infinité de fonctions des dominos dans $E$; malheureusement beaucoup d'entre elles ne sont pas descriptibles (cf. ensemble récursif), on va donc s'intéresser à un fragment de ces fonctions: les fonctions récursives.

Comme le suggère la structure des dominos en deux cas (A) et (B), il suffit de définir notre fonction $f$ des dominos vers $E$ sur chacun de ces cas; c'est la construction par récurrence:

• (RA) on se donne $e_{O}\in E$, et on pose $f(O)=e_{O}$
• (RB) on se donne $e_{S}\in E\rightarrow E$ et on pose $f(S(D))=e_{S}(f(D))$

Ceci définit récursivement notre fonction.

En programmation fonctionnelle, on peut même parfois définir une fonction $Rec\_domino$ de type:

$\forall E,(E\times (E\rightarrow E))\rightarrow (domino\rightarrow E)$, telle que $f=Rec\_domino(e_{O},e_{S})$.

On peut encore généraliser cela au cas où $E$ dépend du domino, et définir par récurrence une fonction dont le type est: $\forall (D:domino),E(D)$ par:

• (RA') on se donne $e_{O}\in E(O)$, et on pose $f(O)=e_{O}$
• (RB') on se donne $e_{S}\in \forall D,E(D)\rightarrow E(S(D))$ et on pose $f(S(D))=e_{S}(f(D))$

Dans ce contexte, $Rec\_domino$ a pour type: $\forall E,(E(O)\times (\forall D,E(D)\rightarrow E(S(D))))\rightarrow (\forall D,E(D))$.

En utilisant notre association entre domino et entiers, on obtient:

$\forall P,P(0)\times (\forall n,P(n)\rightarrow P(1+(n)))\rightarrow (\forall n,P(n))$,

type que les mathématiciens ont l'habitude de voir écrit:

$\forall P,P(0)\wedge (\forall n,P(n)\Rightarrow P(1+n))\Rightarrow \forall n,P(n)$;

c'est l'axiome de récurrence.

La propriété (P) énoncée au début de cette partie se démontre donc dans le cas inductif grâce à $Rec\_domino(P)$ qui s'écrit aussi:

$P(O)\wedge (\forall D,P(D)\Rightarrow P(S(D))))\Rightarrow \forall D,P(D)$

et qui exprime:

Si je sais prouver que:

• "quand $O$ tombe, $O$ tombe" ($P(O)$)

et que: ($\wedge$)

• pour tout $D$, ($\forall D,$)
  • si je sais prouver que:
    • "quand $O$ tombe, $D$ tombe" ($P(D)$)
  • alors je sais prouver que: ($\Rightarrow$)
    • "quand $O$ tombe, $S(D)$ tombe" ($P(S(D))$)

alors je sais prouver que: ($\Rightarrow$)

• pour tout $D$, ($\forall D,$)
  • "quand $O$ tombe, $D$ tombe" ($P(D)$)

Rappel: cet axiome, n'est pas valide en coinduction.

Un autre cas concret: l'avalanche

Le cas précédent montre que la récurrence n'est qu'une forme d'induction, on va ici utiliser une forme plus intéressante.

Une pré-avalanche est soit:

• (AA) une boule de neige, notée $L$
• (AB) deux pré-avalanches déclenchables par une boule de neige, notée $N$

Exemples:

• Une boule seule: $L$
• Une petite avalanche: $N(L,L)$
• Une autre avalanche: $N(N(L,L),L)$

Cette fois ci, l'induction consiste en les avalanches finies (qui se terminent toujours en déclenchant une boule $L$).

La coinduction mène à des avalanches très exotiques dont certaines parties terminent en déclenchant $L$, d'autres parties bouclent en se déclenchant elle-même, et d'autres ne finissent jamais.

Les avalanches sont des arbres

En informatique cette structure d'avalanche et celle d'arbre binaire; c'est une structure avec deux constructeurs:

• $L$ est d'arité 0, c'est la partie terminale de la structure
• $N$ est d'arité 2 et prend 2 arbres en arguments, elle permet de réunir deux arbres

Plus puissant que la réccurrence?

Le principe d'induction est cette fois ci le suivant:

$\forall E,(E\times ((E\times E)\rightarrow E))\rightarrow (pre\_avalanche\rightarrow E)$

(sans dépendance)

ou: $\forall E,(E(L)\times (\forall p_{1}p_{2},(E(p_{1})\times E(p_{2}))\rightarrow E(N(p_{1},p_{2}))))\rightarrow (\forall p,E(p))$

(avec dépendance),

et on a donc l'axiome d'induction: $\forall P,P(L)\wedge (\forall p_{1}p_{2},P(p_{1})\wedge P(p_{2})\Rightarrow P(N(p_{1},p_{2})))\Rightarrow \forall p,P(p)$

On peut se ramener au raisonnement par récurrence sur les entiers, mais cela oblige à définir une fonction de profondeur de l'arbre; puis raisonner par récurrence sur cette profondeur.

En règle générale, tout raisonnement par induction peut se prouver par récurrence sur les entiers (la réciproque est évidente, puisque la récurrence est l'induction sur les entiers comme vu avec les dominos), mais cela implique la définition d'une fonction $\mu$, de mesure de nos structures vers les entiers (heureusement pas nécessairement injective), puis faire une récurrence sur $\mu$ appliquée à notre structure.

L'induction n'est donc pas plus puissante que la récurrence, elle est juste d'une utilisation plus aisée.

Une structure courante de coinductif: le flux

Les parties précédentes portaient sur les inductifs et peu des coinductifs; il n'en est question ici que pour présenter une structure coinductive tant utilisée en mathématiques qu'en informatique: celle du flux.

Un flux sur $A$ est:

• un élément $a$ de $A$ suivi de d'un flux $f$ sur $A$, noté $a\mapsto f$

C'est tout.

La version inductive du flux n'est pas très intéressante; c'est l'ensemble vide, en effet, cet ensemble vérifie cette propriété ("pour tout élément de A et tout élément de l'ensemble vide, je peux construire un élément de l'ensemble vide") et c'est le plus petit.

Noter que:

• dans la version des dominos, l'ensemble vide ne vérifie pas (A): $O\notin \emptyset$
• dans la version des pré-avalanches, l'ensemble vide ne vérifie pas (AA): $L\notin \emptyset$
• on peut prouver $\forall f\in flux\_inductif\_sur\_A,Faux$ en utilisant l'axiome d'induction $(\forall af,P(f)\Rightarrow P(a\mapsto f))\Rightarrow \forall f,P(f)$ avec $P(f)=Faux$

L'objet coinductif, lui, a soit aucun élément ($A=\emptyset$), soit un unique élément $eee...$ ($A=\lbrace e\rbrace$), soit une infinité non dénombrable d'éléments.

En mathématiques, il peut représenter les suites (au lieu de les représenter par une fonction), les p-adiques, les développements dans une base...

Mais si on ne peut pas raisonner par induction dessus, on peut tout de même l'utiliser pour construire d'autres coinductifs par coinduction.

Les fonctions corécursives ont la propriété que chacun de leurs appels récursifs doivent produire un constructeur, dont les arguments pourront être évalués paresseusement.

Par exemple, le flux $i(n)$ des entiers positifs supérieurs à $n$ se définit par:

• $i(n)=n\mapsto i(1+n)$

Théorie

Liens internes

• Type algébrique de données
• Raisonnement par récurrence
• Définition par récurrence
• Relation bien fondée

catégorie:Algèbre]]