Type inductif

En théorie des types , un système possède des types inductifs s'il offre la possibilité de créer un nouveau type à partir de constantes et de fonctions générant des termes de ce type. Cette fonctionnalité joue un rôle similaire à celui des structures de données dans un langage de programmation et permet à une théorie des types d'intégrer des concepts tels que les nombres , les relations et les arbres . Comme son nom l'indique, les types inductifs peuvent être autoréférentiels, mais généralement uniquement de manière à autoriser la récursivité structurelle .

L'exemple classique consiste à encoder les nombres naturels à l'aide de l'encodage de Peano . Il peut être défini dans Rocq (anciennement Coq ) comme suit :

nat inductif : Type := | O : nat | S : nat -> nat .

Ici, un nombre naturel est créé soit à partir de la constante « O » (représentant zéro), soit en appliquant la fonction « S » à un autre nombre naturel. « S » est la fonction successeur qui représente l'ajout de un à un nombre. Ainsi, « S O » vaut un, « S (S O) » vaut deux, « S (S (S O)) » vaut trois, et ainsi de suite.

Depuis leur introduction, les types inductifs ont été étendus pour encoder de plus en plus de structures, tout en restant prédicatifs et en prenant en charge la récursivité structurelle.

Principe d'induction

Les types inductifs sont généralement accompagnés d'une fonction permettant de prouver leurs propriétés. Ainsi, « nat » peut être accompagné (en syntaxe Rocq) de :

nat_ind : ( pour tout P : nat -> Prop , ( P O ) -> ( pour tout n , P n -> P ( S n )) -> ( pour tout n , P n )).

En d'autres termes : pour tout prédicat « P » sur les nombres naturels, étant donné une preuve de « P ⊆ 0 » et une preuve de « P ∩ n → P ∩ (n+1) », on obtient une preuve de « pour tout n, P ∩ n ». C'est le principe d'induction classique pour les nombres naturels.

Mises en œuvre

Types W et M

Les types W sont des types bien fondés en théorie des types intuitionnistes (TTI). Ils généralisent les nombres naturels, les listes, les arbres binaires et d'autres types de données « en forme d'arbre ». Soit univers de types . Étant donné un type : famille dépendante : ${\displaystyle {\mathsf {W}}_{a:A}B(a) <semantics><mrow><mstyle><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>un</mi><mo>:</mo><mi>UN</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>un</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\mathsf {W}}_{a:A}B(a)}</annotation></semantics></math><img src=$ arité (potentiellement infinie) de chaque constructeur. Les types W (resp. les types M) peuvent également être compris comme des arbres bien fondés (resp. non bien fondés) dont les nœuds sont étiquetés par des éléments : foncteur polynomial .

Soient 0 , 1 , 2 , etc. des types finis avec des habitants 1 _1 : 1 , 1 _2 , 22 _ : 2 , etc. On peut définir les nombres naturels comme le type W ${\displaystyle \mathbb {N} :={\mathsf {W}}_{x:\mathbf {2} }f(x) <semantics><mrow><mstyle><mrow><mi>N</mi></mrow><mo>:=</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mrow><mn>2</mn></mrow></mrow></msub><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {N}</annotation></semantics></math>:={\mathsf {W}}_{x:\mathbf {2} }f(x)} <img src=$ : 2 → 2 ) = 0 (représentant le constructeur pour zéro, qui ne prend aucun argument), et 2 ) = 1 (représentant la fonction successeur, qui prend un argument).

