💻 computer science

Multi-clocked Guarded Recursion Beyond {\omega}

This paper extends the extensional presheaf model of multi-clocked guarded recursion to higher ordinals, thereby enabling set-theoretic interpretations that verify the correctness of encodings for complex coinductive types involving finite powersets, distributions, and existential quantification.

Original authors: Rasmus Ejlers Møgelberg

Published 2026-06-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rasmus Ejlers Møgelberg

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

Imagine you are an architect trying to design a building that never stops growing. In the world of computer science, this is called a "coinductive type." It's a program that keeps running forever, like a video game that never ends or a server that constantly processes data.

To make sure these infinite programs don't crash or get stuck, computer scientists use a special set of rules called Guarded Recursion. Think of this as a "time delay" mechanism. Before the program can do the next step, it must wait for a "tick" of a clock. This ensures the program is always making progress, even if it goes on forever.

The Problem: The "Dream World" vs. Reality

For a long time, mathematicians have built a "Dream World" (a mathematical model called the topos of trees) where these infinite programs are easy to design and prove are correct. It's a paradise where every equation has a solution.

However, there's a catch. The "Dream World" is very different from the "Real World" (standard set theory, which is how we usually understand math and computers).

The Translation Issue: Sometimes, a proof that works perfectly in the Dream World doesn't translate to the Real World. For example, if you prove "there exists a solution" in the Dream World, it doesn't always mean you can actually find that specific solution in the Real World.
The Missing Tools: The Dream World has special tools (like functors for probability and randomness) that work great there. But when you try to bring those tools into the Real World, they break or behave differently.

The Solution: Expanding the Map

This paper, written by Rasmus Ejlers Møgelberg, proposes a clever fix. Instead of trying to force the Dream World to look exactly like the Real World, the author suggests expanding the Dream World.

Imagine the Dream World was a map of a small island. The author says, "Let's make the island bigger." Specifically, they suggest using a much larger "clock" system.

The Old Clock: Previously, the model used a clock that ticked through the natural numbers (1, 2, 3...), which is like counting up to infinity.
The New Clock: The paper suggests using a clock that ticks through much larger, "uncountable" numbers (like the first uncountable ordinal, $\omega_1$ ).

By making the clock system this massive, the "Dream World" becomes big enough to contain the "Real World" as a special, stable part of itself.

What This Achieves

By using this "Super-Large Clock," the paper shows that we can finally do three important things that were previously impossible or shaky:

Handling Randomness and Choices: We can now safely use tools for non-determinism (making random choices) and probability (like rolling dice) in our infinite programs. In the old, smaller model, these tools didn't play nice with the "time delay" rules. In this new, larger model, they do.
Proving Existence: If we prove that "a solution exists" in this new model, we can be sure that a real solution actually exists in the standard mathematical world. The "translation" between the two worlds now works perfectly.
Connecting Logic to Reality: We can take complex proofs about how these infinite programs behave (like checking if two programs are effectively the same) and trust that they hold true for real-world computers, not just in the abstract mathematical paradise.

The Analogy of the "Drop"

The paper also looks at the rules (algebraic theories) used to build these programs.

Good Rules: Some rules are like a recipe where every ingredient you use must appear in the final dish. These work perfectly with the new clock system.
Bad Rules: Some rules allow you to "drop" ingredients (ignore them). The paper shows that if your rules allow you to drop ingredients, the new clock system breaks. But if your rules are "honest" (no dropping), the system works beautifully.

The Bottom Line

This paper is like finding a new, larger lens for a microscope. With the old lens, you could see the structure of infinite programs, but the image was blurry when you tried to compare it to reality. With this new, "super-large" lens (the extended clock model), the image becomes crystal clear. It proves that the complex, infinite programs we design in our mathematical "Dream World" are not just fantasy—they are solid, correct, and applicable to the real world of computing.

Technical Summary: Multi-clocked Guarded Recursion Beyond $\omega$

Problem Statement
Type theories with multi-clocked guarded recursion (such as Clocked Type Theory, CloTT) provide a flexible framework for programming with coinductive types and constructing denotational models of programming languages featuring advanced constructs like non-determinism and probabilistic choice. While these theories have been successfully modeled using presheaves over the topos of trees (indexed by $\omega$ ) and, more recently, presheaves of cubical sets, a gap remains in relating these results to the "real world" of standard set theory.

