Decidability of Conversion for Type Theory in Type Theory

• Type theory should be able to handle its own meta-theory, both to justify its foundational claims and to obtain a verified implementation. At the core of a type checker for intensional type theory lies an algorithm to check equality of types, or in other words, to check whether two types are convertible. We have formalized in Agda a practical conversion checking algorithm for a dependent type theory with one universe à la Russell, natural numbers, and η-equality for Π types. We prove the algorithm correct via a Kripke logical relation parameterized by a suitable notion of equivalence of terms. We then instantiate the parameterized fundamental lemma twice: once to obtain canonicity and injectivity of type formers, and once again to prove the completeness of the algorithm. Our proof relies on inductive-recursive definitions, but not on the uniqueness of identity proofs. Thus, it is valid in variants of intensional Martin-Löf Type Theory as long as they support induction-recursion, for instance, Extensional, Observational, or Homotopy Type Theory.

Ämnesord

NATURVETENSKAP  -- Matematik -- Algebra och logik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Algebra and Logic (hsv//eng)

NATURVETENSKAP  -- Matematik -- Geometri (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Geometry (hsv//eng)

NATURVETENSKAP  -- Matematik -- Matematisk analys (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Mathematical Analysis (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Programvaruteknik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Software Engineering (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

Formalization

Agda

Logical relations

Dependent types

Publikations- och innehållstyp

art (ämneskategori)

ref (ämneskategori)