{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module ALMA.SecondPass.CumulativeHierarchyLimit where
open import Agda.Primitive using (Level; _⊔_; lsuc; Setω)
open import Agda.Builtin.Equality using (_≡_; refl)
open import Relation.Binary.Reasoning.Setoid as Setoid
open import Data.Nat using (ℕ; zero; suc; _+_)
open import Data.Unit.Polymorphic.Base using (tt)
open import Categories.Functor.Core using (Functor)
open import Categories.Functor using (_∘F_)
open import Categories.NaturalTransformation.NaturalIsomorphism
using (NaturalIsomorphism)
open import Categories.NaturalTransformation.Core using (ntHelper)
open import ALMA.SecondPass.Cosmos using (Cosmos; UnitCat; UnitContainerFunctor; UnitCosmos)
open import ALMA.SecondPass.Terminal using (_≈C_; ≈C-refl; ≈C-trans; cosmosSetoid)
open import ALMA.SecondPass.CoalgCat using (IsTerminalUpToBisim; cosmosIsTerminal)
open import ALMA.SecondPass.CumulativeHierarchy using (π)
open import ALMA.SecondPass.StrictLift
using (StrictLayer; strictStep-suc; EmbeddingRule; EmbedFamily; outer-rule)
record LayerIdx : Set₁ where
field
o h e s p : Level
open LayerIdx
nextIdx : LayerIdx → LayerIdx
nextIdx i = record
{ o = o i ⊔ s i
; h = h i ⊔ s i
; e = e i
; s = lsuc (s i ⊔ p i)
; p = lsuc (s i ⊔ p i)
}
idxAt : LayerIdx → ℕ → LayerIdx
idxAt i zero = i
idxAt i (suc n) = nextIdx (idxAt i n)
s-strict-at : (i : LayerIdx) (n : ℕ)
→ LayerIdx.s (idxAt i (suc n))
≡ lsuc (LayerIdx.s (idxAt i n) ⊔ LayerIdx.p (idxAt i n))
s-strict-at i n = refl
record Tower (i : LayerIdx) : Setω where
field
layer₀ : StrictLayer (o i) (h i) (e i) (s i) (p i)
layer : ∀ n → let j = idxAt i n in
StrictLayer (o j) (h j) (e j) (s j) (p j)
layer zero = layer₀
layer (suc n) = strictStep-suc (layer n)
layer-terminal :
∀ {o h e s p} (L : StrictLayer o h e s p)
→ IsTerminalUpToBisim {C = StrictLayer.C L} {FC = StrictLayer.FC L}
layer-terminal L = cosmosIsTerminal
tower-layer-terminal :
(i : LayerIdx) (T : Tower i) (n : ℕ)
→ IsTerminalUpToBisim
{C = StrictLayer.C (Tower.layer T n)}
{FC = StrictLayer.FC (Tower.layer T n)}
tower-layer-terminal i T n = layer-terminal (Tower.layer T n)
tower-step-preserves-≈C :
(R : EmbeddingRule)
(i : LayerIdx) (T : Tower i)
→ (fams : ∀ n → EmbedFamily R (Tower.layer T n))
→ ∀ n {x y}
→ _≈C_ {C = StrictLayer.C (Tower.layer T n)}
{FC = StrictLayer.FC (Tower.layer T n)} x y
→ _≈C_ {C = StrictLayer.C (Tower.layer T (suc n))}
{FC = StrictLayer.FC (Tower.layer T (suc n))}
(EmbeddingRule.Embed R (Tower.layer T n) x
(EmbedFamily.getData (fams n) x))
(EmbeddingRule.Embed R (Tower.layer T n) y
(EmbedFamily.getData (fams n) y))
tower-step-preserves-≈C R i T fams n =
EmbedFamily.resp-≈C (fams n)
record LimitLayer (i : LayerIdx) (T : Tower i) : Setω where
field
o∞ h∞ e∞ s∞ p∞ : Level
layer∞ : StrictLayer o∞ h∞ e∞ s∞ p∞
projC : ∀ n
→ Functor (StrictLayer.C (Tower.layer T n))
(StrictLayer.C layer∞)
open LimitLayer
limit-terminal :
(i : LayerIdx) (T : Tower i) (L∞ : LimitLayer i T)
→ IsTerminalUpToBisim
{C = StrictLayer.C (L∞ .layer∞)}
{FC = StrictLayer.FC (L∞ .layer∞)}
limit-terminal i T L∞ = cosmosIsTerminal
record LimitCompatible {i : LayerIdx} {T : Tower i}
(L∞ : LimitLayer i T) : Setω where
field
proj-step-coh :
∀ n
→ NaturalIsomorphism
(projC L∞ (suc n))
(projC L∞ n
∘F π (StrictLayer.C (Tower.layer T n))
(StrictLayer.FC (Tower.layer T n)))
open LimitCompatible
unitIdx : (ℓ : Level) → LayerIdx
unitIdx ℓ = record
{ o = ℓ
; h = ℓ
; e = ℓ
; s = ℓ
; p = ℓ
}
unitLayer₀ : (ℓ : Level) → StrictLayer ℓ ℓ ℓ ℓ ℓ
unitLayer₀ ℓ = record
{ C = UnitCat {ℓ}
; FC = UnitContainerFunctor {ℓ}
}
unitTower : (ℓ : Level) → Tower (unitIdx ℓ)
unitTower ℓ .Tower.layer₀ = unitLayer₀ ℓ
unit-tower-layer-terminal :
(ℓ : Level) (n : ℕ)
→ IsTerminalUpToBisim
{C = StrictLayer.C (Tower.layer (unitTower ℓ) n)}
{FC = StrictLayer.FC (Tower.layer (unitTower ℓ) n)}
unit-tower-layer-terminal ℓ n =
tower-layer-terminal (unitIdx ℓ) (unitTower ℓ) n
record EnrichedTower (R : EmbeddingRule) (i : LayerIdx) : Setω where
field
tower : Tower i
fams : ∀ n → EmbedFamily R (Tower.layer tower n)
open EnrichedTower
iterEmbed :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i) (m : ℕ)
→ Cosmos (StrictLayer.C (Tower.layer (tower ET) zero))
(StrictLayer.FC (Tower.layer (tower ET) zero))
→ Cosmos (StrictLayer.C (Tower.layer (tower ET) (zero + m)))
(StrictLayer.FC (Tower.layer (tower ET) (zero + m)))
iterEmbed R i ET zero x = x
iterEmbed R i ET (suc m) x =
EmbeddingRule.Embed R (Tower.layer (tower ET) (zero + m))
(iterEmbed R i ET m x)
(EmbedFamily.getData
(EnrichedTower.fams ET (zero + m))
(iterEmbed R i ET m x))
iterEmbed-suc :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(n : ℕ) (x : _)
→ iterEmbed R i ET (suc n) x
≡ EmbeddingRule.Embed R (Tower.layer (tower ET) n)
(iterEmbed R i ET n x)
(EmbedFamily.getData
(EnrichedTower.fams ET n)
(iterEmbed R i ET n x))
iterEmbed-suc R i ET n x = refl
iterEmbed-preserves-≈C :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i) (n : ℕ)
→ ∀ {x y : Cosmos (StrictLayer.C (Tower.layer (tower ET) zero))
(StrictLayer.FC (Tower.layer (tower ET) zero))}
→ _≈C_ {C = StrictLayer.C (Tower.layer (tower ET) zero)}
{FC = StrictLayer.FC (Tower.layer (tower ET) zero)}
x y
→ _≈C_ {C = StrictLayer.C (Tower.layer (tower ET) (zero + n))}
{FC = StrictLayer.FC (Tower.layer (tower ET) (zero + n))}
(iterEmbed R i ET n x) (iterEmbed R i ET n y)
iterEmbed-preserves-≈C R i ET zero eq = eq
iterEmbed-preserves-≈C R i ET (suc n) eq =
EmbedFamily.resp-≈C (EnrichedTower.fams ET n)
(iterEmbed-preserves-≈C R i ET n eq)
infixl 6 _+ʳ_
_+ʳ_ : ℕ → ℕ → ℕ
m +ʳ zero = m
m +ʳ suc n = suc (m +ʳ n)
iterEmbedFrom :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
→ (k m : ℕ)
→ Cosmos (StrictLayer.C (Tower.layer (tower ET) k))
(StrictLayer.FC (Tower.layer (tower ET) k))
→ Cosmos (StrictLayer.C (Tower.layer (tower ET) (k +ʳ m)))
(StrictLayer.FC (Tower.layer (tower ET) (k +ʳ m)))
iterEmbedFrom R i ET k zero x = x
iterEmbedFrom R i ET k (suc m) x =
EmbeddingRule.Embed R (Tower.layer (tower ET) (k +ʳ m))
(iterEmbedFrom R i ET k m x)
(EmbedFamily.getData
(EnrichedTower.fams ET (k +ʳ m))
(iterEmbedFrom R i ET k m x))
iterEmbed-add :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(m n : ℕ)
(x : Cosmos (StrictLayer.C (Tower.layer (tower ET) zero))
(StrictLayer.FC (Tower.layer (tower ET) zero)))
→ _≈C_ {C = StrictLayer.C (Tower.layer (tower ET) (m +ʳ n))}
{FC = StrictLayer.FC (Tower.layer (tower ET) (m +ʳ n))}
(iterEmbed R i ET (m +ʳ n) x)
(iterEmbedFrom R i ET m n (iterEmbed R i ET m x))
iterEmbed-add R i ET m zero x = ≈C-refl
iterEmbed-add R i ET m (suc n) x =
EmbedFamily.resp-≈C (EnrichedTower.fams ET (m +ʳ n))
(iterEmbed-add R i ET m n x)
enriched-layer-terminal :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i) (n : ℕ)
→ IsTerminalUpToBisim
{C = StrictLayer.C (Tower.layer (tower ET) n)}
{FC = StrictLayer.FC (Tower.layer (tower ET) n)}
enriched-layer-terminal R i ET n =
tower-layer-terminal i (tower ET) n
record LiftedLimitStructure (R : EmbeddingRule) (i : LayerIdx)
(ET : EnrichedTower R i) : Setω where
private
T = EnrichedTower.tower ET
FS = EnrichedTower.fams ET
field
limit : LimitLayer i T
liftAt : ∀ n
→ Cosmos (StrictLayer.C (Tower.layer T n))
(StrictLayer.FC (Tower.layer T n))
→ Cosmos (StrictLayer.C (LimitLayer.layer∞ limit))
(StrictLayer.FC (LimitLayer.layer∞ limit))
liftAt-resp-≈C : ∀ n {x y}
→ _≈C_ {C = StrictLayer.C (Tower.layer T n)}
{FC = StrictLayer.FC (Tower.layer T n)}
x y
→ _≈C_ {C = StrictLayer.C (LimitLayer.layer∞ limit)}
{FC = StrictLayer.FC (LimitLayer.layer∞ limit)}
(liftAt n x) (liftAt n y)
liftAt-step : ∀ n x
→ liftAt (suc n)
(EmbeddingRule.Embed R (Tower.layer T n) x
(EmbedFamily.getData (FS n) x))
≈C liftAt n x
open LiftedLimitStructure
liftAt-iterEmbed :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(LLS : LiftedLimitStructure R i ET)
→ ∀ n (x : Cosmos (StrictLayer.C (Tower.layer (EnrichedTower.tower ET) zero))
(StrictLayer.FC (Tower.layer (EnrichedTower.tower ET) zero)))
→ liftAt LLS n (iterEmbed R i ET n x)
≈C liftAt LLS zero x
liftAt-iterEmbed R i ET LLS zero x = ≈C-refl
liftAt-iterEmbed R i ET LLS (suc n) x =
≈C-trans
(liftAt-step LLS n (iterEmbed R i ET n x))
(liftAt-iterEmbed R i ET LLS n x)
liftAt-iterEmbedFrom :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(LLS : LiftedLimitStructure R i ET)
→ ∀ k m
(x : Cosmos (StrictLayer.C (Tower.layer (EnrichedTower.tower ET) k))
(StrictLayer.FC (Tower.layer (EnrichedTower.tower ET) k)))
→ liftAt LLS (k +ʳ m) (iterEmbedFrom R i ET k m x)
≈C liftAt LLS k x
liftAt-iterEmbedFrom R i ET LLS k zero x = ≈C-refl
liftAt-iterEmbedFrom R i ET LLS k (suc m) x =
≈C-trans
(liftAt-step LLS (k +ʳ m) (iterEmbedFrom R i ET k m x))
(liftAt-iterEmbedFrom R i ET LLS k m x)
liftAt-compose :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(LLS : LiftedLimitStructure R i ET)
→ ∀ k m n
(x : Cosmos (StrictLayer.C (Tower.layer (EnrichedTower.tower ET) k))
(StrictLayer.FC (Tower.layer (EnrichedTower.tower ET) k)))
→ liftAt LLS (k +ʳ (m +ʳ n)) (iterEmbedFrom R i ET k (m +ʳ n) x)
≈C liftAt LLS ((k +ʳ m) +ʳ n)
(iterEmbedFrom R i ET (k +ʳ m) n (iterEmbedFrom R i ET k m x))
liftAt-compose R i ET LLS k m n x =
let
C∞ = StrictLayer.C (LimitLayer.layer∞ (limit LLS))
FC∞ = StrictLayer.FC (LimitLayer.layer∞ (limit LLS))
module R' = Setoid (cosmosSetoid {C = C∞} {FC = FC∞})
in R'.begin
liftAt LLS (k +ʳ (m +ʳ n)) (iterEmbedFrom R i ET k (m +ʳ n) x)
R'.≈⟨ liftAt-iterEmbedFrom R i ET LLS k (m +ʳ n) x ⟩
liftAt LLS k x
R'.≈˘⟨ liftAt-iterEmbedFrom R i ET LLS k m x ⟩
liftAt LLS (k +ʳ m) (iterEmbedFrom R i ET k m x)
R'.≈˘⟨ liftAt-iterEmbedFrom R i ET LLS (k +ʳ m) n
(iterEmbedFrom R i ET k m x) ⟩
liftAt LLS ((k +ʳ m) +ʳ n)
(iterEmbedFrom R i ET (k +ʳ m) n (iterEmbedFrom R i ET k m x))
R'.∎
liftAt-iterEmbed-resp-≈C :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(LLS : LiftedLimitStructure R i ET) (n : ℕ)
→ ∀ {x y : Cosmos (StrictLayer.C (Tower.layer (EnrichedTower.tower ET) zero))
(StrictLayer.FC (Tower.layer (EnrichedTower.tower ET) zero))}
→ _≈C_ {C = StrictLayer.C (Tower.layer (EnrichedTower.tower ET) zero)}
{FC = StrictLayer.FC (Tower.layer (EnrichedTower.tower ET) zero)}
x y
→ _≈C_ {C = StrictLayer.C (LimitLayer.layer∞ (limit LLS))}
{FC = StrictLayer.FC (LimitLayer.layer∞ (limit LLS))}
(liftAt LLS n (iterEmbed R i ET n x))
(liftAt LLS n (iterEmbed R i ET n y))
liftAt-iterEmbed-resp-≈C R i ET LLS n eq =
liftAt-resp-≈C LLS n (iterEmbed-preserves-≈C R i ET n eq)
lift-zero-resp-≈C :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(LLS : LiftedLimitStructure R i ET)
→ ∀ {x y : Cosmos (StrictLayer.C (Tower.layer (EnrichedTower.tower ET) zero))
(StrictLayer.FC (Tower.layer (EnrichedTower.tower ET) zero))}
→ _≈C_ {C = StrictLayer.C (Tower.layer (EnrichedTower.tower ET) zero)}
{FC = StrictLayer.FC (Tower.layer (EnrichedTower.tower ET) zero)}
x y
→ _≈C_ {C = StrictLayer.C (LimitLayer.layer∞ (limit LLS))}
{FC = StrictLayer.FC (LimitLayer.layer∞ (limit LLS))}
(liftAt LLS zero x) (liftAt LLS zero y)
lift-zero-resp-≈C R i ET LLS = liftAt-resp-≈C LLS zero
lifted-limit-terminal :
(R : EmbeddingRule) (i : LayerIdx) (ET : EnrichedTower R i)
(LLS : LiftedLimitStructure R i ET)
→ IsTerminalUpToBisim
{C = StrictLayer.C (LimitLayer.layer∞ (limit LLS))}
{FC = StrictLayer.FC (LimitLayer.layer∞ (limit LLS))}
lifted-limit-terminal R i ET LLS =
limit-terminal i (EnrichedTower.tower ET) (limit LLS)
UnitFamily : (ℓ : Level) → Setω
UnitFamily ℓ =
∀ n → EmbedFamily outer-rule (Tower.layer (unitTower ℓ) n)
unitEnrichedTower : (ℓ : Level) → UnitFamily ℓ
→ EnrichedTower outer-rule (unitIdx ℓ)
unitEnrichedTower ℓ fams = record
{ tower = unitTower ℓ
; fams = fams
}
unitLimit : (ℓ ℓ∞ : Level) → LimitLayer (unitIdx ℓ) (unitTower ℓ)
unitLimit ℓ ℓ∞ = record
{ o∞ = ℓ∞
; h∞ = ℓ∞
; e∞ = ℓ∞
; s∞ = ℓ∞
; p∞ = ℓ∞
; layer∞ = record
{ C = UnitCat {ℓ∞}
; FC = UnitContainerFunctor {ℓ∞}
}
; projC = λ n → record
{ F₀ = λ _ → tt
; F₁ = λ _ → tt
; identity = tt
; homomorphism = tt
; F-resp-≈ = λ _ → tt
}
}
unitLimit-compatible : (ℓ ℓ∞ : Level) → LimitCompatible (unitLimit ℓ ℓ∞)
unitLimit-compatible ℓ ℓ∞ = record
{ proj-step-coh = λ n → record
{ F⇒G = ntHelper record
{ η = λ _ → tt
; commute = λ _ → tt
}
; F⇐G = ntHelper record
{ η = λ _ → tt
; commute = λ _ → tt
}
; iso = λ _ → record { isoˡ = tt ; isoʳ = tt }
}
}
unitLiftAt : (ℓ ℓ∞ : Level) (n : ℕ)
→ Cosmos (StrictLayer.C (Tower.layer (unitTower ℓ) n))
(StrictLayer.FC (Tower.layer (unitTower ℓ) n))
→ Cosmos (UnitCat {ℓ∞}) (UnitContainerFunctor {ℓ∞})
unitLiftAt ℓ ℓ∞ n _ = UnitCosmos {ℓ∞}
unitLiftedLimitStructure :
(ℓ ℓ∞ : Level) (fams : UnitFamily ℓ)
→ LiftedLimitStructure outer-rule (unitIdx ℓ) (unitEnrichedTower ℓ fams)
unitLiftedLimitStructure ℓ ℓ∞ fams = record
{ limit = unitLimit ℓ ℓ∞
; liftAt = unitLiftAt ℓ ℓ∞
; liftAt-resp-≈C = λ n _ → ≈C-refl
; liftAt-step = λ n x → ≈C-refl
}
unit-liftAt-iterEmbed :
(ℓ ℓ∞ : Level) (fams : UnitFamily ℓ) (n : ℕ)
(x : Cosmos (StrictLayer.C (Tower.layer (unitTower ℓ) zero))
(StrictLayer.FC (Tower.layer (unitTower ℓ) zero)))
→ _≈C_ {C = UnitCat {ℓ∞}}
{FC = UnitContainerFunctor {ℓ∞}}
(LiftedLimitStructure.liftAt
(unitLiftedLimitStructure ℓ ℓ∞ fams) n
(iterEmbed outer-rule (unitIdx ℓ)
(unitEnrichedTower ℓ fams) n x))
(LiftedLimitStructure.liftAt
(unitLiftedLimitStructure ℓ ℓ∞ fams) zero x)
unit-liftAt-iterEmbed ℓ ℓ∞ fams =
liftAt-iterEmbed outer-rule (unitIdx ℓ)
(unitEnrichedTower ℓ fams)
(unitLiftedLimitStructure ℓ ℓ∞ fams)