In type theory, a system has inductive types if it has facilities for creating a new type from constants and functions that create terms of that type. The feature serves a role similar to data structures in a programming language and allows a type theory to add concepts like numbers, relations, and trees. As the name suggests, inductive types can be self-referential, but usually only in a way that permits structural recursion. The standard example is encoding the natural numbers using Peano's encoding. It can be defined in Rocq (formerly named Coq) as follows:
Here, a natural number is created either from the constant "O" (representing zero) or by applying the function "S" to another natural number. "S" is the successor function which represents adding one to a number. Thus, "S O" is one, "S (S O)" is two, "S (S (S O))" is three, and so on. Since their introduction, inductive types have been extended to encode more and more structures, while still being predicative and supporting structural recursion.
Induction principle Inductive types usually come with a function to prove properties about them. Thus, "nat" may come with (in Rocq syntax):
In words: for any predicate "P" over natural numbers, given a proof of "P O" and a proof of "P n -> P (n+1)", we get back a proof of "forall n, P n". This is the familiar induction principle for natural numbers.
Implementations
W- and M-types W-types are well-founded types in intuitionistic type theory (ITT). They generalize natural numbers, lists, binary trees, and other "tree-shaped" data types. Let U be a universe of types. Given a type A : U and a dependent family B : A → U, one can form a W-type W a : A B ( a ) {\displaystyle {\mathsf {W}}_{a:A}B(a)} . The type A may be thought of as "labels" for the (potentially infinitely many) constructors of the inductive type being defined, whereas B indicates the (potentially infinite) arity of each constructor. W-types (resp. M-types) may also be understood as well-founded (resp. non-well-founded) trees with nodes labeled by elements a : A and where the node labeled by a has B(a)-many subtrees. Each W-type is isomorphic to the initial algebra of a so-called polynomial functor. Let 0, 1, 2, etc. be finite types with inhabitants 11 : 1, 12, 22:2, etc. One may define the natural numbers as the W-type
N := W x : 2 f ( x ) {\displaystyle \mathbb {N} :={\mathsf {W}}_{x:\mathbf {2} }f(x)}
with f : 2 → U is defined by f(12) = 0 (representing the constructor for zero, which takes no arguments), and f(22) = 1 (representing the successor function, which takes one argument). One may define lists over a type A : U as List ( A ) := W ( x : 1 + A ) f ( x ) {\displaystyle \operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)} where
f ( inl ( 1 1 ) ) = 0 f ( inr ( a ) ) = 1 {\displaystyle {\begin{aligned}f(\operatorname {inl} (1_{\mathbf {1} }))&=\mathbf {0} \\f(\operatorname {inr} (a))&=\mathbf {1} \end{aligned}}}
and 11 is the sole inhabitant of 1. The value of f ( inl ( 1 1 ) ) {\displaystyle f(\operatorname {inl} (1_{\mathbf {1} }))} corresponds to the constructor for the empty list, whereas the value of f ( inr ( a ) ) {\displaystyle f(\operatorname {inr} (a))} corresponds to the constructor that appends a to the beginning of another list. The constructor for elements of a generic W-type W x : A B ( x ) {\displaystyle {\mathsf {W}}_{x:A}B(x)} has type
s u p : ∏ a : A ( B ( a ) → W x : A B ( x ) ) → W x : A B ( x ) . {\displaystyle {\mathsf {sup}}:\prod _{a:A}{\Big (}B(a)\to {\mathsf {W}}_{x:A}B(x){\Big )}\to {\mathsf {W}}_{x:A}B(x).}
We can also write this rule in the style of a natural deduction proof,
… excerpt ends here. Continue reading the full article.
