nLab equivalence in homotopy type theory

Equivalences in type theory

Context

Type theory

natural deduction metalanguage, practical foundations

  1. type formation rule
  2. term introduction rule
  3. term elimination rule
  4. computation rule

type theory (dependent, intensional, observational type theory, homotopy type theory)

syntax object language

computational trinitarianism =
propositions as types +programs as proofs +relation type theory/category theory

logicset theory (internal logic of)category theorytype theory
propositionsetobjecttype
predicatefamily of setsdisplay morphismdependent type
proofelementgeneralized elementterm/program
cut rulecomposition of classifying morphisms / pullback of display mapssubstitution
cut elimination for implicationcounit for hom-tensor adjunctionbeta reduction
introduction rule for implicationunit for hom-tensor adjunctioneta conversion
truesingletonterminal object/(-2)-truncated objecth-level 0-type/unit type
falseempty setinitial objectempty type
proposition, truth valuesubsingletonsubterminal object/(-1)-truncated objecth-proposition, mere proposition
logical conjunctioncartesian productproductproduct type
disjunctiondisjoint union (support of)coproduct ((-1)-truncation of)sum type (bracket type of)
implicationfunction setinternal homfunction type
negationfunction set into empty setinternal hom into initial objectfunction type into empty type
universal quantificationindexed cartesian productdependent productdependent product type
existential quantificationindexed disjoint union (support of)dependent sum ((-1)-truncation of)dependent sum type (bracket type of)
logical equivalencebijectionisomorphism/adjoint equivalenceequivalence of types
support setsupport object/(-1)-truncationpropositional truncation/bracket type
n-image of morphism into terminal object/n-truncationn-truncation modality
equalitydiagonal function/diagonal subset/diagonal relationpath space objectidentity type/path type
completely presented setsetdiscrete object/0-truncated objecth-level 2-type/set/h-set
setset with equivalence relationinternal 0-groupoidBishop set/setoid with its pseudo-equivalence relation an actual equivalence relation
equivalence class/quotient setquotientquotient type
inductioncolimitinductive type, W-type, M-type
higher inductionhigher colimithigher inductive type
-0-truncated higher colimitquotient inductive type
coinductionlimitcoinductive type
presettype without identity types
set of truth valuessubobject classifiertype of propositions
domain of discourseuniverseobject classifiertype universe
modalityclosure operator, (idempotent) monadmodal type theory, monad (in computer science)
linear logic(symmetric, closed) monoidal categorylinear type theory/quantum computation
proof netstring diagramquantum circuit
(absence of) contraction rule(absence of) diagonalno-cloning theorem
synthetic mathematicsdomain specific embedded programming language

homotopy levels

semantics

Equality and Equivalence

Equivalences in type theory

Idea

In homotopy type theory, the notion of equivalence is an internalization of the notion of equivalence or homotopy equivalence.

These are sometimes called weak equivalences, but there is nothing weak about them (in particular, they always have homotopy inverses).

Definition

We work in intensional type theory with dependent sums, dependent products, and identity types.

Definition

For f:ABf\colon A\to B a term of function type; we define new dependent types as follows:

the homotopy fiber type

f:AB,b:Bhfiber(f,b) a:A(f(a)=b) f \colon A \to B, b\colon B \vdash hfiber(f,b) \coloneqq \sum_{a\colon A} (f(a) = b)

and the proposition that the homotopy fiber type is a (dependently) contractible type:

f:ABisEquiv(f) b:BisContr(hfiber(f,b)). f \colon A \to B \vdash isEquiv(f) \coloneqq \prod_{b\colon B} isContr(hfiber(f,b)) \,.

We say ff is an equivalence if isEquiv(f)isEquiv(f) is an inhabited type.

That is, a function is an equivalence if all of its homotopy fiber types are contractible types (in a way which depends continuously on the base point).

Definition

For X,Y:TypeX, Y : Type two types, the type of equivalences from XX to YY is the dependent sum

Equiv(X,Y)=(XY) f:(XY)isEquiv(f). Equiv(X,Y) = (X \stackrel{\simeq}{\to}Y) \coloneqq \sum_{f : (X \to Y)} isEquiv(f) \,.

