🔢 mathematics

Itegories

This paper develops the theory of "itegories," which are restriction categories equipped with Kleene wands, by demonstrating how these operators provide a robust alternative to trace-based iteration in settings lacking coproducts and establishing their equivalence to standard iteration in extensive restriction categories.

Original authors: Robin Cockett, Jean-Simon Pacaud Lemay

Published 2026-07-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Robin Cockett, Jean-Simon Pacaud Lemay

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: What is an "Itegory"?

Imagine you are writing a computer program or solving a puzzle. Often, you have a process that loops: "Do step A, then check if you're done. If not, do step A again." This is called iteration.

In the world of advanced mathematics (specifically category theory), there are different ways to describe how these loops work. This paper introduces a new, simpler way to describe loops called an Itegory (a pun on "Category" and "Kleene," a famous logician).

The authors argue that you don't need complex machinery like "coproducts" (which are like fancy ways of combining different types of data) to describe loops. Instead, you just need two things:

A way to say when two paths are disjoint (they don't interfere with each other).
A special operator called a Kleene wand (pronounced "wand") that tells you how to run a loop until a specific condition is met.

The Core Concept: The "Kleene Wand"

Think of the Kleene wand (denoted as $\star|$ ) as a magical instruction manual for a robot.

The Setup: You have a robot that can do two things:
1. Looping: It can run a routine $f$ that keeps it in the same room (Type $X \to X$ ).
2. Exiting: It can run a routine $g$ that takes it out of the room to a new destination (Type $X \to A$ ).
The Rule: The robot can only run the exit routine $g$ if it hasn't already run the looping routine $f$ in a way that blocks it. They must be "disjoint" (like two people who can't be in the same spot at the same time).
The Wand's Job: The Kleene wand takes these two routines and creates a new, single routine: "Keep doing $f$ until you can finally do $g$ ."

If the robot gets stuck in an infinite loop of $f$ and never finds a chance to do $g$ , the wand says the result is "undefined" (the robot is stuck forever). If it eventually finds a spot to do $g$ , the wand outputs that path.

The Problem They Solved: "The Missing Coproduct"

In traditional math, describing these loops usually requires a structure called a coproduct.

Analogy: Imagine a coproduct is like a traffic intersection where two roads merge. To describe a loop, you usually need to draw a map showing how the road splits and merges back together.
The Issue: Not all mathematical worlds have these "intersections" (coproducts). Some worlds are too simple or too messy to have them.
The Solution: The authors show that you don't actually need the intersection. You just need to know when two paths are "disjoint" (they don't crash into each other). They call this relationship interference.
- If two paths are disjoint, they are like two people walking on different floors of a building; they never meet.
- The Kleene wand works perfectly in these "no-intersection" worlds.

The "Itegory" Connection

The paper proves a beautiful equivalence:

If you have a world with intersections (coproducts) and you can trace loops (a Traced Category), you can build a Kleene wand.
If you have a world without intersections but you have a Kleene wand, you can pretend it has intersections and trace loops just the same.

They call a world with a Kleene wand an Itegory. It's essentially a "loop-friendly" category that doesn't need the heavy machinery of intersections to function.

Real-World Examples in the Paper

The authors use two main examples to show this works:

Partial Functions (The "Maybe" Map):
- Imagine a map where some locations are marked "Here" and others are "Unknown."
- If you try to walk from "Unknown" to "Here," you can't.
- The Kleene wand here is simply: "Keep walking the loop until you hit a 'Here' spot. If you walk forever in the 'Unknown' zone, stop."
- This is exactly how computers handle loops that might run forever.
Recursive Functions (The "Computable" Map):
- This is similar to the first example, but restricted to things a computer can actually calculate.
- The paper shows that even with these strict rules, the Kleene wand works perfectly to describe iteration.

The "Matrix" Trick

One of the coolest parts of the paper is a construction they call the Matrix Representation.

Analogy: Imagine you have a small, simple room (a category) where you can't easily draw intersections.
The Trick: The authors show you can build a giant "Matrix Room" (like a spreadsheet) where every cell is a path from your small room.
The Result: In this giant spreadsheet, the "intersections" appear naturally. You can take your simple Kleene wand and use it to calculate complex loops in this big spreadsheet. It's like taking a simple rule for a single hallway and applying it to an entire city grid.

Summary of the "Dedication"

The paper is dedicated to Phil Scott, a mathematician who passed away in 2023. The authors share personal stories about him:

Robin recalls Phil helping him get a job and a memorable story about Phil waiting six hours at a train station in the rain to help Robin with his luggage, just so Robin could go hiking.
Jean-Simon remembers Phil as his first math professor who taught him how to write proofs and introduced him to the field of category theory.

The paper is a tribute to Phil's influence, using his ideas about loops and logic to build this new framework.

The Bottom Line

This paper says: "You don't need complex traffic intersections to describe computer loops. If you just know when two paths don't crash into each other, you can use a simple 'magic wand' (the Kleene wand) to describe any loop, even in the simplest mathematical worlds."

