💻 computer science

Terminal Coalgebras and Non-wellfounded Sets in Homotopy Type Theory

This paper constructs models of non-well-founded material sets in Homotopy Type Theory that satisfy Scott's and Aczel's Anti-Foundation Axioms via M-types and terminal coalgebras, extends these axioms to higher type levels within Univalent Material Set Theory, and provides a characterisation of M-type identity types, with all results formalised in Agda.

Original authors: Hakon Robbestad Gylterud, Elisabeth Stenholm, Niccolò Veltri

Published 2026-07-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Hakon Robbestad Gylterud, Elisabeth Stenholm, Niccolò Veltri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Building a Universe of "Spinning" Sets

Imagine you are building a universe of objects (sets). In the traditional way of doing math (called "well-founded" set theory), every object is built from smaller objects, which are built from even smaller ones, all the way down to nothing. It's like a pyramid: you can't have a block floating in mid-air; it must rest on something below it.

But what if you want to build a universe where things can rest on themselves? What if you have a box that contains itself? Or a chain of boxes where Box A is inside Box B, which is inside Box C, which is inside Box A? In traditional math, this is forbidden because it creates an infinite loop. In this paper, the authors explore how to build a mathematical universe that allows these loops, using a modern framework called Homotopy Type Theory (HoTT).

The paper does two main things:

It builds a model of sets that allows loops, following rules set by a mathematician named Scott.
It builds a different model of sets that allows loops, following rules set by a mathematician named Aczel.

The Tools: Trees, Coalgebras, and "Unfolding"

To understand their models, imagine a tree.

Well-founded trees (the old way) are like family trees. They have a root, branches, and eventually end in leaves. They stop growing.
Non-wellfounded trees (the new way) can be like a fractal or a hall of mirrors. A branch might loop back and become the root again. Or a branch might split into two identical branches that look exactly like the whole tree.

The authors use a concept called Coalgebras to describe these trees. Think of a coalgebra as a "machine" that tells you how to look at a node and see what comes next.

If the machine says "stop," you have a leaf.
If the machine says "go to these children," you have branches.
If the machine says "go to a child that is actually you," you have a loop.

The paper asks: What is the "ultimate" machine that can describe all possible loops?

The Two Models: Scott vs. Aczel

The authors construct two different "ultimate machines" (mathematical models) to handle these loops. They correspond to two different philosophies on how to treat equality in these looping worlds.