Three variations of this definition are, informally:

  • f:ABf\colon A\to B is an equivalence if there is a map g:BAg\colon B\to A and homotopies p: a:A(g(f(a))=a)p\colon \prod_{a\colon A} (g(f(a)) = a) and q: b:B(f(g(b))=b)q\colon \prod_{b\colon B} (f(g(b)) = b) (a homotopy equivalence)

  • f:ABf\colon A\to B is an equivalence if there is the above data, together with a higher homotopy expressing one triangle identity for ff and gg (an adjoint equivalence).

  • f:ABf\colon A\to B is an equivalence if there are maps g,h:BAg,h\colon B\to A and homotopies p: a:A(g(f(a))=a)p\colon \prod_{a\colon A} (g(f(a)) = a) and q: b:B(f(h(b))=b)q\colon \prod_{b\colon B} (f(h(b)) = b) (sometimes called a homotopy isomorphism).

By formalizing these, we obtain types homotopyEquiv(f)homotopyEquiv(f), isAdjointEquiv(f)isAdjointEquiv(f), and isHIso(f)isHIso(f). All four of these types are co-inhabited: we have a function from any one of them to any of the others. Moreover, at least if we assume function extensionality, the types isAdjointEquiv(f)isAdjointEquiv(f) and isHIso(f)isHIso(f) are themselves equivalent to isEquiv(f)isEquiv(f), and all three are h-propositions.

This is not true for homotopyEquiv(f)homotopyEquiv(f), which is not in general an h-prop even with function extensionality. However, often the most convenient way to show that ff is an equivalence is by exhibiting a term in homotopyEquiv(f)homotopyEquiv(f) (although such a term could just as well be interpreted to lie in isHIso(f)isHIso(f) with hgh\coloneqq g).

As one-to-one correspondences

Let 𝒰\mathcal{U} be a universe and A:𝒰A:\mathcal{U} and B:𝒰B:\mathcal{U} be terms of the universe, and R:A×B𝒰R :A \times B \to \mathcal{U} be a correspondence between AA and BB. We define the property of RR being one-to-one as follows:

isOneToOne(R)( a:AisContr( b:BR(a,b)))×( b:BisContr( a:AR(a,b)))isOneToOne(R) \coloneqq \left(\prod_{a:A} \mathrm{isContr}\left(\sum_{b:B} R(a,b)\right)\right) \times \left(\prod_{b:B} \mathrm{isContr}\left(\sum_{a:A} R(a,b)\right)\right)

We define the type of equivalences from AA to BB in 𝒰\mathcal{U} as

(A 𝒰B) R:(A×B)𝒰isOneToOne(R)(A \simeq_\mathcal{U} B) \equiv \sum_{R : (A \times B) \to \mathcal{U}} isOneToOne(R)

Rules for isEquiv

In any dependent type theory with identity types, function types, fiber types, and isContr defined either through isProp or contraction types, all of which could be defined without dependent product types or dependent sum types, we can still define isEquiv by adding the formation, introduction, elimination, computation, and uniqueness rules for isEquiv

Formation rules for isEquiv types:

ΓAtypeΓBtypeΓ,f:AB,y:BisContr(fiber A,B(f,y))typeΓisEquiv A,B(f)type\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash B \; \mathrm{type} \quad \Gamma, f:A \to B, y:B \vdash \mathrm{isContr}(\mathrm{fiber}_{A, B}(f, y)) \; \mathrm{type}}{\Gamma \vdash \mathrm{isEquiv}_{A, B}(f) \; \mathrm{type}}

Introduction rules for isEquiv types:

ΓAtypeΓBtypeΓ,f:AB,y:Bb(y):isContr(fiber A,B(f,y))Γ,f:ABλx.b(x):isEquiv A,B(f)\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash B \; \mathrm{type} \quad \Gamma, f:A \to B, y:B \vdash b(y):\mathrm{isContr}(\mathrm{fiber}_{A, B}(f, y))}{\Gamma, f:A \to B \vdash \lambda x.b(x):\mathrm{isEquiv}_{A, B}(f)}

Elimination rules for isEquiv types:

