nLab univalence axiom

Contents

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

Universes

Homotopy theory

homotopy theory, (∞,1)-category theory, homotopy type theory

flavors: stable, equivariant, rational, p-adic, proper, geometric, cohesive, directed

models: topological, simplicial, localic, …

see also algebraic topology

Introductions

Definitions

Paths and cylinders

Homotopy groups

Basic facts

Theorems

Contents

Idea

In intensional type theory, identity types behave like path space objects; this viewpoint is called homotopy type theory. This induces furthermore a notion of homotopy fibers, hence of homotopy equivalences between types.

On the other hand, if type theory contains a universe Type, so that types can be considered as points of TypeType, then between two types we also have an identity type Paths Type(X,Y)Paths_{Type}(X,Y). The univalence axiom says that these two notions of “sameness” for types are the same.

Extensionality principles like function extensionality, propositional extensionality (where XX and YY are h-propositions, and univalence (“typal extensionality”) are naturally regarded as a stronger form of identity of indiscernibles. In particular, the consistency of univalence means that in Martin-Löf type theory without univalence, one cannot define any predicate that provably distinguishes isomorphic types; thus isomorphic types are “externally indiscernible”, and univalence incarnates that principle internally by making them identical.

The name univalence (due to Voevodsky) comes from the following reasoning. A fibration or bundle p:EBp\colon E\to B of some sort is commonly said to be universal if every other bundle of the same sort is a pullback of pp in a unique way (up to homotopy). Less commonly, a bundle is said to be versal if every other bundle is a pullback of it in some way, not necessarily unique. By contrast, a bundle is said to be univalent if every other bundle is a pullback of it in at most one way (up to homotopy). In the language of (∞,1)-category theory, a univalent bundle is an object classifier.

The univalence axiom does not literally say that anything is univalent in this sense. However, it is equivalent to saying that the canonical fibration over TypeType is univalent: every fibration with small fibers is an essentially unique pullback of this one (while those with large fibers are not, they are pullbacks of the next higher Type 1Type_1). For a description of this equivalence, see section 4.8 of the HoTT Book (syntactically) and Gepner-Kock (semantically).

Univalence is a commonly assumed axiom in homotopy type theory, and is central to the proposal (Voevodsky) that this provides a natively homotopy theoretic foundation of mathematics (see at univalent foundations for mathematics).

Definition

We work in a dependent type theory with identity types, function types, dependent product types, product types, and dependent sum types.

While traditionally in dependent type theory, Russell universes UU are considered to be distinct from Tarski universes (U,T)(U, T), in this article, we define a Russell universe to be a Tarski universe (U,)(U, \!\,) whose type reflector type family is represented by a zero-width whitespace character \!\, instead of some other symbol TT. Thus, we can use the more general notion of Tarski universe throughout the article.

Given a universe UU, there are multiple notions of equivalence of UU-small types which can be used in the definition of univalence, such as functions with contractible fibers and one-to-one correspondences.

Using functions with contractible fibers

In any dependent type theory, given types AA and BB and a function f:ABf:A \to B, ff is an equivalence if for all b:Bb:B, the fiber of ff at bb is contractible:

isEquiv(f) b:BisContr( a:Af(a)= Bb)\mathrm{isEquiv}(f) \coloneqq \prod_{b:B} \mathrm{isContr}\left(\sum_{a:A} f(a) =_B b\right)

Now, let (U,T)(U, T) is a Tarski universe. The univalence axiom states that the transport function trans T(A,B)\mathrm{trans}^T(A, B), defined by identification elimination which take the reflexive identification refl U(A):A= UA\mathrm{refl}_U(A):A =_U A to the identity equivalence id T(A):T(A)T(A)\mathrm{id}_{T(A)}:T(A) \simeq T(A), is an equivalence of types for all A:UA:U and B:UB:U

trans T(A,B):(A= UB)(T(A)T(B))\mathrm{trans}^T(A, B):(A =_U B) \simeq (T(A) \simeq T(B))

If (U,)(U, \!\,) is a Russell universe, transport across the zero-width whitespace character type family \!\, is typically written as idtoequiv(A,B)\mathrm{idtoequiv}(A, B):

idtoequiv(A,B)trans (A,B)\mathrm{idtoequiv}(A, B) \coloneqq \mathrm{trans}^{\!\,}(A, B)

Using one-to-one correspondences

In any dependent type theory with a Tarski universe (U,T)(U, T), we define a correspondence R:T(A)×T(B)UR:T(A) \times T(B) \to U to be a one-to-one correspondence as:

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

and we define the type of one-to-one correspondences from AA to BB in UU as

A UB R:T(A)×T(B)UisOneToOne(R)A \simeq_U B \coloneqq \sum_{R:T(A) \times T(B) \to U} isOneToOne(R)

A universe UU is univalent if for all A:UA:U and B:UB:U, the canonical map

idtoequiv U(A,B):(A= UB)(A UB)\mathrm{idtoequiv}_U(A, B):(A =_U B) \to (A \simeq_U B)

from the identity type A= UBA =_U B to the type of one-to-one correspondences A UBA \simeq_U B, defined by identification elimination which take the reflexive identification refl U(X):X= UX\mathrm{refl}_U(X):X =_U X to the identity one-to-one correspondence Δ X:XX\Delta_X:X \simeq X, is an equivalence of types

idtoequiv U(A,B):(A= UB)(A UB)\mathrm{idtoequiv}_U(A, B):(A =_U B) \simeq (A \simeq_U B)

Alternate versions of univalence

In this section, we abbreviate each of the above notions of equivalence (A UBA \simeq_U B or T(A)T(B)T(A) \simeq T(B)) as ABA \simeq B.

Weaker equivalent versions

The univalence axiom proper says that the canonical map coe:(X=Y)(XY)coe:(X=Y)\to (X\simeq Y) is an equivalence. However, there are several seemingly-weaker (and therefore often easier to verify) statements that are equivalent to this, such as:

  1. For any type XX, the type Y:U(XY)\sum_{Y:U} (X\simeq Y) is contractible. This follows since then the map on total spaces from Y:U(X=Y)\sum_{Y:U} (X=Y) to Y:U(XY)\sum_{Y:U} (X\simeq Y) induced by coecoe is an equivalence, hence a fiberwise equivalence (X=Y)(XY)(X=Y) \simeq (X\simeq Y).

  2. For any X,Y:UX,Y:U we have a map ua:(XY)(X=Y)ua:(X\simeq Y) \to (X=Y) such that coe(ua(f))=fcoe(ua(f)) = f. This exhibits XYX\simeq Y as a retract of X=YX=Y, hence Y:U(XY)\sum_{Y:U} (X\simeq Y) as a retract of the contractible type Y:U(X=Y)\sum_{Y:U} (X=Y), so it is contractible. This was observed by Dan Licata.

  3. Ian Orton and Andrew Pitts showed here that assuming function extensionality, this can be further simplified to the following special cases:

    • unit:A= a:A1unit : A = \sum_{a:A} 1
    • flip:( a:A b:BC(a,b))=( b:B a:AC(a,b))flip : (\sum_{a:A} \sum_{b:B} C(a,b)) = (\sum_{b:B} \sum_{a:A} C(a,b))
    • contract:IsContr(A)(A=1)contract: IsContr(A) \to (A=1)
    • unit β:coe(unit(a))=(a,)unit_\beta : coe(unit(a)) = (a,\star)
    • flip β:coe(flip(a,b,c))=(b,a,c)flip_\beta : coe(flip(a,b,c)) = (b,a,c).

    The proof constructs ua(f):A=Bua(f): A=B (for f:ABf:A\simeq B) as the composite

    A=unit a:A1=contract a:A b:Bfa=b=flip b:B a:Afa=b=contract b:B1=unitB A \overset{unit}{=} \sum_{a:A} 1 \overset{contract}{=} \sum_{a:A} \sum_{b:B} f a=b \overset{flip}{=} \sum_{b:B} \sum_{a:A} f a = b \overset{contract}{=} \sum_{b:B} 1 \overset{unit}{=} B

    and uses unit βunit_\beta and flip βflip_\beta to compute that coe(ua(f))(a)=f(a)coe(ua(f))(a) = f(a), hence by function extensionality coe(ua(f))=fcoe(ua(f)) = f.

Stricter versions of univalence

There are also stricter versions of univalence, where we replace the equivalence of types between the identity type A= UBA =_U B and the type of equivalences of the universe ABA \simeq B in the univalence axioms with some notion of equality, such as judgmental equality, propositional equality, and typal equality.

  1. In any dependent type theory with judgmental equality, given a type universe UU, one could replace the equivalence of types in the definition of univalence with a judgmental equality of types. This results in judgmental univalence, which states that for all small types A:UA:U and B:UB:U, one could judge that (A= UB)(AB)type(A =_U B) \equiv (A \simeq B) \; \mathrm{type}.

  2. Similarly, in the context of any logic over type theory with propositional equality, given a type universe UU, one could replace the equivalence of types in the definition of univalence with a propositional equality of types. This results in propositional univalence, which states that for all small types A:UA:U and B:UB:U, (A= UB)(AB)true(A =_U B) \equiv (A \simeq B) \; \mathrm{true}.

  3. Finally, if we are working inside a Tarski universe (𝒱,𝒯)(\mathcal{V}, \mathcal{T}), then given an internal Tarski universe U:𝒱U:\mathcal{V} with T:𝒯(U)𝒱T:\mathcal{T}(U) \to \mathcal{V}, one could replace the equivalence of types in the definition of univalence with a typal equality of types. This results in typal univalence, which states that for all small types A:𝒯(U)A:\mathcal{T}(U) and B:𝒯(U)B:\mathcal{T}(U), there is an identification ua(A,B):(T(A)= UT(B))= 𝒱(T(A) 𝒱T(B))\mathrm{ua}(A, B):(T(A) =_U T(B)) =_{\mathcal{V}} (T(A) \simeq_{\mathcal{V}} T(B)).

Each of these imply the usual versions of univalence either through the structural rules for judgmental equality and propositional equality, or through identification elimination, transport, and action on identifications for typal equality.

Shulman univalence

We shall call these forms of univalence Shulman univalence because it first appeared in Mike Shulman‘s model of higher observational type theory.

Given a type universe UU, there is a canonical function

idtoequiv(A,B):(A= UB)(AB)\mathrm{idtoequiv}(A, B):(A =_U B) \to (A \simeq B)

for all A:UA:U and B:UB:U.

Suppose we are working in a dependent type theory with judgmental equality of terms \equiv. Then UU is judgmentally Shulman univalent if for all A:UA:U and B:UB:U there is a function ua(A,B):(AB)(A= UB)\mathrm{ua}(A, B):(A \simeq B) \to (A =_U B) such that for all equivalences R:ABR:A \simeq B, one could judge that idtoequiv(A,B)(ua(A,B)(R))R\mathrm{idtoequiv}(A, B)(\mathrm{ua}(A, B)(R)) \equiv R.

Now, suppose we are working in the framework of logic over type theory, where our dependent type theory has propositional equality of terms \equiv. Then UU is propositionally Shulman univalent if there is a function ua(A,B):(AB)(A= UB)\mathrm{ua}(A, B):(A \simeq B) \to (A =_U B) for all A:UA:U and B:UB:U such that for all equivalences R:ABR:A \simeq B, the proposition idtoequiv(A,B)(ua(A,B)(R))R\mathrm{idtoequiv}(A, B)(\mathrm{ua}(A, B)(R)) \equiv R is true.

Internal univalence

Suppose the Tarski universe UU has

  • internal identity types
    Id U: A:UT(A)×T(A)U\mathrm{Id}^U:\prod_{A:U} T(A) \times T(A) \to U
  • internal dependent product types
    Π U(x:()).()(x):(U× A:UT(A)U)U\Pi_U (x:(-)).(-)(x):\left(U \times \prod_{A:U} T(A) \to U\right) \to U
  • internal dependent sum types
    Σ U(x:()).()(x):(U× A:UT(A)U)U\Sigma_U (x:(-)).(-)(x):\left(U \times \prod_{A:U} T(A) \to U\right) \to U

We assume the weakest notion of Tarski universe, where the type reflection T(A)T(A) of each A:UA:U is only equivalent to the external type, since (judgmentally, propositionally, typally) strict Tarski universes are weakly Tarski universes, because the judgmental equality and propositional equality imply equivalence of types by the structural rules for judgmental and propostional equality, and typal equality in a type universe of types imply equivalence of types by identification elimination, transport, and action on identifications.

This allows us to define the internal type of equivalences A U inBA \simeq_U^\mathrm{in} B, internal to the universe UU, which comes with a canonical equivalence of types

canonical (A,B):T(A U inB)(T(A)T(B))\mathrm{canonical}_\simeq(A, B):T(A \simeq_U^\mathrm{in} B) \simeq (T(A) \simeq T(B))

This implies that the equivalence T(A)T(B)T(A) \simeq T(B) is UU-small, and transport being an equivalence then implies that in any universe UU which is closed under function types, dependent product types, and dependent sum types, for all A:UA:U and B:UB:U, the identity type A= UBA =_U B is UU-small.

The internal univalence axiom states that the canonical function

idtointernalequiv(A,B):(A= UB)T(A U inB)\mathrm{idtointernalequiv}(A, B):(A =_U B) \to T(A \simeq_U^\mathrm{in} B)

is an equivalence of types

idtoequiv(A,B):(A= UB)T(A U inB)\mathrm{idtoequiv}(A, B):(A =_U B) \simeq T(A \simeq_U^\mathrm{in} B)

This is not definable for strongly predicative type universes, since strongly predicative type universes are by definition not closed under dependent product types.

In addition, the internal and external versions of univalence imply each other. In order to show that the two axioms imply each other, we need to show that there is an identification

i(p):canonical (A,B)(idtoequiv(A,B)(p))= T(A)T(B)trans T(A,B)(p)i(p):\mathrm{canonical}_\simeq(A, B)(\mathrm{idtoequiv}(A, B)(p)) =_{T(A) \simeq T(B)} \mathrm{trans}^{T}(A, B)(p)

for all identifications p:A= UBp:A =_U B. By the J rule it is enough to show that canonical (A,A)\mathrm{canonical}_\simeq(A, A) maps the identity equivalence of T(A U inA)T(A \simeq_U^\mathrm{in} A) to the identity equivalence in T(A)T(A)T(A) \simeq T(A). Since the identity equivalence in T(A U inA)T(A \simeq_U^\mathrm{in} A) is just the identity function canonical 1(A,A)(λx.x)\mathrm{canonical}_\simeq^{-1}(A, A)(\lambda x.x) the above statement is always true. Thus, if the universe is closed under identity types, dependent product types, and dependent sum types the two univalence axioms imply each other and both define the same notion of univalent universe.

In categorical semantics

Let 𝒞\mathcal{C} be a locally cartesian closed model category in which all objects are cofibrant.

By the categorical semantics of homotopy type theory, a dependent type

b:BE(b):Type b : B \vdash E(b) : Type

corresponds to a morphism EBE \to B in 𝒞\mathcal{C} that is a fibration between fibrant objects.

Then the dependent function type

b 1,b 2:B(E(b 1)E(b 2)):Type b_1, b_2 : B \vdash ( E(b_1) \to E(b_2)) : Type

is interpreted as the internal hom [,] 𝒞/ B×B[-,-]_{\mathcal{C}/_{B \times B}} in the slice category 𝒞/ B×B\mathcal{C}/_{B \times B} after extending EE to the context B×BB \times B by pulling back along the two projections p 1,p 2:B×BBp_1, p_2 : B \times B \to B, respectively. Hence this is interpreted as

[p 1 *E,p 2 *E] 𝒞/ B×B[E×B,B×E] 𝒞/ B×B𝒞/ B×B. [p_1^* E \, , \, p_2^* E]_{\mathcal{C}/_{B \times B}} \simeq [E \times B \, , \, B \times E]_{\mathcal{C}/_{B \times B}} \in \mathcal{C}/_{B \times B} \,.

Consider then the diagonal morphism Δ B:BB×B\Delta_B : B \to B \times B in 𝒞\mathcal{C} as an object of 𝒞/ B×B\mathcal{C}/_{B \times B}. We would like to define a morphism

q:Δ B[E×B,B×E] 𝒞/ B×B. q \colon \Delta_B \to [E \times B , B \times E]_{\mathcal{C}/_{B \times B}} \,.

in 𝒞/ B×B\mathcal{C}/_{B \times B}. By the defining (product \dashv internal hom)-adjunction, it suffices to define a morphism

Δ B× 𝒞/ B×BE×BB×E \Delta_B \times_{\mathcal{C}/_{B \times B}} E \times B \to B \times E

in 𝒞/ B×B\mathcal{C}/_{B \times B}. But now by the universal property of pullback, it suffices to define just in 𝒞 /B\mathcal{C}_{/B} a morphism

Δ B× 𝒞/ B×BE×BΔ B× 𝒞/ B×BB×E. \Delta_B \times_{\mathcal{C}/_{B \times B}} E \times B \to \Delta_B \times_{\mathcal{C}/_{B \times B}} B \times E\,.

And since the composite pullback along either composite

BΔ BB×Bπ 1B B \xrightarrow{\Delta_B} B\times B \xrightarrow{\pi_1} B
BΔ BB×Bπ 2B B \xrightarrow{\Delta_B} B\times B \xrightarrow{\pi_2} B

is the identity, both Δ B× 𝒞/ B×BE×B\Delta_B \times_{\mathcal{C}/_{B \times B}} E \times B and Δ B× 𝒞/ B×BB×E\Delta_B \times_{\mathcal{C}/_{B \times B}} B \times E are isomorphic to EE; thus here we can take the identity morphism.

Now, using the path object factorization in 𝒞\mathcal{C}

B B I Δ B B×B \array{ B &&\stackrel{\simeq}{\hookrightarrow}&& B^I \\ & {}_{\mathllap{\Delta_B}}\searrow && \swarrow_{\mathrlap{}} \\ && B \times B }

by an acyclic cofibration followed by a fibration, we obtain a fibrant replacement of Δ B\Delta_B in the slice model category 𝒞 B×B\mathcal{C}_{B \times B}.

Since also [E×B,B×E] 𝒞/ B×B[E \times B, B \times E]_{\mathcal{C}/_{B \times B}} is fibrant by the axioms on the locally cartesian closed model category 𝒞\mathcal{C}, we have a lift q^\hat q in the diagram in 𝒞/ B×B\mathcal{C}/_{B \times B}

B q [E×B,B×E] 𝒞/ B×B q^ B I B×B=* 𝒞/ B×B. \array{ B &\stackrel{q}{\to}& [E \times B, B \times E]_{\mathcal{C}/_{B \times B}} \\ \downarrow &{}^{\mathllap{\hat q}}\nearrow& \downarrow \\ B^I &\to& B \times B = *_{\mathcal{C}/_{B \times B}} } \,.

This lift is the interpretation of the path induction that deduces a map on all paths γB I\gamma \in B^I from one on just the identity paths id bBB Iid_b \in B \hookrightarrow B^I.

Finally, let Eq(E)[E×B,B×E] 𝒞/ B×BEq(E) \hookrightarrow [E \times B , B \times E]_{\mathcal{C}/_{B \times B}} be the subobject on the weak equivalences (…), and observe that qq and q^\hat q factor through this to give a morphism

q^:B IEq(E). \hat q : B^I \to Eq(E) \,.

The fibration EBE \to B is univalent in 𝒞\mathcal{C} if this morphism is a weak equivalence. By the 2-out-of-3 property, of course, it is equivalent to ask that q:BEq(E)q\colon B\to Eq(E) be a weak equivalence.

(…)

In simplicial sets

We specialize the general discussion above to the realization in 𝒞=\mathcal{C} = sSet, equipped with the standard model structure on simplicial sets.

For EBE \to B any fibration (Kan fibration) between fibrant objects (Kan complexes), consider first the simplicial set

[E×B,B×E] B×BsSet/ B×B [E \times B , B \times E]_{B \times B} \in sSet/_{B \times B}

defined as the internal hom in the slice category sSet/ B×BsSet/_{B \times B}.

Notice that the vertices of this simplicial set over a fixed pair (b 1,b 2):*B×B(b_1, b_2) : * \to B \times B of vertices in BB form the set of morphisms E b 1E b 2E_{b_1} \to E_{b_2} between the fibers in sSetsSet.

This is because – by the defining property of the internal hom in the slice and using that products in sSet/ B×BsSet/_{B \times B} are pullbacks in sSetsSet – the horizontal morphisms of simplcial sets in

* [E×B,B×E] B×B (b 1,b 2) B×B \array{ * &&\to&& [E \times B, B \times E]_{B \times B} \\ & {}_{\mathllap{(b_1,b_2)}}\searrow && \swarrow \\ && B \times B }

correspond bijectively to the horizontal morphisms in

E b 1×{b 2} {b 1}×E b 2 B×B \array{ E_{b_1} \times \{b_2\} &&\to&& \{b_1\} \times E_{b_2} \\ & \searrow && \swarrow \\ && B \times B }

in sSetsSet, which are precisely morphisms E b 1E b 2E_{b_1} \to E_{b_2}.

Let then

Eq(E)[E×B,B×E] B×BsSet/ B×B Eq(E) \hookrightarrow [E \times B, B \times E]_{B \times B} \in sSet/_{B \times B}

be the full sub-simplicial set on those vertices that correspond to weak equivalences ((weak) homotopy equivalences).

By a similar consideration, one sees that the diagonal morphism Δ B:BB×B\Delta_B : B \to B \times B in sSetsSet, regarded as an object BsSet/ B×BB \in sSet/_{B \times B}, comes with a canonical morphism

BEq(E). B \to Eq(E) \,.

The fibration EBE \to B is univalent, precisely when this morphism is a weak equivalence.

This appears originally as Voevodsky, def. 3.4

In simplicial presheaves

(…)

See (Shulman 12, UF 13)

(…)

Properties

Relation to function extensionality

The univalence axiom implies function extensionality.

A commented version of a formal proof of this fact can be found in (Bauer-Lumsdaine).

Univalence and axiom K

In this section we assume that the universe is a Tarski universe. Axiom K states that for all A:UA:U the type T(A)T(A) is a set. This means the type reflection of the internal equivalences T(A UB)T(A \simeq_U B) is an h-set, and the univalence axiom then implies that UU is an h-groupoid.

It is frequently stated that the univalence axiom and axiom K are inconsistent with each other. However, this is only true if the Tarski universe UU has internal univalent Tarski universes V:UV:U where the type T(V)T(V) has terms A:T(V)A:T(V) such that T V(A)T_V(A) is an h-set which is not an h-proposition, such as the booleans type. As a result, T(V)T(V) can be proven to not be a set, causing axiom K for UU to be inconsistent with the existence of V:UV:U and univalence.

Canonicity and homotopy canonicity

It is currently open whether the univalence axiom enjoys canonicity in general, but for the special case of 1-truncated homotopy types (groupoids) (and two nested univalent universes and function extensionality), homotopy canonicity has been shown in (Shulman 12, section 13. Thus, in univalent homotopy 1-type theory with two universes, every term of type of the natural numbers is propositionally equal to a numeral.

The construction in (Shulman 12, section 13) uses Artin gluing of a suitable type-theoretic fibration category with the category Set and Grpd, respectively, effectively inducing canonicity from these categories. By (Shulman 12, remark 13.13) for this construction to generalize to untruncated univalent type theory, one seems to need a sufficiently strict global sections functor with values in some model for infinity-groupoids. A proof of the full result has been announced by Christian Sattler and Krzysztof Kapulkin (Sattler 19).

Notice that this sort of canonicity does not yet imply computational effectiveness?, which would require also an algorithm to extract that numeral from the given term. There may be such an algorithm, but so far attempts to extract one from the proof (or to give a constructive version of the proof, which would imply the existence of an algorithm) have not succeeded.

It is also a propositional canonicity, as opposed to the judgmental canonicity which many traditional type theories enjoy. Another approach to canonicity for 1-truncated univalence can be found in (Harper-Licata), which involves modifying the type theory by adding more judgmental equalities, resulting in a judgmental canonicity. However, no algorithm for computing canonical forms has yet been given for this approach either.

Canonicity has been proved for cubical type theory.

One might also try to construct the Hoffman-Streicher groupoid model in a constructive framework; Awodey and Bauer have done some work in this direction with an impredicative universe of h-sets.

A univalent universe inside a non-univalent universe

In a post to the Homotopy Type Theory Google Group, Peter LeFanu Lumsdaine wrote:

Let (x 0:X)(x_0:X) be any pointed type, and (𝒰,El)(\mathcal{U}, El) be a universe (with rules as I set out a couple of emails ago). Then X×𝒰X \times \mathcal{U} is again a universe, admitting all the same constructors as 𝒰\mathcal{U}: take

El(x,A)=El(A)El(x,A) = El(A),
(x,A)+ 𝒰(y,B)=(x 0,A+ 𝒰B)(x,A) +_\mathcal{U} (y,B) = (x_0, A +_\mathcal{U} B),

and so on; that is, constructor operations on (X×𝒰)(X \times \mathcal{U}) are constantly x 0x_0 on the first component, and mirror those of 𝒰\mathcal{U} on the second component.

Now if 𝒰\mathcal{U} is univalent, and XX has non-trivial π 0\pi_0 (e.g. X=S 1X=S^1), then 𝒰(X×𝒰\mathcal{U} \rightarrow (X \times \mathcal{U}) gives a univalent universe sitting inside a non-univalent one (again, with the rules as I set out earlier).

Slightly more generally, given any cumulative pair of universes 𝒰 0𝒰 1\mathcal{U}_0 \rightarrow \mathcal{U}_1, we can consider 𝒰 0A×𝒰 1\mathcal{U}_0 \rightarrow A \times \mathcal{U}_1; this shows we can additionally have the smaller universe represented by an element of the larger one.

Mike Shulmanadded:

[N]ot only is X×𝒰X \times \mathcal{U} not univalent, it’s not even “univalent on the image of 𝒰\mathcal{U}”, as was the case for the example in the groupoid model that I mentioned.

References

The earliest occurrence of the univalence axiom is due to:

under the name “universe extensionality”. These authors formulate almost the modern univalence axiom; the only difference is the lack of a coherent definition of equivalence.

The univalence axiom has famously come to be attributed to Vladimir Voevodsky, though early documentation is hard to come by.

The first technical understanding of univalence in simplicial sets seems to be due to:

(which 6 years later came to be written up as Kapulkin, Lumsdaine & Voevodsky12 and another 10 years later was published as Kapulkin & Lumsdaine 2021).

The first mentioning by Voevodsky of the term “univalence” by email is 3.5 years later, from Dec. 30 2009 (according to Grayson, Oct. 2017).

The earliest accounts by Voevodsky’s hand date from 2010, but the un-iniated may have trouble recognizing the univalence axiom here:

Later in:

appears the claim that:

have been working on the ideas that led to the discovery of univalent models since 2005 and gave the first public presentation on this subject at Ludwig-Maximilians-Universität München in November 2009.

A clean and comprehensive discussion finally appears in the textbook:

Voevodsky’s (Bousfield’s) original idea for the universal Kan fibration as a model for a univalent universe in simplicial sets/ \infty -groupoids was eventually published as:

Exposition and survey:

An accessible account of Voevodsky’s proof (following Bousfield 06) that the universal Kan fibration in simplicial sets is univalent:

A quick elegant proof of the object classifier/universal associated infinity-bundle in simplicial sets/\infty-groupoids is in

See also

The HoTT-Coq code is at

A guided walk through the formal proof that univalence implies functional extensionality is at

Some details regarding the univalence axiom for weakly Tarski universes appeared on MathOverflow in:

  • Madeleine Birchfield, Valery Isaev, Univalence for weakly Tarski universes, MathOverflow, (web)

A discussion of univalence in categories of diagrams over an inverse category with values in a category for which univalence is already established is discussed in

This discusses canonicity of univalence in its section 13. Another approach to showing canonicity is (via cubical sets) in

A proof of canonicity is presented in the talk

On the issue of strict pullback of the univalent universe see

  • Univalent Foundations Mailing List, Quotients, March 2013

The computational interpretation of univalence / canonicity is discussed in

and realized in cubical type theory in

A study of the semantic side of univalence in (infinity,1)-toposes, as well as further cases of locally cartesian closed (infinity,1)-categories is in

This does not yet show that the univalence axiom in its usual form holds in the internal type theory of (infinity,1)-toposes, however, due to the lack of a (known) sufficiently strict model for the object classifier. (But it works with Tarski universes, see there and type universes). Constructions of such a model in some very special cases are in Shulman12 above, and also in

Finally, full proof that all ∞-stack (∞,1)-topos have presentations by model categories which interpret (provide categorical semantics) for homotopy type theory with univalent type universes:

For more references see homotopy type theory.

Last revised on November 21, 2022 at 01:07:43. See the history of this page for a list of all contributions to it.