Univalent categories and the Rezk completion

Benedikt Ahrens; Chris Kapulkin; Michael Shulman

Source-linked AI summary

Univalent categories and the Rezk completion

Benedikt Ahrens, Chris Kapulkin, Michael Shulman

arXiv:1303.0584v2Mar 4, 2013math.CTmath.LO

TL;DR

Category theory often treats isomorphic or equivalent structures as the same, a fit that traditional foundations do not capture well. The paper defines univalent categories and constructs a universal Rezk completion for any precategory; this completion is fully faithful and essentially surjective, and saturated categories identify equivalence with equality.

Problem
Traditional foundations do not capture category theory’s invariance under isomorphism and equivalence, a mismatch that becomes especially important in computer formalization.
Source: §1 · p. 1
Method
The paper defines saturated categories by identifying object identity with isomorphism and constructs a universal Rezk completion that takes any precategory to a saturated category.
Source: §1 · pp. 2–3
Results
The Rezk completion functor is fully faithful and essentially surjective, and saturated categories treat equivalent categories as equal.
Source: §1 · pp. 2–3
Takeaways & Limitations
In Univalent Foundations, saturated categories make category-theoretic constructions invariant under isomorphism of objects and equivalence of categories.
Source: §10 · p. 26
The constructed Rezk completion lies in the next higher universe than its input, though a higher-inductive-type construction can avoid this increase.
Source: §8 · p. 24

Abstract

from arXiv · show

We develop category theory within Univalent Foundations, which is a foundational system for mathematics based on a homotopical interpretation of dependent type theory. In this system, we propose a definition of "category" for which equality and equivalence of categories agree. Such categories satisfy a version of the Univalence Axiom, saying that the type of isomorphisms between any two objects is equivalent to the identity type between these objects; we call them "saturated" or "univalent" categories. Moreover, we show that any category is weakly equivalent to a univalent one in a universal way. In homotopical and higher-categorical semantics, this construction corresponds to a truncated version of the Rezk completion for Segal spaces, and also to the stack completion of a prestack.

1. Introduction

Category theory often treats isomorphism or equivalence, rather than equality, as sameness, which creates difficulties for equality-based foundations and formalization. The paper develops univalent categories and a universal construction that saturates precategories.

1. Introduction

Univalent Foundations addresses the mismatch between category theory’s weaker notions of sameness and traditional foundations, especially in computer formalization.The paper frames this as distinct from the size problems caused by naive category theory.Source: §1 · pp. 1–2
A saturated category identifies the identity type of two objects with their type of isomorphisms, making statements about objects invariant under isomorphism.The authors call such categories saturated or univalent and regard them as the appropriate notion of category in Univalent Foundations.Source: §1 · pp. 1–2
For saturated categories, equivalent categories are equal, and fully faithful, essentially surjective functors are equivalences without an axiom of choice.The corresponding statement remains equivalent to choice for strict categories and cannot be made true for precategories by adding an axiom of choice.Source: §1 · p. 2
Every precategory has a universal saturation: a saturated category bA equipped with a universal functor from the original precategory.The construction is called the Rezk completion and is also described as a stack completion in higher-topos semantics.Source: §1 · p. 3
The Rezk completion functor is fully faithful and essentially surjective, and saturation is characterized by recognizing all such functors as equivalences.This makes the notion of saturated category inherent in the notion of fully faithful and essentially surjective functor.Source: §1 · p. 3

Outline of the paper.

The paper verifies large parts of its theory, including the Rezk completion and its universal property, in Coq.The paper’s outline covers foundational definitions, category theory, the completion, and its formalization.Source: §1 · p. 3, Outline of the paper · pp. 3–4

2. Review of univalent foundations

The section recalls how Univalent Foundations interprets types and equality, and introduces operations and notions used in the paper. Its univalence axiom identifies equality of types with equivalence of types.

2. Review of univalent foundations

Identity types behave as paths: they support induction, transport, and composition, while function equality can be characterized pointwise.Function extensionality follows from the Univalence Axiom.Source: §2 · p. 4
Mere propositions have at most one element, sets have proposition-valued identity types, and n-types extend this hierarchy of truncation.The paper identifies sets as 0-types and mere propositions as (−1)-types.Source: §2 · pp. 4–5
An equivalence is defined through a quasi-inverse with a coherence condition, and the type asserting that a function is an equivalence is a mere proposition.In the formalization, equivalence is instead defined by contractible homotopy fibers.Source: §2 · p. 5
The Univalence Axiom says that the canonical map from equality of types to equivalence of types is an equivalence.The paper assumes all universes satisfy this axiom.Source: §2 · p. 5
Propositional truncation turns a type into a mere proposition while preserving its use in proofs of mere propositions.The formalization’s impredicative encoding depends on an impredicativity axiom and raises the universe level; a higher inductive type avoids both issues.Source: §2 · p. 5
In this paper, “merely exists” indicates propositional truncation and does not specify a particular witness.For sets, surjectivity uses mere existence, whereas split surjectivity requires a specified preimage; the two can differ without choice.Source: §2 · pp. 5–6