Γ,f:ABp:isEquiv A,B(f)Γc:BΓ,f:ABp(a):isEquiv A,B(f)(c)\frac{\Gamma, f:A \to B \vdash p:\mathrm{isEquiv}_{A, B}(f) \quad \Gamma \vdash c:B}{\Gamma, f:A \to B \vdash p(a):\mathrm{isEquiv}_{A, B}(f)(c)}

Computation rules for isEquiv types:

Γ,f:AB,y:Bb(y):isContr(fiber A,B(f,y))Γc:BΓ,f:ABβ isEquiv:λx.b(x)(c)= isContr(fiber A,B(f,c))b(c)\frac{\Gamma, f:A \to B, y:B \vdash b(y):\mathrm{isContr}(\mathrm{fiber}_{A, B}(f, y)) \quad \Gamma \vdash c:B}{\Gamma, f:A \to B \vdash \beta_\mathrm{isEquiv}:\lambda x.b(x)(c) =_{\mathrm{isContr}(\mathrm{fiber}_{A, B}(f, c))} b(c)}

Uniqueness rules for isEquiv types:

Γ,f:ABp:isEquiv A,B(f)Γ,f:ABη isEquiv:p= isEquiv A,B(f)λ(x).p(x)\frac{\Gamma, f:A \to B \vdash p:\mathrm{isEquiv}_{A, B}(f)}{\Gamma, f:A \to B \vdash \eta_\mathrm{isEquiv}:p =_{\mathrm{isEquiv}_{A, B}(f)} \lambda(x).p(x)}

Rules for equivalence types

We work in a dependent type theory with identity types, function types, and some set of rules for isEquiv defined above which does not require dependent product types or dependent sum types. The type of equivalences ABA \simeq B is given by the following rules:

Formation rules for equivalence types:

ΓAtypeΓBtypeΓ,f:ABisEquiv(f)typeΓABtype\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash B \; \mathrm{type} \quad \Gamma, f:A \to B \vdash \mathrm{isEquiv}(f) \; \mathrm{type}}{\Gamma \vdash A \simeq B \; \mathrm{type}}

Introduction rules for equivalence types:

ΓAtypeΓBtypeΓ,f:ABp(f):isEquiv(f)Γg:ABΓp:isEquiv[g/f]Γ(g,p):AB\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash B \; \mathrm{type} \quad \Gamma, f:A \to B \vdash p(f):\mathrm{isEquiv}(f) \quad \Gamma \vdash g:A \to B \quad \Gamma \vdash p:\mathrm{isEquiv}[g/f]}{\Gamma \vdash (g, p):A \simeq B}

Elimination rules for equivalence types:

Γh:ABΓπ 1(h):ABΓh:ABΓπ 2(h):isEquiv(π 1(h))\frac{\Gamma \vdash h:A \simeq B}{\Gamma \vdash \pi_1(h):A \to B} \qquad \frac{\Gamma \vdash h:A \simeq B}{\Gamma \vdash \pi_2(h):\mathrm{isEquiv}(\pi_1(h))}

Computation rules for equivalence types:

Γ,f:ABp(f):isEquiv(f)Γg:ABΓβ 1:π 1(g,p)= ABgΓ,f:ABp:isEquivΓg:ABΓβ 2:π 2(g,p)= isEquiv(π 1(g,p))p\frac{\Gamma, f:A \to B \vdash p(f):\mathrm{isEquiv}(f) \quad \Gamma \vdash g:A \to B}{\Gamma \vdash \beta_{\simeq 1}:\pi_1(g, p) =_{A \to B} g} \qquad \frac{\Gamma, f:A \to B \vdash p:\mathrm{isEquiv} \quad \Gamma \vdash g:A \to B}{\Gamma \vdash \beta_{\simeq 2}:\pi_2(g, p) =_{\mathrm{isEquiv}(\pi_1(g, p))} p}

Uniqueness rules for equivalence types:

Γh:ABΓη :h= AB(π 1(h),π 2(h))\frac{\Gamma \vdash h:A \simeq B}{\Gamma \vdash \eta_\simeq:h =_{A \simeq B} (\pi_1(h), \pi_2(h))}

Semantics

