The Calculus of Inductive Constructions (CIC) is a type theory used as a foundation for formal mathematics and verified programming. It extends the Calculus of Constructions with inductively defined types, allowing mathematical objects, logical propositions, proofs, and terminating programs to be expressed within a common formal language. Through the Curry–Howard correspondence, a proposition is represented by a type and a proof by a term inhabiting that type. CIC is the principal logical foundation of the Rocq proof assistant, formerly known as Coq.
Origins and scope
The Calculus of Constructions, developed by Thierry Coquand and Gérard Huet in the 1980s, combined dependent types, polymorphism, and higher-order type formation. These features provided a compact language for expressing both programs and logical arguments.
Although many data structures can be encoded using functions alone, such encodings do not automatically provide all the induction and computation principles needed for convenient mathematical development. Work on inductive definitions, notably by Christine Paulin-Mohring and others, helped establish the extension known as CIC. Inductively defined numbers, lists, trees, and logical relations could then be treated directly rather than only through functional encodings.
CIC denotes a family of closely related formal systems rather than a single specification covering every implementation feature. Universe rules, elimination restrictions, recursive definitions, and additional sorts must be specified when stating precise metatheoretic results. Modern proof assistants based on CIC include extensions and implementation mechanisms beyond a minimal presentation of the calculus.
Dependent types and typing judgments
A central feature of CIC is the dependent type: a type that can depend on a term. For example, the type of vectors of length depends on a natural number :
Here is the type of vector entries. A function that concatenates vectors can have a type recording the lengths of its inputs and output:
The notation , also written , denotes a dependent function type. A term of this type takes an argument and returns a result of type . Ordinary function types are the special case in which does not depend on the argument.
Typing is expressed by a judgment
meaning that, under the declarations and assumptions in the context , the term has type .
The language includes variables, function abstraction, function application, dependent products, sorts or universes, inductive objects, and operations for eliminating or recursively processing those objects. A complete presentation specifies which expressions are well formed and the rules under which typing judgments hold.
Propositions as types
CIC internalizes logical reasoning through the propositions-as-types interpretation. Its basic logic is intuitionistic logic: constructing a proof generally requires appropriate evidence, not merely an appeal to classical truth conditions.
Logical constructions have corresponding type-theoretic forms:
- An implication is a function taking evidence of to evidence of .
- Universal quantification is a dependent product.
- Conjunction can be defined inductively with a constructor taking proofs of both conjuncts.
- Disjunction has constructors identifying which alternative is established.
- Existential quantification packages a witness with evidence that it satisfies the stated property.
- Falsity is an inductive proposition with no constructors.
Thus, a formal proof is a term whose type expresses the theorem being established. Checking the proof amounts to checking the typing judgment.
The law of excluded middle is not generally derivable in the constructive core. It can be introduced as an additional axiom, as can other principles used in classical mathematics. Such assumptions become explicit dependencies of the resulting theorems.
Universes and the separation of logic from data
Types themselves must be classified. CIC therefore uses sorts and a hierarchy of universes rather than allowing a single unrestricted type of all types.
A typical hierarchy has the form
Universe levels prevent problematic forms of self-reference associated with an unrestricted rule such as . Implementations commonly support cumulativity, allowing a type in a lower universe to be used at a higher universe level under specified rules.
In the formulation underlying Rocq, Prop is a distinguished sort for propositions. It is impredicative: quantification over types in higher universes can still produce a proposition in Prop. By contrast, the Type hierarchy is predicative, with dependent-product formation governed by universe-level constraints.
A further distinction concerns elimination from propositions into computational types. Such elimination is restricted, with permitted exceptional cases, so an arbitrary proof cannot be inspected as unrestricted computational data. This supports the separation between logical evidence and executable content.
The exact treatment of Set, additional proposition sorts, and universe polymorphism depends on the particular system or implementation. These details affect the rules of the theory and are not merely notation.
Inductive definitions
An inductive type is specified by constructors describing how its elements may be formed. The natural numbers provide the standard example:
Its elimination principle expresses mathematical induction:
Related elimination principles allow functions to be defined by recursion. The same inductive declaration therefore supports both proofs about numbers and computations on numbers.
Inductive families generalize this mechanism by allowing indices to vary between constructors. For instance, vectors can be described using constructors of the forms
and
Their indices express invariants in the types themselves. Similar definitions represent typing derivations, evaluation relations, balanced structures, and evidence that a program satisfies a specification.
Strict positivity
Inductive declarations are subject to a strict positivity condition. Roughly, recursive occurrences of the type being defined must appear in permitted positive positions, rather than as inputs to arbitrary functions.
A constructor with a recursive argument of type may be acceptable, whereas a declaration containing an argument of type is generally not strictly positive in . Unrestricted negative occurrences can undermine normalization and consistency.
Positivity checking is therefore part of the logical discipline of the system, not simply a restriction imposed for programming convenience.
Computation and equality
CIC combines logical deduction with computation. Its conversion rules include function application, such as
together with rules for local definitions, pattern matching on constructors, and permitted recursive computations. Implementations also unfold transparent definitions when checking convertibility.
This gives rise to two important notions of equality.
Definitional equality is determined by the calculus's conversion rules. Expressions that compute to the same result can be treated as interchangeable during type checking without requiring an explicit equality proof.
Propositional equality is represented by an inductively defined equality type. An equality statement is itself a proposition and requires a proof term. Its elimination principle permits substitution of equal objects in dependent expressions.
These notions need not coincide. With addition defined by recursion on its first argument, can reduce directly to , whereas for an arbitrary variable normally requires induction. Both statements express valid equalities, but only the first follows immediately from that choice of computation rules.
CIC is consequently an intensional type theory. Principles such as function extensionality—that pointwise equal functions are equal—are not generally derivable in its basic form.
Recursion, termination, and metatheory
Unrestricted general recursion is unsuitable for the propositions-as-types interpretation: if arbitrary nonterminating terms could inhabit every type, a divergent computation could masquerade as a proof of any proposition.
CIC therefore restricts recursive definitions. Structural recursion requires recursive calls to operate on suitably smaller parts of inductively defined inputs. More general terminating algorithms can be expressed using well-founded recursion and explicit termination arguments.
For standard formulations of the inductive core, normalization results establish that well-typed computations terminate. Subject reduction establishes that reduction preserves typing. With the relevant universe and inductive-definition restrictions, these results support consistency arguments and effective type checking.
The precise scope of such theorems matters. Extensions involving coinduction, additional reduction rules, or axioms require their own analysis. Axioms may preserve the ability to check proof terms while preventing closed expressions from computing to ordinary data constructors.
Decidable checking of an explicitly supplied term also does not imply automatic proof discovery. Finding a proof or reconstructing omitted information can require substantial search.
Proof assistants and applications
In Rocq, high-level commands and tactics construct terms that are checked by a comparatively small kernel. Tactics need not themselves constitute the final authority for a theorem: their output must satisfy the kernel's typing rules. This architecture separates proof search from proof checking.
CIC supports several forms of formal verification:
- Mathematical formalization: definitions and theorems can be developed with explicit dependencies and machine-checked proofs.
- Program verification: specifications can be expressed as propositions, dependent types, or inductive relations.
- Programming-language metatheory: syntax, typing judgments, and operational semantics can be represented by inductive families.
- Verified algorithms: programs can be developed together with correctness and termination proofs.
Program extraction can translate computational parts of developments into a conventional programming language while erasing proof material where appropriate. Correctness of the formal development and correctness of the complete execution pipeline are nevertheless distinct questions: extraction, compilation, runtime behavior, and external interfaces introduce further assumptions.
Limitations and related foundations
CIC's expressive type system places demands on elaboration and computation. Dependent types can make error messages complex; conversion checking can require expensive reductions; and structural termination criteria may reject terminating programs until they are reformulated or supplied with explicit arguments.
Proofs also remain relative to their specifications. A successfully checked theorem establishes the formal statement encoded in the system, not that this statement captures every intended property of an external application.
CIC differs from set theory by organizing mathematics around typed terms rather than primarily around membership in sets. It also differs from Martin-Löf type theory in characteristic features such as its impredicative proposition sort, although both belong to the broader tradition of dependent type theory.
Homotopy type theory emphasizes the higher structure of equality and principles such as univalence. These principles are not built into ordinary CIC. They can be studied through axiomatic extensions or alternative type theories, but adding an axiom does not automatically provide new computational rules for it.