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

module 1Lab.Type.Pi where

Properties of Ξ  typesπŸ”—

This module contains properties of dependent function types, not necessarily organised in any way.

Closure under equivalencesπŸ”—

Univalence automatically implies that every type former respects equivalences. However, this theorem is limited to equivalences between types in the same universe. Thus, there are functions to perturb the codomain of a dependent function by an equivalence across universe levels:

Ξ -cod≃ : ((x : A) β†’ P x ≃ Q x) β†’ ((x : A) β†’ P x) ≃ ((x : A) β†’ Q x)
Ξ -cod≃ k .fst f x = k x .fst (f x)
Ξ -cod≃ k .snd .is-eqv f .centre .fst x   = equiv-centre (k x) (f x) .fst
Ξ -cod≃ k .snd .is-eqv f .centre .snd i x = equiv-centre (k x) (f x) .snd i
Ξ -cod≃ k .snd .is-eqv f .paths (g , p) i .fst x =
  equiv-path (k x) (f x) (g x , Ξ» j β†’ p j x) i .fst
Ξ -cod≃ k .snd .is-eqv f .paths (g , p) i .snd j x =
  equiv-path (k x) (f x) (g x , Ξ» k β†’ p k x) i .snd j

Ξ -impl-cod≃ : ((x : A) β†’ P x ≃ Q x) β†’ ({x : A} β†’ P x) ≃ ({x : A} β†’ Q x)
Ξ -impl-cod≃ k .fst f {x} = k x .fst (f {x})
Ξ -impl-cod≃ k .snd .is-eqv f .centre .fst {x}   = equiv-centre (k x) (f {x}) .fst
Ξ -impl-cod≃ k .snd .is-eqv f .centre .snd i {x} = equiv-centre (k x) (f {x}) .snd i
Ξ -impl-cod≃ k .snd .is-eqv f .paths (g , p) i .fst {x} =
  equiv-path (k x) (f {x}) (g {x} , Ξ» j β†’ p j {x}) i .fst
Ξ -impl-cod≃ k .snd .is-eqv f .paths (g , p) i .snd j {x} =
  equiv-path (k x) (f {x}) (g {x} , Ξ» k β†’ p k {x}) i .snd j

For non-dependent functions, we can easily perturb both domain and codomain:

function≃ : (A ≃ B) β†’ (C ≃ D) β†’ (A β†’ C) ≃ (B β†’ D)
function≃ dom rng = Isoβ†’Equiv the-iso where
  rng-iso = is-equiv→is-iso (rng .snd)
  dom-iso = is-equiv→is-iso (dom .snd)

  the-iso : Iso _ _
  the-iso .fst f x = rng .fst (f (dom-iso .is-iso.inv x))
  the-iso .snd .is-iso.inv f x = rng-iso .is-iso.inv (f (dom .fst x))
  the-iso .snd .is-iso.rinv f =
    funext Ξ» x β†’ rng-iso .is-iso.rinv _
               βˆ™ ap f (dom-iso .is-iso.rinv _)
  the-iso .snd .is-iso.linv f =
    funext Ξ» x β†’ rng-iso .is-iso.linv _
               βˆ™ ap f (dom-iso .is-iso.linv _)

Dependent FunextπŸ”—

When the domain and codomain are simple types (rather than a higher shape), paths in function spaces are characterised by funext. We can generalise this to funext-dep, in which the domain and codomain are allowed to be lines of types:

funext-dep
  : {A : I β†’ Type β„“} {B : (i : I) β†’ A i β†’ Type ℓ₁}
    {f : (x : A i0) β†’ B i0 x} {g : (x : A i1) β†’ B i1 x}
  β†’ ( {xβ‚€ : A i0} {x₁ : A i1}
    β†’ (p : PathP A xβ‚€ x₁)
    β†’ PathP (Ξ» i β†’ B i (p i)) (f xβ‚€) (g x₁) )
  β†’ PathP (Ξ» i β†’ (x : A i) β†’ B i x) f g

funext-dep {A = A} {B} {f} {g} h i x =
  comp
    (λ k → B i (coei→i A i x k))
    (Ξ» k β†’ Ξ»
      { (i = i0) → f (coei→i A i0 x k)
      ; (i = i1) → g (coei→i A i1 x k)
      })
    (h (Ξ» j β†’ coe A i j x) i)

