Skip to content

InjectiveTypes.Structure

Martin Escardo, 13th June 2025

We repackage the definitions of algebraic injective and flabby types
in a more convenient way, which we refer to as injective structure and
flabby structure.

We also prove some useful lemmas about them.


{-# OPTIONS --safe --without-K --lossy-unification #-}

open import MLTT.Spartan

module InjectiveTypes.Structure
        {𝓦 : Universe}
        (D : 𝓦 Μ‡ )
       where

open import UF.Embeddings
open import UF.SubtypeClassifier

flabby-structure : (𝓀 : Universe) β†’ 𝓀 ⁺ βŠ” 𝓦 Μ‡
flabby-structure 𝓀
 = Ξ£ ⨆ κž‰ ((P : Ξ© 𝓀) β†’ (P holds β†’ D) β†’ D)
       , ((P : Ξ© 𝓀) (f : P holds β†’ D) (p : P holds) β†’ ⨆ P f ＝ f p)

injective-structure : (𝓀 π“₯ : Universe) β†’ 𝓀 ⁺ βŠ” π“₯ ⁺ βŠ” 𝓦 Μ‡
injective-structure 𝓀 π“₯
 = Ξ£ _∣_ κž‰ ({X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } β†’ (X β†’ D) β†’ (X β†ͺ Y) β†’ (Y β†’ D))
         , ({X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } (f : X β†’ D) (𝕛 : X β†ͺ Y) β†’ (f ∣ 𝕛) ∘ ⌊ 𝕛 βŒ‹ ∼ f)

derived-injective-structure
 : flabby-structure (𝓀 βŠ” π“₯) β†’ injective-structure 𝓀 π“₯
derived-injective-structure {𝓀} {π“₯} (⨆ , e)
 = _∣_ , e'
 where
  _∣_ : {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } β†’ (X β†’ D) β†’ (X β†ͺ Y) β†’ (Y β†’ D)
  (f ∣ 𝕛) y = ⨆ (Fiber 𝕛 y) (f ∘ fiber-point)

  e' : {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } (f : X β†’ D) (𝕛 : X β†ͺ Y) β†’ (f ∣ 𝕛) ∘ ⌊ 𝕛 βŒ‹ ∼ f
  e' f 𝕛 x = e (Fiber 𝕛 (⌊ 𝕛 βŒ‹ x)) (f ∘ fiber-point) (x , refl)

derived-flabby-structure
 : injective-structure 𝓀 π“₯ β†’ flabby-structure 𝓀
derived-flabby-structure {𝓀} (_∣_ , e) = ⨆ , e'
 where
  ⨆ : (P : Ξ© 𝓀) β†’ (P holds β†’ D) β†’ D
  ⨆ P f = (f ∣ embedding-to-πŸ™) ⋆

  e' : (P : Ξ© 𝓀) (f : P holds β†’ D) (p : P holds) β†’ ⨆ P f ＝ f p
  e' P f = e f embedding-to-πŸ™


We had already given (in InjectiveTypes.BlackBoard) conversions
between ainjective types and a flabby types. We now record that the
ones we gave here agree definitionally with those there, via the
"repackaging" equivalences gives below.

Unfortunately, InjectiveTypes has a global assumption of function
extensionality, which is not used for the definitions of algebraic
injective and flabby structure. Fortunately, we don't need to use the
proofs below (particularly because they are proved with refl), which
are here only for the purpose of emphasizing that we are working with
the same definitions repackaged in a different way.


open import UF.FunExt
open import UF.Equiv

module _ (fe : FunExt) where

 open import InjectiveTypes.Blackboard fe

 ainjective-type-repackaging : injective-structure 𝓀 π“₯ ≃ ainjective-type D 𝓀 π“₯
 ainjective-type-repackaging =
  qinveq
   (Ξ» (_∣_ , e) β†’ Ξ» {X} {Y} j i f β†’ (f ∣ (j , i)) , e f (j , i))
   ((Ξ» ainj β†’
       (Ξ» {X} {Y} f 𝕛 β†’ pr₁ (ainj ⌊ 𝕛 βŒ‹ ⌊ 𝕛 βŒ‹-is-embedding f)) ,
       (Ξ» {X} {Y} f 𝕛 β†’ prβ‚‚ (ainj ⌊ 𝕛 βŒ‹ ⌊ 𝕛 βŒ‹-is-embedding f))) ,
    (Ξ» _ β†’ refl) ,
    (Ξ» _ β†’ refl))

 aflabby-repackaging : flabby-structure 𝓀 ≃ aflabby D 𝓀
 aflabby-repackaging
  = qinveq
     (Ξ» (⨆ , e) P i f β†’ ⨆ (P , i) f , e (P , i) f)
     ((Ξ» aflab β†’
        (Ξ» P f β†’ pr₁ (aflab (P holds) (holds-is-prop P) f)) ,
        (Ξ» P f β†’ prβ‚‚ (aflab (P holds) (holds-is-prop P) f))) ,
      (Ξ» _ β†’ refl) ,
      (Ξ» _ β†’ refl))


TODO. Write the commutative squares corresponding to the following two
proofs as a comment.


 derived-flabby-structure-agreement
  : (s : injective-structure 𝓀 π“₯)
  β†’ ⌜ aflabby-repackaging ⌝ (derived-flabby-structure s)
  ＝ ainjective-types-are-aflabby D (⌜ ainjective-type-repackaging ⌝ s)
 derived-flabby-structure-agreement s = refl


 For the second one we need to do a manual eta expasion to deal with
 the way Agda works with implicit arguments, which gives unsolved
 constraints otherwise (this is a well known design issue).


 derived-injective-structure-agreement
  : (s : flabby-structure 𝓀)
  β†’ (Ξ» {X Y : 𝓀 Μ‡} (j : X β†’ Y)
     β†’ ⌜ ainjective-type-repackaging ⌝ (derived-injective-structure s) {X} {Y} j)
  ＝ aflabby-types-are-ainjective D (⌜ aflabby-repackaging ⌝ s)
 derived-injective-structure-agreement s = refl


We can change variables in ⨆ in the following sense. Notice that there
is a similar fact proved with the stronger assumption of univalence in
the development of the lifting monad. But propositional and functional
extensionality are enough.


open import UF.Subsingletons

module _
        (pe : propext 𝓀)
        (fe : funext 𝓀 𝓀)
        (⨆ : (P : Ξ© 𝓀) β†’ (P holds β†’ D) β†’ D)
        {P Q : Ξ© 𝓀}
        (f : P holds β†’ D)
       where

 ⨆-change-of-variable : ((g , h) : (P holds) ↔ Q holds)
                      β†’ ⨆ P f ＝ ⨆ Q (f ∘ h)
 ⨆-change-of-variable (g , h) = IV
  where
   h' : (e : P ＝ Q) β†’ Q holds β†’ P holds
   h' e = ⌜ idtoeq _ _ (ap _holds e) ⌝⁻¹

   I : (e : P ＝ Q) β†’ h' e ＝ h
   I e = dfunext fe (Ξ» p β†’ holds-is-prop P (h' e p) (h p))

   II : (e : P ＝ Q) β†’ ⨆ P f ＝ ⨆ Q (f ∘ h' e)
   II refl = refl

   e : P ＝ Q
   e = Ξ©-extensionality pe fe g h

   III : ⨆ P f ＝ ⨆ Q (f ∘ h' e)
   III = II e

   IV : ⨆ P f ＝ ⨆ Q (f ∘ h)
   IV = transport (Ξ» - β†’ ⨆ P f ＝ ⨆ Q (f ∘ -)) (I e) III

 ⨆-change-of-variable-≃ : (π•˜ : (P holds) ≃ Q holds)
                        β†’ ⨆ P f ＝ ⨆ Q (f ∘ ⌜ π•˜ ⌝⁻¹)
 ⨆-change-of-variable-≃ π•˜ = ⨆-change-of-variable (⌜ π•˜ ⌝ , ⌜ π•˜ ⌝⁻¹)


TODO. The above just be placed in a better home, as it is not specific
to what we are doing here.

We give names to the projections.


injective-extension-operator
 : injective-structure 𝓀 π“₯
 β†’ {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } β†’ (X β†’ D) β†’ (X β†ͺ Y) β†’ (Y β†’ D)
injective-extension-operator (_∣_ , e) = _∣_

injective-identification
 : ((_∣_ , e) : injective-structure 𝓀 π“₯)
 β†’ {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } (f : X β†’ D) (𝕛 : X β†ͺ Y) β†’ (f ∣ 𝕛) ∘ ⌊ 𝕛 βŒ‹ ∼ f
injective-identification (_∣_ , e) = e

flabby-extension-operator
 : flabby-structure 𝓀
 β†’ (P : Ξ© 𝓀) β†’ (P holds β†’ D) β†’ D
flabby-extension-operator (⨆ , h) = ⨆

flabby-identification
 : ((⨆ , e) : flabby-structure 𝓀)
 β†’ (P : Ξ© 𝓀) (f : P holds β†’ D) (p : P holds) β†’ ⨆ P f ＝ f p
flabby-identification (_∣_ , e) = e


\end{code}

Maybe we should have worked with the following equivalent derived
injective structure, as this would have avoided some detours in
proofs in the module InjectiveTypes.Algebra.


module _
        {𝓀 π“₯ : Universe}
        (s@(⨆ , e) : flabby-structure (𝓀 βŠ” π“₯))
       where

 private
  module _ {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } (𝕛 : X β†ͺ Y) (y : Y) where
   k : fiber ⌊ 𝕛 βŒ‹ y β†’ πŸ™
   k = unique-to-πŸ™ {𝓀 βŠ” π“₯} {𝓀 βŠ” π“₯}

   g : fiber ⌊ 𝕛 βŒ‹ y β†’ fiber k ⋆
   g w = w , refl

   h : fiber k ⋆ β†’ fiber ⌊ 𝕛 βŒ‹ y
   h = pr₁

 derived-injective-structure' : injective-structure 𝓀 π“₯
 derived-injective-structure' = _∣_ , e'
  where
   _∣_ : {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } β†’ (X β†’ D) β†’ (X β†ͺ Y) β†’ (Y β†’ D)
   (f ∣ 𝕛) y = ⨆ (Fiber (fiber-to-πŸ™ 𝕛 y) ⋆) (f ∘ fiber-point ∘ h 𝕛 y)

   e' : {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } (f : X β†’ D) (𝕛 : X β†ͺ Y) β†’ (f ∣ 𝕛) ∘ ⌊ 𝕛 βŒ‹ ∼ f
   e' f 𝕛 x = e (Fiber (fiber-to-πŸ™ 𝕛 (⌊ 𝕛 βŒ‹ x)) ⋆)
                (f ∘ fiber-point ∘ h 𝕛 (⌊ 𝕛 βŒ‹ x))
                ((x , refl) , refl)

 private
  _∣_ _∣'_ : {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } β†’ (X β†’ D) β†’ (X β†ͺ Y) β†’ (Y β†’ D)
  _∣_  = injective-extension-operator (derived-injective-structure s)
  _∣'_ = injective-extension-operator derived-injective-structure'


The agreement of these two extension operators is a direct application
of change of variables in ⨆, defined above.


 derived-injective-structure-operator-lemma
  : propext (𝓀 βŠ” π“₯)
  β†’ funext (𝓀 βŠ” π“₯) (𝓀 βŠ” π“₯)
  β†’ {X : 𝓀 Μ‡ } {Y : π“₯ Μ‡ } (f : X β†’ D) (𝕛 : X β†ͺ Y)
  β†’ f ∣ 𝕛 ∼ f ∣' 𝕛
 derived-injective-structure-operator-lemma pe fe f 𝕛 y
  = (f ∣ 𝕛) y                                              ＝⟨refl⟩
    ⨆ (Fiber 𝕛 y) (f ∘ fiber-point)                       ＝⟨ I ⟩
    ⨆ (Fiber (fiber-to-πŸ™ 𝕛 y) ⋆) (f ∘ fiber-point ∘ h 𝕛 y) ＝⟨refl⟩
    (f ∣' 𝕛) y ∎
    where
     I = ⨆-change-of-variable pe fe ⨆ (f ∘ fiber-point) (g 𝕛 y , h 𝕛 y)