Martin Escardo 17th December 2018. (This has a connection with injectivity.) We have a look at the algebras of the lifting monad. \begin{code} {-# OPTIONS --safe --without-K --lossy-unification #-} open import MLTT.Spartan module Lifting.Algebras (π£ : Universe) where open import UF.Base open import UF.Equiv open import UF.EquivalenceExamples open import UF.FunExt open import UF.Subsingletons open import UF.Subsingletons-FunExt open import UF.UA-FunExt open import UF.Univalence open import Lifting.Construction π£ open import Lifting.Identity π£ open import Lifting.Monad π£ \end{code} An element of π (π X) amounts to a family of partial elements of X indexed by a proposition: \begin{code} double-π-charac : (X : π€Μ ) β π (π X) β (Ξ£ P κ π£ Μ , (Ξ£ Q κ (P β π£Μ ) , ((p : P) β Q p β X) Γ ((p : P) β is-prop (Q p))) Γ is-prop P) double-π-charac X = Ξ£-cong (Ξ» P β Γ-cong (Ξ³ X P) (β-refl (is-prop P))) where Ξ³ : (X : π€ Μ ) (P : π£ Μ ) β (P β π X) β (Ξ£ Q κ (P β π£ Μ ), ((p : P) β Q p β X) Γ ((p : P) β is-prop (Q p))) Ξ³ X P = (P β Ξ£ Q κ π£ Μ , (Q β X) Γ is-prop Q) ββ¨ I β© (Ξ£ Q κ (P β π£Μ ), ((p : P) β ((Q p β X) Γ is-prop (Q p)))) ββ¨ II β© (Ξ£ Q κ (P β π£ Μ ), ((p : P) β Q p β X) Γ ((p : P) β is-prop (Q p))) β where I = Ξ Ξ£-distr-β II = Ξ£-cong (Ξ» Q β βΓ) \end{code} The usual definition of algebra of a monad and construction of free algebras: \begin{code} π-algebra : π€ Μ β π£βΊ β π€ Μ π-algebra X = Ξ£ s κ (π X β X) , (s β Ξ· βΌ id) Γ (s β ΞΌ βΌ s β πΜ s) free-π-algebra : is-univalent π£ β (X : π€Μ ) β π-algebra (π X) free-π-algebra ua X = ΞΌ , π-unit-leftβΌ ua , π-assocβΌ ua \end{code} We can describe algebras in terms of "extension" operations subject to two laws: \begin{code} extension-op : π€ Μ β π£βΊ β π€ Μ extension-op X = {P : π£Μ } β is-prop P β (P β X) β X \end{code} The intuitive idea is that a "extension" operation extends a partial element to a total element. To characterize algebras, the extension operations have two satisfy the following two laws: \begin{code} π-alg-Lawβ : {X : π€ Μ } β extension-op X β π€ Μ π-alg-Lawβ {π€} {X} β = (x : X) β β π-is-prop (Ξ» (p : π) β x) οΌ x π-alg-Lawβ : {X : π€Μ } β extension-op X β π£ βΊ β π€ Μ π-alg-Lawβ {π€} {X} β = (P : π£Μ ) (Q : P β π£ Μ ) (i : is-prop P) (j : (p : P) β is-prop (Q p)) (Ο : Ξ£ Q β X) β β (Ξ£-is-prop i j) Ο οΌ β i (Ξ» p β β (j p) (Ξ» q β Ο (p , q))) \end{code} Omitting the witnesses of proposition-hood, the above two laws can be written in more standard mathematical notation as follows: β x = x p:π β Ο r = β β Ο (p , q) r : Ξ£ {P} Q p:P q:Q(p) \begin{code} π-alg : π€ Μ β π£βΊ β π€ Μ π-alg X = Ξ£ β κ extension-op X , π-alg-Lawβ β Γ π-alg-Lawβ β π-alg-structure-map : {X : π€Μ } β π-alg X β extension-op X π-alg-structure-map (β , lβ , lβ) = β π-alg-lawβ : {X : π€ Μ } (π : π-alg X) β π-alg-Lawβ (π-alg-structure-map π) π-alg-lawβ (β , lβ , lβ) = lβ π-alg-lawβ : {X : π€ Μ } (π : π-alg X) β π-alg-Lawβ (π-alg-structure-map π) π-alg-lawβ (β , lβ , lβ) = lβ \end{code} Before proving that we have an equivalence π-algebra X β π-alg X, we characterize the algebra morphisms in terms of extensions (unfortunately overloading is not available): \begin{code} private β : {X : π€ Μ } β (π X β X) β extension-op X β s {P} i Ο = s (P , Ο , i) βΜ : {X : π€ Μ } β π-algebra X β extension-op X βΜ (s , _) = β s β : {X : π€ Μ } β π-alg X β extension-op X β (β , ΞΊ , ΞΉ) = β lawβ : {X : π€ Μ } (a : π-alg X) β π-alg-Lawβ (β a) lawβ (β , ΞΊ , ΞΉ) = ΞΊ lawβ : {X : π€ Μ } (a : π-alg X) β π-alg-Lawβ (β a) lawβ (β , ΞΊ , ΞΉ) = ΞΉ \end{code} The algebra morphisms are the maps that preserve extensions. Omitting the first argument of β, the following says that the morphisms are the maps h : X β Y with h (β Ο) οΌ β h (Ο p) p:P for all Ο : P β X. \begin{code} π-morphism-charac : {X : π€ Μ } {Y : π₯ Μ } (s : π X β X) (t : π Y β Y) (h : X β Y) β (h β s βΌ t β πΜ h) β ({P : π£ Μ } (i : is-prop P) (Ο : P β X) β h (β s i Ο) οΌ β t i (Ξ» p β h (Ο p))) π-morphism-charac s t h = qinveq (Ξ» H {P} i Ο β H (P , Ο , i)) ((Ξ» {Ο (P , Ο , i) β Ο {P} i Ο}) , (Ξ» _ β refl) , (Ξ» _ β refl)) \end{code} We name the other two projections of π-alg: \begin{code} π-alg-const : {X : π€ Μ } (A : π-alg X) (x : X) β β A π-is-prop (Ξ» (p : π) β x) οΌ x π-alg-const (β , ΞΊ , ΞΉ) = ΞΊ π-alg-iterated : {X : π€ Μ } (A : π-alg X) (P : π£ Μ ) (Q : P β π£ Μ ) (i : is-prop P) (j : (p : P) β is-prop (Q p)) (Ο : Ξ£ Q β X) β β A (Ξ£-is-prop i j) Ο οΌ β A i (Ξ» p β β A (j p) (Ξ» q β Ο (p , q))) π-alg-iterated (β , ΞΊ , ΞΉ) = ΞΉ \end{code} We could write a proof of the following characterization of the π-algebras by composing equivalences as above, but it seems more direct, and just as clear, to write a direct proof, by construction of the equivalence and its inverse. This also emphasizes that the equivalence is definitional, in the sense that the two required equations hold definitionally. \begin{code} π-algebra-gives-alg : {X : π€ Μ } β π-algebra X β π-alg X π-algebra-gives-alg (s , unit , assoc) = β s , unit , (Ξ» P Q i j Ο β assoc (P , (Ξ» p β Q p , (Ξ» q β Ο (p , q)) , j p) , i)) π-alg-gives-algebra : {X : π€ Μ } β π-alg X β π-algebra X π-alg-gives-algebra {π€} {X} (β , unit , ΞΉ) = s , unit , assoc where s : π X β X s (P , Ο , i) = β i Ο assoc : s β ΞΌ βΌ s β πΜ s assoc (P , g , i) = ΞΉ P (prβ β g) i (Ξ» p β prβ (prβ (g p))) (Ξ» r β prβ (prβ (g (prβ r))) (prβ r)) π-alg-charac : {X : π€ Μ } β π-algebra X β π-alg X π-alg-charac = qinveq π-algebra-gives-alg (π-alg-gives-algebra , ((Ξ» _ β refl) , (Ξ» _ β refl))) \end{code} We now consider an equivalent of π-alg-Lawβ (which is useful e.g. for type injectivity purposes). \begin{code} π-alg-Lawβ' : {X : π€ Μ } β extension-op X β π£ βΊ β π€ Μ π-alg-Lawβ' {π€} {X} β = (P : π£Μ ) (i : is-prop P) (Ο : P β X) (p : P) β β i Ο οΌ Ο p π-alg-Lawβ-givesβ' : propext π£ β funext π£ π£ β funext π£ π€ β {X : π€ Μ } (β : extension-op X) β π-alg-Lawβ β β π-alg-Lawβ' β π-alg-Lawβ-givesβ' pe fe fe' {X} β ΞΊ P i Ο p = Ξ³ where r : Ο οΌ Ξ» (_ : P) β Ο p r = dfunext fe' (Ξ» p' β ap Ο (i p' p)) s : P οΌ π β β {P} i Ο οΌ β {π} π-is-prop (Ξ» (_ : π) β Ο p) s refl = apβ β (being-prop-is-prop fe i π-is-prop) r t : P οΌ π t = pe i π-is-prop unique-to-π (Ξ» _ β p) Ξ³ = β {P} i Ο οΌβ¨ s t β© β π-is-prop (Ο β (Ξ» _ β p)) οΌβ¨ ΞΊ (Ο p) β© Ο p β π-alg-Lawβ'-givesβ : {X : π€ Μ } (β : extension-op X) β π-alg-Lawβ' β β π-alg-Lawβ β π-alg-Lawβ'-givesβ {π€} {X} β Ο x = Ο π π-is-prop (Ξ» _ β x) β \end{code} We now consider a non-dependent version of π-alg-Lawβ, and show that it is equivalent to π-alg-Lawβ: \begin{code} π-alg-Lawβ' : {X : π€ Μ } β extension-op X β π£ βΊ β π€ Μ π-alg-Lawβ' {π€} {X} β = (P Q : π£Μ ) (i : is-prop P) (j : is-prop Q) (Ο : P Γ Q β X) β β (Γ-is-prop i j) Ο οΌ β i (Ξ» p β β j (Ξ» q β Ο (p , q))) \end{code} The difference with π-alg-Lawβ is that the family Ο has type P Γ Q β X rather than Ξ£ {P} Q β X, and so the modified, logically equivalent law amounts to β β Ο (p , q) = β Ο r p:P q:Q r : P Γ Q One direction of the logical equivalence is trivial: \begin{code} π-alg-Lawβ-givesβ' : {X : π€ Μ } (β : extension-op X) β π-alg-Lawβ β β π-alg-Lawβ' β π-alg-Lawβ-givesβ' {π€} {X} β a P Q i j = a P (Ξ» _ β Q) i (Ξ» p β j) \end{code} To establish the converse we need the following lemma for extensions, which is interesting on its own right, β Ο p οΌ β Ο (k q), p:P q:Q and also gives self-distributivity of extensions: β β Ο (p , q) = β β Ο (p , q) p:P q:Q q:Q p:P \begin{code} change-of-variables-in-extension : {X : π€ Μ } (β : extension-op X) (P : π£ Μ ) (i : is-prop P) (Q : π£ Μ ) (j : is-prop Q) (h : P β Q) (k : Q β P) (Ο : P β X) β is-univalent π£ β β i Ο οΌ β j (Ο β k) change-of-variables-in-extension β P i Q j h k Ο ua = Ξ³ where cd : (r : Q οΌ P) β β i Ο οΌ β j (Ο β Idtofun r) cd refl = ap (Ξ» - β β - Ο) (being-prop-is-prop (univalence-gives-funext ua) i j) e : Q β P e = qinveq k (h , ((Ξ» q β j (h (k q)) q) , Ξ» p β i (k (h p)) p)) a : Idtofun (eqtoid ua Q P e) οΌ k a = ap β_β (idtoeq'-eqtoid ua Q P e) Ξ³ : β i Ο οΌ β j (Ο β k) Ξ³ = cd (eqtoid ua Q P e) β ap (Ξ» - β β j (Ο β -)) a \end{code} NB. The above is proved without univalence, but with propositional and functional extensionality in the module InjectiveTypes.Structure. \begin{code} π-alg-self-distr : {X : π€ Μ } (β : extension-op X) (P : π£ Μ ) (i : is-prop P) (Q : π£ Μ ) (j : is-prop Q) β is-univalent π£ β π-alg-Lawβ' β β (Ο : P Γ Q β X) β β i (Ξ» p β β j (Ξ» q β Ο (p , q))) οΌ β j (Ξ» q β β i (Ξ» p β Ο (p , q))) π-alg-self-distr β P i Q j ua lβ' Ο = β i (Ξ» p β β j (Ξ» q β Ο (p , q))) οΌβ¨ a β© β (Ξ£-is-prop i (Ξ» p β j)) Ο οΌβ¨ b β© β (Ξ£-is-prop j (Ξ» p β i)) (Ο β (Ξ» t β prβ t , prβ t)) οΌβ¨ c β© β j (Ξ» q β β i (Ξ» p β Ο (p , q))) β where a = (lβ' P Q i j Ο)β»ΒΉ b = change-of-variables-in-extension β (P Γ Q) (Ξ£-is-prop i (Ξ» p β j)) (Q Γ P) (Ξ£-is-prop j (Ξ» p β i)) (Ξ» t β prβ t , prβ t) (Ξ» t β prβ t , prβ t) Ο ua c = lβ' Q P j i (Ξ» t β Ο (prβ t , prβ t)) \end{code} Using this we can prove the other direction of the logical equivalence claimed above: \begin{code} π-alg-Lawβ'-givesβ : {X : π€ Μ } (β : extension-op X) β is-univalent π£ β funext π£ π€ β π-alg-Lawβ' β β π-alg-Lawβ β π-alg-Lawβ'-givesβ {π€} {X} β ua fe a P Q i j Ο = Ξ³ where h : (p : P) β Q p β Ξ£ Q h p q = (p , q) k : (p : P) β Ξ£ Q β Q p k p (p' , q) = transport Q (i p' p) q Ο' : P Γ Ξ£ Q β X Ο' (p , p' , q) = Ο (p , k p (p' , q)) k' : Ξ£ Q β P Γ Ξ£ Q k' (p , q) = p , p , q H : Ο' β k' βΌ Ο H (p , q) = ap (Ξ» - β Ο (p , -)) (j p _ _) Ξ³ = β {Ξ£ Q} (Ξ£-is-prop i j) Ο οΌβ¨ b β© β {Ξ£ Q} (Ξ£-is-prop i j) (Ο' β k') οΌβ¨ c β»ΒΉ β© β {P Γ Ξ£ Q} (Γ-is-prop i (Ξ£-is-prop i j)) Ο' οΌβ¨ d β© β {P} i (Ξ» p β β {Ξ£ Q} (Ξ£-is-prop i j) ((Ξ» Ο β Ο (p , Ο)) β k p)) οΌβ¨ e β© β {P} i (Ξ» p β β {Q p} (j p) (Ξ» q β Ο (p , q))) β where b = (ap (β {Ξ£ Q} (Ξ£-is-prop i j)) (dfunext fe H))β»ΒΉ c = change-of-variables-in-extension β (P Γ Ξ£ Q) (Γ-is-prop i (Ξ£-is-prop i j)) (Ξ£ Q) (Ξ£-is-prop i j) prβ k' Ο' ua d = a P (Ξ£ Q) i (Ξ£-is-prop i j) (Ξ» z β Ο (prβ z , k (prβ z) (prβ z))) e = (ap (β {P} i) (dfunext fe (Ξ» p β change-of-variables-in-extension β (Q p) (j p) (Ξ£ Q) (Ξ£-is-prop i j) (h p) (k p) (Ξ» Ο β Ο (p , Ο)) ua)))β»ΒΉ \end{code} The algebras form an exponential ideal with the pointwise operations. More generally: \begin{code} Ξ -is-alg : funext π€ π₯ β {X : π€ Μ } (A : X β π₯ Μ ) β ((x : X) β π-alg (A x)) β π-alg (Ξ A) Ξ -is-alg {π€} {π₯} fe {X} A π = βΒ· , lβ , lβ where βΒ· : {P : π£ Μ } β is-prop P β (P β Ξ A) β Ξ A βΒ· i Ο x = β (π x) i (Ξ» p β Ο p x) lβ : (Ο : Ξ A) β βΒ· π-is-prop (Ξ» p β Ο) οΌ Ο lβ Ο = dfunext fe (Ξ» x β lawβ (π x) (Ο x)) lβ : (P : π£ Μ ) (Q : P β π£ Μ ) (i : is-prop P) (j : (p : P) β is-prop (Q p)) (Ο : Ξ£ Q β Ξ A) β βΒ· (Ξ£-is-prop i j) Ο οΌ βΒ· i (Ξ» p β βΒ· (j p) (Ξ» q β Ο (p , q))) lβ P Q i j Ο = dfunext fe (Ξ» x β lawβ (π x) P Q i j (Ξ» Ο β Ο Ο x)) \end{code} This is the case for any monad of a certain kind, but the way we proved this above using our characterizations of the algebras applies only to our monad. The following examples are crucial for injectivity. They say that the universe is an algebra in at least two ways, with β = Ξ£ and β = Ξ respectively. \begin{code} universe-is-algebra-Ξ£ : is-univalent π£ β π-alg (π£ Μ ) universe-is-algebra-Ξ£ ua = sum , k , ΞΉ where sum : {P : π£ Μ } β is-prop P β (P β π£ Μ ) β π£ Μ sum {P} i = Ξ£ k : (X : π£Μ ) β Ξ£ (Ξ» p β X) οΌ X k X = eqtoid ua (π Γ X) X π-lneutral ΞΉ : (P : π£ Μ ) (Q : P β π£ Μ ) (i : is-prop P) (j : (p : P) β is-prop (Q p)) (Ο : Ξ£ Q β π£ Μ ) β Ξ£ Ο οΌ Ξ£ (Ξ» p β Ξ£ (Ξ» q β Ο (p , q))) ΞΉ P Q i j Ο = eqtoid ua _ _ Ξ£-assoc universe-is-algebra-Ξ : is-univalent π£ β π-alg (π£ Μ ) universe-is-algebra-Ξ ua = prod , k , ΞΉ where fe : funext π£ π£ fe = univalence-gives-funext ua prod : {P : π£ Μ } β is-prop P β (P β π£ Μ ) β π£ Μ prod {P} i = Ξ k : (X : π£Μ ) β Ξ (Ξ» p β X) οΌ X k X = eqtoid ua (π β X) X (β-sym (πβ (univalence-gives-funext ua))) ΞΉ : (P : π£ Μ ) (Q : P β π£ Μ ) (i : is-prop P) (j : (p : P) β is-prop (Q p)) (Ο : Ξ£ Q β π£ Μ ) β Ξ Ο οΌ Ξ (Ξ» p β Ξ (Ξ» q β Ο (p , q))) ΞΉ P Q i j Ο = eqtoid ua _ _ (curry-uncurry' fe fe) \end{code} Added 6th June 2025. A retract of the underlying type of an algebra can be given an algebra structure, if the induced idempotent is an automorphism, in such a way that the section becomes a homomorphism. \begin{code} is-hom : {A : π€Μ } {B : π₯ Μ } β π-alg A β π-alg B β (A β B) β π£ βΊ β π€ β π₯ Μ is-hom {π€} {π₯} {A} {B} (βα΅ , _) (βα΅ , _) h = (P : π£Μ ) (i : is-prop P) (Ο : P β A) β h (βα΅ i Ο) οΌ βα΅ i (h β Ο) id-is-hom : {A : π€ Μ } (π : π-alg A) β is-hom π π id id-is-hom π P i Ο = refl β-is-hom : {A : π€ Μ } {B : π₯ Μ } {C : π¦ Μ } (π : π-alg A) (π : π-alg B) (π : π-alg C) (h : A β B) (k : B β C) β is-hom π π h β is-hom π π k β is-hom π π (k β h) β-is-hom (βα΅ , _) (βα΅ , _) (βαΆ , _) h k h-is-hom k-is-hom P i Ο = k (h (βα΅ i Ο)) οΌβ¨ ap k (h-is-hom P i Ο) β© k (βα΅ i (h β Ο)) οΌβ¨ k-is-hom P i (h β Ο) β© βαΆ i (k β h β Ο) β open import UF.Sets being-hom-is-prop : Fun-Ext β {A : π€ Μ } (π : π-alg A) {B : π₯ Μ } (π : π-alg B) β is-set B β (h : A β B) β is-prop (is-hom π π h) being-hom-is-prop fe π π B-is-set h = Ξ β-is-prop fe (Ξ» _ _ _ β B-is-set) β¨_β© : {A : π€ Μ } β π-alg A β π€ Μ β¨_β© {π€} {A} π = A Hom : {A : π€Μ } {B : π₯ Μ } β π-alg A β π-alg B β π£ βΊ β π€ β π₯ Μ Hom π π = Ξ£ h κ (β¨ π β© β β¨ π β©) , is-hom π π h open import UF.Retracts module _ (A : π€Μ ) (B : π₯ Μ ) (π@(βα΅ , lawα΅β , lawα΅β) : π-alg A) ((r , s , rs) : retract B of A) (sr-is-hom : is-hom π π (s β r)) (fe : Fun-Ext) where private βα΅ : extension-op B βα΅ i Ο = r (βα΅ i (s β Ο)) lawα΅β : π-alg-Lawβ βα΅ lawα΅β b = βα΅ π-is-prop (Ξ» _ β b) οΌβ¨reflβ© r (βα΅ π-is-prop (Ξ» _ β s b)) οΌβ¨ ap r (lawα΅β (s b)) β© r (s b) οΌβ¨ rs b β© b β \end{code} Before we know that βα΅ satisfies the second algebra law, we can show that the section is a homomorphism. In fact, we use this to prove the second algebra law. \begin{code} s-is-hom = Ξ» (P : π£ Μ ) (i : is-prop P) (Ο : P β B) β s (βα΅ i Ο) οΌβ¨reflβ© s (r (βα΅ i (s β Ο))) οΌβ¨ sr-is-hom P i (s β Ο) β© βα΅ i (s β r β s β Ο) οΌβ¨ ap (Ξ» - β βα΅ i (s β - β Ο)) (dfunext fe rs) β© βα΅ i (s β Ο) β lawα΅β : π-alg-Lawβ βα΅ lawα΅β P Q i j Ο = βα΅ (Ξ£-is-prop i j) Ο οΌβ¨reflβ© r (βα΅ (Ξ£-is-prop i j) (s β Ο)) οΌβ¨ by-lawα΅β β© r (βα΅ i (Ξ» p β βα΅ (j p) (Ξ» q β s (Ο (p , q))))) οΌβ¨ because-s-is-hom β© r (βα΅ i (Ξ» p β s (r (βα΅ (j p) (Ξ» q β s (Ο (p , q))))))) οΌβ¨reflβ© βα΅ i (Ξ» p β βα΅ (j p) (Ξ» q β Ο (p , q))) β where by-lawα΅β = ap r (lawα΅β P Q i j (s β Ο)) because-s-is-hom = ap (r β βα΅ i) ((dfunext fe (Ξ» p β s-is-hom (Q p) (j p) (Ξ» q β Ο (p , q))))β»ΒΉ) π : π-alg B π = βα΅ , lawα΅β , lawα΅β \end{code} The following are the only public things in this anonymous module. \begin{code} retract-of-algebra : π-alg B retract-of-algebra = π section-is-hom : is-hom retract-of-algebra π s section-is-hom = s-is-hom \end{code} Added 6th September 2025 by Martin Escardo. Use Ξ© to repackage things more neatly. We use uppercase names to distinguish the repackaged things. \begin{code} module algebra-repackaging where open import UF.SubtypeClassifier Extension-op : π€Μ β π£βΊ β π€ Μ Extension-op X = (P : Ξ© π£) β (P holds β X) β X π-Alg-Lawβ : {X : π€Μ } β Extension-op X β π€ Μ π-Alg-Lawβ {π€} {X} β = (x : X) β β β€ (Ξ» _ β x) οΌ x π-Alg-Lawβ : {X : π€Μ } β Extension-op X β π£ βΊ β π€ Μ π-Alg-Lawβ {π€} {X} β = (P : Ξ© π£) (Q : P holds β Ξ© π£) (Ο : (ΣΩ p κ P , Q p) holds β X) β β (ΣΩ p κ P , Q p) Ο οΌ β P (Ξ» p β β (Q p) (Ξ» q β Ο (p , q))) π-Alg : π€Μ β π£βΊ β π€ Μ π-Alg X = Ξ£ β κ Extension-op X , π-Alg-Lawβ β Γ π-Alg-Lawβ β π-Alg-gives-π-alg : {X : π€Μ } β π-Alg X β π-alg X π-Alg-gives-π-alg (β , lβ , lβ) = (Ξ» {P} P-is-prop β β (P , P-is-prop)) , lβ , (Ξ» P Q i j β lβ (P , i) (Ξ» p β Q p , j p)) \end{code} But we probably won't use the above repackaging, as we already have everything written with the original choice of implementation. Added 8th September 2025 by Martin Escardo. The discussion of free algebras in the category of sets can be carried out without using univalence, and only its two consequences, propositional and functional extensionality. Notice that already the associativity law for the lifting monad uses univalence. \begin{code} is-free-π-alg : {F : π€Μ } (π : π-alg F) (X : π₯ Μ ) (ΞΉ : X β F) β π€Ο is-free-π-alg π X ΞΉ = {π¦ : Universe} {A : π¦ Μ } (i : is-set A) (π : π-alg A) (f : X β A) β β! (fΜ , _) κ Hom π π , fΜ β ΞΉ βΌ f \end{code} Notice that above definition says that precomposition with ΞΉ is an equivalence. \begin{code} module free-algebra-eliminators {F : π€ Μ } (π : π-alg F) (X : π₯ Μ ) (ΞΉ : X β F) (π-is-free : is-free-π-alg π X ΞΉ) {A : π¦ Μ } (i : is-set A) (π : π-alg A) (f : X β A) where private eu : β! (fΜ , _) κ Hom π π , fΜ β ΞΉ βΌ f eu = π-is-free i π f unique-hom : F β A unique-hom = prβ (β!-witness eu) unique-hom-is-hom : is-hom π π unique-hom unique-hom-is-hom = prβ (β!-witness eu) unique-hom-is-extension : unique-hom β ΞΉ βΌ f unique-hom-is-extension = β!-is-witness eu at-most-one-extending-hom : is-prop (Ξ£ (fΜ , _) κ Hom π π , fΜ β ΞΉ βΌ f) at-most-one-extending-hom = singletons-are-props eu at-most-one-extending-hom' : ((h , h-is-hom) (k , k-is-hom) : Hom π π) β h β ΞΉ βΌ f β k β ΞΉ βΌ f β h βΌ k at-most-one-extending-hom' π@(h , h-is-hom) π@(k , k-is-hom) p q = happly (ap (prβ β prβ) (at-most-one-extending-hom (π , p) (π , q))) the-only-hom-extension : ((h , h-is-hom) : Hom π π) β h β ΞΉ βΌ f β h βΌ unique-hom the-only-hom-extension π@(h , h-is-hom) x = at-most-one-extending-hom' π (β!-witness eu) x unique-hom-is-extension \end{code} We now construct the canonical free algebra. \begin{code} module free-algebras-in-the-category-of-sets (pe : Prop-Ext) (fe : Fun-Ext) {π€ : Universe} (X : π€ Μ ) (X-is-set : is-set X) where β¨ : extension-op (π X) β¨ {P} P-is-prop Ο = (Ξ£ p κ P , is-defined (Ο p)) , (Ξ» (p , d) β value (Ο p) d) , Ξ£-is-prop P-is-prop (Ξ» p β being-defined-is-prop (Ο p)) canonical-free-algebra : π-alg (π X) canonical-free-algebra = β¨ , lβ , lβ where lβ : π-alg-Lawβ β¨ lβ l@(P , Ο , P-is-prop) = from-β pe fe fe (((Ξ» (β , p) β p) , (Ξ» p β β , p)) , (Ξ» _ β refl)) lβ : π-alg-Lawβ β¨ lβ P Q i j f = from-β pe fe fe (((Ξ» ((p , q) , d) β (p , (q , d))) , Ξ» (p , (q , d)) β ((p , q), d)) , (Ξ» _ β refl)) \end{code} We rely on the following useful lemma, which says that every element of π X is a join of positive elements, as in the case after Anders Kock (see [1] below), and which is interesting in its own right. The positive elements of the free algebra π X are those of the form Ξ· x, but we don't need to know this or the definition of positive element in order to formulate and prove the following. \begin{code} every-element-of-π-is-a-positive-join : (l@(P , Ο , i) : π X) β l οΌ β¨ i (Ξ· β Ο) every-element-of-π-is-a-positive-join l@(P , Ο , i) = from-β pe fe fe (((Ξ» (p : P) β p , β) , prβ) , (Ξ» (_ : P) β refl)) private π = canonical-free-algebra module _ {π₯ : Universe} {A : π₯ Μ } (A-is-set : is-set A) (π@(β , lβ , lβ) : π-alg A) (f : X β A) where π-extension : (π X β A) π-extension (P , Ο , P-is-prop) = β P-is-prop (f β Ο) private fΜ = π-extension π-extension-is-hom : is-hom π π fΜ π-extension-is-hom P i Ο = lβ P (Ξ» p β is-defined (Ο p)) i (Ξ» p β being-defined-is-prop (Ο p)) (Ξ» (p , d) β f (value (Ο p) d)) π-extension-extends : fΜ β Ξ· βΌ f π-extension-extends x = lβ (f x) private H : π£ βΊ β π€ β π₯ Μ H = Ξ£ (h , _) κ Hom π π , h β Ξ· βΌ f hom-agreement : (((h , _) , _) ((h' , _) , _) : H) β h βΌ h' hom-agreement ((h , h-is-hom) , e) ((h' , h'-is-hom) , e') l@(P , Ο , i) = h l οΌβ¨ I β© h (β¨ i (Ξ· β Ο)) οΌβ¨ II β© β i (h β Ξ· β Ο) οΌβ¨ III β© β i (h' β Ξ· β Ο) οΌβ¨ II' β© h' (β¨ i (Ξ· β Ο)) οΌβ¨ I' β© h' l β where I = ap h (every-element-of-π-is-a-positive-join l) II = h-is-hom P i (Ξ· β Ο) III = ap (Ξ» - β β i (- β Ο)) (dfunext fe (Ξ» (x : X) β h (Ξ· x) οΌβ¨ e x β© f x οΌβ¨ (e' x)β»ΒΉ β© h' (Ξ· x) β)) II' = (h'-is-hom P i (Ξ· β Ο))β»ΒΉ I' = (ap h' (every-element-of-π-is-a-positive-join l))β»ΒΉ homomorphic-π-extensions-form-a-prop : is-prop H homomorphic-π-extensions-form-a-prop he he' = to-subtype-οΌ (Ξ» h β Ξ -is-prop fe (Ξ» x β A-is-set)) (to-subtype-οΌ (being-hom-is-prop fe π π A-is-set) (dfunext fe (hom-agreement he he'))) free-algebra-universal-property : is-singleton H free-algebra-universal-property = pointed-props-are-singletons ((fΜ , π-extension-is-hom) , π-extension-extends) homomorphic-π-extensions-form-a-prop \end{code} Notice that the universal property of the algebra freely generated by X : π€ with insertion of generators Ξ· : X β π X eliminates into any universe π₯: \begin{code} π-is-free : is-free-π-alg canonical-free-algebra X Ξ· π-is-free = free-algebra-universal-property \end{code}Moved from AnAlgebraWhichIsNotAlwaysFree 29th Nov 2025. If two algebras A and B are freely generated by the same set of generators, they are canonically equivalent. i G βββββββββ A β² β β β² β β β² β β j β² h β β hβ»ΒΉ β² β β β² β β β² β β β² β β β B The proof is a standard categorical argument. The homomorphism h is the unique homomorphic extension of j along i, and the homomorphism hβ»ΒΉ is the unique homomorphisc extension of i along j. But also the composites h β hβ»ΒΉ : A β A and hβ»ΒΉ β h : B β B are the unique homomorphisms extending the identity function along i and j respectively, and so, because the identity functions are respectively such a homomorphisms, we conclude that both composites agree with the respective identity functions. \begin{code} module _ {A : π€Μ } {B : π₯ Μ } (G : π¦ Μ ) (A-is-set : is-set A) (B-is-set : is-set B) (G-is-set : is-set G) (i : G β A) (j : G β B) (π : π-alg A) (π : π-alg B) (Ο : is-free-π-alg π G i) (Ξ³ : is-free-π-alg π G j) where module A = free-algebra-eliminators π G i Ο B-is-set π j module B = free-algebra-eliminators π G j Ξ³ A-is-set π i private h : A β B h = A.unique-hom h-is-hom : is-hom π π h h-is-hom = A.unique-hom-is-hom h-extends-j : h β i βΌ j h-extends-j = A.unique-hom-is-extension hβ»ΒΉ : B β A hβ»ΒΉ = B.unique-hom hβ»ΒΉ-is-hom : is-hom π π hβ»ΒΉ hβ»ΒΉ-is-hom = B.unique-hom-is-hom hβ»ΒΉ-extends-i : hβ»ΒΉ β j βΌ i hβ»ΒΉ-extends-i = B.unique-hom-is-extension I : is-hom π π (hβ»ΒΉ β h) I = β-is-hom π π π h hβ»ΒΉ h-is-hom hβ»ΒΉ-is-hom II : is-hom π π (h β hβ»ΒΉ) II = β-is-hom π π π hβ»ΒΉ h hβ»ΒΉ-is-hom h-is-hom III : hβ»ΒΉ β h βΌ id III = at-most-one-extending-hom' (hβ»ΒΉ β h , I) (id , id-is-hom π) (Ξ» g β hβ»ΒΉ (h (i g)) οΌβ¨ ap hβ»ΒΉ (h-extends-j g) β© hβ»ΒΉ (j g) οΌβ¨ hβ»ΒΉ-extends-i g β© i g β) (Ξ» (_ : G) β by-definition) where open free-algebra-eliminators π G i Ο A-is-set π i IV : h β hβ»ΒΉ βΌ id IV = at-most-one-extending-hom' (h β hβ»ΒΉ , II) (id , id-is-hom π) (Ξ» g β h (hβ»ΒΉ (j g)) οΌβ¨ ap h (hβ»ΒΉ-extends-i g) β© h (i g) οΌβ¨ h-extends-j g β© j g β) (Ξ» (_ : G) β by-definition) where open free-algebra-eliminators π G j Ξ³ B-is-set π j unique-hom-is-equiv : is-equiv h unique-hom-is-equiv = qinvs-are-equivs h (hβ»ΒΉ , III , IV) \end{code} The following was moved here 5th Dec 2025 from another 2nd Dec 2025 file. Any algebra isomorphic to the free algebra π G in the category of algebras is itself free. \begin{code} module _ (pe : Prop-Ext) (fe : Fun-Ext) {A : π₯ Μ } (A-is-set : is-set A) (G : π¦ Μ ) (G-is-set : is-set G) (ΞΉ : G β A) (π : π-alg A) where private open free-algebras-in-the-category-of-sets pe fe G G-is-set h : π G β A h = π-extension A-is-set π ΞΉ πG : π-alg (π G) πG = canonical-free-algebra module _ (hβ»ΒΉ : A β π G) (hβ»ΒΉ-is-section : h β hβ»ΒΉ βΌ id) (hβ»ΒΉ-is-retraction : hβ»ΒΉ β h βΌ id) (hβ»ΒΉ-is-hom : is-hom π πG hβ»ΒΉ) where π-alg-isomorphic-to-free-π-alg-is-itself-free : is-free-π-alg π G ΞΉ π-alg-isomorphic-to-free-π-alg-is-itself-free {π¦} {B} B-is-set π f = III where h-is-hom : is-hom πG π h h-is-hom = π-extension-is-hom A-is-set π ΞΉ h-extends-ΞΉ : h β Ξ· βΌ ΞΉ h-extends-ΞΉ = π-extension-extends A-is-set π ΞΉ hβ»ΒΉ-extends-Ξ· : hβ»ΒΉ β ΞΉ βΌ Ξ· hβ»ΒΉ-extends-Ξ· g = hβ»ΒΉ (ΞΉ g) οΌβ¨ ap hβ»ΒΉ (h-extends-ΞΉ g β»ΒΉ) β© hβ»ΒΉ (h (Ξ· g)) οΌβ¨ hβ»ΒΉ-is-retraction (Ξ· g) β© Ξ· g β I : β! (fΜ , _) κ Hom πG π , fΜ β Ξ· βΌ f I = π-is-free B-is-set π f II : (Ξ£ (fΜ , _) κ Hom πG π , fΜ β Ξ· βΌ f) β (β! (fΜ Μ , _) κ Hom π π , fΜ Μ β ΞΉ βΌ f) II ((fΜ , fΜ -is-hom) , e) = IIβ where fΜ Μ : A β B fΜ Μ = fΜ β hβ»ΒΉ fΜ Μ -is-hom : is-hom π π fΜ Μ fΜ Μ -is-hom = β-is-hom π πG π hβ»ΒΉ fΜ hβ»ΒΉ-is-hom fΜ -is-hom eΜ : fΜ Μ β ΞΉ βΌ f eΜ g = fΜ Μ (ΞΉ g) οΌβ¨by-definitionβ© fΜ (hβ»ΒΉ (ΞΉ g)) οΌβ¨ ap fΜ (hβ»ΒΉ-extends-Ξ· g) β© fΜ (Ξ· g) οΌβ¨ e g β© f g β c : Ξ£ (fΜ Μ , _) κ Hom π π , fΜ Μ β ΞΉ βΌ f c = (fΜ Μ , fΜ Μ -is-hom) , eΜ IIβ : is-prop (type-of c) IIβ ((fβ , fβ-is-hom) , eβ) ((fβ , fβ-is-hom) , eβ) = IIββ where fβ-agrees-with-fβ : fβ βΌ fβ fβ-agrees-with-fβ Ο = fβ Ο οΌβ¨ ap fβ ((hβ»ΒΉ-is-section Ο)β»ΒΉ) β© fβ (h (hβ»ΒΉ Ο)) οΌβ¨ IIββ (hβ»ΒΉ Ο) β© fβ (h (hβ»ΒΉ Ο)) οΌβ¨ ap fβ (hβ»ΒΉ-is-section Ο) β© fβ Ο β where IIββ : fβ β h βΌ fβ β h IIββ = hom-agreement B-is-set π f ((fβ β h , β-is-hom πG π π h fβ h-is-hom fβ-is-hom) , (Ξ» g β fβ (h (Ξ· g)) οΌβ¨ ap fβ (h-extends-ΞΉ g) β© fβ (ΞΉ g) οΌβ¨ eβ g β© f g β)) ((fβ β h , β-is-hom πG π π h fβ h-is-hom fβ-is-hom) , (Ξ» g β fβ (h (Ξ· g)) οΌβ¨ ap fβ (h-extends-ΞΉ g) β© fβ (ΞΉ g) οΌβ¨ eβ g β© f g β)) IIββ : ((fβ , fβ-is-hom) , eβ) οΌ ((fβ , fβ-is-hom) , eβ) IIββ = to-subtype-οΌ (Ξ» Ο β Ξ -is-prop fe (Ξ» (_ : G) β B-is-set)) (to-subtype-οΌ (Ξ» (_ : A β B) β Ξ β-is-prop fe (Ξ» P i Ο β B-is-set)) (dfunext fe fβ-agrees-with-fβ)) IIβ : β! (fΜ Μ , _) κ Hom π π , fΜ Μ β ΞΉ βΌ f IIβ = pointed-props-are-singletons c IIβ III : β! (fΜ Μ , _) κ Hom π π , fΜ Μ β ΞΉ βΌ f III = II (center I) \end{code} Added 23rd Nov 2025. Anders Kock' [1] definition of positive element. [1] Anders Kock. The constructive lift monad. BRICS Report Series (Aarhus), ISSN 0909-0878 (1995) http://tildeweb.au.dk/au76680/CLM.pdf \begin{code} is-positive : {A : π€Μ } β π-alg A β A β π£ βΊ β π€ Μ is-positive (β¨ , lβ , lβ) a = (P : π£Μ ) (i : is-prop P) β β¨ i (Ξ» (_ : P) β a) οΌ a β P being-positive-is-prop : Fun-Ext β {A : π€ Μ } β (π : π-alg A) β (a : A) β is-prop (is-positive π a) being-positive-is-prop fe π a = Ξ β-is-prop fe (Ξ» _ P-is-prop _ β P-is-prop) \end{code}