3. Categories and precategories

A precategory has a type of objects and set-valued hom-types, but its object equality can differ from isomorphism. The section defines categories by requiring these notions to agree.

3. Categories and precategories

A precategory has objects, set-valued hom-types, identities, composition, and the usual unit and associativity laws.The definition uses hom-types indexed by source and target objects.Source: §3 · p. 6
In a precategory, object equality and isomorphism are distinct notions of sameness, connected by a canonical map from equality to isomorphism.The map sends reflexivity to the identity morphism.Source: §3 · pp. 6–7
The Univalence Axiom makes Set a category and likewise makes precategories of set-level structures such as groups and rings categories.For Set, the equality-to-isomorphism map is the restriction of the identity-to-equivalence map.Source: §3 · p. 7
A category is a precategory for which the canonical map from object equality to isomorphism is an equivalence.Consequently, isomorphic objects are equal, and each object identity type is a set.Source: §3 · p. 7
A preorder is a precategory with proposition-valued hom-types, and it is a category precisely when its objects form a set and its relation is antisymmetric.Such a preorder is a partial order, or poset.Source: §3 · p. 8
The paper calls a precategory with a set of objects strict and says it will have little to say about strict categories.Source: §3 · p. 8

4. Functors and transformations

The section defines functors and natural transformations and develops their composition and equality. For functors between categories, natural isomorphism implies equality, and functor categories with category-valued codomain are categories.

4. Functors and transformations

A natural transformation consists of component morphisms satisfying a naturality equation, and its identity is determined by its components.Because hom-types are sets, natural transformations between fixed functors also form a set.Source: §4 · pp. 8–9
A natural transformation is an isomorphism exactly when each of its components is an isomorphism.The inverse transformation is assembled from the componentwise inverses.Source: §4 · p. 9
If the codomain B is a category, then the functor precategory B^A is a category.In particular, naturally isomorphic functors between categories are equal.Source: §4 · pp. 9–10
The two standard composites of a pair of natural transformations are equal, but the paper keeps them distinct because they are not definitionally equal.This choice lets the authors use one composition symbol unambiguously for natural transformations.Source: §4 · p. 10
Composition of functors is associative up to a coherent equality, rather than being definitionally associative.The associativity equality satisfies a commuting pentagon, and unit equalities satisfy a corresponding triangle.Source: §4 · p. 11

5. Adjunctions

The section defines adjunctions diagrammatically through a functor, unit and counit satisfying triangle identities. When the source is a category, being a left adjoint is a mere proposition, with uniqueness proved by identifying right adjoints and transporting the adjunction data.

5. Adjunctions

An adjunction is specified by a right adjoint, unit and counit natural transformations, and the two triangle identities.Source: §5 · p. 11
When A is a category, being a left adjoint is a mere proposition, even if B is only a precategory.Source: §5 · p. 11
Two adjunction structures yield naturally isomorphic right adjoints, which are identified as equal before their units and counits are shown to agree.Source: §5 · p. 12
The triangle identities transport automatically because hom-sets are sets, and the paper notes that §7 gives another proof of the uniqueness lemma.Source: §5 · p. 12

6. Equivalences

In Univalent Foundations, equivalences are formulated as adjoint equivalences, and their characterizations depend on whether the precategories involved are categories. For categories, weak equivalence, isomorphism, and equality coincide in ways that fail for general precategories.

6. Equivalences

In Univalent Foundations, defining equivalence via adjoint equivalences avoids the poorly behaved type produced by requiring an arbitrary quasi-inverse.The definition uses a left adjoint whose unit and counit are isomorphisms.Source: §6 · p. 12
A functor between precategories is an equivalence exactly when it is fully faithful and split essentially surjective.Split essential surjectivity specifies an object and isomorphism for each target object.Source: §6 · p. 13
For categories, equivalence and weak equivalence coincide: full faithfulness plus essential surjectivity suffices without specified witnesses.For fully faithful functors from a category, essential surjectivity is equivalent to split essential surjectivity.Source: §6 · p. 14
An isomorphism of precategories is always an equivalence, but the converse can fail for precategories.The functor from a chaotic precategory on X to the terminal precategory is an equivalence, but not an isomorphism unless X is contractible.Source: §6 · p. 17
For categories, a functor is an equivalence if and only if it is an isomorphism of categories.This relies on the category condition to turn natural isomorphisms into identities.Source: §6 · p. 17
For precategories, equality is equivalent to isomorphism; for categories, this also makes equality equivalent to equivalence.The authors describe this as a categorified saturation property.Source: §6 · p. 18
The type of categories is a 2-type, since equivalences between categories form a 1-type and therefore their identity types are 1-types.Source: §6 · p. 18

