Two-Level Type Theory

Basics

Two-level type theory (2LTT) refers to versions of Martin-Löf type theory that combine two type theories: one “inner” level that is potentially a homotopy type theory or cubical type theory, which may include univalent universes and higher inductive types, and a second “outer” level that validates uniqueness of identity proofs.

Since version 2.6.2, Agda enables 2LTT with the --two-level flag. The two levels are distinguished with two hierarchies of universes: the usual universes Set for the inner level, and a new hierarchy of universes denoted SSet (for “strict sets”) for the outer level.

Note

The types in SSet have various names in the literature. They are called non-fibrant types in HTS (2017), outer types in 2LTT (2017), and exo-types in UP (2021). Similarly, these references refer to the types in Set as fibrant types, inner types, and types, respectively.

Function-types belong to Set if both their domain and codomain do, and to SSet otherwise. Records and datatypes can always be declared to belong to SSet, and can be declared to belong to Set instead if all their inputs belong to Set. In particular, any type in Set has an isomorphic copy in SSet defined as a trivial record:

  1. record c (A : Set) : SSet where
  2.   constructor ↑
  3.   field
  4.     ↓ : A
  6. open c

The main differences between the two levels are that, firstly, homotopical flags such as --without-K and --cubical apply only to the Set level (the SSet level is never homotopical); and secondly, datatypes belonging to the inner level cannot be pattern-matched on when the motive belongs to the outer level (this is necessary to maintain the previous distinction).

As a primary example, we can define separate inductive equality types for both levels:

  1. infix 4 _≡ˢ_ _≡_
  3. data _≡ˢ_ {a} {A : SSet a} (x : A) : A → SSet a where
  4.   reflˢ : x ≡ˢ x
  6. data _≡_ {a} {A : Set a} (x : A) : A → Set a where
  7.   refl : x ≡ x

With these definitions, we can prove uniqueness of identity proofs for the strict equality even if --without-K or --cubical is enabled:

  1. UIP : {a : Level} {A : SSet a} {x y : A} (p q : x ≡ˢ y) → p ≡ˢ q
  2. UIP reflˢ reflˢ = reflˢ

We can also prove that strictly equal elements are also non-strictly equal:

  1. ≡ˢ-to-≡ : {A : Set} {x y : c A} → (x ≡ˢ y) → (↓ x ≡ ↓ y)
  2. ≡ˢ-to-≡ reflˢ = refl

The opposite implication, however, fails because, as noted above, we cannot pattern-match against a datatype in Set when the motive lies in SSet. Similarly, we can map from the strict natural numbers into the ordinary ones:

  1. data ℕ : Set where
  2.   zero : ℕ
  3.   succ : ℕ → ℕ
  5. data ℕˢ : SSet where
  6.   zeroˢ : ℕˢ
  7.   succˢ : ℕˢ → ℕˢ
  9. ℕˢ-to-ℕ : ℕˢ → ℕ
  10. ℕˢ-to-ℕ zeroˢ = zero
  11. ℕˢ-to-ℕ (succˢ n) = succ (ℕˢ-to-ℕ n)

but not vice versa. (Agda does currently allow mapping from the empty SSet to the empty Set, but this feature is disputed.)

If the --two-level flag is combined with --cumulativity, then each universe Set a becomes a subtype of SSet a. In this case we can instead define the coercion c to be the identity function:

  1. c' : Set → SSet
  2. c' A = A

and replace the coercions ↑ and ↓ with the identity function. However, this combination currently allows some functions to be defined that shouldn’t be allowed; see Agda issue #5761 for details.