Tom de Jong, 1-18 March 2021 We show that the induction principle for πΒΉ with propositional computation rules follows from the universal property of πΒΉ. This is claimed at the end of Section 6.2 in the HoTT Book and follows from a general result by Sojakova in her PhD Thesis "Higher Inductive Types as Homotopy-Initial Algebras" (CMU-CS-16-125). The proof of the general result is quite complicated (see for instance Lemma 105 in the PhD thesis) and the development below offers an alternative proof for πΒΉ. \begin{code} {-# OPTIONS --safe --without-K #-} open import MLTT.Spartan open import UF.Base open import UF.Equiv open import UF.FunExt open import UF.Sets open import UF.Sets-Properties open import UF.Subsingletons module SyntheticHomotopyTheory.Circle.Induction where \end{code} First some preliminaries on the free loop space. \begin{code} π : (X : π€Μ ) β π€ Μ π X = Ξ£ x κ X , x οΌ x π-functor : {X : π€Μ } {Y : π₯ Μ } (f : X β Y) β π X β π Y π-functor f (x , p) = f x , ap f p π-functor-id : {X : π€ Μ } β π-functor id βΌ id {π€} {π X} π-functor-id {π€} {X} (x , p) = to-Ξ£-οΌ (refl , Ξ³ p) where Ξ³ : {y z : X} (q : y οΌ z) β transport (Ξ» - β y οΌ -) q refl οΌ q Ξ³ refl = refl π-functor-comp : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } (f : X β Y) (g : Y β Z) β π-functor g β π-functor f βΌ π-functor (g β f) π-functor-comp f g (x , p) = to-Ξ£-οΌ (refl , (ap-ap f g p)) ap-π-functor-lemma : {A : π€ Μ } {B : π₯ Μ } (f g : A β B) {a : A} (p : a οΌ a) {b : B} (q : b οΌ b) (u : π-functor f (a , p) οΌ (b , q)) (v : π-functor g (a , p) οΌ (b , q)) (w : (f , u) οΌ (g , v)) β ap (Ξ» - β π-functor - (a , p)) (ap prβ w) οΌ u β v β»ΒΉ ap-π-functor-lemma f g p q refl v refl = refl happly-π-functor-lemma : {A : π€ Μ } {B : π₯ Μ } (f g : A β B) {a : A} (p : a οΌ a) {b : B} (q : b οΌ b) (u : π-functor f (a , p) οΌ (b , q)) (v : π-functor g (a , p) οΌ (b , q)) (w : (f , u) οΌ (g , v)) β happly (ap prβ w) a οΌ (ap prβ u) β (ap prβ v) β»ΒΉ happly-π-functor-lemma f g p q refl v refl = refl \end{code} Next we introduce the circle πΒΉ with its point base, its loop at base and its universal property. \begin{code} module _ (πΒΉ : π€ Μ ) (base : πΒΉ) (loop : base οΌ base) where πΒΉ-universal-map : (A : π₯ Μ ) β (πΒΉ β A) β π A πΒΉ-universal-map A f = (f base , ap f loop) module _ (πΒΉ-universal-property : {π₯ : Universe} (A : π₯ Μ ) β is-equiv (πΒΉ-universal-map A)) where πΒΉ-uniqueness-principle : {A : π₯ Μ } (a : A) (p : a οΌ a) β β! r κ (πΒΉ β A) , (r base , ap r loop) οΌ (a , p) πΒΉ-uniqueness-principle {π₯} {A} a p = equivs-are-vv-equivs (πΒΉ-universal-map A) (πΒΉ-universal-property A) (a , p) πΒΉ-at-most-one-function : {A : π₯ Μ } (a : A) (p : a οΌ a) β is-prop (Ξ£ r κ (πΒΉ β A) , (r base , ap r loop) οΌ (a , p)) πΒΉ-at-most-one-function a p = singletons-are-props (πΒΉ-uniqueness-principle a p) \end{code} The recursion principle for πΒΉ with its computation rule follows immediately from the universal property of πΒΉ. \begin{code} πΒΉ-rec : {A : π₯ Μ } (a : A) (p : a οΌ a) β πΒΉ β A πΒΉ-rec {π₯} {A} a p = β!-witness (πΒΉ-uniqueness-principle a p) πΒΉ-rec-comp : {A : π₯ Μ } (a : A) (p : a οΌ a) β π-functor (πΒΉ-rec a p) (base , loop) οΌ[ π A ] (a , p) πΒΉ-rec-comp {π₯} {A} a p = β!-is-witness (πΒΉ-uniqueness-principle a p) πΒΉ-rec-on-base : {A : π₯ Μ } (a : A) (p : a οΌ a) β πΒΉ-rec a p base οΌ a πΒΉ-rec-on-base a p = ap prβ (πΒΉ-rec-comp a p) πΒΉ-rec-on-loop : {A : π₯ Μ } (a : A) (p : a οΌ a) β transport (Ξ» - β - οΌ -) (πΒΉ-rec-on-base a p) (ap (πΒΉ-rec a p) loop) οΌ p πΒΉ-rec-on-loop a p = from-Ξ£-οΌ' (πΒΉ-rec-comp a p) \end{code} The induction principle for πΒΉ also follows quite directly. The idea is to turn a type family A over πΒΉ to the type Ξ£ A and consider a nondependent map πΒΉ β Ξ£ A as a substitute for the dependent function (x : πΒΉ) β A x. What is significantly harder is showing that it obeys the computation rules. \begin{code} module πΒΉ-induction (A : πΒΉ β π₯ Μ ) (a : A base) (l : transport A loop a οΌ a) where lβΊ : (base , a) οΌ[ Ξ£ A ] (base , a) lβΊ = to-Ξ£-οΌ (loop , l) r : πΒΉ β Ξ£ A r = πΒΉ-rec (base , a) lβΊ \end{code} Next we show that r is a retraction of prβ : Ξ£ A β πΒΉ. This tells us that r (x) = (x , prβ (r x)), so that we can define πΒΉ-induction by transport. \begin{code} r-retraction-lemma : π-functor (prβ β r) (base , loop) οΌ[ π πΒΉ ] (base , loop) r-retraction-lemma = ((prβ β r) base , ap (prβ β r) loop) οΌβ¨ I β© π-functor prβ (r base , ap r loop) οΌβ¨ II β© (base , ap prβ (to-Ξ£-οΌ (loop , l))) οΌβ¨ III β© (base , loop) β where I = to-Ξ£-οΌ (refl , ((ap-ap r prβ loop) β»ΒΉ)) II = ap (π-functor prβ) (πΒΉ-rec-comp (base , a) lβΊ) III = to-Ξ£-οΌ (refl , (ap-prβ-to-Ξ£-οΌ (loop , l))) r-is-retraction-of-prβ : prβ β r οΌ id r-is-retraction-of-prβ = ap prβ (πΒΉ-at-most-one-function base loop (prβ β r , r-retraction-lemma) (id , to-Ξ£-οΌ (refl , ap-id-is-id loop))) πΒΉ-induction : (x : πΒΉ) β A x πΒΉ-induction x = transport A (happly r-is-retraction-of-prβ x) (prβ (r x)) \end{code} Next we set out to prove the computation rules for πΒΉ-induction. \begin{code} Ο : πΒΉ β Ξ£ A Ο x = (x , πΒΉ-induction x) r-comp : (r base , ap r loop) οΌ[ π (Ξ£ A) ] ((base , a) , lβΊ) r-comp = πΒΉ-rec-comp (base , a) lβΊ Ο-r-homotopy : Ο βΌ r Ο-r-homotopy x = to-Ξ£-οΌ ((Ξ³β β»ΒΉ) , Ξ³β) where Ξ³β : prβ (r x) οΌ prβ (Ο x) Ξ³β = happly r-is-retraction-of-prβ x Ξ³β = transport A (Ξ³β β»ΒΉ) (prβ (Ο x)) οΌβ¨reflβ© transport A (Ξ³β β»ΒΉ) (transport A Ξ³β (prβ (r x))) οΌβ¨ I β© transport A (Ξ³β β Ξ³β β»ΒΉ) (prβ (r x)) οΌβ¨ II β© transport A refl (prβ (r x)) οΌβ¨reflβ© prβ (r x) β where I = (transport-β A Ξ³β (Ξ³β β»ΒΉ)) β»ΒΉ II = ap (Ξ» - β transport A - (prβ (r x))) ((right-inverse Ξ³β) β»ΒΉ) Ο-and-r-on-base-and-loop : (Ο base , ap Ο loop) οΌ[ π (Ξ£ A) ] (r base , ap r loop) Ο-and-r-on-base-and-loop = to-Ξ£-οΌ (Ο-r-homotopy base , Ξ³) where Ξ³ = transport (Ξ» - β - οΌ -) (Ο-r-homotopy base) (ap Ο loop) οΌβ¨ I β© Ο-r-homotopy base β»ΒΉ β ap Ο loop β Ο-r-homotopy base οΌβ¨ II β© ap r loop β where I = transport-along-οΌ (Ο-r-homotopy base) (ap Ο loop) II = homotopies-are-natural'' Ο r Ο-r-homotopy {base} {base} {loop} Ο-comp : (Ο base , ap Ο loop) οΌ[ π (Ξ£ A) ] ((base , a) , lβΊ) Ο-comp = Ο-and-r-on-base-and-loop β r-comp \end{code} Looking at Ο-comp, we see that Ο base = (base , πΒΉ-induction base) οΌ (base , a), which looks promising, for if we can show that the equality in the first component is refl, then πΒΉ-induction base οΌ a would follow. So that's exactly what we do next. \begin{code} Ο-comp-lemma : ap prβ (ap prβ Ο-comp) οΌ refl Ο-comp-lemma = ap prβ (ap prβ Ο-comp) οΌβ¨ I β© ap (prβ β prβ) Ο-comp οΌβ¨ II β© ap (prβ β prβ) Ο-and-r-on-base-and-loop β ap (prβ β prβ) r-comp οΌβ¨ III β© p β»ΒΉ β p οΌβ¨ IV β© refl β where p = happly r-is-retraction-of-prβ base I = ap-ap prβ prβ Ο-comp II = ap-β (prβ β prβ) Ο-and-r-on-base-and-loop r-comp IV = left-inverse p III = apβ _β_ Ξ³β Ξ³β where Ξ³β : ap (prβ β prβ) Ο-and-r-on-base-and-loop οΌ p β»ΒΉ Ξ³β = ap (prβ β prβ) Ο-and-r-on-base-and-loop οΌβ¨ Iβ β© ap prβ (ap prβ Ο-and-r-on-base-and-loop) οΌβ¨ IIβ β© ap prβ (Ο-r-homotopy base) οΌβ¨ IIIβ β© p β»ΒΉ β where Iβ = (ap-ap prβ prβ Ο-and-r-on-base-and-loop) β»ΒΉ IIβ = ap (ap prβ) (ap-prβ-to-Ξ£-οΌ (Ο-r-homotopy base , _)) IIIβ = ap-prβ-to-Ξ£-οΌ ((p β»ΒΉ) , _) Ξ³β : ap (prβ β prβ) r-comp οΌ p Ξ³β = Ο β»ΒΉ where ΞΊ = r-retraction-lemma Ο = p οΌβ¨ Iβ β© ap prβ ΞΊ β ap Ο (to-Ξ£-οΌ (refl , ap-id-is-id loop)) β»ΒΉ οΌβ¨ IIβ β© ap prβ ΞΊ β refl β»ΒΉ οΌβ¨reflβ© ap prβ ΞΊ οΌβ¨ IIIβ β© ap prβ (ap prβ r-comp) οΌβ¨ IVβ β© ap (prβ β prβ) r-comp β where Ο : π (πΒΉ) β πΒΉ Ο = prβ Iβ = happly-π-functor-lemma (prβ β r) id loop loop ΞΊ (to-Ξ£-οΌ (refl , ap-id-is-id loop)) (πΒΉ-at-most-one-function base loop (prβ β r , r-retraction-lemma) (id , to-Ξ£-οΌ (refl , ap-id-is-id loop))) IIβ = ap (Ξ» - β ap prβ ΞΊ β - β»ΒΉ) (ap-prβ-to-Ξ£-οΌ {π€} {π€} {πΒΉ} {Ξ» - β (- οΌ -)} {_} {_} (refl , ap-id-is-id loop)) IVβ = ap-ap prβ prβ r-comp IIIβ = ap prβ ΞΊ οΌβ¨reflβ© ap prβ (ΞΊβ β (ΞΊβ β ΞΊβ)) οΌβ¨ I' β© ap prβ ΞΊβ β ap prβ (ΞΊβ β ΞΊβ) οΌβ¨ II' β© refl β ap prβ (ΞΊβ β ΞΊβ) οΌβ¨ III' β© ap prβ (ΞΊβ β ΞΊβ) οΌβ¨ IV' β© ap prβ ΞΊβ β ap prβ ΞΊβ οΌβ¨ V' β© ap prβ ΞΊβ β refl οΌβ¨reflβ© ap prβ ΞΊβ οΌβ¨ VI' β© ap (prβ β π-functor prβ) r-comp οΌβ¨reflβ© ap (prβ β prβ) r-comp οΌβ¨ VII' β© ap prβ (ap prβ r-comp) β where ΞΊβ = to-Ξ£-οΌ (refl , ((ap-ap r prβ loop) β»ΒΉ)) ΞΊβ = ap (π-functor prβ) r-comp ΞΊβ = to-Ξ£-οΌ (refl , (ap-prβ-to-Ξ£-οΌ (loop , l))) I' = ap-β prβ ΞΊβ (ΞΊβ β ΞΊβ) II' = ap (_β (ap prβ (ΞΊβ β ΞΊβ))) (ap-prβ-to-Ξ£-οΌ {π€} {π€} {πΒΉ} {Ξ» - β (- οΌ -)} {_} {_} (refl , ((ap-ap r prβ loop) β»ΒΉ))) III' = refl-left-neutral IV' = ap-β prβ ΞΊβ ΞΊβ V' = ap ((ap prβ ΞΊβ) β_) (ap-prβ-to-Ξ£-οΌ {π€} {π€} {πΒΉ} {Ξ» - β (- οΌ -)} {_} {_} (refl , ap-prβ-to-Ξ£-οΌ (loop , l))) VI' = ap-ap (π-functor prβ) prβ r-comp VII' = (ap-ap prβ prβ r-comp) β»ΒΉ πΒΉ-induction-on-base : πΒΉ-induction base οΌ a πΒΉ-induction-on-base = transport (Ξ» - β transport A - (πΒΉ-induction base) οΌ a) Ο-comp-lemma Ξ³ where Ξ³ : transport A (ap prβ (ap prβ Ο-comp)) (πΒΉ-induction base) οΌ a Ξ³ = from-Ξ£-οΌ' (ap prβ Ο-comp) \end{code} This takes care of the first computation rule for πΒΉ-induction. We can get a fairly direct proof of the second computation rule (the one for loop) by assuming that base οΌ base is a set, because this tells us that every element of loop οΌ loop must be refl. We can satisfy this assumption for our intended application (see SyntheticHomotopyTheory.Circle.Construction), because for the construction involving β€-torsors it's is quite easy to prove that base οΌ base is a set. However, for completeness sake, below we also show that assuming function extensionality and univalence, it is possible to prove that base οΌ base is a set, by using both computation rules for πΒΉ-rec and the first computation rule for πΒΉ-induction. \begin{code} πΒΉ-induction-on-loop-lemma : (loop , transport (Ξ» - β transport A loop - οΌ -) πΒΉ-induction-on-base (apd πΒΉ-induction loop)) οΌ (loop , l) πΒΉ-induction-on-loop-lemma = (fromto-Ξ£-οΌ (loop , transport (Ξ» - β transport A loop - οΌ -) Ο Ο)) β»ΒΉ β (ap from-Ξ£-οΌ Ξ³) β (fromto-Ξ£-οΌ (loop , l)) where Ο = πΒΉ-induction-on-base Ο = apd πΒΉ-induction loop Ξ³ : to-Ξ£-οΌ (loop , transport (Ξ» - β transport A loop - οΌ -) Ο Ο) οΌ to-Ξ£-οΌ (loop , l) Ξ³ = to-Ξ£-οΌ (loop , transport (Ξ» - β transport A loop - οΌ -) Ο Ο) οΌβ¨ I β© transport (Ξ» - β - οΌ -) (to-Ξ£-οΌ (refl , Ο)) (to-Ξ£-οΌ (loop , Ο)) οΌβ¨ II β© transport (Ξ» - β - οΌ -) (ap prβ Ο-comp) (to-Ξ£-οΌ (loop , Ο)) οΌβ¨ III β© transport (Ξ» - β - οΌ -) (ap prβ Ο-comp) (ap Ο loop) οΌβ¨ IV β© to-Ξ£-οΌ (loop , l) β where I = h loop Ο Ο where h : {X : π¦ Μ } {Y : X β π£ Μ } {x : X} (p : x οΌ x) {y y' : Y x} (q : y οΌ y') (q' : transport Y p y οΌ y) β to-Ξ£-οΌ (p , transport (Ξ» - β transport Y p - οΌ -) q q') οΌ transport (Ξ» - β - οΌ -) (to-Ξ£-οΌ (refl , q)) (to-Ξ£-οΌ (p , q')) h p refl q' = refl II = ap (Ξ» - β transport (Ξ» - β - οΌ -) - (to-Ξ£-οΌ (loop , Ο))) h where h = to-Ξ£-οΌ (refl , Ο) οΌβ¨ I' β© to-Ξ£-οΌ (from-Ξ£-οΌ (ap prβ Ο-comp)) οΌβ¨ II' β© ap prβ Ο-comp β where I' = (ap to-Ξ£-οΌ (to-Ξ£-οΌ (Ο-comp-lemma , refl))) β»ΒΉ II' = tofrom-Ξ£-οΌ (ap prβ Ο-comp) III = ap (transport (Ξ» - β - οΌ -) (ap prβ Ο-comp)) (h πΒΉ-induction loop) where h : {X : π¦ Μ } {Y : X β π£ Μ } (f : (x : X) β Y x) {x x' : X} (p : x οΌ x') β to-Ξ£-οΌ (p , apd f p) οΌ ap (Ξ» x β (x , f x)) p h f refl = refl IV = from-Ξ£-οΌ' Ο-comp module _ (base-sethood : is-set (base οΌ base)) where πΒΉ-induction-on-loop : transport (Ξ» - β transport A loop - οΌ -) πΒΉ-induction-on-base (apd πΒΉ-induction loop) οΌ l πΒΉ-induction-on-loop = ap-prβ-refl-lemma (Ξ» - β transport A - a οΌ a) πΒΉ-induction-on-loop-lemma Ξ³ where Ξ³ : ap prβ πΒΉ-induction-on-loop-lemma οΌ refl Ξ³ = base-sethood (ap prβ πΒΉ-induction-on-loop-lemma) refl πΒΉ-induction-comp : (πΒΉ-induction base , apd πΒΉ-induction loop) οΌ[ Ξ£ y κ A base , transport A loop y οΌ y ] (a , l) πΒΉ-induction-comp = to-Ξ£-οΌ (πΒΉ-induction-on-base , πΒΉ-induction-on-loop) \end{code} As promised above, here follows a proof, assuming function extensionality and univalence, that base οΌ base is a set, using both computation rules for πΒΉ-rec and the first computation rule for πΒΉ-induction. The proof uses the encode-decode method (Section 8.1.4 of the HoTT Book) to show that base οΌ base is a retract of β€. Since sets are closed under retracts, the claim follows. \begin{code} open import SyntheticHomotopyTheory.Circle.Integers open import SyntheticHomotopyTheory.Circle.Integers-Properties open import UF.Univalence module _ (ua : is-univalent π€β) where succ-β€-οΌ : β€ οΌ β€ succ-β€-οΌ = eqtoid ua β€ β€ succ-β€-β code : πΒΉ β π€β Μ code = πΒΉ-rec β€ succ-β€-οΌ \end{code} Using the first computation rule for πΒΉ-rec: \begin{code} code-on-base : code base οΌ β€ code-on-base = πΒΉ-rec-on-base β€ succ-β€-οΌ β€-to-code-base : β€ β code base β€-to-code-base = Idtofun (code-on-base β»ΒΉ) code-base-to-β€ : code base β β€ code-base-to-β€ = Idtofun code-on-base transport-code-loop-is-succ-β€ : code-base-to-β€ β transport code loop β β€-to-code-base οΌ succ-β€ transport-code-loop-is-succ-β€ = Ξ΄ β transport code loop β Ξ΅ οΌβ¨ I β© Ξ΄ β transport id acl β Ξ΅ οΌβ¨reflβ© Idtofun cob β Idtofun acl β Idtofun (cob β»ΒΉ) οΌβ¨ II β© Idtofun cob β Idtofun (cob β»ΒΉ β acl) οΌβ¨ III β© Idtofun (cob β»ΒΉ β acl β cob) οΌβ¨ IV β© Idtofun succ-β€-οΌ οΌβ¨ V β© succ-β€ β where cob = code-on-base acl = ap code loop Ξ΅ = β€-to-code-base Ξ΄ = code-base-to-β€ I = ap (Ξ» - β Ξ΄ β - β Ξ΅) (transport-ap' id code loop) II = ap (_β_ (Idtofun cob)) ((Idtofun-β ua (cob β»ΒΉ) acl) β»ΒΉ) III = (Idtofun-β ua (cob β»ΒΉ β acl) cob) β»ΒΉ \end{code} Using the second computation rule for πΒΉ-rec \begin{code} IV = ap Idtofun ((transport-along-οΌ cob acl) β»ΒΉ β (πΒΉ-rec-on-loop β€ succ-β€-οΌ)) V = Idtofun-eqtoid ua succ-β€-β transport-code-loopβ»ΒΉ-is-pred-β€ : code-base-to-β€ β transport code (loop β»ΒΉ) β β€-to-code-base βΌ pred-β€ transport-code-loopβ»ΒΉ-is-pred-β€ x = equivs-are-lc succ-β€ succ-β€-is-equiv Ξ³ where Ξ³ : (succ-β€ β code-base-to-β€ β transport code (loop β»ΒΉ) β β€-to-code-base) x οΌ (succ-β€ β pred-β€) x Ξ³ = (succ-β€ β Ξ΄ β tβ»ΒΉ β Ξ΅) x οΌβ¨ I β© (Ξ΄ β t β Ξ΅ β Ξ΄ β tβ»ΒΉ β Ξ΅) x οΌβ¨ II β© (Ξ΄ β t β tβ»ΒΉ β Ξ΅) x οΌβ¨ III β© (Ξ΄ β Ξ΅) x οΌβ¨ IV β© x οΌβ¨ V β© (succ-β€ β pred-β€) x β where Ξ΅ = β€-to-code-base Ξ΄ = code-base-to-β€ tβ»ΒΉ = transport code (loop β»ΒΉ) t = transport code loop I = happly (transport-code-loop-is-succ-β€ β»ΒΉ) ((Ξ΄ β tβ»ΒΉ β Ξ΅) x) II = ap (Ξ΄ β t) (Idtofun-section code-on-base (tβ»ΒΉ (Ξ΅ x))) III = ap Ξ΄ (back-and-forth-transport loop) IV = Idtofun-retraction code-on-base x V = (succ-β€-is-retraction x) β»ΒΉ transport-code-loopβ»ΒΉ-is-pred-β€' : transport code (loop β»ΒΉ) βΌ β€-to-code-base β pred-β€ β code-base-to-β€ transport-code-loopβ»ΒΉ-is-pred-β€' x = transport code (loop β»ΒΉ) x οΌβ¨ I β© (Ξ΅ β Ξ΄ β transport code (loop β»ΒΉ)) x οΌβ¨ II β© (Ξ΅ β Ξ΄ β transport code (loop β»ΒΉ) β Ξ΅ β Ξ΄) x οΌβ¨ III β© (Ξ΅ β pred-β€ β Ξ΄) x β where Ξ΅ = β€-to-code-base Ξ΄ = code-base-to-β€ I = (Idtofun-section code-on-base (transport code (loop β»ΒΉ) x)) β»ΒΉ II = ap (Ξ΅ β Ξ΄ β transport code (loop β»ΒΉ)) ((Idtofun-section code-on-base x) β»ΒΉ) III = ap Ξ΅ (transport-code-loopβ»ΒΉ-is-pred-β€ (Ξ΄ x)) encode : (x : πΒΉ) β (base οΌ x) β code x encode x p = transport code p (β€-to-code-base π) iterated-path : {X : π¦Μ } {x : X} β x οΌ x β β β x οΌ x iterated-path p zero = refl iterated-path p (succ n) = p β iterated-path p n iterated-path-comm : {X : π¦ Μ } {x : X} (p : x οΌ x) (n : β) β iterated-path p n β p οΌ p β iterated-path p n iterated-path-comm p zero = refl β p οΌβ¨ refl-left-neutral β© p οΌβ¨ refl β© p β refl β iterated-path-comm p (succ n) = p β iterated-path p n β p οΌβ¨ I β© p β (iterated-path p n β p) οΌβ¨ II β© p β (p β iterated-path p n) β where I = βassoc p (iterated-path p n) p II = ap (p β_) (iterated-path-comm p n) loops : β€ β base οΌ base loops π = refl loops (pos n) = iterated-path loop (succ n) loops (neg n) = iterated-path (loop β»ΒΉ) (succ n) module _ (fe : funext π€β π€) where open import UF.Lower-FunExt loops-lemma : (_β loop) β loops β pred-β€ οΌ loops loops-lemma = dfunext fe h where h : (k : β€) β loops (pred-β€ k) β loop οΌ loops k h π = loop β»ΒΉ β refl β loop οΌβ¨ refl β© loop β»ΒΉ β loop οΌβ¨ left-inverse loop β© refl β h (pos n) = g n where g : (n : β) β loops (pred-β€ (pos n)) β loop οΌ loops (pos n) g zero = iterated-path-comm loop zero g (succ n) = iterated-path-comm loop (succ n) h (neg n) = loop β»ΒΉ β (loop β»ΒΉ β iterated-path (loop β»ΒΉ) n) β loop οΌβ¨ I' β© loop β»ΒΉ β (iterated-path (loop β»ΒΉ) n β loop β»ΒΉ) β loop οΌβ¨ II' β© loop β»ΒΉ β iterated-path (loop β»ΒΉ) n β (loop β»ΒΉ β loop) οΌβ¨ III' β© loop β»ΒΉ β iterated-path (loop β»ΒΉ) n β where I' = ap (Ξ» - β loop β»ΒΉ β - β loop) ((iterated-path-comm (loop β»ΒΉ) n) β»ΒΉ) II' = βassoc (loop β»ΒΉ) (iterated-path (loop β»ΒΉ) n β loop β»ΒΉ) loop β ap (loop β»ΒΉ β_) (βassoc (iterated-path (loop β»ΒΉ) n) (loop β»ΒΉ) loop) β (βassoc (loop β»ΒΉ) (iterated-path (loop β»ΒΉ) n) (loop β»ΒΉ β loop)) β»ΒΉ III' = ap ((loop β»ΒΉ β iterated-path (loop β»ΒΉ) n) β_) (left-inverse loop) transport-loops-lemma : transport (Ξ» - β code - β base οΌ -) loop (loops β code-base-to-β€) οΌ (loops β code-base-to-β€) transport-loops-lemma = transport (Ξ» - β code - β base οΌ -) loop f οΌβ¨ I β© transport (Ξ» - β base οΌ -) loop β f β transport code (loop β»ΒΉ) οΌβ¨ II β© (_β loop) β f β transport code (loop β»ΒΉ) οΌβ¨ III β© (_β loop) β loops β Ξ΄ β Ξ΅ β pred-β€ β Ξ΄ οΌβ¨ IV β© (_β loop) β loops β pred-β€ β Ξ΄ οΌβ¨ V β© loops β Ξ΄ β where Ξ΅ : β€ β code base Ξ΅ = β€-to-code-base Ξ΄ : code base β β€ Ξ΄ = code-base-to-β€ f : code base β base οΌ base f = loops β Ξ΄ I = transport-along-β code (_οΌ_ base) loop f II = refl III = ap ((_β loop) β f β_) (dfunext (lower-funext π€β π€ fe) transport-code-loopβ»ΒΉ-is-pred-β€') IV = ap (Ξ» - β (_β loop) β loops β - β pred-β€ β Ξ΄) (dfunext (lower-funext π€β π€ fe) (Idtofun-retraction code-on-base)) V = ap (_β Ξ΄) loops-lemma open πΒΉ-induction (Ξ» - β code - β base οΌ -) (loops β code-base-to-β€) transport-loops-lemma decode : (x : πΒΉ) β code x β base οΌ x decode = πΒΉ-induction decode-encode : (x : πΒΉ) (p : base οΌ x) β decode x (encode x p) οΌ p decode-encode base refl = decode base (encode base refl) οΌβ¨reflβ© decode base (transport code refl (β€-to-code-base π)) οΌβ¨reflβ© decode base (β€-to-code-base π) οΌβ¨ I β© loops (code-base-to-β€ (β€-to-code-base π)) οΌβ¨ II β© loops π οΌβ¨reflβ© refl β where \end{code} Using the first computation rule for πΒΉ-induction \begin{code} I = happly πΒΉ-induction-on-base (β€-to-code-base π) II = ap loops (Idtofun-retraction code-on-base π) open import UF.Retracts Ξ©πΒΉ-is-set : is-set (base οΌ base) Ξ©πΒΉ-is-set = subtypes-of-sets-are-sets' (encode base) (sections-are-lc (encode base) ((decode base) , (decode-encode base))) (transport is-set (code-on-base β»ΒΉ) β€-is-set) module πΒΉ-induction' {π₯ : Universe} (A : πΒΉ β π₯ Μ ) (a : A base) (l : transport A loop a οΌ a) (fe : funext π€β π€) (ua : is-univalent π€β) where open πΒΉ-induction A a l πΒΉ-induction-on-loop' : transport (Ξ» - β transport A loop - οΌ -) πΒΉ-induction-on-base (apd πΒΉ-induction loop) οΌ l πΒΉ-induction-on-loop' = πΒΉ-induction-on-loop (Ξ©πΒΉ-is-set ua fe) πΒΉ-induction-comp' : (πΒΉ-induction base , apd πΒΉ-induction loop) οΌ[ Ξ£ y κ A base , transport A loop y οΌ y ] (a , l) πΒΉ-induction-comp' = πΒΉ-induction-comp (Ξ©πΒΉ-is-set ua fe) \end{code}