On peut définir des listes sur un type : ${\displaystyle \operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x) <semantics><mrow><mstyle><mi>Liste</mi><mo>⁡</mo><mo>(</mo><mi>UN</mi><mo>)</mo><mo>:=</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mo>(</mo><mi>x</mi><mo>:</mo><mrow><mn>1</mn></mrow><mo>+</mo><mi>UN</mi><mo>)</mo></mrow></msub><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)}</annotation></semantics></math><img src=$ ${\displaystyle {\begin{aligned}f(\operatorname {inl} (1_{\mathbf {1} }))&=\mathbf {0} \\f(\operatorname {inr} (a))&=\mathbf {1} \end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>f</mi><mo>(</mo><mi>inl</mi><mo>⁡</mo><mo>(</mo><msub><mn>1</mn><mrow><mrow><mn>1</mn></mrow></mrow></msub><mo>)</mo><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mrow><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mi>f</mi><mo>(</mo><mi>inr</mi><mo>⁡</mo><mo>(</mo><mi>un</mi><mo>)</mo><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mrow><mn>1</mn></mrow></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}f(\operatorname {inl} (1_{\mathbf {1} }))&=\mathbf {0} \\f(\operatorname {inr} (a))&=\mathbf {1} \end{aligned}}}</annotation></semantics></math><img src=$ ₁ est le seul habitant de 1. La valeur de ${\displaystyle f(\operatorname {inl} (1_{\mathbf {1} })) <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>inl</mi><mo>⁡</mo><mo>(</mo><msub><mn>1</mn><mrow><mrow><mn>1</mn></mrow></mrow></msub><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f(\operatorname {inl} (1_{\mathbf {1} }))}</annotation></semantics></math><img src=$ ${\displaystyle f(\operatorname {inr} (a)) <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>inr</mi><mo>⁡</mo><mo>(</mo><mi>un</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f(\operatorname {inr} (a))}</annotation></semantics></math><img src=$ Le constructeur des éléments d'un type W générique ${\displaystyle {\mathsf {W}}_{x:A}B(x) <semantics><mrow><mstyle><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mi>UN</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\mathsf {W}}_{x:A}B(x)}</annotation></semantics></math><img src=$ ${\displaystyle {\mathsf {sup}}:\prod _{a:A}{\Big (}B(a) o {\mathsf {W}}_{x:A}B(x){\Big )} o {\mathsf {W}}_{x:A}B(x). <semantics><mrow><mstyle><mrow><mrow><mi>s</mi><mi>vous</mi><mi>p</mi></mrow></mrow><mo>:</mo><munder><mo>∏</mo><mrow><mi>un</mi><mo>:</mo><mi>UN</mi></mrow></munder><mrow><mrow><mo>(</mo></mrow></mrow><mi>B</mi><mo>(</mo><mi>un</mi><mo>)</mo><mo>→</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mi>UN</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>x</mi><mo>)</mo><mrow><mrow><mo>)</mo></mrow></mrow><mo>→</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mi>UN</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\mathsf {sup}}:\prod _{a:A}{\Big (}B(a) o {\mathsf {W}}_{x:A}B(x){\Big )} o {\mathsf {W}}_{x:A}B(x).}</annotation></semantics></math><img src=$ ${\displaystyle {\frac {a:A\qquad f:B(a) o {\mathsf {W}}_{x:A}B(x)}{{\mathsf {sup}}(a,f):{\mathsf {W}}_{x:A}B(x)}}. <semantics><mrow><mstyle><mrow><mfrac><mrow><mi>un</mi><mo>:</mo><mi>UN</mi><mspace></mspace><mi>f</mi><mo>:</mo><mi>B</mi><mo>(</mo><mi>un</mi><mo>)</mo><mo>→</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mi>UN</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mrow><mrow><mrow><mi>s</mi><mi>vous</mi><mi>p</mi></mrow></mrow><mo>(</mo><mi>un</mi><mo>,</mo><mi>f</mi><mo>)</mo><mo>:</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mi>UN</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\frac {a:A\qquad f:B(a) o {\mathsf {W}}_{x:A}B(x)}{{\mathsf {sup}}(a,f):{\mathsf {W}}_{x:A}B(x)}}.}</annotation></semantics></math><img src=$

The elimination rule for W-types works similarly to structural induction on trees. If, whenever a property (under the propositions-as-types interpretation) ${\displaystyle C:{\mathsf {W}}_{x:A}B(x) o U <semantics><mrow><mstyle><mi>C</mi><mo>:</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mi>A</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>→</mo><mi>U</mi></mstyle></mrow><annotation>{\displaystyle C:{\mathsf {W}}_{x:A}B(x) o U}</annotation></semantics></math><img src=$

${\displaystyle {\frac {w:{\mathsf {W}}_{a:A}B(a)\qquad a:A,\;f:B(a) o {\mathsf {W}}_{x:A}B(x),\;c:\prod _{b:B(a)}C(f(b))\;\vdash \;h(a,f,c):C({\mathsf {sup}}(a,f))}{{\mathsf {elim}}(w,h):C(w) <semantics><mrow><mstyle><mrow><mfrac><mrow><mi>w</mi><mo>:</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>a</mi><mo>:</mo><mi>A</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>a</mi><mo>)</mo><mspace></mspace><mi>a</mi><mo>:</mo><mi>A</mi><mo>,</mo><mspace></mspace><mi>f</mi><mo>:</mo><mi>B</mi><mo>(</mo><mi>a</mi><mo>)</mo><mo>→</mo><msub><mrow><mrow><mi>W</mi></mrow></mrow><mrow><mi>x</mi><mo>:</mo><mi>A</mi></mrow></msub><mi>B</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>,</mo><mspace></mspace><mi>c</mi><mo>:</mo><munder><mo>∏</mo><mrow><mi>b</mi><mo>:</mo><mi>B</mi><mo>(</mo><mi>a</mi><mo>)</mo></mrow></munder><mi>C</mi><mo>(</mo><mi>f</mi><mo>(</mo><mi>b</mi><mo>)</mo><mo>)</mo><mspace></mspace><mo>⊢</mo><mspace></mspace><mi>h</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>f</mi><mo>,</mo><mi>c</mi><mo>)</mo><mo>:</mo><mi>C</mi><mo>(</mo><mrow><mrow><mi>s</mi><mi>u</mi><mi>p</mi></mrow></mrow><mo>(</mo><mi>a</mi><mo>,</mo><mi>f</mi><mo>)</mo><mo>)</mo></mrow><mrow><mrow><mrow><mi>e</mi><mi>l</mi><mi>i</mi><mi>m</mi></mrow></mrow><mo>(</mo><mi>w</mi><mo>,</mo><mi>h</mi><mo>)</mo><mo>:</mo><mi>C</mi><mo>(</mo><mi>w</mi><mo>)</mo></mrow></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle {\frac {w:{\mathsf {W}}_{a:A}B(a)\qquad a:A,\;f:B(a) o {\mathsf {W}}_{x:A}B(x),\;c:\prod _{b:B(a)}C(f(b))\;\vdash \;h(a,f,c):C({\mathsf {sup}}(a,f))}{{\mathsf {elim}}(w,h):C(w)}}}</annotation></semantics></math><img src=$

In extensional type theories, W-types (resp. M-types) can be defined up to isomorphism as initial algebras (resp. final coalgebras) for polynomial functors. In this case, the property of initiality (res. finality) corresponds directly to the appropriate induction principle. In intensional type theories with the univalence axiom, this correspondence holds up to homotopy (propositional equality).

M-types are dual to W-types, and represent coinductive (potentially infinite) data such as streams. M-types can be derived from W-types.

Mutually inductive definitions

This technique allows some definitions of multiple types that depend on each other. For example, defining two parity predicates on natural numbers using two mutually inductive types in Rocq:

Inductiveeven:nat->Prop:=|zero_is_even:evenO|S_of_odd_is_even:(foralln:nat,oddn->even(Sn))withodd:nat->Prop:=|S_of_even_is_odd:(foralln:nat,evenn->odd(Sn)).

Induction-recursion

Induction-recursion started as a study into the limits of ITT. Once found, the limits were turned into rules that allowed defining new inductive types. These types could depend upon a function and the function on the type, as long as both were defined simultaneously.

Universe types can be defined using induction-recursion.

Induction-induction

Induction-induction allows definition of a type and a family of types at the same time. So, a type ${\displaystyle B:A o Type </span referrerpolicy=$ .

Higher inductive types

Il s'agit d'un domaine de recherche actuel en théorie des types homotopiques (HoTT). Celle-ci diffère de la théorie des types inductifs (ITT) par son type identité (égalité). Les types inductifs supérieurs définissent un nouveau type à l'aide de constantes et de fonctions qui créent des éléments de ce type, ainsi que de nouvelles instances du type identité qui les relient.

Un exemple simple est le type : cercle

et une boucle ;

: base = base .

L'existence d'un nouveau constructeur pour le type identité fait

Univalent Foundations Program (2013). Homotopy Type Theory: Univalent Foundations of Mathematics. Institute for Advanced Study.