A very ugly cubical argument shows that this function is an equivalence:

funext-dep≃
  : {A : I β†’ Type β„“} {B : (i : I) β†’ A i β†’ Type ℓ₁}
    {f : (x : A i0) β†’ B i0 x} {g : (x : A i1) β†’ B i1 x}

  β†’ ( {xβ‚€ : A i0} {x₁ : A i1} (p : PathP A xβ‚€ x₁)
    β†’ PathP (Ξ» i β†’ B i (p i)) (f xβ‚€) (g x₁)
    )
  ≃ PathP (Ξ» i β†’ (x : A i) β†’ B i x) f g

funext-dep≃ {A = A} {B} {f} {g} = Isoβ†’Equiv isom where
  open is-iso
  isom : Iso _ _
  isom .fst = funext-dep
  isom .snd .is-iso.inv q p i = q i (p i)

  isom .snd .rinv q m i x =
    comp
      (Ξ» k β†’ B i (coeiβ†’i A i x (k ∨ m)))
      (Ξ» k β†’ Ξ»
        { (i = i0) β†’ f (coeiβ†’i A i0 x (k ∨ m))
        ; (i = i1) β†’ g (coeiβ†’i A i1 x (k ∨ m))
        ; (m = i1) β†’ q i x
        })
      (q i (coei→i A i x m))

  isom .snd .linv h m p i =
    comp
      (λ k → B i (lemi→i m k))
      (Ξ» k β†’ Ξ»
        { (i = i0) → f (lemi→i m k)
        ; (i = i1) → g (lemi→i m k)
        ; (m = i1) β†’ h p i
        })
      (h (λ j → lemi→j j m) i)
    where
    lemiβ†’j : βˆ€ j β†’ coe A i j (p i) ≑ p j
    lemi→j j =
      coe (Ξ» k β†’ coe A i k (p i) ≑ p k) i j (coeiβ†’i A i (p i))

    lemi→i : Square (lemi→j i) (coei→i A i (p i)) refl refl
    lemi→i =
      sym (coeiβ†’i (Ξ» k β†’ coe A i k (p i) ≑ p k) i (coeiβ†’i A i (p i)))
      ◁ Ξ» m k β†’ lemiβ†’j i (m ∨ k)

hetero-homotopy≃homotopy
  : {A : I β†’ Type β„“} {B : (i : I) β†’ Type ℓ₁}
    {f : A i0 β†’ B i0} {g : A i1 β†’ B i1}

  β†’ ({xβ‚€ : A i0} {x₁ : A i1} β†’ PathP A xβ‚€ x₁ β†’ PathP B (f xβ‚€) (g x₁))
  ≃ ((xβ‚€ : A i0) β†’ PathP B (f xβ‚€) (g (coe0β†’1 A xβ‚€)))

hetero-homotopy≃homotopy {A = A} {B} {f} {g} = Isoβ†’Equiv isom where
  open is-iso
  isom : Iso _ _
  isom .fst h xβ‚€ = h (SinglP-is-contr A xβ‚€ .centre .snd)
  isom .snd .inv k {xβ‚€} {x₁} p =
    subst (Ξ» fib β†’ PathP B (f xβ‚€) (g (fib .fst))) (SinglP-is-contr A xβ‚€ .paths (x₁ , p)) (k xβ‚€)

  isom .snd .rinv k = funext Ξ» xβ‚€ β†’
    ap (Ξ» Ξ± β†’ subst (Ξ» fib β†’ PathP B (f xβ‚€) (g (fib .fst))) Ξ± (k xβ‚€))
      (is-prop→is-set SinglP-is-prop (SinglP-is-contr A x₀ .centre) _
        (SinglP-is-contr A xβ‚€ .paths (SinglP-is-contr A xβ‚€ .centre))
        refl)
    βˆ™ transport-refl (k xβ‚€)

  isom .snd .linv h j {xβ‚€} {x₁} p =
    transp
      (Ξ» i β†’ PathP B (f xβ‚€) (g (SinglP-is-contr A xβ‚€ .paths (x₁ , p) (i ∨ j) .fst)))
      j
      (h (SinglP-is-contr A xβ‚€ .paths (x₁ , p) j .snd))