open import 1Lab.Type.Sigma
open import 1Lab.HLevel
open import 1Lab.Equiv
open import 1Lab.Path
open import 1Lab.Type

module 1Lab.Univalence where

UnivalenceπŸ”—

In Homotopy Type Theory, univalence is the principle stating that equivalent types can be identified. When the book first came out, there was no widely-accepted computational interpretation of this principle, so it was added to the theory as an axiom: the univalence axiom.

Precisely, the axiom as presented in the book consists of the following data (right under remark Β§2.10.4):

  • A map which turns equivalences into identifications of types. This map is called ua.

  • A rule for eliminating identifications of types, by turning them into equivalences: pathβ†’equiv

  • The propositional computation rule, stating that transport along ua(f) is identical to applying f: uaΞ².

In the book, there is an extra postulated datum asserting that ua is an inverse to pathβ†’equiv. This datum does not have a name in this development, because it’s proved in-line in the construction of the term univalence.

The point of cubical type theory is to give these terms constructive interpretations, i.e., make them definable in the theory, in terms of constructions that have computational behaviour. Let’s see how this is done.

GlueπŸ”—

To even state univalence, we first have to make sure that the concept of β€œpaths between types” makes sense in the first place. In β€œBook HoTT”, paths between types are a well-formed concept because the path type is uniformly inductively defined for everything β€” including universes. This is not the case in Cubical type theory, where for paths in to be well-behaved, must be fibrant.

Since there’s no obvious choice for how to interpret hcomp in Type, a fine solution is to make hcomp its own type former. This is the approach taken by some Cubical type theories in the RedPRL school. Univalence in those type theories is then achieved by adding a type former, called V, which turns an equivalence into a path.

In CCHM (2016) β€” and therefore Cubical Agda β€” a different approach is taken, which combines proving univalence with defining a fibrancy structure for the universe. The core idea is to define a new type former, Glue, which β€œglues” a partial type, along an equivalence, to a total type.

private variable
  β„“ β„“' β„“'' β„“''' : Level
  A Aβ‚€ A₁ B Bβ‚€ B₁ C Cβ‚€ C₁ : Type β„“