Specifically, standard set-theoretic interpretations often fail to preserve the commutativity of clock quantification with certain functors (such as the finite powerset functor $P_f$ and finite distribution functor $D_f$ ) and existential quantification. In the topos of trees, existential quantification does not always externalize to existence in sets, and functors like $P_f$ and $D_f$ do not commute with clock quantification in the standard model. Consequently, results proved in Clocked Cubical Type Theory (e.g., regarding distributive laws between monads or contextual equivalence in Probabilistic FPC) are currently interpreted as statements about monads on hsets within the cubical model, leaving their validity in the standard category of sets ( $\mathbf{Set}$ ) unverified.

Methodology
The paper investigates how to extend the extensional presheaf model of multi-clocked guarded recursion to higher ordinals ( $\rho > \omega$ ) to restore the necessary commutativity properties. The methodology involves:

Model Extension: Generalizing the presheaf model of CloTT (originally defined by Mannaa et al. for $\rho = \omega$ ) to be indexed by an arbitrary regular limit ordinal $\rho$ . The model is constructed in the category of presheaves over a category of time objects $T_\rho$ , where objects are pairs of finite clock sets and maps to $\rho$ .
Semantic Analysis of Commutativity: The paper analyzes the conditions under which universal quantification over clocks ( $\forall \kappa$ $\forall κ$ ) commutes with:
- Functors generated by algebraic theories (specifically monads like $P_f$ and $D_f$ ).
- Existential quantification ( $\exists$ ).
Syntactic and Semantic Conditions:
- For Functors: The paper establishes that a functor $F$ commutes with $\rho^{op}$ -indexed limits (and thus clock quantification) if $F$ is $\kappa$ -accessible, preserves $\kappa$ -small intersections, and preserves pullbacks of monomorphisms, provided $\rho$ contains an ordinal of cardinality $\kappa$ .
- For Algebraic Theories: A syntactic condition is identified: algebraic theories must not contain "drop equations" (equations where the set of free variables in the two terms differs). This ensures the generated monad satisfies the semantic conditions above.
- For Existential Quantification: The paper proves that $\forall \kappa$ commutes with $\exists$ over a type $X$ if the fibers of $X$ have cardinality strictly smaller than the indexing ordinal $\rho$ . It also addresses "essentially unique" existential quantifications, where the witness is unique up to a finite number of delay steps.

Key Contributions and Results

Conservativity over Set: The paper explicitly states and proves the conservativity of the Clocked Type Theory model over the standard set-theoretic model of type theory. This implies that any statement expressible in the internal language of $\mathbf{Set}$ that is provable in CloTT is also true in $\mathbf{Set}$ .
Commutativity of Monads: The paper provides semantic conditions and a syntactic criterion (absence of drop equations) for monads generated by algebraic theories to commute with clock quantification. This validates the use of $P_f$ and $D_f$ in the set-theoretic model, provided the indexing ordinal $\rho$ is sufficiently large (e.g., $\omega_1$ for countable operations).
Commutativity of Existential Quantification: The paper demonstrates that by choosing a sufficiently large regular ordinal $\rho$ (e.g., $\omega_1$ or higher), universal quantification over clocks commutes with existential quantification over sets of cardinality less than $\rho$ . This resolves the issue of externalizing existential proofs from the topos of trees to $\mathbf{Set}$ .
Interpretation of Prior Work: The paper shows that applications previously formalized in Clocked Cubical Type Theory—specifically:
- Coalgebraic modeling of non-deterministic and probabilistic systems.
- Reasoning about weak bisimilarity and distributive laws between monads.
- Contextual equivalence proofs for Probabilistic FPC.
  —can be interpreted in the set-theoretic model indexed by a sufficiently large ordinal. This proves the correctness of these results under their standard set-theoretic interpretation.

Significance
The paper claims that by varying the indexing ordinal of the model, one can bridge the gap between the internal logic of guarded recursion (which handles productivity and coinduction elegantly) and the external world of standard set theory.

The primary significance is that it allows results proved using the machinery of Clocked Cubical Type Theory to be validated in standard set theory without relying on the specific properties of cubical sets. This suggests that the semantic basis for formalizing applications involving non-determinism, probability, and coinductive predicates can be established in proof assistants that do not rely on cubical type theory, provided the underlying model uses a sufficiently large indexing ordinal. The paper notes that while the metatheory used for these proofs is classical set theory, the results provide a rigorous set-theoretic justification for the correctness of encodings of coinductive types involving quotient inductive types and existential quantification.