{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Wellspring.Properties.Bisim where
open import Wellspring.Properties.MorphLift public
record Bisim {ℓ : Level} {F : Cosmos ℓ} (ml : MorphLift F) {A B : Obj F} (f g : Hom F A B) : Set (lsuc ℓ) where
coinductive
private
module F = Cosmos F
module ML = MorphLift ml
field
shape-eq : (s : F.Shape A) → F.actS f s ≡ F.actS g s
pos-eq : (s : F.Shape A) (p : F.Pos (F.actS f s))
→ F.actP f s p ≡ F.actP g s (subst F.Pos (shape-eq s) p)
morph-bisim : ∀ (s : F.Shape A)
→ let liftF = ML.morphLift {A} {B} f s
liftG = ML.morphLift {A} {B} g s
liftG' = subst (λ X → F.unfold s ⇒ℱ F.unfold X) (sym (shape-eq s)) liftG
in liftF ≃⇒ℱ liftG'
unfold-bisim : (s : F.Shape A)
→ let chF = F.unfold-hom f s
chG = F.unfold-hom g s
chG' = subst (λ X → F.Hom (F.unfold-obj s) (F.unfold-obj X)) (sym (shape-eq s)) chG
in Bisim ml {A = F.unfold-obj s} {B = F.unfold-obj (F.actS f s)} chF chG'
open Bisim public
module _ {ℓ} {F : Cosmos ℓ} {ml : MorphLift F} where
refl-bisim : ∀ {A B : Obj F} (f : Hom F A B) → Bisim ml f f
refl-bisim {A} {B} f = go A B f
where
go : ∀ A B (f : Hom F A B) → Bisim ml f f
go A B f .Bisim.shape-eq s = refl
go A B f .Bisim.pos-eq s p = refl
go A B f .Bisim.morph-bisim s = refl-≃⇒ℱ
go A B f .Bisim.unfold-bisim s =
go (unfold-obj F s)
(unfold-obj F (actS F f s))
(unfold-hom F f s)
≡→bisim : ∀ {A B : Obj F} {f g : Hom F A B} → f ≡ g → Bisim ml f g
≡→bisim refl = refl-bisim _
subst-≃⇒ℱ-shape : ∀ {X : Obj F} {s1 s2 : Shape F X}
→ (eq : s1 ≡ s2)
→ {C : Cosmos ℓ}
→ {m1 m2 : C ⇒ℱ unfold F s1}
→ m1 ≃⇒ℱ m2
→ subst (λ s' → C ⇒ℱ unfold F s') eq m1
≃⇒ℱ
subst (λ s' → C ⇒ℱ unfold F s') eq m2
subst-≃⇒ℱ-shape refl h = h
sym-bisim : ∀ {A B} {f g : Hom F A B} → Bisim ml f g → Bisim ml g f
sym-bisim {A} {B} {f} {g} b = go A B f g b
where
mutual
go : ∀ Aₒ Bₒ (f g : Hom F Aₒ Bₒ) → Bisim ml f g → Bisim ml g f
go Aₒ Bₒ f g b .Bisim.shape-eq s = sym (Bisim.shape-eq b s)
go Aₒ Bₒ f g b .Bisim.pos-eq s p =
let eqS = Bisim.shape-eq b s
p' = subst (Pos F) (sym eqS) p
orig = Bisim.pos-eq b s p'
cancel : subst (Pos F) eqS p' ≡ p
cancel = subst-inv' (Pos F) eqS {b = p}
in sym (trans orig (cong (actP F g s) cancel))
go Aₒ Bₒ f g b .Bisim.morph-bisim s =
let eqS = Bisim.shape-eq b s
P : Shape F Bₒ → Set (lsuc ℓ)
P X = unfold F s ⇒ℱ unfold F X
liftF = morphLift ml f s
liftG = morphLift ml g s
orig = Bisim.morph-bisim b s
symOrig : subst P (sym eqS) liftG ≃⇒ℱ liftF
symOrig = sym-≃⇒ℱ orig
substSym : subst P eqS (subst P (sym eqS) liftG) ≃⇒ℱ subst P eqS liftF
substSym = subst-≃⇒ℱ-shape eqS symOrig
cancel : subst P eqS (subst P (sym eqS) liftG) ≡ liftG
cancel = subst-inv' P eqS {b = liftG}
eq1 : liftG ≃⇒ℱ subst P eqS liftF
eq1 = ≡-left-≃⇒ℱ (sym cancel) substSym
eq2 : liftG ≃⇒ℱ subst P (sym (sym eqS)) liftF
eq2 = ≡-right-≃⇒ℱ eq1 (cong (λ e → subst P e liftF) (sym-sym eqS))
in eq2
go Aₒ Bₒ f g b .Bisim.unfold-bisim s =
let eqS = Bisim.shape-eq b s
f' = unfold-hom F f s
g' = unfold-hom F g s
orig = Bisim.unfold-bisim b s
in aux Aₒ Bₒ s (actS F f s) (actS F g s) eqS f' g' orig
aux : ∀ (A' B' : Obj F) (s : Shape F A') (X Y : Shape F B') (eq : X ≡ Y)
(u : Hom F (unfold-obj F s) (unfold-obj F X))
(v : Hom F (unfold-obj F s) (unfold-obj F Y))
→ Bisim ml u (subst (λ Z → Hom F (unfold-obj F s) (unfold-obj F Z)) (sym eq) v)
→ Bisim ml v (subst (λ Z → Hom F (unfold-obj F s) (unfold-obj F Z)) (sym (sym eq)) u)
aux A' B' s X .X refl u v h = go (unfold-obj F s) (unfold-obj F X) u v h
trans-bisim : ∀ {A B} {f g h : Hom F A B}
→ Bisim ml f g → Bisim ml g h → Bisim ml f h
trans-bisim {A} {B} {f} {g} {h} b1 b2 = go A B f g h b1 b2
where
mutual
go : ∀ Aₒ Bₒ (f g h : Hom F Aₒ Bₒ)
→ Bisim ml f g → Bisim ml g h → Bisim ml f h
go Aₒ Bₒ f g h b1 b2 .Bisim.shape-eq s =
trans (Bisim.shape-eq b1 s) (Bisim.shape-eq b2 s)
go Aₒ Bₒ f g h b1 b2 .Bisim.pos-eq s p =
let
eq1 = Bisim.shape-eq b1 s
eq2 = Bisim.shape-eq b2 s
pos1 = Bisim.pos-eq b1 s p
pos2 = Bisim.pos-eq b2 s (subst (Pos F) eq1 p)
step = trans pos1 pos2
comp = subst-comp eq1 eq2 {b = p}
in trans step (cong (actP F h s) comp)
go Aₒ Bₒ f g h b1 b2 .Bisim.morph-bisim s =
let
eq1 = Bisim.shape-eq b1 s
eq2 = Bisim.shape-eq b2 s
eq = trans eq1 eq2
P : Shape F Bₒ → Set (lsuc ℓ)
P X = unfold F s ⇒ℱ unfold F X
liftH = morphLift ml h s
mor1 = Bisim.morph-bisim b1 s
mor2 = Bisim.morph-bisim b2 s
mor2' = subst-≃⇒ℱ-shape (sym eq1) mor2
step = trans-≃⇒ℱ mor1 mor2'
comp : subst P (sym eq1) (subst P (sym eq2) liftH)
≡ subst P (sym eq) liftH
comp =
trans
(subst-comp (sym eq2) (sym eq1) {b = liftH})
(cong (λ e → subst P e liftH) (sym (sym-trans eq1 eq2)))
in ≡-right-≃⇒ℱ step comp
go Aₒ Bₒ f g h b1 b2 .Bisim.unfold-bisim s =
let
eq1 = Bisim.shape-eq b1 s
eq2 = Bisim.shape-eq b2 s
f' = unfold-hom F f s
g' = unfold-hom F g s
h' = unfold-hom F h s
orig1 = Bisim.unfold-bisim b1 s
orig2 = Bisim.unfold-bisim b2 s
in aux Aₒ Bₒ s (actS F f s) (actS F g s) (actS F h s)
eq1 eq2 f' g' h' orig1 orig2
aux : ∀ (A' B' : Obj F) (s : Shape F A')
(X Y Z : Shape F B')
(eq1 : X ≡ Y) (eq2 : Y ≡ Z)
(u : Hom F (unfold-obj F s) (unfold-obj F X))
(v : Hom F (unfold-obj F s) (unfold-obj F Y))
(w : Hom F (unfold-obj F s) (unfold-obj F Z))
→ Bisim ml u (subst (λ Q → Hom F (unfold-obj F s) (unfold-obj F Q)) (sym eq1) v)
→ Bisim ml v (subst (λ Q → Hom F (unfold-obj F s) (unfold-obj F Q)) (sym eq2) w)
→ Bisim ml u (subst (λ Q → Hom F (unfold-obj F s) (unfold-obj F Q)) (sym (trans eq1 eq2)) w)
aux A' B' s X .X .X refl refl u v w h1 h2 =
go (unfold-obj F s) (unfold-obj F X) u v w h1 h2