idtypes

Identity types, sometimes referred to as idtypes, are a foundational construct in dependent type theory used to express equality between two values of a given type. For a type A and elements x, y : A, the identity type Id_A(x, y) (often written x =_A y) consists of proofs that x and y are equal. The canonical inhabitant of Id_A(a, a) is refl_a, the reflexivity witness, and shape of proofs about equality is determined by how this type is constructed and eliminated in the surrounding theory.

In dependent type theories used by languages such as Coq, Agda, Idris, and Lean, identity types come with an eliminator principle often called J or pattern matching on the proof of equality. This enables reasoning that if a property holds for the reflexive case, it can be transported along any equality proof to hold for related terms. The notion of transporting a value along an equality is central to dependent types, allowing one to rewrite and substitute within dependent types and terms.

In homotopy type theory (HoTT), identity types are interpreted as paths between points in a space, with higher identity types corresponding to equivalences between paths. This path interpretation provides a geometric intuition for equality and motivates axioms such as univalence, which equates isomorphic structures with equal ones.

Usage and implications: identity types are used to prove that two terms are equal, to transport data along equalities, and to formalize substitution principles within proofs and programs. They also highlight distinctions between intensional and extensional equality; in many systems, not every function is extensional, and equality of results may require additional assumptions or axioms.

Overall, idtypes are a central tool for constructive reasoning, formal verification, and the expressiveness of dependently typed languages.