betaFeedback

WorksComputer Science

Strict Equality in Higher Identity Types: Axioms, Completeness, Decidability

Abstract

Reasoning about higher identity types uses two equalities, strict equality and equivalence of cells witnessed by a path. Strict equality is a congruence for every operation on cells, but associativity and the identity laws fail for it. Equivalence of cells satisfies those two laws, but it is not a congruence. Representations of higher identity types often conflate equational properties that hold strictly with those that hold only up to a path. We separate the two and axiomatize the former, introducing SEq, an equational theory generated by eleven axioms for strict equality between cells. We prove soundness and completeness for homotopy models, and completeness already over finite CW-complexes. Nine of these axioms form a strongly normalizing rewrite system whose normal forms are unique up to picture equivalence, and the resulting word problem is decidable in exponential time. We also give presheaf models over a cubical base category in which composition arises from a pushout in the base category itself, without requiring Kan filling structure. The same pushout structure provides explicit higher-dimensional witnesses for associativity and the identity laws.

Introduction

Recent years have seen the development of many complementary approaches to understanding the structure of higher types, especially higher identity types, in Martin-Löf type theory and constructive mathematics. This includes topological approaches such as HoTT and univalent foundations [24], categorical approaches such as strong and weak ω\omega-categories and their cubical counterparts [1, 13], type-theoretic approaches such as cubical type theory [7, 9, 12, 19], and algebraic approaches such as computads [20]. These approaches are all related on some basic level but may differ in their axiomatizations, choice of primitive concepts, and degree of constructivity.

A fundamental notion, and perhaps the primary motivation for much research in this area, is that of equality at a type, where Martin-Löf’s higher identity types play a dominant role. A proof of equality is typically a path in a space, serving as a witness for an equality judgment. This type of equality is often called propositional equality and is denoted ≃\simeq in this paper. This is weaker than strict equality, often called judgmental equality and here denoted ==. Paths form spaces themselves, so one may speak of paths between paths, and so on, giving the hierarchy of higher identity types. Many of the structures above were designed to capture the properties of this hierarchy at an abstract level.

In this paper we focus on the model theory of higher identity types in their various incarnations as weak ω\omega-categories, homotopy models, and presheaf models over cubical sets. Our starting point is the observation that standard presentations tend to conflate desirable equational properties that come from strict equality (==) and those that come from equivalence as witnessed by a path (≃\simeq), whereas there are subtle but important reasons to treat them separately. For example, two nn-cells of a higher identity type can be composed only when their boundaries agree on the nose: the composite1 α∘n−knβ\alpha\mathbin{\circ^{n}_{n-k}} \beta exists only if src⁡kα=tgt⁡kβ\operatorname{src}^{k}\alpha=\operatorname{tgt}^{k}\beta, and no can be asked to witness that equation, because until it holds there is nothing for a path to connect. The same is true of the globular laws src⁡tgt⁡α=src⁡2α\operatorname{src}\operatorname{tgt}\alpha= \operatorname{src}^{2}\alpha and tgt⁡src⁡α=tgt⁡2α\operatorname{tgt}\operatorname{src}\alpha= \operatorname{tgt}^{2}\alpha.

Standard presentations, however, do not isolate it and in fact mix laws that hold strictly with laws that hold only up to equivalence witnessed by a path. Strict equality enjoys the advantage that all relevant algebraic operations (e.g., the globular maps src⁡\operatorname{src} and tgt⁡\operatorname{tgt}, the identity map id⁡\operatorname{id}, and compositions ∘kn\circ^{n}_{k}) are congruences. However, associativity of composition and the identity laws α=α∘n−knid⁡ksrc⁡kα\alpha= \alpha\circ^{n}_{n-k} \operatorname{id}^{k}\operatorname{src}^{k}\alpha and α=id⁡ktgt⁡kα∘n−knα\alpha= \operatorname{id}^{k}\operatorname{tgt}^{k}\alpha\circ^{n}_{n-k}\alpha do not hold strictly, but only up to ≃\simeq. On the other hand, although ≃\simeq satisfies associativity and the identity laws, it fails to be a congruence with respect to id⁡\operatorname{id}. Write α≃β\alpha\simeq\beta when some cell ϕ\phi one dimension higher has α\alpha as source and β\beta as target. If id⁡α≃id⁡β\operatorname{id}\alpha\simeq\operatorname{id}\beta via ϕ\phi, then α=src⁡id⁡α=src⁡src⁡ϕ=src⁡tgt⁡ϕ=src⁡id⁡β=β\alpha= \operatorname{src}\operatorname{id}\alpha= \operatorname{src}\operatorname{src}\phi= \operatorname{src}\operatorname{tgt}\phi= \operatorname{src}\operatorname{id}\beta= \beta, using only src⁡id⁡α=α\operatorname{src}\operatorname{id}\alpha= \alpha and the globular law. So ≃\simeq can be a congruence for id⁡\operatorname{id} only if it is equality.

