{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module ALMA.SecondPass.FinCatInfinityColimit where
open import Agda.Primitive using (Level; _⊔_)
open import Agda.Builtin.Equality using (_≡_; refl)
open import Level using (lift)
open import Data.Unit.Polymorphic.Base using (tt)
open import Data.Nat using (ℕ; zero; suc; _+_; _∸_; _≤_; _<_)
open import Data.Nat.Properties
using ( +-identityʳ; +-suc; m+[n∸m]≡n
; ≤-refl; ≤-trans; m≤n⇒m≤1+n )
open import Data.Fin.Base using (Fin; toℕ; inject₁)
open import Data.Fin.Properties using (toℕ-inject₁)
open import Data.Product.Base using (_,_; proj₁; proj₂)
open import Data.Sum.Base using (inj₁; inj₂)
open import Relation.Binary.PropositionalEquality.Core using (cong; sym; trans)
open import Relation.Binary.PropositionalEquality.Properties using (module ≡-Reasoning)
open ≡-Reasoning
open import Categories.Category.Core using (Category)
open import Categories.Functor.Core using (Functor)
open import Categories.Functor using (id; _∘F_)
open import ALMA.Cosmos.ContCategory using (ContCat)
open import ALMA.Cosmos.ContCategoryLemmas using (ShapeOf; PosOf)
open import ALMA.Cosmos.ContCatEquiv using (ShapeCat)
open import ALMA.SecondPass.Unfolding using (Unfolding; module Unfolding)
open import ALMA.SecondPass.MorphismObject
using (MorphismObject; idMorphismObject; compMorphismObject)
open import ALMA.SecondPass.MorphismMorphism
using (MorphismMorphism; idMorphismMorphism; compMorphismMorphism)
open import ALMA.SecondPass.Cosmos using (Cosmos; out)
open import ALMA.SecondPass.Terminal using (_≈C_; ≈C-refl; ≈C-sym; ≈C-trans)
open _≈C_
open import ALMA.SecondPass.FinCatNWitness using (module FinCatN)
open import ALMA.SecondPass.FinCatInfinity using (FinCat∞; TrivialFC∞; n-at)
open import ALMA.SecondPass.FinCatInfinityProjection
using (module FinCatNColimitProjection)
open FinCatNColimitProjection
using (extendFin; defaultFin; projCosmos; projCosmos-F₀-spec; cl-self)
open import ALMA.SecondPass.FinCatInfinityTowerCompat using (module FinCatTowerCompat)
open import ALMA.Cosmos.Carried.LimitSystem using (cl; ≤-or->)
mutual
record _⇒ℱX[_]_
{o h e o′ ℓ′ e′ s p : Level}
{C : Category o h e} {D : Category o′ ℓ′ e′}
{FC : Functor C (ContCat s p)} {FD : Functor D (ContCat s p)}
(F : Cosmos C FC)
(S : Functor (ShapeCat C FC) (ShapeCat D FD))
(G : Cosmos D FD)
: Set (o ⊔ h ⊔ e ⊔ o′ ⊔ ℓ′ ⊔ e′ ⊔ s ⊔ p) where
coinductive
field
out : ⇒ℱXLayer[ S ] F G
record ⇒ℱXLayer[_]
{o h e o′ ℓ′ e′ s p : Level}
{C : Category o h e} {D : Category o′ ℓ′ e′}
{FC : Functor C (ContCat s p)} {FD : Functor D (ContCat s p)}
(S : Functor (ShapeCat C FC) (ShapeCat D FD))
(F : Cosmos C FC) (G : Cosmos D FD)
: Set (o ⊔ h ⊔ e ⊔ o′ ⊔ ℓ′ ⊔ e′ ⊔ s ⊔ p) where
inductive
private
UF = out F
UG = out G
module Sf = Functor S
field
shapeTrans : ∀ {A} {s : ShapeOf FC A}
→ PosOf FC s
→ ShapeOf FD (Functor.₀ (Unfolding.unfoldFunctor UG) (Sf.₀ (A , s)))
morphismObj : MorphismObject UF UG S shapeTrans
morphismMor : MorphismMorphism UF UG S shapeTrans morphismObj
onunfold-next : ∀ {A} (s : ShapeOf FC A)
→ Unfolding.unfold-next UF s ⇒ℱX[ S ]
Unfolding.unfold-next UG (proj₂ (Sf.₀ (A , s)))
open _⇒ℱX[_]_ public
open ⇒ℱXLayer[_] public
id⇒ℱX : ∀ {o h e s p} {C : Category o h e} {FC : Functor C (ContCat s p)}
→ {F : Cosmos C FC} → F ⇒ℱX[ id ] F
id⇒ℱX {F = F} .out = record
{ shapeTrans = λ p → Unfolding.pos-to-shape UF _ p
; morphismObj = idMorphismObject UF
; morphismMor = idMorphismMorphism UF
; onunfold-next = λ _ → id⇒ℱX
}
where UF = out F
comp⇒ℱX : ∀
{o₁ h₁ e₁ o₂ h₂ e₂ o₃ h₃ e₃ s p}
{C : Category o₁ h₁ e₁} {D : Category o₂ h₂ e₂} {E : Category o₃ h₃ e₃}
{FC : Functor C (ContCat s p)} {FD : Functor D (ContCat s p)} {FE : Functor E (ContCat s p)}
{S₁ : Functor (ShapeCat C FC) (ShapeCat D FD)}
{S₂ : Functor (ShapeCat D FD) (ShapeCat E FE)}
{F : Cosmos C FC} {G : Cosmos D FD} {H : Cosmos E FE}
→ G ⇒ℱX[ S₂ ] H → F ⇒ℱX[ S₁ ] G → F ⇒ℱX[ S₂ ∘F S₁ ] H
comp⇒ℱX {S₁ = S₁} {S₂ = S₂} {F = F} {G = G} {H = H} g f .out = record
{ shapeTrans = λ p → shapeTrans (g .out) (MorphismObject.onPos moF p)
; morphismObj = compMorphismObject UF UG UH S₁ S₂ stF stG moF moG
; morphismMor = compMorphismMorphism UF UG UH S₁ S₂ stF stG mmF mmG
; onunfold-next = λ {A} s′ →
let A′ = proj₁ (S₁.₀ (A , s′))
s″ = proj₂ (S₁.₀ (A , s′))
in comp⇒ℱX (onunfold-next (g .out) {A = A′} s″)
(onunfold-next (f .out) s′)
}
where
open MorphismObject
module S₁ = Functor S₁
UF = out F; UG = out G; UH = out H
stF = shapeTrans (f .out); stG = shapeTrans (g .out)
moF = morphismObj (f .out); moG = morphismObj (g .out)
mmF = morphismMor (f .out); mmG = morphismMor (g .out)
module TowerShapeFunctors (m : ℕ) where
module M = FinCatN m
module S = FinCatN (suc m)
open M
S-proj : Functor (ShapeCat M.FinCatN TrivialFCN) (ShapeCat FinCat∞ TrivialFC∞)
S-proj = record
{ F₀ = λ { (A , _) → (toℕ A , lift tt) }
; F₁ = λ { (f , _) → (tt , refl) }
; identity = refl
; homomorphism = refl
; F-resp-≈ = λ _ → refl
}
S-embed : Functor (ShapeCat M.FinCatN TrivialFCN) (ShapeCat S.FinCatN S.TrivialFCN)
S-embed = record
{ F₀ = λ { (A , _) → (inject₁ A , lift tt) }
; F₁ = λ { (f , _) → (tt , refl) }
; identity = refl
; homomorphism = refl
; F-resp-≈ = λ _ → refl
}
module ProjCosmosMorphism (m : ℕ) where
open TowerShapeFunctors m
open FinCatN m
module S-proj = Functor S-proj
open MorphismObject
open MorphismMorphism
projCosmos-morphism : ∀ (x : Cosmos M.FinCatN TrivialFCN)
→ x ⇒ℱX[ S-proj ] projCosmos m x
projCosmos-morphism x .out .shapeTrans {A} _ = lift tt
projCosmos-morphism x .out .morphismObj .onPos {A} _ = lift tt
projCosmos-morphism x .out .morphismObj .pts-compat {A} _ = refl
projCosmos-morphism x .out .morphismMor .onActP {A} {B} _ _ _ = refl
projCosmos-morphism x .out .onunfold-next {A} (lift tt)
rewrite FinCatNColimitProjection.defaultFin-toℕ-self m A =
projCosmos-morphism (UX.unfold-next {A = A} (lift tt))
where
UX = out x
module UX = Unfolding UX
module EmbedCosmosMorphism (m : ℕ) where
open TowerShapeFunctors m
open FinCatTowerCompat m using (embedCosmos)
open FinCatN m
module S-embed = Functor S-embed
pred-inject₁ : ∀ (A : Fin M.n) → cl m (toℕ (inject₁ A)) ≡ A
pred-inject₁ A rewrite toℕ-inject₁ A =
FinCatNColimitProjection.cl-self m A
embedCosmos-morphism : ∀ (x : Cosmos M.FinCatN M.TrivialFCN)
→ x ⇒ℱX[ S-embed ] embedCosmos x
embedCosmos-morphism x .out = record
{ shapeTrans = λ {A} _ → lift tt
; morphismObj = record
{ onPos = λ {A} _ → lift tt
; pts-compat = λ {A} _ → refl
}
; morphismMor = record
{ onActP = λ {A} {B} _ _ _ → refl
}
; onunfold-next = onunfold
}
where
UX = out x
module UX = Unfolding UX
onunfold : ∀ {A} (s : ShapeOf M.TrivialFCN A)
→ UX.unfold-next s ⇒ℱX[ S-embed ]
Unfolding.unfold-next (out (embedCosmos x))
{A = inject₁ A} (lift tt)
onunfold {A} (lift tt)
rewrite pred-inject₁ A
= embedCosmos-morphism (UX.unfold-next {A = A} (lift tt))
record CompatibleTower : Set₁ where
field
seq : ∀ m → Cosmos (FinCatN.FinCatN m) (FinCatN.TrivialFCN m)
compat : ∀ m → seq (suc m) ≈C FinCatTowerCompat.embedCosmos m (seq m)
open CompatibleTower
private
f-at : ∀ (tower : CompatibleTower) m → Fin (n-at m) → Fin (n-at m)
f-at tower m A =
Functor.F₀ (Unfolding.unfoldFunctor (out (seq tower m))) (A , lift tt)
extendFin-cong : ∀ m (f g : Fin (n-at m) → Fin (n-at m)) k
→ (∀ x → f x ≡ g x) → extendFin m f k ≡ extendFin m g k
extendFin-cong m f g k feq with ≤-or-> (suc m) k
... | inj₁ _ = cong toℕ (feq (cl m k))
... | inj₂ _ = refl
extendFin-step : ∀ (tower : CompatibleTower) m k
→ extendFin (suc m) (f-at tower (suc m)) k ≡ extendFin m (f-at tower m) k
extendFin-step tower m k =
begin
extendFin (suc m) (f-at tower (suc m)) k
≡⟨ extendFin-cong (suc m) (f-at tower (suc m))
(FinCatTowerCompat.embedF₀ m (f-at tower m)) k
(λ A → compat tower m .unfoldFunctor₀-eq {A = A} (lift tt)) ⟩
extendFin (suc m) (FinCatTowerCompat.embedF₀ m (f-at tower m)) k
≡⟨ FinCatTowerCompat.extendFin-embedF₀ m (f-at tower m) k ⟩
extendFin m (f-at tower m) k
∎
extendFin-iter : ∀ (tower : CompatibleTower) m d k
→ extendFin (m + d) (f-at tower (m + d)) k ≡ extendFin m (f-at tower m) k
extendFin-iter tower m zero k
rewrite +-identityʳ m = refl
extendFin-iter tower m (suc d) k rewrite +-suc m d =
begin
extendFin (suc (m + d)) (f-at tower (suc (m + d))) k
≡⟨ extendFin-step tower (m + d) k ⟩
extendFin (m + d) (f-at tower (m + d)) k
≡⟨ extendFin-iter tower m d k ⟩
extendFin m (f-at tower m) k
∎
layer-up : ∀ (tower : CompatibleTower) m k
→ (m<k : m < k)
→ extendFin m (f-at tower m) k ≡ extendFin k (f-at tower k) k
layer-up tower m k m<k =
trans (sym (extendFin-iter tower m (k ∸ m) k))
(cong (λ j → extendFin j (f-at tower j) k)
(m+[n∸m]≡n m≤k))
where
m≤k = ≤-trans (m≤n⇒m≤1+n (≤-refl {x = m})) m<k
layer-down : ∀ (tower : CompatibleTower) m k
→ (k≤m : k ≤ m)
→ extendFin m (f-at tower m) k ≡ extendFin k (f-at tower k) k
layer-down tower m k k≤m =
trans (cong (λ j → extendFin j (f-at tower j) k)
(sym (m+[n∸m]≡n k≤m)))
(extendFin-iter tower k (m ∸ k) k)
extendFin-layer-independent : ∀ (tower : CompatibleTower) m k
→ extendFin m (f-at tower m) k ≡ extendFin k (f-at tower k) k
extendFin-layer-independent tower m k with ≤-or-> m k
... | inj₂ m<k = layer-up tower m k m<k
... | inj₁ k≤m = layer-down tower m k k≤m
subtower : CompatibleTower → ℕ → CompatibleTower
subtower tower k = record
{ seq = λ m →
Unfolding.unfold-next (out (seq tower m))
{A = FinCatNColimitProjection.defaultFin m k} (lift tt)
; compat = subtower-compat tower k
}
where
subtower-compat : ∀ tower k m
→ Unfolding.unfold-next (out (seq tower (suc m)))
{A = FinCatNColimitProjection.defaultFin (suc m) k} (lift tt)
≈C FinCatTowerCompat.embedCosmos m
(Unfolding.unfold-next (out (seq tower m))
{A = FinCatNColimitProjection.defaultFin m k} (lift tt))
subtower-compat tower k m = ≈C-trans step resp
where
open FinCatTowerCompat m using (embedCosmos; cl-embed-default)
c : seq tower (suc m) ≈C embedCosmos (seq tower m)
c = compat tower m
A0 = FinCatNColimitProjection.defaultFin (suc m) k
A1 = FinCatNColimitProjection.defaultFin m k
step
: Unfolding.unfold-next (out (seq tower (suc m)))
{A = A0} (lift tt)
≈C Unfolding.unfold-next (out (embedCosmos (seq tower m)))
{A = A0} (lift tt)
step = c .unfold-next-eq {A = A0} (lift tt)
goal
: Unfolding.unfold-next (out (embedCosmos (seq tower m)))
{A = A0} (lift tt)
≡ embedCosmos
(Unfolding.unfold-next (out (seq tower m))
{A = A1} (lift tt))
goal =
cong (λ B → embedCosmos
(Unfolding.unfold-next (out (seq tower m))
{A = B} (lift tt)))
(cl-embed-default k)
resp
: Unfolding.unfold-next (out (embedCosmos (seq tower m)))
{A = A0} (lift tt)
≈C embedCosmos
(Unfolding.unfold-next (out (seq tower m))
{A = A1} (lift tt))
resp rewrite goal = ≈C-refl
towerColimit : CompatibleTower → Cosmos FinCat∞ TrivialFC∞
towerColimit tower .out = record
{ unfoldFunctor = record
{ F₀ = λ { (k , _) →
Functor.₀ (Unfolding.unfoldFunctor (out (projCosmos k (seq tower k)))) (k , lift tt) }
; F₁ = λ _ → tt
; identity = refl
; homomorphism = refl
; F-resp-≈ = λ _ → refl
}
; unfold-next = λ { {k} _ → towerColimit (subtower tower k) }
; pos-to-shape = λ _ _ → lift tt
; pos-actS-compat = λ _ _ _ → refl
}
towerColimit-spec : ∀ (tower : CompatibleTower) m
→ projCosmos m (seq tower m) ≈C towerColimit tower
towerColimit-spec tower m = go
where
go : projCosmos m (seq tower m) ≈C towerColimit tower
go .unfoldFunctor₀-eq {A = k} (lift tt) =
begin
Functor.₀ (Unfolding.unfoldFunctor
(out (projCosmos m (seq tower m)))) (k , lift tt)
≡⟨ projCosmos-F₀-spec m (seq tower m) k ⟩
extendFin m (f-at tower m) k
≡⟨ extendFin-layer-independent tower m k ⟩
extendFin k (f-at tower k) k
≡˘⟨ projCosmos-F₀-spec k (seq tower k) k ⟩
Functor.₀ (Unfolding.unfoldFunctor
(out (projCosmos k (seq tower k)))) (k , lift tt)
∎
go .pos-to-shape-eq _ _ = refl
go .unfold-next-eq {A = k} (lift tt) =
towerColimit-spec (subtower tower k) m
towerColimit-unique : ∀ (tower : CompatibleTower) (z : Cosmos FinCat∞ TrivialFC∞)
→ (∀ m → projCosmos m (seq tower m) ≈C z)
→ z ≈C towerColimit tower
towerColimit-unique tower z spec =
≈C-trans (≈C-sym (spec zero)) (towerColimit-spec tower zero)