7. The Yoneda lemma

The section develops the Yoneda embedding for locally small precategories and proves the Yoneda lemma, which identifies natural transformations from a representable functor with elements of its value. The embedding is fully faithful, and in a category representations of a functor are unique.

7. The Yoneda lemma

For a locally small precategory, the hom-functor sends each pair (a, b) to the set homA(a, b).The section constructs opposites and products of precategories to define this Set-valued functor.Source: §7 · pp. 18–19
Natural transformations ya → F correspond to elements of F(a), naturally in both a and F.The section proves this isomorphism as the Yoneda lemma.Source: §7 · p. 19
The Yoneda embedding y : A → SetAop is fully faithful for any locally small precategory A.Its target need not be locally small unless A is small.Source: §7 · pp. 19–20
In a category, representability is a mere proposition, so any two representations of the same functor are equal.The section derives this from the Yoneda embedding being monic on objects.Source: §7 · p. 20

8. The Rezk completion

The section constructs a Rezk completion bA for every precategory A, with a weak equivalence A → bA through which functors into categories factor essentially uniquely. It also characterizes categories by how they respond to weak equivalences.

8. The Rezk completion

For any precategories A and B and category C, precomposition with a weak equivalence H : A → B induces an isomorphism CB → CA.The proof establishes the precomposition functor as fully faithful and essentially surjective.Source: §8 · pp. 20–22
The completion A → bA is a reflection: every functor from A into a category factors essentially uniquely through bA.The section identifies this universal property using the behavior of categories under weak equivalences.Source: §8 · pp. 20, 23
Every precategory A has a category bA and a weak equivalence A → bA.The construction takes bA as the full subcategory of SetAop determined by merely representable functors; the Yoneda embedding is fully faithful and essentially surjective into it.Source: §8 · p. 23
For a small A, this construction places bA in the next higher universe.A direct construction using higher inductive types can leave the universe level unchanged.Source: §8 · p. 24
The Rezk completion of the pregroupoid on X is its fundamental groupoid, identifiable with the 1-truncation ∥X∥1.The completion of the precategory of types with hom(X, Y) := ∥X → Y∥0 is called the homotopy category of types, whose objects identify with ∥Type∥1.Source: §8 · p. 24
A precategory C is a category exactly when precomposition with every weak equivalence induces an isomorphism CB → CA.The section proves the forward direction via Theorem 8.4 and the converse using A → bA.Source: §8 · p. 24

9. The Formalization

The formalization implements the paper’s basic theory, including the Rezk completion and its universal property, in Coq. Its design favors type constructors with understood homotopy-theoretic semantics while using notation and coercions to manage complex structures.

9. The Formalization

The formalization uses Coq 8.3pl5, patched as instructed by Voevodsky, and is based on the Foundations library [18].It is available online and as an addendum to the arXiv submission.Source: §9 · p. 24

Design principles.

The design uses Π, Σ, and Id constructors, plus implicit arguments and coercions, following Voevodsky’s conventions with a few departures [18].The basic constructors have well-understood semantics in homotopy-theoretic models; implicit arguments and coercions manage complex structures and reflect mathematical practice.Source: Design principles · pp. 24–25

Reading the code.

The code presents precategory data and axioms through predicates and definitions, with notation such as f ;; g for composition.It uses identity c for an identity morphism and splits large definitions into parts, including object and hom-set data before the remaining structure.Source: Reading the code · p. 25

Contents of the formalization.

The formalization comprises ten files covering precategories, functors, Yoneda, precomposition, and the Rezk completion.The listed files include proofs of Lemmas 8.1 and 8.2, Theorem 8.4, and Theorem 8.5.Source: Contents of the formalization · p. 26

Formalization vs informal definitions.

One formalization change makes the adjunction axiom pointwise, avoiding a transport needed because the natural transformations are not definitionally composable.The pointwise and natural-transformation equality statements are logically and type-theoretically equivalent.Source: Formalization vs informal definitions · p. 26

Statistics.

The library contains about 180 definitions and 170 lemmas, with 1,200 lines of specification and 2,700 lines of proof script.Source: Statistics · p. 26

10. Conclusions and further work

The paper presents Univalent Foundations as a basis for category theory in which saturated categories make constructions invariant under isomorphism and equivalence. It also describes a universal completion, its stack-completion semantics, and directions for further development.

10. Conclusions and further work

With saturated categories, category-theoretic constructions and proofs are automatically invariant under isomorphism of objects and equivalence of categories.Source: §10 · p. 26
Strict categories remain available when less invariant treatment is wanted, allowing both approaches to coexist with a type distinction.Source: §10 · p. 26
The universal passage from a precategory to a saturated category corresponds to stack completion in higher-topos semantics.Source: §10 · pp. 26–27
Future work includes basic category theory and saturated 2-categories; formalizing full (∞, 1)-categories remains difficult with current type theories.Source: §10 · p. 27