This makes the theory of loops more flexible and applicable to a wider range of mathematical and computational problems.

Technical Summary of "Itegories"

Problem Statement
The paper addresses the categorical formulation of iteration, specifically within the context of restriction categories, which provide the foundations for the theory of partiality. While the standard categorical interpretation of iteration relies on trace operators defined on coproducts (specifically in traced coCartesian monoidal categories), this approach requires the presence of coproducts. The authors note that Kleene wand operators were previously introduced in [13] to capture iteration in restriction categories arising from complexity theory, but these were only briefly defined for distributive extensive restriction categories using the maximal interference relation. Furthermore, a full proof establishing the equivalence between Kleene wands and trace operators was not provided. The central problem is to develop a robust theory of Kleene wands that functions in settings without coproducts and to rigorously establish their equivalence to parametrized iteration and trace operators in extensive restriction categories.

Methodology
The authors develop the theory through a series of structural definitions and categorical constructions:

Interference Relations: The paper introduces the concept of an interference relation ( $\perp$ ) on a restriction category with restriction zeroes. This relation formalizes when two maps are "disjoint" (i.e., where one is defined, the other is not). The authors distinguish between the maximal interference relation ( $\perp_0$ , where disjointness is defined by $fg=0$) and other relations, noting that an interference restriction category is a pair $(\mathcal{X}, \perp)$ .
Disjoint Joins: The concept of $\perp$ -joins (joins of $\perp$ -disjoint maps) is adapted. The authors define "strong" joins, which preserve disjointness, and show how any interference restriction category can be embedded into a "disjoint" one via a construction $DJ[(\mathcal{X}, \perp)]$ .
Kleene Wands: A Kleene wand ( $\star|$ ) is defined as a binary operator on an interference restriction category that takes a map $f: X \to X$ and a disjoint map $g: X \to A$ and produces a map $f \star| g: X \to A$ . This is interpreted as iterating $f$ until the "guard" $g$ is satisfied. The axioms for Kleene wands are presented as analogues to iteration operator axioms but formulated without coproducts.
Extensive Restriction Categories: The paper reviews extensive restriction categories, which possess restriction coproducts and "decisions" (maps that separate the domain of definition of a map into parts landing in different coproduct components). The authors define a canonical interference relation ( $\perp_d$ ) on these categories induced by decisions.
Classical Setting: In the presence of relative complements (classical restriction categories), the authors show that Kleene wands are completely determined by their action on endomorphisms, leading to the definition of a "Kleene upper-star."
Matrix Construction: A matrix construction $MAT[(\mathcal{X}, \perp)]$ is introduced, which embeds a finitely disjoint interference restriction category into an extensive restriction category.

Key Contributions and Results

Definition of Itegories: The authors define an itegory as an interference restriction category with binary disjoint joins and a Kleene wand.
Equivalence in Extensive Restriction Categories: The primary result (Theorem 9.11) establishes a bijective correspondence between parametrized iteration operators (and equivalently, trace operators) on an extensive restriction category and Kleene wands defined with respect to the canonical decision-induced interference relation ( $\perp_d$ ). This proves that for extensive restriction categories, being "traced" is equivalent to being an "itegory."
Canonical Construction: In settings with countable disjoint joins, the authors demonstrate the existence of a canonical, strongly inductive Kleene wand defined by the disjoint join of all iterations ( $f \star| g = \bigsqcup_{n \in \mathbb{N}} f^n g$ ).
Classical Equivalence: For classical interference restriction categories (those with relative complements), the paper proves a bijective correspondence between Kleene wands and Kleene upper-stars (Theorem 6.9), showing that in this setting, the iteration operator is fully determined by its behavior on endomorphisms.
Matrix Representation of Traces: The paper provides a matrix calculus for extensive restriction categories. It demonstrates that computing the trace of an arbitrary $n+m \times n+p$ matrix in a traced extensive restriction category reduces to computing traces of $2 \times 2$ matrices.
Embedding Theorems: The authors show that applying the matrix construction to an itegory yields a traced extensive restriction category (Proposition 9.15). Furthermore, any restriction category with restriction zeroes can be embedded into a traced extensive restriction category via the composition of the disjoint join construction and the matrix construction (Corollary 9.18).

Significance
The paper claims that Kleene wands provide a more general notion of iteration that does not require the existence of coproducts, making them applicable to a broader class of restriction categories than traditional trace operators. By establishing the equivalence between Kleene wands and trace operators in extensive restriction categories, the work unifies the "particle style" trace (iteration) with the restriction category framework. The introduction of interference relations allows for a nuanced treatment of disjointness that is not limited to the maximal relation, correcting and generalizing previous definitions found in [13]. The results suggest that Kleene wands can serve as a primitive for interpreting imperative programming constructs (loops) within categorical models of computability, particularly in contexts where coproducts are absent or where a specific interference relation (such as recursive separability) is more appropriate than simple domain disjointness.