1. The "Mirror" Model (Scott's Anti-Foundation Axiom)

The Analogy: Imagine a hall of mirrors. If you stand in front of a mirror, you see a reflection. If that reflection is in another mirror, you see a reflection of a reflection.
The Rule: In this model, two objects are considered "equal" if their unfolding patterns look the same. If you keep opening the layers of a set (like peeling an onion or unfolding a tree), and the pattern of branches is identical to another set, they are the same.
The Result: The authors built a specific type of tree structure (called $V^0_\infty$ ) that acts as this model. It's a "fixed point," meaning if you apply the rules of the universe to it, you get the same universe back.
Key Finding: This model is not the "final" or "terminal" machine in the strictest sense. It's a "third option"—it's not the starting point (initial) and not the absolute end point (terminal). It sits in the middle. It satisfies Scott's rules, which are stricter about how loops are identified.

2. The "Universal" Model (Aczel's Anti-Foundation Axiom)

The Analogy: Imagine a master catalog of every possible story you could tell, including stories that tell themselves.
The Rule: In this model, any graph (a picture of dots and lines) can be turned into a set. If you have a picture of a loop, there is a unique set that matches that picture perfectly.
The Result: The authors constructed a "Terminal Coalgebra" (the ultimate machine) for this purpose. However, to build this specific machine, they had to use a special, somewhat controversial mathematical tool called Propositional Resizing.
- What is Propositional Resizing? Imagine you have a giant library of books (propositions). This tool allows you to shrink the entire library down so it fits on a single shelf, without losing any of the stories. It's a powerful shortcut that makes the construction possible.
Key Finding: This model satisfies Aczel's rules. It is the "terminal" object, meaning it is the most complete version of a looping set universe possible under these rules.

The "Identity" Puzzle: What Makes Two Things the Same?

A major part of the paper is solving a tricky puzzle: How do we know when two looping trees are actually the same?

In standard math, if two things look the same, they are equal. But in a world with loops, things get weird.

The authors discovered that the "equality" between two points in their looping trees can be described as another type of tree (an "indexed M-type").
The Metaphor: Imagine you are comparing two infinite fractals. To prove they are the same, you don't just look at the whole picture; you have to compare every single branch, and every sub-branch, and every sub-sub-branch. The paper provides a precise recipe (a "characterization") for how to do this comparison. They proved that the "equality" of these complex loops is itself a structured, infinite object.

Summary of Achievements

Scott's Model: They built a universe of sets that allows loops, where equality is determined by the shape of the "unfolding" tree. This model is a fixed point but not the absolute "terminal" one.
Aczel's Model: They built the "ultimate" universe of sets that allows loops, where any graph can be turned into a set. This required a special mathematical assumption (Propositional Resizing).
The "Equality" Recipe: They figured out exactly how to define "sameness" for these infinite, looping structures, showing that equality is just another kind of tree structure.
Formalization: They didn't just write this on paper; they built it inside a computer program called Agda, which checks every logical step to ensure there are no mistakes.

Why Does This Matter?

The paper doesn't claim to solve real-world engineering problems or medical issues. Instead, it solves a foundational puzzle in mathematics. It shows that we can build a consistent, logical universe where "circles" and "loops" are allowed, using the modern language of Homotopy Type Theory. It bridges the gap between classical set theory (which forbids loops) and modern computer science logic (which needs to handle complex, circular data structures like streams and transition systems).

In short: They built two different "universes" where things can contain themselves, proved they work according to specific rules, and showed exactly how to tell if two such self-containing things are actually the same.

Technical Summary: Terminal Coalgebras and Non-Wellfounded Sets in Homotopy Type Theory

Problem Statement
The paper addresses the challenge of modeling non-wellfounded material sets within Homotopy Type Theory (HoTT). While wellfounded set theory has been successfully modeled in HoTT using higher inductive types (where equality is the identity type), the modeling of non-wellfounded sets—sets that may contain themselves or form infinite membership chains—has historically relied on setoids (where equality is a separate binary relation) rather than the identity type. The authors aim to construct models of non-wellfounded sets in HoTT where equality is interpreted strictly as the identity type, thereby integrating classical notions from universal coalgebra and non-wellfounded set theory into the higher-dimensional structures supported by HoTT. Specifically, the paper seeks to construct terminal coalgebras for restricted powerset functors to model Aczel's Anti-Foundation Axiom (AFA) and to construct alternative fixed points modeling Scott's Anti-Foundation Axiom (SAFA).

Methodology
The authors employ the framework of Univalent Material Set Theory and the theory of coalgebras for wild endofunctors on the universe of types. The methodology involves three primary technical approaches:

Dualization of Iterative Sets: The authors construct a hierarchy of types $V^n_\infty$ by dualizing the construction of iterative sets ( $V^n$ ). While $V^n$ is the initial algebra of the restricted powerset functor $P^n$ , $V^n_\infty$ is constructed as a specific subtype of the M-type (the terminal coalgebra of the unrestricted powerset functor $P^\infty$ ). This subtype is defined by a coinductive predicate ensuring that the branching maps at every node are truncated to a specific level.
Characterization of Identity Types: A crucial technical step involves characterizing the identity types of M-types. The authors prove that the identity type between two elements of an M-type is equivalent to an indexed M-type (specifically, the terminal coalgebra of an indexed polynomial functor derived from the "unfolding" of a relation). This characterization is essential for proving the local smallness of the constructed models.
Adaptation of Aczel–Mendler Construction: To construct a true terminal coalgebra for the restricted powerset functor $P^0$ $P^{0}$ (which models AFA), the authors adapt the classical Aczel–Mendler theorem to type theory. This adaptation requires:
- Defining "U-based" functors (functors where values on large types are colimits of values on small types).
- Utilizing relation lifting and the concept of "precongruences" to quotient the weakly terminal coalgebra.
- Assuming propositional resizing to ensure that the resulting quotient types are locally small and that the construction holds for set-valued functors like $P^0$ .

Key Contributions and Results

A Model of Scott's Anti-Foundation Axiom (SAFA): The authors construct a type $V^0_\infty$ which is a fixed point of the restricted powerset functor $P^0$ but is neither the initial algebra nor the terminal coalgebra. They prove that this type, equipped with the induced elementhood relation, satisfies Scott's Anti-Foundation Axiom. In this model, equality is the identity type, and the model is "simple" (any two homomorphisms into it are equal) but not terminal.
Generalization to Higher Types: The construction is generalized to a hierarchy $V^n_\infty$ for any truncation level $n$ . These models satisfy the generalized $k$ -SAFA axioms for all $k \le n$ . The paper demonstrates that these models satisfy standard set-theoretic axioms (empty set, separation, union, etc.) at the appropriate truncation levels, provided the models are locally small.
Characterization of M-type Identity Types: The paper provides a full characterization of the identity type of M-types as indexed M-types (Theorem 2.15). This result is used to prove that the constructed models are locally small, a necessary condition for them to serve as valid models of material set theory in HoTT.
A Model of Aczel's Anti-Foundation Axiom (AFA): Assuming the axiom of propositional resizing, the authors construct a terminal coalgebra for the restricted powerset functor $P^0$ (and more generally for $U$ -based functors). This terminal coalgebra serves as a model of Aczel's AFA, where every graph has a unique decoration.
Non-Terminality of $V^0_\infty$ : The paper explicitly demonstrates that $V^0_\infty$ is not the terminal coalgebra for $P^0$ . It provides a counterexample showing that distinct coalgebra homomorphisms can exist from a specific graph into $V^0_\infty$ , distinguishing it from the terminal coalgebra constructed via the Aczel–Mendler method.

Significance and Claims
The paper claims to provide the first models of non-wellfounded material sets in HoTT where equality is the identity type, moving beyond the setoid-based models of the past.

Distinction between AFA and SAFA: The work clarifies the relationship between Aczel's and Scott's anti-foundation axioms within the context of HoTT. It shows that while the terminal coalgebra (requiring propositional resizing) validates AFA, the co-iterative fixed point (constructible without resizing) validates SAFA. The authors note that in the untruncated case ( $\infty$ ), AFA and SAFA coincide, but they diverge at lower truncation levels.
Constructive Nature: The construction of the SAFA model ( $V^n_\infty$ ) is fully constructive and does not rely on impredicative axioms like propositional resizing.
Formalization: All main results are formalized in the Agda proof assistant, utilizing both standard Agda and Cubical Agda (for Section 6), ensuring the correctness of the complex homotopical arguments.
Open Questions: The authors modestly note that the existence of the terminal coalgebra for $P^0$ without propositional resizing remains an open question. They do not claim to have resolved whether such a construction is possible or if its existence implies classical principles, but they highlight this as a primary motivation for future work.

In summary, the paper successfully extends the theory of non-wellfounded sets to the higher-dimensional setting of HoTT, providing distinct models for different anti-foundation axioms and establishing the necessary technical groundwork regarding M-types and coalgebraic structures.