Definitions of weak ω\omega-categories [5, 6, 8, 13, 16, 17, 18] and computads [20] impose both kinds of law at once. The division also presents itself in the exchange rule that is usually presented as a law of ≃\simeq, yet under the standard topological definition of composition it holds strictly. Another example is id⁡α=id⁡α∘n−1nid⁡α\operatorname{id}\alpha= \operatorname{id}\alpha\circ^{n}_{n-1} \operatorname{id}\alpha. In the strict setting it is an immediate consequence of the identity laws [1, 11, 13], and its type-theoretic shadow is the judgmental equality refl⁡a⋅refl⁡a≡refl⁡a\operatorname{refl}a \mathbin{\cdot} \operatorname{refl}a \equiv\operatorname{refl}a of [24 §2.1]. But once the identity laws are weakened to hold only up to ≃\simeq, it seems that it must be taken as a law in its own right.

These observations indicate that there is insight to be gained from a more careful separation of concerns. We propose to consider separately the properties of == and ≃\simeq in models of higher identity types. In this paper, we focus on the former. We provide SEq, an equational axiomatization of strict equality (==) consisting of eleven equational axioms and explore its consequences. The axiomatization consists of various well-known laws involving the globular maps src⁡\operatorname{src} and tgt⁡\operatorname{tgt}, the identity map id⁡\operatorname{id}, and compositions ∘mn\circ^{n}_{m}, including the globular laws and exchange. Thus our strict equational theory is quite different from computads [13, 20], which are assumed to satisfy associativity and identity laws for composition, and from strong ω\omega-categories [22], in which additionally id⁡\operatorname{id} is a congruence. Futia [13] takes a step in this direction and considers the two equational theories separately, but his axiomatization of the strict theory does not mention the equation id⁡α=id⁡α∘n−1nid⁡α\operatorname{id}\alpha= \operatorname{id}\alpha\circ^{n}_{n-1} \operatorname{id}\alpha and treats the exchange law as a property of ≃\simeq. The separation of the two layers also has a semantic counterpart: Swan [23] shows that path types and identity types can be separated in presheaf models of univalent type theory.

Our main results are that SEq is sound and complete for the strict equational theory of all homotopy models. More strongly, we show that it is sound for a (very wide) class of presheaf models over a certain cubical base category and complete for a (very narrow) class of topological models, namely the finite CW-complexes. We also show that the equational theory admits an exponential-time decision procedure.

That the laws of SEq hold on the nose is a consequence of how composition is obtained. Cubical algebra has carried composition as primitive structure since [1, 11], where each ∘nm\circ^{m}_{n} is part of the data. The presheaf models of cubical type theory do not. They differ in what the interval object of the base category carries, a de Morgan algebra in [12] and merely Cartesian structure in [2], but in all of them composition of cells is absent from the base category: each type must instead be equipped with Kan composition structure of its own. Thus, composition is not primitive and does not respect globularity. We here recover it as structure on the base category itself (§5). Concretely, we propose a primitive composition mechanism in the form of a certain pushout on the base category of cubes. One can then define compositions natively without recourse to space-filling and in a way that respects the structure of higher identity types.

The construction provides a direct, constructive account of the weak laws. In standard presheaf models of cubical type theory, higher-dimensional witnesses are obtained through Kan filling, whereas we construct them from morphisms of the cubical base category. In particular, witnesses for associativity and identity laws arise from the same pushout structure defining composition, and coherence conditions such as the pentagon identity can be verified equationally. This complements our decidability result for strict equality: equality of terms in our equational theory can be decided algorithmically, while associativity and the identity laws are given explicit witnesses.

Main contributions:

  • an equational presentation of the strict equational theory of higher identity types, including a construction of free models and their properties (§3);

  • completeness for homotopy models (§ 4);

  • completeness for finite CW-complexes (§ 4.4);

  • an exponential-time decision procedure for strict equality (§ 4.5);

  • a formulation of presheaf models with native composition and soundness over these models (§ 5);

  • a calculus for the morphisms of □\square, in which witnesses for associativity and the identity laws are constructed directly (§ 6, §B, and §C).

  • a homeomorphism between higher identity types as iterated path spaces and as cubical sets (§ 2 and §D).

Homotopy Models

