Concept
Induction-recursion
Overview
In intuitionistic type theory (ITT), a discipline within mathematical logic, induction-recursion is a feature for simultaneously declaring a type and function on that type. It allows the creation of larger types than inductive types, such as universes. The types created still remain predicative inside ITT.
An inductive definition is given by rules for generating elements of a type. One can then define functions from that type by induction on the way the elements of the type are generated. Induction-recursion generalizes this situation since one can simultaneously define the type and the function, because the rules for generating elements of the type are allowed to refer to the function.
Induction-recursion can be used to define large types including various universe constructions. It increases the proof-theoretic strength of type theory substantially. Nevertheless, inductive-recursive definitions are still considered predicative.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
Any such select set is called the set of postulates, or premises, from which the reasoning proceeds. The reasoning is nothing else than the exhibition of the whole pattern of general conditions involved in the pattern derived from the selected postulates.
Alfred North Whitehead, Science and the modern world
States what Induction-recursion is.
Hence, in the conclusion of a syllogism we restrict a predicate to a certain object, after having thought it in the major in its whole extent under a certain condition. This complete quantity of the extent in relation to such a condition is called universality (universalitas). To this corresponds totality (universitas) of conditions in the synthesis of intuitions. The transcendental conception of reason is therefore…
Immanuel Kant, The Critique of Pure Reason
States what Induction-recursion is.
This definition excludes from the meaning of the term Induction, various logical operations, to which it is not unusual to apply that name. Induction, as above defined, is a process of inference; it proceeds from the known to the unknown; and any operation involving no inference, any process in which what seems the conclusion is no wider than the premises from which it is drawn, does not fall within the meaning of…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Induction-recursion is.
Related ideas
Place in the tradition
Part of Type theory.