Martin Escardo Notion of equivalence and its basic properties. \begin{code} {-# OPTIONS --safe --without-K #-} module UF.Equiv where open import MLTT.Spartan open import MLTT.Unit-Properties open import UF.Base open import UF.Retracts open import UF.Subsingletons \end{code} We take Joyal's version of the notion of equivalence as the primary one because it is more symmetrical. \begin{code} is-equiv : {X : π€Μ } {Y : π₯ Μ } β (X β Y) β π€ β π₯ Μ is-equiv f = has-section f Γ is-section f inverse : {X : π€Μ } {Y : π₯ Μ } (f : X β Y) β is-equiv f β (Y β X) inverse f = prβ β prβ equivs-have-sections : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-equiv f β has-section f equivs-have-sections f = prβ equivs-are-sections : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-equiv f β is-section f equivs-are-sections f = prβ section-retraction-equiv : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β has-section f β is-section f β is-equiv f section-retraction-equiv f hr hs = (hr , hs) equivs-are-lc : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-equiv f β left-cancellable f equivs-are-lc f e = sections-are-lc f (equivs-are-sections f e) _β_ : π€ Μ β π₯Μ β π€ β π₯Μ X β Y = Ξ£ f κ (X β Y) , is-equiv f Aut : π€Μ β π€Μ Aut X = (X β X) id-is-equiv : (X : π€Μ ) β is-equiv (id {π€} {X}) id-is-equiv X = (id , Ξ» x β refl) , (id , Ξ» x β refl) β-refl : (X : π€ Μ ) β X β X β-refl X = id , id-is-equiv X ππ : {X : π€ Μ } β X β X ππ = β-refl _ β-is-equiv : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } {f : X β Y} {f' : Y β Z} β is-equiv f β is-equiv f' β is-equiv (f' β f) β-is-equiv {π€} {π₯} {π¦} {X} {Y} {Z} {f} {f'} ((g , fg) , (h , hf)) ((g' , fg') , (h' , hf')) = (g β g' , fg'') , (h β h' , hf'') where fg'' : (z : Z) β f' (f (g (g' z))) οΌ z fg'' z = ap f' (fg (g' z)) β fg' z hf'' : (x : X) β h (h' (f' (f x))) οΌ x hf'' x = ap h (hf' (f x)) β hf x \end{code} For type-checking efficiency reasons: \begin{code} β-is-equiv-abstract : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } {f : X β Y} {f' : Y β Z} β is-equiv f β is-equiv f' β is-equiv (f' β f) β-is-equiv-abstract {π€} {π₯} {π¦} {X} {Y} {Z} {f} {f'} = Ξ³ where abstract Ξ³ : is-equiv f β is-equiv f' β is-equiv (f' β f) Ξ³ = β-is-equiv β-comp : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } β X β Y β Y β Z β X β Z β-comp {π€} {π₯} {π¦} {X} {Y} {Z} (f , d) (f' , e) = f' β f , β-is-equiv d e _β_ : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } β X β Y β Y β Z β X β Z _β_ = β-comp _ββ¨_β©_ : (X : π€ Μ ) {Y : π₯ Μ } {Z : π¦ Μ } β X β Y β Y β Z β X β Z _ ββ¨ d β© e = d β e _β : (X : π€ Μ ) β X β X _β = β-refl \end{code} Added by Carlo Angiuli on November 20, 2025. Special syntax for definitional steps in equivalence chain reasoning: \begin{code} _ββ¨reflβ©_ : (X : π€Μ ) {Y : π₯ Μ } β X β Y β X β Y _ ββ¨reflβ© e = e _ββ¨by-definitionβ©_ : (X : π€ Μ ) {Y : π₯ Μ } β X β Y β X β Y _ββ¨by-definitionβ©_ = _ββ¨reflβ©_ \end{code} End of addition. \begin{code} Eqtofun : (X : π€Μ ) (Y : π₯ Μ ) β X β Y β X β Y Eqtofun X Y (f , _) = f eqtofun β_β : {X : π€ Μ } {Y : π₯ Μ } β X β Y β X β Y eqtofun = Eqtofun _ _ β_β = eqtofun eqtofun- ββ-is-equiv β_β-is-equiv : {X : π€ Μ } {Y : π₯ Μ } (e : X β Y) β is-equiv β e β eqtofun- = prβ ββ-is-equiv = eqtofun- β_β-is-equiv = ββ-is-equiv back-eqtofun β_ββ»ΒΉ : {X : π€ Μ } {Y : π₯ Μ } β X β Y β Y β X back-eqtofun e = prβ (prβ (prβ e)) β_ββ»ΒΉ = back-eqtofun idtoeq : (X Y : π€ Μ ) β X οΌ Y β X β Y idtoeq X Y p = transport (X β_) p (β-refl X) idtoeq-traditional : (X Y : π€ Μ ) β X οΌ Y β X β Y idtoeq-traditional X _ refl = β-refl X \end{code} We would have a definitional equality if we had defined the traditional one using J (based), but because of the idiosyncrasies of Agda, we don't with the current definition: \begin{code} eqtoeq-agreement : (X Y : π€ Μ ) (p : X οΌ Y) β idtoeq X Y p οΌ idtoeq-traditional X Y p eqtoeq-agreement {π€} X _ refl = refl idtofun : (X Y : π€ Μ ) β X οΌ Y β X β Y idtofun X Y p = β idtoeq X Y p β idtofun' : {X Y : π€ Μ } β X οΌ Y β X β Y idtofun' = idtofun _ _ \end{code} Added 19 June 2026 by Tom de Jong: relating transport, idtofun and ap. \begin{code} transport-is-idtofun-after-ap : {A : π€Μ } (B : A β π₯ Μ ) {aβ aβ : A} (p : aβ οΌ aβ) β transport B p οΌ idtofun (B aβ) (B aβ) (ap B p) transport-is-idtofun-after-ap B refl = refl transport-is-idtofun-after-apβ»ΒΉ : {A : π€ Μ } (B : A β π₯ Μ ) {aβ aβ : A} (p : aβ οΌ aβ) β transport B (p β»ΒΉ) οΌ β idtoeq (B aβ) (B aβ) (ap B p) ββ»ΒΉ transport-is-idtofun-after-apβ»ΒΉ B refl = refl \end{code} End of addition. \begin{code} idtofun-agreement : (X Y : π€Μ ) (p : X οΌ Y) β idtofun X Y p οΌ Idtofun p idtofun-agreement X Y refl = refl equiv-closed-under-βΌ : {X : π€ Μ } {Y : π₯ Μ } (f g : X β Y) β is-equiv f β g βΌ f β is-equiv g equiv-closed-under-βΌ {π€} {π₯} {X} {Y} f g (hass , hasr) h = has-section-closed-under-βΌ f g hass h , is-section-closed-under-βΌ f g hasr h equiv-closed-under-βΌ' : {X : π€ Μ } {Y : π₯ Μ } {f g : X β Y} β is-equiv f β f βΌ g β is-equiv g equiv-closed-under-βΌ' ise h = equiv-closed-under-βΌ _ _ ise (Ξ» x β (h x)β»ΒΉ) invertible : {X : π€ Μ } {Y : π₯ Μ } β (X β Y) β π€ β π₯ Μ invertible f = Ξ£ g κ (codomain f β domain f), (g β f βΌ id) Γ (f β g βΌ id) qinv = invertible inverses-are-retractions : {X : π€Μ } {Y : π₯ Μ } (f : X β Y) (e : is-equiv f) β inverse f e β f βΌ id inverses-are-retractions f ((g , Ξ΅) , (g' , Ξ·)) = Ξ·' where Ξ·' : g β f βΌ id Ξ·' x = g (f x) οΌβ¨ (Ξ· (g (f x)))β»ΒΉ β© g' (f (g (f x))) οΌβ¨ ap g' (Ξ΅ (f x)) β© g' (f x) οΌβ¨ Ξ· x β© x β inverses-are-retractions' : {X : π€ Μ } {Y : π₯ Μ } (π : X β Y) β β π ββ»ΒΉ β β π β βΌ id inverses-are-retractions' (f , e) = inverses-are-retractions f e equivs-are-qinvs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-equiv f β qinv f equivs-are-qinvs {π€} {π₯} {X} {Y} f e@((g , Ξ΅) , (g' , Ξ·)) = g , inverses-are-retractions f e , Ξ΅ naive-inverses-are-sections : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (e : is-equiv f) β f β inverse f e βΌ id naive-inverses-are-sections f ((g' , Ξ΅) , (g , Ξ·)) = Ξ΅ inverses-are-sections : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (e : is-equiv f) β f β inverse f e βΌ id inverses-are-sections f e@((g , Ξ΅) , (g' , Ξ·)) = Ξ΅' where Ξ΅' : f β g βΌ id Ξ΅' y = f (g y) οΌβ¨ (Ξ΅ (f (g y)))β»ΒΉ β© f (g (f (g y))) οΌβ¨ ap f (inverses-are-retractions f e (g y)) β© f (g y) οΌβ¨ Ξ΅ y β© y β inverses-are-sections' : {X : π€ Μ } {Y : π₯ Μ } (π : X β Y) β β π β β β π ββ»ΒΉ βΌ id inverses-are-sections' (f , e) = inverses-are-sections f e inverses-are-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (e : is-equiv f) β is-equiv (inverse f e) inverses-are-equivs f e = (f , inverses-are-retractions f e) , (f , inverses-are-sections f e) βββ»ΒΉ-is-equiv : {X : π€ Μ } {Y : π₯ Μ } (e : X β Y) β is-equiv β e ββ»ΒΉ βββ»ΒΉ-is-equiv (f , i) = inverses-are-equivs f i β_ββ»ΒΉ-is-equiv : {X : π€ Μ } {Y : π₯ Μ } (e : X β Y) β is-equiv β e ββ»ΒΉ β_ββ»ΒΉ-is-equiv = βββ»ΒΉ-is-equiv inversion-involutive : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (e : is-equiv f) β inverse (inverse f e) (inverses-are-equivs f e) οΌ f inversion-involutive f e = refl \end{code} That the above proof is refl is an accident of our choice of notion of equivalence as primary. \begin{code} qinvs-are-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β qinv f β is-equiv f qinvs-are-equivs f (g , (gf , fg)) = (g , fg) , (g , gf) qinveq : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β qinv f β X β Y qinveq f q = (f , qinvs-are-equivs f q) lc-split-surjections-are-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β left-cancellable f β ((y : Y) β Ξ£ x κ X , f x οΌ y) β is-equiv f lc-split-surjections-are-equivs f l s = qinvs-are-equivs f (g , Ξ· , Ξ΅) where g : codomain f β domain f g y = prβ (s y) Ξ΅ : f β g βΌ id Ξ΅ y = prβ (s y) Ξ· : g β f βΌ id Ξ· x = l p where p : f (g (f x)) οΌ f x p = Ξ΅ (f x) lc-retractions-are-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β left-cancellable f β has-section f β is-equiv f lc-retractions-are-equivs f lc-f (s , H) = lc-split-surjections-are-equivs f lc-f (Ξ» y β s y , H y) β-sym : {X : π€ Μ } {Y : π₯ Μ } β X β Y β Y β X β-sym {π€} {π₯} {X} {Y} (f , e) = inverse f e , inverses-are-equivs f e β-sym-is-linv : {X : π€ Μ } {Y : π₯ Μ } (π― : X β Y) β β π― ββ»ΒΉ β β π― β βΌ id β-sym-is-linv (f , e) x = inverses-are-retractions f e x β-sym-is-rinv : {X : π€ Μ } {Y : π₯ Μ } (π― : X β Y) β β π― β β β π― ββ»ΒΉ βΌ id β-sym-is-rinv (f , e) y = inverses-are-sections f e y β-gives-β : {X : π€ Μ } {Y : π₯ Μ } β X β Y β X β Y β-gives-β (f , (g , fg) , (h , hf)) = h , f , hf β-gives-β· : {X : π€ Μ } {Y : π₯ Μ } β X β Y β Y β X β-gives-β· (f , (g , fg) , (h , hf)) = f , g , fg Id-retract-l : {X Y : π€ Μ } β X οΌ Y β retract X of Y Id-retract-l p = β-gives-β (idtoeq (lhs p) (rhs p) p) Id-retract-r : {X Y : π€ Μ } β X οΌ Y β retract Y of X Id-retract-r p = β-gives-β· (idtoeq (lhs p) (rhs p) p) equiv-to-prop : {X : π€ Μ } {Y : π₯ Μ } β Y β X β is-prop X β is-prop Y equiv-to-prop e = retract-of-prop (β-gives-β e) equiv-to-singleton : {X : π€ Μ } {Y : π₯ Μ } β Y β X β is-singleton X β is-singleton Y equiv-to-singleton e = retract-of-singleton (β-gives-β e) equiv-to-singleton' : {X : π€ Μ } {Y : π₯ Μ } β X β Y β is-singleton X β is-singleton Y equiv-to-singleton' e = retract-of-singleton (β-gives-β· e) singleton-types-are-equivalent : {X : π€ Μ } (x : X) β singleton-type x β singleton-type' x singleton-types-are-equivalent x = f , ((g , fg) , (g , gf)) where f : singleton-type x β singleton-type' x f (y , p) = y , (p β»ΒΉ) g : singleton-type' x β singleton-type x g (y , p) = y , (p β»ΒΉ) fg : f β g βΌ id fg (y , p) = ap (Ξ» - β y , -) (β»ΒΉ-involutive p) gf : g β f βΌ id gf (y , p) = ap (Ξ» - β y , -) (β»ΒΉ-involutive p) singleton-types'-are-singletons : {X : π€ Μ } (x : X) β is-singleton (singleton-type' x) singleton-types'-are-singletons x = retract-of-singleton (β-gives-β· (singleton-types-are-equivalent x)) (singleton-types-are-singletons x) singleton-types'-are-props : {X : π€ Μ } (x : X) β is-prop (singleton-type' x) singleton-types'-are-props x = singletons-are-props (singleton-types'-are-singletons x) transports-are-equivs : {X : π€ Μ } {A : X β π₯ Μ } {x y : X} (p : x οΌ y) β is-equiv (transport A p) transports-are-equivs refl = id-is-equiv _ transports-are-equivs' : {X : π€ Μ } (A : X β π₯ Μ ) {x y : X} (p : x οΌ y) β is-equiv (transport A p) transports-are-equivs' A refl = id-is-equiv _ transport-β : {X : π€ Μ } (A : X β π₯ Μ ) {x y : X} (p : x οΌ y) β A x β A y transport-β A p = transport A p , transports-are-equivs p back-transports-are-equivs : {X : π€ Μ } {A : X β π₯ Μ } {x y : X} (p : x οΌ y) β is-equiv (transportβ»ΒΉ A p) back-transports-are-equivs p = transports-are-equivs (p β»ΒΉ) is-vv-equiv : {X : π€ Μ } {Y : π₯ Μ } β (X β Y) β π€ β π₯ Μ is-vv-equiv f = each-fiber-of f is-singleton _ : {X : π€Μ } {Y : π₯ Μ } (f : X β Y) β is-vv-equiv f οΌ (Ξ y κ Y , β! x κ X , f x οΌ y) _ = Ξ» f β refl vv-equivs-are-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-vv-equiv f β is-equiv f vv-equivs-are-equivs {π€} {π₯} {X} {Y} f Ο = (g , fg) , (g , gf) where Ο' : (y : Y) β Ξ£ c κ (Ξ£ x κ X , f x οΌ y) , ((Ο : Ξ£ x κ X , f x οΌ y) β c οΌ Ο) Ο' = Ο c : (y : Y) β Ξ£ x κ X , f x οΌ y c y = prβ (Ο y) d : (y : Y) β (Ο : Ξ£ x κ X , f x οΌ y) β c y οΌ Ο d y = prβ (Ο y) g : Y β X g y = prβ (c y) fg : (y : Y) β f (g y) οΌ y fg y = prβ (c y) e : (x : X) β g (f x) , fg (f x) οΌ x , refl e x = d (f x) (x , refl) gf : (x : X) β g (f x) οΌ x gf x = ap prβ (e x) id-is-vv-equiv : (X : π€ Μ ) β is-vv-equiv (id {π€} {X}) id-is-vv-equiv X y = (y , refl) , (Ξ» where (.y , refl) β refl) fiber' : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β Y β π€ β π₯ Μ fiber' f y = Ξ£ x κ domain f , y οΌ f x fiber-lemma : {X : π€Μ } {Y : π₯ Μ } (f : X β Y) (y : Y) β fiber f y β fiber' f y fiber-lemma f y = g , (h , gh) , (h , hg) where g : fiber f y β fiber' f y g (x , p) = x , (p β»ΒΉ) h : fiber' f y β fiber f y h (x , p) = x , (p β»ΒΉ) hg : β Ο β h (g Ο) οΌ Ο hg (x , refl) = refl gh : β Ο β g (h Ο) οΌ Ο gh (x , refl) = refl is-hae : {X : π€ Μ } {Y : π₯ Μ } β (X β Y) β π€ β π₯ Μ is-hae {π€} {π₯} {X} {Y} f = Ξ£ g κ (Y β X) , Ξ£ Ξ· κ g β f βΌ id , Ξ£ Ξ΅ κ f β g βΌ id , Ξ x κ X , ap f (Ξ· x) οΌ Ξ΅ (f x) haes-are-equivs : {X : π€Μ } {Y : π₯ Μ } (f : X β Y) β is-hae f β is-equiv f haes-are-equivs {π€} {π₯} {X} f (g , Ξ· , Ξ΅ , Ο) = qinvs-are-equivs f (g , Ξ· , Ξ΅) id-homotopies-are-natural : {X : π€ Μ } (h : X β X) (Ξ· : h βΌ id) {x : X} β Ξ· (h x) οΌ ap h (Ξ· x) id-homotopies-are-natural h Ξ· {x} = Ξ· (h x) οΌβ¨reflβ© Ξ· (h x) β refl οΌβ¨ I β© Ξ· (h x) β (Ξ· x β (Ξ· x)β»ΒΉ) οΌβ¨ II β© Ξ· (h x) β Ξ· x β (Ξ· x)β»ΒΉ οΌβ¨ III β© Ξ· (h x) β ap id (Ξ· x) β (Ξ· x)β»ΒΉ οΌβ¨ IV β© ap h (Ξ· x) β where I = ap (Ξ» - β Ξ· (h x) β -) ((trans-sym' (Ξ· x))β»ΒΉ) II = (βassoc (Ξ· (h x)) (Ξ· x) (Ξ· x β»ΒΉ))β»ΒΉ III = ap (Ξ» - β Ξ· (h x) β - β (Ξ· x)β»ΒΉ) ((ap-id-is-id' (Ξ· x))) IV = homotopies-are-natural' h id Ξ· {h x} {x} {Ξ· x} half-adjoint-condition : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (e : is-equiv f) (x : X) β ap f (inverses-are-retractions f e x) οΌ inverses-are-sections f e (f x) half-adjoint-condition {π€} {π₯} {X} {Y} f e@((g , Ξ΅) , (g' , Ξ·)) = Ο where Ξ·' : g β f βΌ id Ξ·' = inverses-are-retractions f e Ξ΅' : f β g βΌ id Ξ΅' = inverses-are-sections f e a : (x : X) β Ξ·' (g (f x)) οΌ ap g (ap f (Ξ·' x)) a x = Ξ·' (g (f x)) οΌβ¨ id-homotopies-are-natural (g β f) Ξ·' β© ap (g β f) (Ξ·' x) οΌβ¨ (ap-ap f g (Ξ·' x))β»ΒΉ β© ap g (ap f (Ξ·' x)) β b : (x : X) β ap f (Ξ·' (g (f x))) β Ξ΅ (f x) οΌ Ξ΅ (f (g (f x))) β ap f (Ξ·' x) b x = ap f (Ξ·' (g (f x))) β Ξ΅ (f x) οΌβ¨ I β© ap f (ap g (ap f (Ξ·' x))) β Ξ΅ (f x) οΌβ¨ II β© ap (f β g) (ap f (Ξ·' x)) β Ξ΅ (f x) οΌβ¨ III β© Ξ΅ (f (g (f x))) β ap id (ap f (Ξ·' x)) οΌβ¨ IV β© Ξ΅ (f (g (f x))) β ap f (Ξ·' x) β where I = ap (Ξ» - β - β Ξ΅ (f x)) (ap (ap f) (a x)) II = ap (Ξ» - β - β Ξ΅ (f x)) (ap-ap g f (ap f (Ξ·' x))) III = (homotopies-are-natural (f β g) id Ξ΅ {_} {_} {ap f (Ξ·' x)})β»ΒΉ IV = ap (Ξ» - β Ξ΅ (f (g (f x))) β -) (ap-ap f id (Ξ·' x)) Ο : (x : X) β ap f (Ξ·' x) οΌ Ξ΅' (f x) Ο x = ap f (Ξ·' x) οΌβ¨ I β© refl β ap f (Ξ·' x) οΌβ¨ II β© (Ξ΅ (f (g (f x))))β»ΒΉ β Ξ΅ (f (g (f x))) β ap f (Ξ·' x) οΌβ¨ III β© (Ξ΅ (f (g (f x))))β»ΒΉ β (Ξ΅ (f (g (f x))) β ap f (Ξ·' x)) οΌβ¨ IV β© (Ξ΅ (f (g (f x))))β»ΒΉ β (ap f (Ξ·' (g (f x))) β Ξ΅ (f x)) οΌβ¨reflβ© Ξ΅' (f x) β where I = refl-left-neutral β»ΒΉ II = ap (Ξ» - β - β ap f (Ξ·' x)) ((trans-sym (Ξ΅ (f (g (f x)))))β»ΒΉ) III = βassoc ((Ξ΅ (f (g (f x))))β»ΒΉ) (Ξ΅ (f (g (f x)))) (ap f (Ξ·' x)) IV = ap (Ξ» - β (Ξ΅ (f (g (f x))))β»ΒΉ β -) (b x)β»ΒΉ equivs-are-haes : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-equiv f β is-hae f equivs-are-haes {π€} {π₯} {X} {Y} f e@((g , Ξ΅) , (g' , Ξ·)) = inverse f e , inverses-are-retractions f e , inverses-are-sections f e , half-adjoint-condition f e qinvs-are-haes : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β qinv f β is-hae f qinvs-are-haes {π€} {π₯} {X} {Y} f = equivs-are-haes f β qinvs-are-equivs f \end{code} The following could be defined by combining functions we already have, but a proof by path induction is direct: \begin{code} identifications-in-fibers : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (y : Y) (x x' : X) (p : f x οΌ y) (p' : f x' οΌ y) β (Ξ£ Ξ³ κ x οΌ x' , ap f Ξ³ β p' οΌ p) β (x , p) οΌ (x' , p') identifications-in-fibers f .(f x) x x refl p' (refl , r) = g where g : x , refl οΌ x , p' g = ap (Ξ» - β (x , -)) (r β»ΒΉ β refl-left-neutral) \end{code} Using this we see that half adjoint equivalences have singleton fibers. \begin{code} haes-are-vv-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-hae f β is-vv-equiv f haes-are-vv-equivs {π€} {π₯} {X} f (g , Ξ· , Ξ΅ , Ο) y = (c , Ξ» Ο β Ξ± (prβ Ο) (prβ Ο)) where c : fiber f y c = (g y , Ξ΅ y) Ξ± : (x : X) (p : f x οΌ y) β c οΌ (x , p) Ξ± x p = Ο where Ξ³ : g y οΌ x Ξ³ = (ap g p)β»ΒΉ β Ξ· x q : ap f Ξ³ β p οΌ Ξ΅ y q = ap f Ξ³ β p οΌβ¨reflβ© ap f ((ap g p)β»ΒΉ β Ξ· x) β p οΌβ¨ I β© ap f ((ap g p)β»ΒΉ) β ap f (Ξ· x) β p οΌβ¨ II β© ap f (ap g (p β»ΒΉ)) β ap f (Ξ· x) β p οΌβ¨ III β© ap f (ap g (p β»ΒΉ)) β Ξ΅ (f x) β p οΌβ¨ IV β© ap (f β g) (p β»ΒΉ) β Ξ΅ (f x) β p οΌβ¨ V β© Ξ΅ y β ap id (p β»ΒΉ) β p οΌβ¨ VI β© Ξ΅ y β p β»ΒΉ β p οΌβ¨ VII β© Ξ΅ y β (p β»ΒΉ β p) οΌβ¨ VIII β© Ξ΅ y β refl οΌβ¨reflβ© Ξ΅ y β where I = ap (Ξ» - β - β p) (ap-β f ((ap g p)β»ΒΉ) (Ξ· x)) II = ap (Ξ» - β ap f - β ap f (Ξ· x) β p) (ap-sym g p) III = ap (Ξ» - β ap f (ap g (p β»ΒΉ)) β - β p) (Ο x) IV = ap (Ξ» - β - β Ξ΅ (f x) β p) (ap-ap g f (p β»ΒΉ)) V = ap (Ξ» - β - β p) (homotopies-are-natural (f β g) id Ξ΅ {y} {f x} {p β»ΒΉ})β»ΒΉ VI = ap (Ξ» - β Ξ΅ y β - β p) (ap-id-is-id (p β»ΒΉ)) VII = βassoc (Ξ΅ y) (p β»ΒΉ) p VIII = ap (Ξ» - β Ξ΅ y β -) (trans-sym p) Ο : g y , Ξ΅ y οΌ x , p Ο = identifications-in-fibers f y (g y) x (Ξ΅ y) p (Ξ³ , q) \end{code} Here are some corollaries: \begin{code} qinvs-are-vv-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β qinv f β is-vv-equiv f qinvs-are-vv-equivs f q = haes-are-vv-equivs f (qinvs-are-haes f q) equivs-are-vv-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-equiv f β is-vv-equiv f equivs-are-vv-equivs f ie = qinvs-are-vv-equivs f (equivs-are-qinvs f ie) \end{code} We pause to characterize negation and singletons. Recall that Β¬ X and is-empty X are synonyms for the function type X β π. \begin{code} equiv-can-assume-pointed-codomain : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β (Y β is-vv-equiv f) β is-vv-equiv f equiv-can-assume-pointed-codomain f Ο y = Ο y y maps-to-π-are-equivs : {X : π€ Μ } (f : X β π {π₯}) β is-vv-equiv f maps-to-π-are-equivs f = equiv-can-assume-pointed-codomain f π-elim negations-are-equiv-to-π : {X : π€ Μ } β is-empty X β X β π negations-are-equiv-to-π = (Ξ» f β f , vv-equivs-are-equivs f (maps-to-π-are-equivs f)) , eqtofun \end{code} Then with functional and propositional extensionality, which follow from univalence, we conclude that Β¬ X = (X β 0) = (X οΌ 0). And similarly, with similar proof: \begin{code} singletons-are-equiv-to-π : {X : π€ Μ } β is-singleton X β X β π {π₯} singletons-are-equiv-to-π (xβ , Ο) = qinveq unique-to-π ((Ξ» _ β xβ) , (Ο , (Ξ» x β (π-all-β x)β»ΒΉ))) types-equiv-to-π-are-singletons : {X : π€ Μ } β X β π {π₯} β is-singleton X types-equiv-to-π-are-singletons (f , (s , fs) , (r , rf)) = retract-of-singleton (r , f , rf) π-is-singleton \end{code} The following again could be defined by combining functions we already have: \begin{code} from-identifications-in-fibers : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (y : Y) (x x' : X) (p : f x οΌ y) (p' : f x' οΌ y) β (x , p) οΌ (x' , p') β Ξ£ Ξ³ κ x οΌ x' , ap f Ξ³ β p' οΌ p from-identifications-in-fibers f .(f x) x x refl refl refl = refl , refl Ξ·-pif : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (y : Y) (x x' : X) (p : f x οΌ y) (p' : f x' οΌ y) β from-identifications-in-fibers f y x x' p p' β identifications-in-fibers f y x x' p p' βΌ id Ξ·-pif f .(f x) x x _ refl (refl , refl) = refl \end{code} Then the following is a consequence of natural-section-is-section, but also has a direct proof by path induction: \begin{code} Ξ΅-pif : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) (y : Y) (x x' : X) (p : f x οΌ y) (p' : f x' οΌ y) β identifications-in-fibers f y x x' p p' β from-identifications-in-fibers f y x x' p p' βΌ id Ξ΅-pif f .(f x) x x refl refl refl = refl prβ-is-vv-equiv : (X : π€ Μ ) (Y : X β π₯ Μ ) β ((x : X) β is-singleton (Y x)) β is-vv-equiv (prβ {π€} {π₯} {X} {Y}) prβ-is-vv-equiv {π€} {π₯} X Y iss x = g where c : fiber prβ x c = (x , prβ (iss x)) , refl p : (y : Y x) β prβ (iss x) οΌ y p = prβ (iss x) f : (w : Ξ£ Ο κ Ξ£ Y , prβ Ο οΌ x) β c οΌ w f ((x , y) , refl) = ap (Ξ» - β (x , -) , refl) (p y) g : is-singleton (fiber prβ x) g = c , f prβ-is-equiv : (X : π€ Μ ) (Y : X β π₯ Μ ) β ((x : X) β is-singleton (Y x)) β is-equiv (prβ {π€} {π₯} {X} {Y}) prβ-is-equiv X Y iss = vv-equivs-are-equivs prβ (prβ-is-vv-equiv X Y iss) prβ-is-vv-equiv-converse : {X : π€ Μ } {A : X β π₯ Μ } β is-vv-equiv (prβ {π€} {π₯} {X} {A}) β ((x : X) β is-singleton (A x)) prβ-is-vv-equiv-converse {π€} {π₯} {X} {A} isv x = Ξ³ where f : Ξ£ A β X f = prβ {π€} {π₯} {X} {A} s : A x β fiber f x s a = (x , a) , refl r : fiber f x β A x r ((x , a) , refl) = a rs : (a : A x) β r (s a) οΌ a rs a = refl Ξ³ : is-singleton (A x) Ξ³ = retract-of-singleton (r , s , rs) (isv x) logical-equivs-of-props-are-equivs : {P : π€ Μ } {Q : π₯ Μ } β is-prop P β is-prop Q β (f : P β Q) β (Q β P) β is-equiv f logical-equivs-of-props-are-equivs i j f g = qinvs-are-equivs f (g , (Ξ» x β i (g (f x)) x) , (Ξ» x β j (f (g x)) x)) logically-equivalent-props-are-equivalent : {P : π€ Μ } {Q : π₯ Μ } β is-prop P β is-prop Q β (P β Q) β (Q β P) β P β Q logically-equivalent-props-are-equivalent i j f g = (f , logical-equivs-of-props-are-equivs i j f g) \end{code} 5th March 2019. A more direct proof that quasi-invertible maps are Voevodsky equivalences (have contractible fibers). \begin{code} qinvs-are-vv-equivs' : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β qinv f β is-vv-equiv f qinvs-are-vv-equivs' {π€} {π₯} {X} {Y} f (g , Ξ· , Ξ΅) yβ = Ξ³ where a : (y : Y) β (f (g y) οΌ yβ) β (y οΌ yβ) a y = r , s , rs where r : y οΌ yβ β f (g y) οΌ yβ r p = Ξ΅ y β p s : f (g y) οΌ yβ β y οΌ yβ s q = (Ξ΅ y)β»ΒΉ β q rs : (q : f (g y) οΌ yβ) β r (s q) οΌ q rs q = Ξ΅ y β ((Ξ΅ y)β»ΒΉ β q) οΌβ¨ (βassoc (Ξ΅ y) ((Ξ΅ y)β»ΒΉ) q)β»ΒΉ β© (Ξ΅ y β (Ξ΅ y)β»ΒΉ) β q οΌβ¨ ap (_β q) ((sym-is-inverse' (Ξ΅ y))β»ΒΉ) β© refl β q οΌβ¨ refl-left-neutral β© q β b : fiber f yβ β singleton-type' yβ b = (Ξ£ x κ X , f x οΌ yβ) ββ¨ Ξ£-reindex-retract g (f , Ξ·) β© (Ξ£ y κ Y , f (g y) οΌ yβ) ββ¨ Ξ£-retract (Ξ» y β f (g y) οΌ yβ) (_οΌ yβ) a β© (Ξ£ y κ Y , y οΌ yβ) β Ξ³ : is-singleton (fiber f yβ) Ξ³ = retract-of-singleton b (singleton-types'-are-singletons yβ) maps-of-singletons-are-equivs : {X : π€ Μ } {Y : π₯ Μ } (f : X β Y) β is-singleton X β is-singleton Y β is-equiv f maps-of-singletons-are-equivs f (c , Ο) (d , Ξ³) = ((Ξ» y β c) , (Ξ» x β f c οΌβ¨ singletons-are-props (d , Ξ³) (f c) x β© x β)) , ((Ξ» y β c) , Ο) is-fiberwise-equiv : {X : π€ Μ } {A : X β π₯ Μ } {B : X β π¦ Μ } β Nat A B β π€ β π₯ β π¦ Μ is-fiberwise-equiv Ο = β x β is-equiv (Ο x) \end{code}Added 1st December 2019. Sometimes it is is convenient to reason with quasi-equivalences directly, in particular if we want to avoid function extensionality, and we introduce some machinery for this. \begin{code} _β _ : π€Μ β π₯Μ β π€ β π₯Μ X β Y = Ξ£ f κ (X β Y) , qinv f id-qinv : (X : π€Μ ) β qinv (id {π€} {X}) id-qinv X = id , (Ξ» x β refl) , (Ξ» x β refl) β -refl : (X : π€ Μ ) β X β X β -refl X = id , (id-qinv X) β-qinv : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } {f : X β Y} {f' : Y β Z} β qinv f β qinv f' β qinv (f' β f) β-qinv {π€} {π₯} {π¦} {X} {Y} {Z} {f} {f'} = Ξ³ where Ξ³ : qinv f β qinv f' β qinv (f' β f) Ξ³ (g , gf , fg) (g' , gf' , fg') = (g β g' , gf'' , fg'') where fg'' : (z : Z) β f' (f (g (g' z))) οΌ z fg'' z = ap f' (fg (g' z)) β fg' z gf'' : (x : X) β g (g' (f' (f x))) οΌ x gf'' x = ap g (gf' (f x)) β gf x β -comp : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } β X β Y β Y β Z β X β Z β -comp {π€} {π₯} {π¦} {X} {Y} {Z} (f , d) (f' , e) = f' β f , β-qinv d e _β β¨_β©_ : (X : π€ Μ ) {Y : π₯ Μ } {Z : π¦ Μ } β X β Y β Y β Z β X β Z _ β β¨ d β© e = β -comp d e _βΎ : (X : π€ Μ ) β X β X _βΎ = β -refl \end{code} Added by Tom de Jong, November 2021. \begin{code} β-2-out-of-3-right : {X : π€Μ } {Y : π₯ Μ } {Z : π¦ Μ } β {f : X β Y} {g : Y β Z} β is-equiv f β is-equiv (g β f) β is-equiv g β-2-out-of-3-right {π€} {π₯} {π¦} {X} {Y} {Z} {f} {g} i j = equiv-closed-under-βΌ (g β f β fβ»ΒΉ) g k h where π : X β Y π = (f , i) fβ»ΒΉ : Y β X fβ»ΒΉ = β π ββ»ΒΉ k : is-equiv (g β f β fβ»ΒΉ) k = β-is-equiv (βββ»ΒΉ-is-equiv π) j h : g βΌ g β f β fβ»ΒΉ h y = ap g ((β-sym-is-rinv π y) β»ΒΉ) β-2-out-of-3-left : {X : π€ Μ } {Y : π₯ Μ } {Z : π¦ Μ } β {f : X β Y} {g : Y β Z} β is-equiv g β is-equiv (g β f) β is-equiv f β-2-out-of-3-left {π€} {π₯} {π¦} {X} {Y} {Z} {f} {g} i j = equiv-closed-under-βΌ (gβ»ΒΉ β g β f) f k h where π : Y β Z π = (g , i) gβ»ΒΉ : Z β Y gβ»ΒΉ = β π ββ»ΒΉ k : is-equiv (gβ»ΒΉ β g β f) k = β-is-equiv j (βββ»ΒΉ-is-equiv π) h : f βΌ gβ»ΒΉ β g β f h x = (β-sym-is-linv π (f x)) β»ΒΉ \end{code} Added by Martin Escardo 2nd November 2023. \begin{code} involutions-are-equivs : {X : π€Μ } β (f : X β X) β involutive f β is-equiv f involutions-are-equivs f f-involutive = qinvs-are-equivs f (f , f-involutive , f-involutive) involution-swap : {X : π€ Μ } (f : X β X) β involutive f β {x y : X} β f x οΌ y β f y οΌ x involution-swap f f-involutive {x} {y} e = f y οΌβ¨ ap f (e β»ΒΉ) β© f (f x) οΌβ¨ f-involutive x β© x β open import UF.Sets involution-swap-β : {X : π€ Μ } (f : X β X) β involutive f β is-set X β {x y : X} β (f x οΌ y) β (f y οΌ x) involution-swap-β f f-involutive X-is-set {x} {y} = qinveq (involution-swap f f-involutive {x} {y}) (involution-swap f f-involutive {y} {x}, I y x , I x y) where I : β a b β involution-swap f f-involutive {a} {b} β (involution-swap f f-involutive {b} {a}) βΌ id I a b e = X-is-set _ _ \end{code} End of addition. Associativities and precedences. \begin{code} infix 0 _β_ infix 0 _β _ infix 1 _β infixr 0 _ββ¨_β©_ infixr 0 _ββ¨reflβ©_ infixr 0 _ββ¨by-definitionβ©_ infixl 2 _β_ \end{code}