private primitive
  primGlue : (A : Type β„“) {Ο† : I}
            β†’ (T : Partial Ο† (Type β„“')) β†’ (e : PartialP Ο† (Ξ» o β†’ T o ≃ A))
            β†’ Type β„“'

  prim^glue : {A : Type β„“} {Ο† : I}
            β†’ {T : Partial Ο† (Type β„“')} β†’ {e : PartialP Ο† (Ξ» o β†’ T o ≃ A)}
            β†’ PartialP Ο† T β†’ A β†’ primGlue A T e

  prim^unglue : {A : Type β„“} {Ο† : I}
              β†’ {T : Partial Ο† (Type β„“')} β†’ {e : PartialP Ο† (Ξ» o β†’ T o ≃ A)}
              β†’ primGlue A T e β†’ A

open import Prim.HCompU
open import 1Lab.Equiv.FromPath

Glue : (A : Type β„“)
     β†’ {Ο† : I}
     β†’ (Te : Partial Ο† (Ξ£[ T ∈ Type β„“' ] T ≃ A))
     β†’ Type β„“'

The public interface of Glue demands a type called the base type, a formula and a partial type which is equivalent to Since the equivalence is defined inside the partial element, it can also (potentially) vary over the interval, so in reality we have a family of partial types and a family of partial equivalences

In the specific case where we set we can illustrate Glue A (T, f) as the dashed line in the square diagram below. The conceptual idea is that by β€œgluing” onto a totally defined type, we get a type which extends 

Glue A {Ο†} Te = primGlue A tys eqvs module glue-sys where
  tys : Partial Ο† (Type _)
  tys (Ο† = i1) = Te 1=1 .fst

  eqvs : PartialP Ο† (Ξ» .o β†’ tys _ ≃ A)
  eqvs (Ο† = i1) = Te 1=1 .snd

unattach
  : {A : Type β„“} (Ο† : I) {T : Partial Ο† (Type β„“')}
    {e : PartialP Ο† (Ξ» o β†’ T o ≃ A)}
  β†’ primGlue A T e β†’ A
unattach Ο† = prim^unglue {Ο† = Ο†}

attach
  : {A : Type β„“} (Ο† : I) {T : Partial Ο† (Type β„“')} {e : PartialP Ο† (Ξ» o β†’ T o ≃ A)}
  β†’ (p : PartialP Ο† T)
  β†’ A [ Ο† ↦ (Ξ» o β†’ e o .fst (p o)) ]
  β†’ primGlue A T e
attach Ο† p x = prim^glue {Ο† = Ο†} p (outS x)

-- Display of primGlue
-- -------------------
--
-- We can't in general recover a pretty Glue application from an
-- internal 'primGlue', since display forms can't do higher order
-- matching.
--
-- But we can instead use a *named* system in the definition
-- of important 'Glue's, and then match on this definition when trying
-- to unapply 'primGlue'.
--
-- Since 'primGlue' is private, the only way to glue things is using the
-- nice interface, so 'Glue's display nicely.

{-# DISPLAY primGlue A (glue-sys.tys _ Te) (glue-sys.eqvs _ Te) = Glue A Te #-}

{-# DISPLAY prim^unglue {l} {l'} {A} {Ο†} {t} {e} x = unattach {l} {l'} {A} Ο† {t} {e} x #-}
{-# DISPLAY prim^glue {_} {_} {_} {Ο†} {_} {_} x y = attach Ο† x y #-}

For Glue to extend we add a computation rule which could be called a boundary condition, since it specifies how Glue behaves on the boundaries of cubes. Concisely, when we have that Glue evaluates to the partial type. This is exactly what it means for Glue to extend 

module _ {A B : Type} {e : A ≃ B} where
  private
    Glue-boundary : Glue B {i1} (Ξ» x β†’ A , e) ≑ A
    Glue-boundary i = A

Furthermore, since we can turn any family of paths into a family of equivalences, we can use the Glue construct to implement something with precisely the same interface as hcomp for Type:

glue-hfill
  : βˆ€ {β„“} Ο† (u : βˆ€ i β†’ Partial (Ο† ∨ ~ i) (Type β„“))
  β†’ βˆ€ i β†’ Type β„“ [ _ ↦ (Ξ» { (i = i0) β†’ u i0 1=1
                          ; (Ο† = i1) β†’ u i 1=1 }) ]

The type of glue-hfill is the same as that of hfill, but the type is stated much more verbosely β€” so that we may define it without previous reference to a hcomp analogue. Like hfill, glue-hfill extends an open box of types to a totally-defined cube. The type of glue-hfill expresses this in terms of extensions: We have a path (that’s the βˆ€ i β†’ binder) of Types which agrees with outS u0 on the left endpoint, and with u everywhere.

glue-hfill Ο† u i = inS (
  Glue (u i0 1=1) {Ο† = Ο† ∨ ~ i}
    Ξ» { (Ο† = i1) β†’ u i 1=1 , lineβ†’equiv (Ξ» j β†’ u (i ∧ ~ j) 1=1)
      ; (i = i0) → u i0 1=1 , line→equiv (λ i → u i0 1=1)
      })

In the case for we must glue onto itself using the identity equivalence. This guarantees that the boundary of the stated type for glue-hfill is satisfied. However, since different faces of partial elements must agree where they are defined, we can not use the identity equivalence directly, since line→equiv refl is not definitionally the identity equivalence.

When hence where is defined, we glue the endpoint onto using the equivalence generated by the path provided by itself! It’s a family of partial paths, after all, and that can be turned into a family of partial equivalences.

Using hcomp-unique and glue-hfill together, we get a internal characterisation of the fibrancy structure of the universe. While hcomp-unique may appear surprising, it is essentially a generalisation of the uniqueness of path compositions: Any open box has a contractible space of fillers.

hcomp≑Glue : βˆ€ {β„“} {Ο†} (u : βˆ€ i β†’ Partial (Ο† ∨ ~ i) (Type β„“))
           β†’ hcomp Ο† u
           ≑ Glue (u i0 1=1)
              (λ { (φ = i1) → u i1 1=1 , line→equiv (λ j → u (~ j) 1=1) })
hcomp≑Glue {Ο† = Ο†} u = hcomp-unique Ο† u (glue-hfill Ο† u)

Paths from GlueπŸ”—

Since Glue generalises hcomp by allowing a partial equivalence as its β€œtube”, rather than a partial path, it allows us to turn any equivalence into a path, using a sort of β€œtrick”: We consider the line with endpoints and as an open cube to be filled. A filler for this line is exactly a path Since Glue fills open boxes of types using equivalences, this path exists!

private module _ where private

  ua : {A B : Type β„“} β†’ A ≃ B β†’ A ≑ B
  ua {A = A} {B} eqv i = Glue B Ξ» where
    (i = i0) β†’ A , eqv
    (i = i1) β†’ B , _ , id-equiv

-- We use two named systems for the definition of 'ua' so that we can
-- make the Glue display away

ua : {A B : Type β„“} β†’ A ≃ B β†’ A ≑ B
ua {A = A} {B} eqv i = primGlue B tys eqvs module ua-sys where
  tys : Partial (βˆ‚ i) (Type _)
  tys (i = i0) = A
  tys (i = i1) = B

  eqvs : PartialP (βˆ‚ i) (Ξ» .o β†’ tys o ≃ B)
  eqvs (i = i0) = eqv
  eqvs (i = i1) = id≃

-- see "Display of primGlue" above
{-# DISPLAY primGlue _ (ua-sys.tys e i) (ua-sys.eqvs _ _) = ua e i #-}

Semantically, the explanation of ua as completing a partial line is sufficient. But we can also ask ourselves: Why does this definition go through, syntactically? Because of the boundary condition for Glue: when i = i0, the whole thing evaluates to A, meaning that the left endpoint of the path is correct. The same thing happens with the right endpoint.

The action of transporting along ua(f) can be described by chasing an element around the diagram that illustrates Glue in the case, specialising to ua. Keep in mind that, since the right face of the diagram β€œpoints in the wrong direction”, it must be inverted. However, the inverse of the identity equivalence is the identity equivalence, so nothing changes (for this example).

  1. The action that corresponds to the left face of the diagram is to apply the underlying function of f. This contributes the f .fst x part of the uaΞ² term below.
  1. For the bottom face, we have a path rather than an equivalence, so we must transport along it. In this case, the path is the reflexivity on B, but in a more general Glue construction, it might be a non-trivial path.

To compensate for this extra transport, we use coe1β†’i, which connects f .fst x and transport (Ξ» i β†’ B) (f .fst x).

  1. Finally, we apply the inverse of the identity equivalence, corresponding to the right face in the diagram. This immediately computes away, and thus contributes nothing to the uaΞ² path.
uaΞ² : {A B : Type β„“} (f : A ≃ B) (x : A) β†’ transport (ua f) x ≑ f .fst x
uaΞ² {A = A} {B} f x i = coe1β†’i (Ξ» _ β†’ B) i (f .fst x)

Since ua is a map that turns equivalences into paths, we can compose it with a function that turns isomorphisms into equivalences to get the map Iso→Path.

Isoβ†’Path : {A B : Type β„“} β†’ Iso A B β†’ A ≑ B
Iso→Path (f , iiso) = ua (f , is-iso→is-equiv iiso)

Paths over uaπŸ”—

The introduction and elimination forms for Glue can be specialised to the case of ua, leading to the definitions of ua-glue and ua-unglue below. Their types are written in terms of interval variables and extension types, rather than using Paths, because these typings make the structure of Glue more explicit.

The first, ua-unglue, tells us that if we have some x : ua e i (varying over an interval variable i), then we have an element of B which agrees with e .fst x on the left and with x on the right.

ua-unglue : βˆ€ {A B : Type β„“} (e : A ≃ B) (i : I) (x : ua e i) β†’ B
ua-unglue e i x = unattach (βˆ‚ i) x

We can factor the interval variable out, to get a type in terms of PathP, leading to an explanation of ua-unglue without mentioning extensions: A path x ≑ y over ua e induces a path e .fst x ≑ y.

ua-pathpβ†’path : βˆ€ {A B : Type β„“} (e : A ≃ B) {x : A} {y : B}
              β†’ PathP (Ξ» i β†’ ua e i) x y
              β†’ e .fst x ≑ y
ua-pathp→path e p i = ua-unglue e i (p i)

In the other direction, we have ua-glue, which expresses that a path e .fst x ≑ y implies that x ≑ y over ua e. For the type of ua-glue, suppose that we have a partial element defined on the left endpoint of the interval, together with an extension of where is defined. What ua-glue expresses is that we can complete this to a path in which agrees with and where these are defined.

ua-glue : βˆ€ {A B : Type β„“} (e : A ≃ B) (i : I)
            (x : Partial (~ i) A)
            (y : B [ _ ↦ (Ξ» { (i = i0) β†’ e .fst (x 1=1) }) ])
          β†’ ua e i
ua-glue e i x y = prim^glue {Ο† = i ∨ ~ i}
  (Ξ» { (i = i0) β†’ x 1=1
     ; (i = i1) β†’ outS y })
  (outS y)

Observe that, since is partially in the image of this essentially constrains to be a β€œpartial preimage” of under the equivalence Factoring in the type of the interval, we get the promised map between dependent paths over ua and paths in B.

pathβ†’ua-pathp : βˆ€ {A B : Type β„“} (e : A ≃ B) {x : A} {y : B}
              β†’ e .fst x ≑ y
              β†’ PathP (Ξ» i β†’ ua e i) x y
path→ua-pathp e {x = x} p i = ua-glue e i (λ { (i = i0) → x }) (inS (p i))

The β€œpathp to path” versions of the above lemmas are definitionally inverses, so they provide a characterisation of PathP (ua f) in terms of non-dependent paths.

ua-pathp≃path : βˆ€ {A B : Type β„“} (e : A ≃ B) {x : A} {y : B}
              β†’ (e .fst x ≑ y) ≃ (PathP (Ξ» i β†’ ua e i) x y)
ua-pathp≃path eqv .fst = pathβ†’ua-pathp eqv
ua-pathp≃path eqv .snd .is-eqv y .centre = strict-fibres (ua-pathpβ†’path eqv) y .fst
ua-pathp≃path eqv .snd .is-eqv y .paths = strict-fibres (ua-pathpβ†’path eqv) y .snd

The β€œaxiomβ€πŸ”—

The actual β€œunivalence axiom”, as stated in the HoTT book, says that the canonical map A ≑ B, defined using J, is an equivalence. This map is idβ†’equiv, defined right above. In more intuitive terms, it’s β€œcasting” the identity equivalence A ≃ A along a proof that A ≑ B to get an equivalence A ≃ B.

module _ where private
  idβ†’equiv : {A B : Type β„“} β†’ A ≑ B β†’ A ≃ B
  idβ†’equiv {A = A} {B} = J (Ξ» x _ β†’ A ≃ x) (_ , id-equiv)

  idβ†’equiv-refl : {A : Type β„“} β†’ idβ†’equiv (Ξ» i β†’ A) ≑ (_ , id-equiv)
  idβ†’equiv-refl {A = A} = J-refl (Ξ» x _ β†’ A ≃ x) (_ , id-equiv)

However, because of efficiency concerns (Agda is a programming language, after all), instead of using id→equiv defined using J, we use path→equiv, which is defined in an auxiliary module.

pathβ†’equiv : {A B : Type β„“} β†’ A ≑ B β†’ A ≃ B
path→equiv p = line→equiv (λ i → p i)

Since identity of equivalences is determined by identity of their underlying functions, to show that path→equiv of refl is the identity equivalence, we use coe1→i to show that transport by refl is the identity.

pathβ†’equiv-refl : {A : Type β„“} β†’ pathβ†’equiv (refl {x = A}) ≑ (id , id-equiv)
path→equiv-refl {A = A} =
  Ξ£-path (Ξ» i x β†’ coe1β†’i (Ξ» i β†’ A) i x)
         (is-prop→pathp (λ i → is-equiv-is-prop _) _ _)

For the other direction, we must show that ua of id-equiv is refl. We can do this quite efficiently using Glue. Since this is a path between paths, we have two interval variables.

ua-id-equiv : {A : Type β„“} β†’ ua (_ , id-equiv {A = A}) ≑ refl
ua-id-equiv {A = A} i j = Glue A {Ο† = i ∨ ~ j ∨ j} (Ξ» _ β†’ A , _ , id-equiv)

We can then prove that the map pathβ†’equiv is an isomorphism, hence an equivalence. It’s very useful to have explicit names for the proofs that pathβ†’equiv and ua are equivalences without referring to components of Path≃Equiv, so we introduce names for them as well.

Path≃Equiv   : {A B : Type β„“} β†’ Iso (A ≑ B) (A ≃ B)
univalence   : {A B : Type ℓ} → is-equiv (path→equiv {A = A} {B})
univalence⁻¹ : {A B : Type β„“} β†’ is-equiv (ua {A = A} {B})

Path≃Equiv {A = A} {B = B} = pathβ†’equiv , iiso where
  iiso : is-iso path→equiv
  iiso .is-iso.inv = ua

We show that path→equiv inverts ua, which means proving that one can recover the original equivalence from the generated path. Because of the computational nature of Cubical Agda, all we have to do is apply uaβ:

  iiso .is-iso.rinv (f , is-eqv) =
    Ξ£-path (funext (uaΞ² (f , is-eqv))) (is-equiv-is-prop f _ _)

For the other direction, we use path induction to reduce the problem from showing that ua inverts path→equiv for an arbitrary path (which is hard) to showing that path→equiv takes refl to the identity equivalence (path→equiv-refl), and that ua takes the identity equivalence to refl (ua-id-equiv).

  iiso .is-iso.linv =
    J (Ξ» _ p β†’ ua (pathβ†’equiv p) ≑ p)
      (ap ua pathβ†’equiv-refl βˆ™ ua-id-equiv)

univalence {A = A} {B} = is-isoβ†’is-equiv (Path≃Equiv .snd)
univalence⁻¹ {A = A} {B} = is-isoβ†’is-equiv (is-iso.inverse (Path≃Equiv .snd))

In some situations, it is helpful to have a proof that path→equiv followed by an adjustment of levels is still an equivalence:

univalence-lift : {A B : Type ℓ} → is-equiv (λ e → lift (path→equiv {A = A} {B} e))
univalence-lift {ℓ = ℓ} = is-iso→is-equiv morp where
  morp : is-iso (λ e → lift {ℓ = lsuc ℓ} (path→equiv e))
  morp .is-iso.inv x = ua (x .lower)
  morp .is-iso.rinv x =
    lift (pathβ†’equiv (ua (x .lower))) β‰‘βŸ¨ ap lift (Path≃Equiv .snd .is-iso.rinv _) βŸ©β‰‘
    x                                 ∎
  morp .is-iso.linv x = Path≃Equiv .snd .is-iso.linv _

Equivalence inductionπŸ”—

One useful consequence of 1 is that the type of equivalences satisfies the same induction principle as the type of identifications. By analogy with how path induction can be characterised as contractibility of singletons and transport, β€œequivalence induction” can be characterised as transport and contractibility of singletons up to equivalence:

Equiv-is-contr : βˆ€ {β„“} (A : Type β„“) β†’ is-contr (Ξ£[ B ∈ Type β„“ ] A ≃ B)
Equiv-is-contr A .centre            = A , _ , id-equiv
Equiv-is-contr A .paths (B , A≃B) i = ua A≃B i , p i , q i where
  p : PathP (Ξ» i β†’ A β†’ ua A≃B i) id (A≃B .fst)
  p i x = ua-glue A≃B i (Ξ» { (i = i0) β†’ x }) (inS (A≃B .fst x))

  q : PathP (Ξ» i β†’ is-equiv (p i)) id-equiv (A≃B .snd)
  q = is-prop→pathp (λ i → is-equiv-is-prop (p i)) _ _

Combining Equiv-is-contr with subst, we get an induction principle for the type of equivalences based at To prove for any it suffices to consider the case where is and is the identity equivalence.

EquivJ : βˆ€ {β„“ β„“'} {A : Type β„“}
       β†’ (P : (B : Type β„“) β†’ A ≃ B β†’ Type β„“')
       β†’ P A (_ , id-equiv)
       β†’ {B : Type β„“} (e : A ≃ B)
       β†’ P B e
EquivJ P pid eqv =
  subst (Ξ» e β†’ P (e .fst) (e .snd)) (Equiv-is-contr _ .is-contr.paths (_ , eqv)) pid

Equivalence induction simplifies the proofs of many properties about equivalences. For example, if is an equivalence, then so is its action on paths 

private
  is-equivβ†’is-embedding : βˆ€ {β„“} {A B : Type β„“}
                        β†’ (f : A β†’ B) β†’ is-equiv f
                        β†’ {x y : A}
                        β†’ is-equiv (ap f {x = x} {y = y})
  is-equiv→is-embedding f eqv =
    EquivJ (Ξ» B e β†’ is-equiv (ap (e .fst))) id-equiv (f , eqv)

The proof can be rendered in English roughly as follows:

Suppose is an equivalence. We want to show that, for any choice of the map is an equivalence.

By induction, it suffices to cover the case where is and is the identity function.

But then, we have that is definitionally equal to which is known to be an equivalence.

Object classifiersπŸ”—

In category theory, the idea of classifiers (or classifying objects) often comes up when categories applied to the study of logic. For example, any elementary topos has a subobject classifier: an object such that maps corresponds to maps with propositional fibres (equivalently, inclusions In higher categorical analyses of logic, classifying objects exist for more maps: an elementary 2-topos has a discrete object classifier, which classify maps with discrete fibres.

Since a has classifiers for maps with fibres, and a has classifiers for maps with fibres, one might expect that an would have classifiers for maps with fibres that are not truncated at all. This is indeed the case! In HoTT, this fact is internalised using the univalent universes, and we can prove that univalent universes are object classifiers.

private variable
  E : Type β„“
open is-iso

As an intermediate step, we prove that the value of a type family at a point is equivalent to the fibre of over The proof follows from the De Morgan structure on the interval, and the β€œspread” operation coe1β†’i.

-- HoTT book lemma 4.8.1
Fibre-equiv : (B : A β†’ Type β„“') (a : A)
            β†’ fibre (fst {B = B}) a ≃ B a
Fibre-equiv B a = Iso→Equiv isom where
  isom : Iso _ _
  isom .fst ((x , y) , p) = subst B p y
  isom .snd .inv x        = (a , x) , refl
  isom .snd .rinv x i     = coe1β†’i (Ξ» _ β†’ B a) i x
  isom .snd .linv ((x , y) , p) i =
    (p (~ i) , coe1β†’i (Ξ» j β†’ B (p (~ i ∧ ~ j))) i y) , Ξ» j β†’ p (~ i ∨ j)

Another fact from homotopy theory that we can import into homotopy type theory is that any map is equivalent to a fibration. More specifically, given a map the total space is equivalent to the dependent sum of the fibres. The theorems Total-equiv and Fibre-equiv are what justify referring to Ξ£ the β€œtotal space” of a type family.

Total-equiv : (p : E β†’ B) β†’ E ≃ Ξ£ B (fibre p)
Total-equiv p = Iso→Equiv isom where
  isom : Iso _ (Ξ£ _ (fibre p))
  isom .fst x                   = p x , x , refl
  isom .snd .inv (_ , x , _)    = x
  isom .snd .rinv (b , x , q) i = q i , x , Ξ» j β†’ q (i ∧ j)
  isom .snd .linv x             = refl

Putting these together, we get the promised theorem: The space of maps is equivalent to the space of fibrations with base space and variable total space If we allow and to live in different universes, then the maps are classified by the biggest universe in which they both fit, namely Type (β„“ βŠ” β„“'). Note that the proof of Fibration-equiv makes fundamental use of ua, to construct the witnesses that taking fibres and taking total spaces are inverses. Without ua, we could only get an β€œisomorphism-up-to-equivalence” of types.

Fibration-equiv : βˆ€ {β„“ β„“'} {B : Type β„“}
                β†’ (Ξ£[ E ∈ Type (β„“ βŠ” β„“') ] (E β†’ B))
                ≃ (B β†’ Type (β„“ βŠ” β„“'))
Fibration-equiv {B = B} = Iso→Equiv isom where
  isom : Iso (Ξ£[ E ∈ Type _ ] (E β†’ B)) (B β†’ Type _)
  isom .fst (E , p)       = fibre p
  isom .snd .inv p⁻¹      = Σ _ p⁻¹ , fst
  isom .snd .rinv prep i x = ua (Fibre-equiv prep x) i
  isom .snd .linv (E , p) i
    = ua e (~ i) , Ξ» x β†’ fst (ua-unglue e (~ i) x)
    where e = Total-equiv p

To solidify the explanation that object classifiers generalise the object classifiers you would find in a we prove that any class of maps described by a property which holds of all of its fibres (or even structure on all of its fibres!) has a classifying object β€” the total space

For instance, if we take to be the property of being a proposition, this theorem tells us that Ξ£ is-prop classifies subobjects. With the slight caveat that Ξ£ is-prop is not closed under impredicative quantification, this corresponds exactly to the notion of subobject classifier in a since the maps with propositional fibres are precisely the injective maps.

_ = is-prop

Since the type of β€œmaps into B with variable domain and P fibres” has a very unwieldy description β€” both in words or in Agda syntax β€” we abbreviate it by The notation is meant to evoke the idea of a slice category: The objects of are objects of the category equipped with choices of maps into Similarly, the objects of are objects of the universe with a choice of map into such that holds for all the fibres of 

_/[_]_ : βˆ€ {β„“' β„“''} (β„“ : Level) β†’ (Type (β„“ βŠ” β„“') β†’ Type β„“'') β†’ Type β„“' β†’ Type _
_/[_]_ {β„“} β„“' P B =
  Ξ£ (Type (β„“ βŠ” β„“')) Ξ» A β†’
  Ξ£ (A β†’ B) Ξ» f β†’
  (x : B) β†’ P (fibre f x)

The proof that the slice is classified by follows from elementary properties of types (namely: reassociation, distributivity of over and the classification theorem Fibration-equiv. Really, the most complicated part of this proof is rearranging the nested sum and product types to a form to which we can apply Fibration-equiv.

Map-classifier
  : βˆ€ {β„“ β„“' β„“''} {B : Type β„“'} (P : Type (β„“ βŠ” β„“') β†’ Type β„“'')
  β†’ (β„“ /[ P ] B) ≃ (B β†’ Ξ£ _ P)
Map-classifier {β„“ = β„“} {B = B} P =
  (Ξ£ _ Ξ» A β†’ Ξ£ _ Ξ» f β†’ (x : B) β†’ P (fibre f x))     β‰ƒβŸ¨ Ξ£-assoc βŸ©β‰ƒ
  (Ξ£ _ Ξ» { (x , f) β†’ (x : B) β†’ P (fibre f x) })   β‰ƒβŸ¨ Ξ£-ap-fst (Fibration-equiv {β„“' = β„“}) βŸ©β‰ƒ
  (Ξ£ _ Ξ» A β†’ (x : B) β†’ P (A x))                   β‰ƒβŸ¨ Ξ£-Ξ -distrib e⁻¹ βŸ©β‰ƒ
  (B β†’ Ξ£ _ P)                                     β‰ƒβˆŽ

module ua {β„“} {A B : Type β„“} = Equiv (ua {A = A} {B} , univalence⁻¹)

unglue-is-equiv
  : βˆ€ {β„“ β„“'} {A : Type β„“} (Ο† : I)
  β†’ {B : Partial Ο† (Ξ£ (Type β„“') (_≃ A))}
  β†’ is-equiv {A = Glue A B} (unattach Ο†)
unglue-is-equiv {A = A} φ {B = B} .is-eqv y = extend→is-contr ctr
  where module _ (ψ : I) (par : Partial ψ (fibre (unattach Ο†) y)) where
    fib : .(p : IsOne Ο†)
        β†’ fibre (B p .snd .fst) y
          [ (ψ ∧ Ο†) ↦ (Ξ» { (ψ = i1) (Ο† = i1) β†’ par 1=1 }) ]
    fib p = is-contrβ†’extend (B p .snd .snd .is-eqv y) (ψ ∧ Ο†) _

    sys : βˆ€ j β†’ Partial (Ο† ∨ ψ ∨ ~ j) A
    sys j (j = i0) = y
    sys j (Ο† = i1) = outS (fib 1=1) .snd (~ j)
    sys j (ψ = i1) = par 1=1 .snd (~ j)

    ctr = inS $β‚› attach Ο† (Ξ» { (Ο† = i1) β†’ outS (fib 1=1) .fst })
                  (inS (hcomp (Ο† ∨ ψ) sys))
               , (Ξ» i β†’ hfill (Ο† ∨ ψ) (~ i) sys)

ua-unglue-is-equiv
  : βˆ€ {β„“} {A B : Type β„“} (f : A ≃ B)
  β†’ PathP (Ξ» i β†’ is-equiv (ua-unglue f i)) (f .snd) id-equiv
ua-unglue-is-equiv f =
  is-prop→pathp (λ j → is-equiv-is-prop (ua-unglue f j)) (f .snd) id-equiv

uaβˆ™ : βˆ€ {β„“} {A B C : Type β„“} {f : A ≃ B} {g : B ≃ C} β†’ ua (f βˆ™e g) ≑ ua f βˆ™ ua g
uaβˆ™ {β„“ = β„“} {A} {B} {C} {f} {g} = βˆ™-unique (ua (f βˆ™e g)) Ξ» i j β†’ Glue C Ξ» where
  (i = i0) β†’ ua f j , (Ξ» x β†’ g .fst (ua-unglue f j x)) ,
    is-prop→pathp (λ j → is-equiv-is-prop (λ x → g .fst (ua-unglue f j x)))
      ((f βˆ™e g) .snd) (g .snd) j
  (i = i1) β†’ ua (f βˆ™e g) j , ua-unglue (f βˆ™e g) j , ua-unglue-is-equiv (f βˆ™e g) j
  (j = i0) β†’ A , f βˆ™e g
  (j = i1) β†’ ua g i , ua-unglue g i , ua-unglue-is-equiv g i

sym-ua : βˆ€ {β„“} {A B : Type β„“} (e : A ≃ B) β†’ sym (ua e) ≑ ua (e e⁻¹)
sym-ua {A = A} {B = B} e i j = Glue B Ξ» where
  (i = i0) β†’ ua e (~ j)   , ua-unglue e (~ j) , ua-unglue-is-equiv e (~ j)
  (i = i1) β†’ ua (e e⁻¹) j , (Ξ» x β†’ e .fst (ua-unglue (e e⁻¹) j x)) ,
    is-propβ†’pathp (Ξ» j β†’ is-equiv-is-prop Ξ» x β†’ e .fst (ua-unglue (e e⁻¹) j x))
      (((e e⁻¹) βˆ™e e) .snd) (e .snd) j
  (j = i0) β†’ B , (Ξ» x β†’ Equiv.Ξ΅ e x (~ i)) ,
    is-prop→pathp (λ j → is-equiv-is-prop λ x → Equiv.Ρ e x (~ j))
      id-equiv (((e e⁻¹) βˆ™e e) .snd) i
  (j = i1) β†’ A , e

ua-inc : βˆ€ {β„“} {Aβ‚€ A₁ : Type β„“} (e : Aβ‚€ ≃ A₁) (x : Aβ‚€) (i : I) β†’ ua e i
ua-inc e x i = ua-glue e i (Ξ» ._ β†’ x) (inS (e .fst x))

ua→
  : βˆ€ {e : Aβ‚€ ≃ A₁} {B : (i : I) β†’ ua e i β†’ Type β„“'} {fβ‚€ f₁}
  β†’ (βˆ€ a β†’ PathP (Ξ» i β†’ B i (ua-inc e a i)) (fβ‚€ a) (f₁ (e .fst a)))
  β†’ PathP (Ξ» i β†’ (x : ua e i) β†’ B i x) fβ‚€ f₁
uaβ†’ {e = e} {B} {fβ‚€ = fβ‚€} {f₁} h = (Ξ» i a β†’ comp (Ξ» j β†’ B (i ∨ ~ j) (x' i (~ j) a)) (βˆ‚ i) (sys i a)) module uaβ†’ where
  x' : βˆ€ i j (x : ua e i) β†’ ua e (i ∨ j)
  x' i j x = ua-glue e (i ∨ j) (Ξ» { (i = i0) (j = i0) β†’ x }) (inS (unattach (βˆ‚ i) x))

  sys : βˆ€ i (a : ua e i) j β†’ Partial (βˆ‚ i ∨ ~ j) (B (i ∨ ~ j) (x' i (~ j) a))
  sys i a j (j = i0) = f₁ (unattach (βˆ‚ i) a)
  sys i a j (i = i0) = h a (~ j)
  sys i a j (i = i1) = f₁ a

  filler : βˆ€ i j (a : ua e i) β†’ B (i ∨ ~ j) (x' i (~ j) a)
  filler i j a = fill (Ξ» j β†’ B (i ∨ ~ j) (x' i (~ j) a)) (βˆ‚ i) j (sys i a)

ua→'
  : βˆ€ {e : Aβ‚€ ≃ A₁} {B : (i : I) β†’ ua e i β†’ Type β„“'} {fβ‚€ : {a : Aβ‚€} β†’ B i0 a} {f₁ : {a : A₁} β†’ B i1 a}
  β†’ (βˆ€ a β†’ PathP (Ξ» i β†’ B i (ua-inc e a i)) (fβ‚€ {a}) (f₁ {e .fst a}))
  β†’ PathP (Ξ» i β†’ {x : ua e i} β†’ B i x) fβ‚€ f₁
uaβ†’' {B = B} {fβ‚€} {f₁} h i {x} = uaβ†’ {B = B} {fβ‚€ = Ξ» x β†’ fβ‚€ {x}} {f₁ = Ξ» x β†’ f₁ {x}} h i x

transport-βˆ™ : βˆ€ {β„“} {A B C : Type β„“}
            β†’ (p : A ≑ B) (q : B ≑ C) (u : A)
            β†’ transport (p βˆ™ q) u ≑ transport q (transport p u)
transport-βˆ™ p q x i =
  transport (βˆ™-filler' p q (~ i)) (transport-filler-ext p i x)

subst-βˆ™ : βˆ€ {β„“ β„“'} {A : Type β„“} β†’ (B : A β†’ Type β„“')
        β†’ {x y z : A} (p : x ≑ y) (q : y ≑ z) (u : B x)
        β†’ subst B (p βˆ™ q) u ≑ subst B q (subst B p u)
subst-βˆ™ B p q Bx i =
  transport (ap B (βˆ™-filler' p q (~ i))) (transport-filler-ext (ap B p) i Bx)

  1. Not the fundamental theorem of engineering!β†©οΈŽ

References

  • Cohen, Cyril, Thierry Coquand, Simon Huber, and Anders MΓΆrtberg. 2016. β€œCubical Type Theory: A Constructive Interpretation of the Univalence Axiom.” https://arxiv.org/abs/1611.02108.