Our motivating semantic models are the homotopy models of higher identity types [4] as they arise in topological models of HoTT and cubical type theory. There are two equivalent views of these models, one as an iterated hierarchy of spaces of continuous paths generated inductively in a uniform way, the other as a class of homotopies α:In→X\alpha: I^n \to X satisfying a certain boundary-preservation condition, where II is the closed real unit interval and XX is an arbitrary topological space. The two views are homeomorphic. Passing from the first to the second is currying: a path between paths is a map I→(I→X)I \to(I \to X), which uncurries to a map I2→XI^2 \to X, and iterating gives In→XI^n \to X. This is a homeomorphism and not merely a bijection because II is compact Hausdorff, so that (−)×I(-) \times I is left adjoint to (−)I(-)^I in the compact-open topology. Under the correspondence, the endpoint conditions at each level, p(0)=ap(0)=a and p(1)=bp(1)=b, become the boundary-preservation condition on In→XI^n \to X. Further details are in §D.

In the first view, one has an inductively constructed hierarchy of spaces

  • Level 0: a:Xa : X

  • Level 1: p:Id⁡X(a,b)p : \operatorname{Id}_X(a,b), where a,b:Xa,b : X

  • Level 2: α:Id⁡Id⁡X(a,b)(p,q)\alpha: \operatorname{Id}_{\operatorname{Id}_X(a,b)}(p,q), where p,q:Id⁡X(a,b)p,q : \operatorname{Id}_X(a,b)

  • Level 3: ϕ:Id⁡Id⁡Id⁡X(a,b)(p,q)(α,β)\phi: \operatorname{Id}_{\operatorname{Id}_{\operatorname{Id}_X(a,b)}(p,q)}(\alpha,\beta), where α,β:Id⁡Id⁡X(a,b)(p,q)\alpha,\beta: \operatorname{Id}_{\operatorname{Id}_X(a,b)}(p,q),

etc., where the space of continuous functions I→XI \to X is endowed with the compact-open topology relative to XX and Id⁡X(a,b)\operatorname{Id}_X(a,b) denotes the subspace of all paths p:I→Xp : I \to X such that p(0)=ap(0)=a and p(1)=bp(1)=b.

In the second view, we have a family of nn-cells for each n≥0n \ge0, which are continuous maps α:In→X\alpha: I^n \to X satisfying a certain boundary preservation condition. These will be models of the axioms to be presented later in § 3.2.

An nn-dimensional homotopy is a continuous map α:In→X\alpha: I^n \to X. Not all homotopies are nn-cells, but only those satisfying the boundary-preservation condition. We define dim⁡α=n\dim\alpha= n. The set of nn-dimensional homotopies is denoted HnH_n.

Given an nn-dimensional homotopy α:In→X\alpha: I^n \to X and 1≤k≤n1 \le k \le n, let α(k)\alpha^{(k)} be α\alpha curried on its kk-th component:

α(k):I→In−1→Xα(k)(xk)(x1,…,xk−1,xk+1,…,xn)=α(x1,…,xn).\alpha^{(k)} : I \to I^{n-1} \to X \qquad\alpha^{(k)}(x_k)(x_1,\ldots,x_{k-1},x_{k+1},\ldots,x_n)=\alpha(x_1,\ldots,x_n).

We always think of the first component as time and often write tt for x1x_1, so

α(1)(t)(x2,…,xn)=α(t,x2,…,xn).\alpha^{(1)}(t)(x_2,\ldots,x_n)=\alpha(t,x_2,\ldots,x_n).

For α∈Hn\alpha\in H_n, x∈Ix \in I, and 1≤k≤n1 \le k \le n, α(k)(x)\alpha^{(k)}(x) is called a section of α\alpha. A face of α\alpha is a section α(k)(b)\alpha^{(k)}(b) with b∈{0,1}b \in\{0,1\}. Two special faces are src⁡α=α(1)(0)\operatorname{src}\alpha=\alpha^{(1)}(0) and tgt⁡α=α(1)(1)\operatorname{tgt}\alpha=\alpha^{(1)}(1), called the source and target of α\alpha, respectively. We thus view α\alpha as a continuous deformation of src⁡α\operatorname{src}\alpha to tgt⁡α\operatorname{tgt}\alpha, passing through intermediate states α(1)(t):In−1→X\alpha^{(1)}(t) : I^{n-1} \to X. For n≥2n \ge2, the maps α(2)(0)\alpha^{(2)}(0) and α(2)(1)\alpha^{(2)}(1) describe the trajectory of src⁡α\operatorname{src}\alpha and tgt⁡α\operatorname{tgt}\alpha throughout the deformation.