We discuss the categorical semantics of equivalences in homotopy type theory.

Let 𝒞\mathcal{C} be a locally cartesian closed category which is a model category, in which the (acyclic cofibration, fibration) weak factorization system has stable path objects, and acyclic cofibrations are preserved by pullback along fibrations between fibrant objects. (We ignore questions of coherence, which are not important for this discussion.) For instance 𝒞\mathcal{C} could be a type-theoretic model category.

Of isEquiv()isEquiv(-)

Proposition

For A,BA, B two cofibrant-fibrant objects in 𝒞\mathcal{C}, a morphism f:ABf\colon A\to B is a weak equivalence or equivalently a homotopy equivalence in 𝒞\mathcal{C} precisely when the interpretation of isEquiv(f)isEquiv(f) has a global point *isEquiv(f)* \to isEquiv(f).

Proof

For f:ABf\colon A\to B, the categorical semantics of the dependent type

b:Bhfiber(f,b):Type b\colon B \;\vdash\; hfiber(f,b)\colon Type

is by the rules for the interpretation of identity types and substitution the mapping path space construction PfP f, given by the pullback

[b:Bhfiber(f,b)] Pf A f B I B B \array{ [b : B \vdash hfiber(f,b)] &\coloneqq & P f &\to& A \\ && \downarrow && \downarrow^{\mathrlap{f}} \\ && B^I &\to& B \\ && \downarrow \\ && B }

which, by the factorization lemma, is one way to factor ff as an acyclic cofibration followed by a fibration

f:APfB. f : A \stackrel{\simeq}{\to} P f \to B \,.

By definition and the semantics of contractible types, therefore, if AA and BB are cofibrant, then isEquiv(f)isEquiv(f) has a global element

* bisContr(hfiber(f,b)) * \to \prod_{b} isContr(hfiber(f,b))

precisely when in this factorization, the fibration PfBP f \to B is an acyclic fibration. (See for instance (Shulman, page 49) for more details.)

But by the 2-out-of-3 property, this is equivalent to ff being a weak equivalence — and hence a homotopy equivalence, since it is a map between fibrant-cofibrant objects.

Remark

In the above we fixed one function f:AXf : A \to X. But the type isEquivisEquiv is actually a dependent type

f:ABisEquiv(f) f : A \to B \vdash isEquiv(f)

on the type of all functions. To obtain the categorical semantics of this general dependent isEquivisEquiv-construction, first notice that the interpretation of

f:AB,a:A,b:B(f(a)=b):Typef : A \to B,\; a : A,\; b : B \;\vdash\; (f(a) = b) \colon Type

is by the rules for interpretation of identity types, evaluation and substitution the left vertical morphism in the pullback diagram

Q B I [A,B]×A×B (eval,id B) B×B, \array{ Q &\to& B^I \\ \downarrow && \downarrow \\ [A,B] \times A \times B &\stackrel{(eval, id_B)}{\to}& B \times B } \,,

where eval:[A,B]×ABeval : [A, B] \times A \to B is the evaluation map for the internal hom. This means that the interpretation of further dependent sum yielding hfibhfib

f:AB,b:B( a:A(f(a)=b)):Type f : A \to B,\; b : B \; \vdash \; \left( \sum_{a : A } (f(a) = b) \right) \colon Type

is the composite left vertical morphism in

Q B I [A,B]×A×B (eval,id B) B×B p 1,3 [A,B]×B \array{ Q &\to& B^I \\ \downarrow && \downarrow \\ [A,B] \times A \times B &\stackrel{(eval, id_B)}{\to}& B \times B \\ \downarrow^{\mathrlap{p_{1,3}}} \\ [A,B] \times B }

Of Equiv()Equiv(-)

(…)

References

An introduction to equivalence in homotopy type theory is in

and basic ideas are also indicated from slide 60 of part 2, slide 49 of part 3 of

Coq code for homotopy equivalences is at

For equivalences as one-to-one correspondences in homotopy type theory, see

  • Mike Shulman, Towards a Third-Generation HOTT Part 1 (slides, video)

Last revised on October 12, 2022 at 23:55:39. See the history of this page for a list of all contributions to it.