Lune

LICS2020Top-tier venue

Coherence via Well-Foundedness: Taming Set-Quotients in Homotopy Type Theory

Nicolai Kraus, Jakob von Raumer

Abstract

Suppose we are given a graph and want to show a property for all its cycles (closed chains). Induction on the length of cycles does not work since sub-chains of a cycle are not necessarily closed. This paper derives a principle reminiscent of induction for cycles for the case that the graph is given as the symmetric closure of a locally confluent and (co-)well-founded relation. We show that, assuming the property in question is sufficiently nice, it is enough to prove it for the empty cycle and for cycles given by local confluence.

Our motivation and application is in the field of homotopy type theory, which allows us to work with the higher-dimensional structures that appear in homotopy theory and in higher category theory, making coherence a central issue. This is in particular true for quotienting -a natural operation which gives a new type for any binary relation on a type and, in order to be wellbehaved, cuts off higher structure (set-truncates). The latter makes it hard to characterise the type of maps from a quotient into a higher type, and several open problems stem from this difficulty.

We prove our theorem on cycles in a type-theoretic setting and use it to show coherence conditions necessary to eliminate from set-quotients into 1types, deriving approximations to open problems on free groups and pushouts. We have formalised the main result in the proof assistant Lean.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Symmetries in reversible programming: from symmetric rig groupoids to reversible programming languagesVikraman Choudhury, Jacek Karwowski, Amr SabryPOPL 2022 · 10 citations

Related papers

  1. Sequential Colimits in Homotopy Type TheoryKristina Sojakova, Floris van Doorn, Egbert RijkeLICS 2020 · 5 citations
  2. The Integers as a Higher Inductive TypeThorsten Altenkirch, Luis ScoccolaLICS 2020 · 11 citations
  3. A Syntax for Strictly Associative and Unital ∞-CategoriesEric Finster, Alex Rice, Jamie VicaryLICS 2024
  4. The Steenrod squares via unordered joinsAxel Ljungström, David WärnLICS 2025 · 1 citation
  5. Higher LensesPaolo Capriotti, Nils Anders Danielsson, Andrea VezzosiLICS 2021
Dusk over the sea between two cliffs drawn in fine vertical lines