References

  1. [1]Al-Agl, F.A., Brown, R., Steiner, R.: Multiple categories: the equivalence of a globular and a cubical approach. Advances in Mathematics 170(1), 71–118 (2002)
  2. [2]Angiuli, C., Brunerie, G., Coquand, T., Hou (Favonia), K.B., Harper, R., Licata, D.R.: Syntax and models of cartesian cubical type theory. Mathematical Structures in Computer Science 31(10), 1117–1166 (2021)DOI
  3. [3]Awodey, S.: A cubical model of homotopy type theory (2016), https://arxiv.org/abs/1607.06413
  4. [4]Awodey, S., Warren, M.A.: Homotopy theoretic models of identity types. Mathematical Proceedings of the Cambridge Philosophical Society 146(1), 45–55 (2009). https://doi.org/10.1017/S0305004108001783
  5. [5]Baez, J.C., Dolan, J.: Higher-dimensional algebra iii: n-categories and the algebra of opetopes. Advances in Mathematics 135(2), 145–206 (1998)arxiv.org/abs/q-alg/9702014
  6. [6]Batanin, M.A.: Monoidal globular categories as a natural environment for the theory of weak n-categories. Advances in Mathematics 136(1), 39–103 (1998). https://doi.org/10.1006/aima.1998.1724
  7. [7]Bentzen, B.: Naive cubical type theory. Mathematical Structures in Computer Science 31(10), 1205–1231 (2021). https://doi.org/10.1017/S0960129522000007X
  8. [8]Bergner, J.E.: A survey of (∞, 1)-categories. arXiv preprint math/0610239 (2006)
  9. [9]Bezem, M., Coquand, T., Huber, S.: A model of type theory in cubical sets. Journal of Automated Reasoning 53(2), 107–134 (2014)
  10. [10]Brown, R., Higgins, P.J.: The algebra of cubes. Journal of Pure and Applied Algebra 21(3), 233–260 (1981). https://doi.org/10.1016/0022-0409(81)90018-9
  11. [11]Brown, R., Higgins, P.J.: On the algebra of cubes. Journal of Pure and Applied Algebra 21(3), 233–260 (1981). https://doi.org/10.1016/0022-0409(81)90018-9, https://www.sciencedirect.com/science/article/pii/0022404981900189
  12. [12]Cohen, C., Coquand, T., Huber, S., Mörtberg, A.: Cubical type theory: A constructive interpretation of the univalence axiom. In: 21st International Conference on Types for Proofs and Programs (TYPES 2015). vol. 69, pp. 5–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2018)
  13. [13]Futia, C.A.: Weak omega categories I (2004), https://arxiv.org/abs/math/0404216
  14. [14]Grätzer, G.: Universal Algebra. Van Nostrand, Princeton, NJ (1968)
  15. [15]Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
  16. [16]Hermida, C., Makkai, M., Power, J.: On weak higher-dimensional categories i-1. Journal of Pure and Applied Algebra 154(1–3), 221–246 (2000)
  17. [17]Hermida, C., Makkai, M., Power, J.: On weak higher-dimensional categories i-2. Journal of Pure and Applied Algebra 157(2–3), 247–277 (2001)DOI
  18. [18]Hermida, C., Makkai, M., Power, J.: On weak higher-dimensional categories i-3. Journal of Pure and Applied Algebra 166(1–2), 83–104 (2002)DOI
  19. [19]Licata, D.R., Orton, I., Pitts, A.M., Spitters, B.: Internal universes in models of homotopy type theory. In: 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). vol. 108, pp. 22–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2018)DOI
  20. [20]Makkai, M.: The word problem for computads (2005), http://www.math.mcgill.ca/makkai/WordProblem/WordProblemCombined.pdf, unpublished
  21. [21]Orton, I., Pitts, A.M.: Axioms for modelling cubical type theory in a topos. Logical Methods in Computer Science 14(4), 8 (Dec 2018). https://doi.org/10.23638/LMCS-14(4:23)2018, https://lmcs.episciences.org/4491
  22. [22]Street, R.: The algebra of oriented simplexes. Journal of Pure and Applied Algebra 49(3), 283–335 (1987)DOI
  23. [23]Swan, A.W.: Separating path and identity types in presheaf models of univalent type theory. Mathematical Structures in Computer Science 36(6), 1–32 (2026). https://doi.org/10.1017/S0960129526100656a
  24. [24]The Univalent Foundations Program: Homotopy Type Theory: Univalent Foundations of Mathematics. Institute for Advanced Study, Princeton (2013), https://homotopytypetheory.org/book/arxiv.org/abs/1308.0729

Paper details

vlnc:W_mzeaavcq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents