Induction-induction

In intuitionistic type theory (ITT), some discipline within mathematical logic, induction-induction is for simultaneously declaring some inductive type and some inductive predicate over this type.

An inductive definition is given by rules for generating elements of some type. One can then define some predicate on that type by providing constructors for forming the elements of the predicate , such inductively on the way the elements of the type are generated. Induction-induction generalizes this situation since one can simultaneously define the type and the predicate, because the rules for generating elements of the type ${\displaystyle A:{\mathsf {Type}}}$ are allowed to refer to the predicate ${\displaystyle B:A\to {\mathsf {Type}}}$.

Induction-induction can be used to define larger types including various universe constructions in type theory.[1] and limit constructions in category/topos theory.

Example 1

Present the type ${\displaystyle A}$ as having the following constructors , note the early reference to the predicate ${\displaystyle B}$ :

• ${\displaystyle aa:A}$
• ${\displaystyle \ell \ell$ :\prod _{x:A}B(x)\to A;}

and-simultaneously present the predicate ${\displaystyle B}$ as having the following constructors :

• ${\displaystyle {\mathsf {Tru}}:B(aa)}$
• ${\displaystyle {\mathsf {Fal}}:B(aa)}$
• if ${\displaystyle x:A}$ and ${\displaystyle y:B(x)}$ then ${\displaystyle {\mathsf {Zer}}:B(\ell \ell (x,y))}$
• if ${\displaystyle x:A}$ and ${\displaystyle y:B(x)}$ and ${\displaystyle z:B(\ell \ell (x,y))}$ then ${\displaystyle {\mathsf {Suc}}(z):B(\ell \ell (x,y))}$.

Example 2

A simple common example is the Universe à la Tarski type former. It creates some inductive type ${\displaystyle U:{\mathsf {Type}}}$ and some inductive predicate ${\displaystyle T:U\to {\mathsf {Type}}}$. For every type in the type theory (except ${\displaystyle U}$ itself!), there will be some element of ${\displaystyle U}$ which may be seen as some code for this corresponding type ; The predicate ${\displaystyle T}$ inductively encodes each possible type to the corresponding element of ${\displaystyle U}$ ; and constructing new codes in ${\displaystyle U}$ will require referring to the decoding-as-type of earlier codes , via the predicate ${\displaystyle T}$ .

See also

• Induction-recursion – for simultaneously declaring some inductive type and some recursive function on this type .

References

1. Dybjer, Peter (June 2000). "A general formulation of simultaneous inductive-recursive definitions in type theory" (PDF). Journal of Symbolic Logic. 65 (2): 525–549. CiteSeerX 10.1.1.6.4575. doi:10.2307/2586554. JSTOR 2586554.

External links

• A list of Peter Dybjer's publications on induction and induction-recursion