Two-Level Type Theory and Applications

Research output: Other contributionNet publication - Internet publicationResearch

Links

We define and develop two-level type theory, a version of Martin-L\"of type theory which is able to combine two type theories. In our case of interest, the first of these two theories is homotopy type theory (HoTT) which may include univalent universes and higher inductive types. The second is a traditional form of type theory validating uniqueness of identity proofs (UIP) and may be understood as internalised meta-theory of the first. We show how two-level type theory can be used to address some of the open issues of HoTT, including the construction of "infinite structures" such as a universe of semi-simplicial types, and the internal definition of higher categorical structures. The idea of two-level type theory is heavily inspired by Voevodsky's Homotopy Type System (HTS). Two-level type theory can be thought of as a version of HTS without equality reflection. We show that the lack of equality reflection does not hinder the development of the ideas that HTS was designed for. Some of the results of this paper have been formalised in the proof assistant Lean, in order to demonstrate how two-level type theory, despite being an extension of the underlying type theory of current proof assistants, can be encoded in existing systems in a way that is both practical and easy to implement.
Original languageEnglish
Publication year9 May 2017
PublisherarXiv.org
Number of pages38
Publication statusPublished - 9 May 2017
SeriesarXiv preprint

    Research areas

  • cs.LO, 03B15, F.4.1

See relations at Aarhus University Citationformats

ID: 141891868