open import Cat.Functor.Equivalence.Complete open import Cat.Functor.Conservative open import Cat.Functor.Equivalence open import Cat.Diagram.Limit.Base open import Cat.Diagram.Terminal open import Cat.Diagram.Monad open import Cat.Prelude import Cat.Reasoning module Cat.Diagram.Monad.Limits {o ℓ} {C : Precategory o ℓ} {M : Monad C} where

# Limits in categories of algebras🔗

Suppose that $\ca{C}$ be a category, $M$ be a monad on $\ca{C}$, and $F$ be a $\ca{J}$-shaped diagram of $M$-algebras (that is, a functor $F : \ca{J} \to \ca{C}^M$ into the Eilenberg-Moore category of M). Suppose that an evil wizard has given you a limit for the diagram in $\ca{C}$ which underlies $F$, but they have not (being evil and all) told you whether $\lim F$ admits an algebra structure at all.

Perhaps we can make this situation slightly more concrete, by working in a category *equivalent to* an Eilenberg-Moore category: If we have two groups $G$, $H$, considered as a discrete diagram, then the limit our evil wizard would give us is the product $U(G) \times U(H)$ in $\sets$. But we already know we can equip this product with a “pointwise” group structure! Does this result generalise?

The answer is positive, though this is one of those cases where abstract nonsense can not help us: gotta roll up our sleeves and calculate away. Suppose we have a diagram as in the setup — we’ll show that the functor $U : \ca{C}^M \to \ca{C}$ both preserves and *reflects* limits, in that $K$ is a limiting cone if, and only if, $U(K)$ is.

module _ {jo jℓ} {J : Precategory jo jℓ} (F : Functor J (Eilenberg-Moore C M)) where private module F = Functor F Forget-reflects-limits : (K : Cone F) → is-limit (Forget C M F∘ F) (F-map-cone (Forget C M) K) → is-limit F K Forget-reflects-limits K uniq other = contr ! unique where !′ = uniq (F-map-cone (Forget C M) other) .centre

Let $L$ be a cone over $F$: Since $U(K)$ is a limiting cone, then we have a unique map of $U(L) \to U(K)$, which we must show extends to a map of *algebras* $L \to K$, which by definition means $! \nu = \nu M_1(!)$. But those are maps $M_0(L) \to U(K)$ — so if $M_0(L)$ was a cone over $U \circ F$, and those two were maps of cones, then they would be equal!

! : Cone-hom _ other K ! .hom .morphism = !′ .hom ! .hom .commutes = ap hom $ is-contr→is-prop (uniq cone′) (record { hom = !′ .hom C.∘ apex other .snd .ν ; commutes = λ o → C.pulll (!′ .commutes o) }) (record { hom = apex K .snd .ν C.∘ M.M₁ (!′ .hom) ; commutes = λ o → C.pulll (K .ψ o .commutes) ·· C.pullr (sym (M.M-∘ _ _) ∙ ap M.M₁ (!′ .commutes o)) ·· sym (other .ψ o .commutes) })

The cone structure on $M_0(L)$ is given by composites $\psi_x \nu$, which commute because $\psi$ is also a cone structure. More explicitly, what we must show is $F_1(o) \psi_x \nu = \psi_y \nu$, which follows immediately.

where cone′ : Cone (Forget C M F∘ F) cone′ .apex = M.M₀ (apex other .fst) cone′ .ψ x = morphism (ψ other x) C.∘ apex other .snd .ν cone′ .commutes o = C.pulll (ap morphism (commutes other o)) ! .commutes o = Algebra-hom-path _ (uniq (F-map-cone (Forget C M) other) .centre .commutes o)

For uniqueness, we use that the map $U(L) \to U(K)$ is unique, and that the functor $U$ is faithful.

unique : ∀ x → ! ≡ x unique x = Cone-hom-path _ $ Algebra-hom-path _ $ ap hom (uniq (F-map-cone (Forget _ M) other) .paths hom′) where hom′ : Cone-hom _ _ _ hom′ .hom = hom x .morphism hom′ .commutes o = ap morphism (x .commutes o)

I hope you like appealing to uniqueness of maps into limits, by the way. We now relax the conditions on the theorem above, which relies on the pre-existence of a cone $K$. In fact, what we have shown is that `Forget`

reflects the property of *being a limit* — what we now show is that it reflects limit *objects*, too: if $U \circ F$ has a limit, then so does $F$.

Forget-lift-limit : Limit (Forget _ M F∘ F) → Limit F Forget-lift-limit lim-over = record { top = cone′ ; has⊤ = Forget-reflects-limits cone′ $ subst (is-limit _) (sym U$L≡L) (lim-over .has⊤) } where open Terminal module cone = Cone (lim-over .top)

What we must do, essentially, is prove that $\lim (U \circ F)$ admits an algebra structure, much like we did for products of groups. In this, we’ll use two auxilliary cones over $U \circ F$, one with underlying object given by $M(\lim (U \circ F))$ and one by $M^2(\lim (U \circ F))$. We construct the one with a single $M$ first, and re-use its maps in the construction of the one with $M^2$.

The maps out of $M_0(\lim (U \circ F))$ are given by the composite below, which assembles into a cone since $F_1(f)$ is a map of algebras and $\psi$ is a cone.

$M_0 (\lim (U \circ F)) \xto{M_1(\psi_x)} M_0 (F_0(x)) \xto{\nu} F_0(x)$

cone₂ : Cone (Forget _ M F∘ F) cone₂ .apex = M.M₀ cone.apex cone₂ .ψ x = F.₀ x .snd .ν C.∘ M.M₁ (cone.ψ x) cone₂ .commutes {x} {y} f = F.₁ f .morphism C.∘ F.₀ x .snd .ν C.∘ M.M₁ (cone.ψ x) ≡⟨ C.pulll (F.₁ f .commutes) ⟩≡ (F.₀ y .snd .ν C.∘ M.M₁ (F.₁ f .morphism)) C.∘ M.M₁ (cone.ψ x) ≡⟨ C.pullr (sym (M.M-∘ _ _) ∙ ap M.M₁ (cone.commutes f)) ⟩≡ F.₀ y .snd .ν C.∘ M.M₁ (cone.ψ y) ∎

Below, we can reuse the work we did above by precomposing with $M$’s multiplication $\mu$.

cone² : Cone (Forget _ M F∘ F) cone² .apex = M.M₀ (M.M₀ cone.apex) cone² .ψ x = cone₂ .ψ x C.∘ M.mult.η _ cone² .commutes f = C.pulll (cone₂ .commutes f)

We now define the algebra structure on $\lim (U \circ F)$. It’s very tedious, but the multiplication is uniquely defined since it’s a map $M(\lim (U \circ F)) \to \lim (U \circ F)$ into a limit, and the algebraic identities follow from again from limits being terminal.

cone′ : Cone F cone′ .apex = cone.apex , alg where

alg : Algebra-on _ M cone.apex alg .ν = lim-over .has⊤ cone₂ .centre .hom alg .ν-unit = ap hom $ is-contr→is-prop (lim-over .has⊤ (lim-over .top)) (record { hom = alg .ν C.∘ M.unit.η cone.apex ; commutes = comm1 }) (record { hom = C.id ; commutes = λ _ → C.idr _ }) alg .ν-mult = ap hom $ is-contr→is-prop (lim-over .has⊤ cone²) (record { hom = alg .ν C.∘ M.M₁ (alg .ν) ; commutes = comm2 }) (record { hom = alg .ν C.∘ M.mult.η cone.apex ; commutes = λ o → C.pulll (lim-over .has⊤ cone₂ .centre .commutes o) })

The cone maps in $\ca{C}^M$ are given by the cone maps we started with — specialising again to groups, we’re essentially showing that the projection map $\pi_1 : G \times H \to G$ *between sets* is actually a group homomorphism.

cone′ .ψ x .morphism = cone.ψ x cone′ .ψ x .commutes = lim-over .has⊤ cone₂ .centre .commutes x cone′ .commutes f = Algebra-hom-path _ (cone.commutes f) U$L≡L : F-map-cone (Forget _ M) cone′ ≡ lim-over .top U$L≡L = Cone-path _ refl λ o → refl

We conclude by saying that, if $\ca{C}$ is a complete category, then so is $\ca{C}^M$, with no assumptions on $M$.

Eilenberg-Moore-is-complete : ∀ {a b} → is-complete a b C → is-complete a b (Eilenberg-Moore _ M) Eilenberg-Moore-is-complete complete F = Forget-lift-limit F (complete _)