🔢 mathematics

Generalized Decidability via Brouwer Trees

This paper introduces a framework in homotopy type theory that generalizes decidability using Brouwer ordinals to establish a hierarchy of $\alpha$ -decidable propositions, characterizing their closure properties under logical operations and quantifiers, with all results formalized in Cubical Agda.

Original authors: Tom de Jong, Nicolai Kraus, Aref Mohammadzadeh, Fredrik Nordvall Forsberg

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tom de Jong, Nicolai Kraus, Aref Mohammadzadeh, Fredrik Nordvall Forsberg

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 a detective trying to solve a mystery. In the world of computer science, we usually sort mysteries into three buckets: Decidable (we can find the answer quickly), Semidecidable (we can find the answer if it's "yes," but if it's "no," we might wait forever), and Undecidable (we can't solve it at all).

But what if there are mysteries that are "more" semidecidable than others? What if some "yes" answers take a little longer to find than others, but still don't take forever?

That's exactly what Tom de Jong, Nicolai Kraus, Aref Mohammadzadeh, and Fredrik Nordvall Forsberg are exploring in their new paper. They suggest a way to measure exactly how long it takes to find a "yes" answer, using a special kind of number system called Brouwer tree ordinals. Think of these not as regular numbers like 1, 2, 3, but as a magical ladder of time-steps that goes way beyond infinity.

The Magic Ladder of Time

In their framework, they don't just say "it's solvable." They say, "It is $\alpha$ -decidable," where $\alpha$ is a specific rung on their magical ladder.

Level 1 (Decidable): If a problem is 1-decidable, it means you can find the answer (or prove it's impossible) in a finite number of steps. It's like checking if a number is prime; you just count up, and eventually, you know for sure.
Level $\omega + 1$ (Semidecidable): If a problem is $(\omega + 1)$ -decidable, it means if the answer is "yes," you will find it within $\omega$ steps. But $\omega$ isn't a normal number; it represents "counting forever." So, if the answer is "yes," you'll eventually find it, but if the answer is "no," you might keep counting forever without ever stopping. This is the classic definition of "semidecidable."

The authors prove that this new system fits perfectly with the old one. If you have a problem that is "decidable," it fits on rung 1. If it's "semidecidable," it fits on rung $\omega + 1$ . But the magic is that they can now talk about rungs between these, or way above them.

The Twin Prime Mystery

To show how this works, they use a famous math puzzle: the Twin Prime Conjecture. This asks: "Is there always a pair of prime numbers (like 3 and 5, or 11 and 13) that are just two numbers apart, no matter how high you count?"

Checking if one specific pair exists is easy (decidable).
Checking if any pair exists above a certain number is semidecidable (you just keep looking; if you find one, you stop).
But the big question asks if this is true for every number.

The authors show that this specific question is $\omega^2$ -decidable. Imagine $\omega$ as a single infinite line of steps. $\omega^2$ is like having an infinite number of those lines stacked on top of each other. It means that if a counter-example to the Twin Prime Conjecture exists, you could find it, but it might take you a time-span equivalent to walking through an infinite stack of infinite lines.

They also looked at what happens when you combine these problems:

AND: If you have two problems that are $\alpha$ -decidable, their "AND" (both must be true) is also $\alpha$ -decidable. It's like checking two boxes; if you can check both within the same time limit, you're good.
OR: This is trickier. If you have two problems, their "OR" (either one is true) is only guaranteed to be decidable if the time limit is small enough (specifically, if the level is something like $\omega \cdot k + n$ ). If the time limit gets too huge, the "OR" might break the rules of their system.

The "Choice" Problem

Here is where it gets really interesting. The authors found that if you want to combine an infinite number of "semidecidable" problems (like checking the Twin Prime Conjecture for every starting number), you run into a wall. Without a special mathematical rule called Countable Choice, you can't prove that the combined result is semidecidable.

In fact, they proved that if you could prove it without that rule, it would break other fundamental laws of logic. So, they suggest that to make the math work smoothly for infinite combinations, you need to assume Countable Choice.

However, they also found a workaround! They looked at a different type of "semidecidable" called Sierpiński-semidecidable. This is a slightly weaker version that does allow you to combine infinite lists without needing the Countable Choice rule. It's like having a different kind of flashlight that doesn't work quite as brightly as the original, but it doesn't need a battery (the Choice rule) to turn on.

What They Didn't Solve

It's important to know what this paper doesn't do. The authors are very clear: they haven't solved the Twin Prime Conjecture. They just used it as a toy example to show how their new measuring stick works.

They also admit they don't know the full shape of their ladder yet. They suspect that if you have a problem on rung $\alpha$ and another on rung $\beta$ , and $\alpha$ is lower than $\beta$ , then the problem on $\alpha$ should also be solvable on $\beta$ . But they haven't proved this for every single rung on the ladder yet. It's a "conjecture" (a strong guess), not a fact.

The Bottom Line

This paper suggests a new way to talk about how hard it is to find a "yes" answer in math and computing. Instead of just saying "we can find it" or "we can't," they give us a precise ruler made of infinite steps. They proved that this ruler works for the things we already know (decidable and semidecidable), and they used it to measure complex problems like the Twin Prime Conjecture, finding that they sit at a specific, measurable height of $\omega^2$ .

They also showed that while this ruler is powerful, it has limits: combining infinite lists of problems requires a specific assumption (Countable Choice) unless you switch to a slightly different kind of ruler (Sierpiński-semidecidability).

All of this was built and checked inside a computer program called Cubical Agda, which acts like a super-strict referee to make sure every single step of their logic is perfect. So, while the ideas are new and exciting, the math behind them is rock-solid.

Technical Summary: Generalized Decidability via Brouwer Trees

Problem Statement
In constructive mathematics and synthetic computability theory, the standard classification of propositions into "decidable," "semidecidable," or "undecidable" is often too coarse. For instance, while the decidability of primality is clear, the status of the Twin Prime Conjecture (whether a twin prime pair exists above any $n$ ) involves a structure of $\omega$ -many semidecidable sub-problems. Classically, this might be viewed as a limit of limits, but constructive frameworks require a more precise way to measure the "duration" or complexity of the search for evidence. Existing notions of ordinals (e.g., syntactic Cantor Normal Forms or semantic well-founded relations) fail to provide a suitable hierarchy: syntactic approaches make all comparisons decidable (collapsing the hierarchy), while semantic approaches often fail to make comparisons semidecidable. The paper addresses the need for a framework that allows for finer distinctions in decidability, specifically to characterize propositions that require transfinite steps to verify.

Methodology
The authors work within Homotopy Type Theory (HoTT), utilizing Brouwer tree ordinals ( $\text{Brw}$ ) as the foundation for their hierarchy. These ordinals are defined via a quotient inductive-inductive type (QIIT) containing constructors for zero, successors, and limits of strictly increasing sequences. Crucially, the limit constructor accepts only strictly increasing sequences, which ensures that finiteness is decidable while preserving the constructive nature of the theory.

The core definition introduced is $\alpha$ -decidability: A proposition $P$ is $\alpha$ -decidable if there exists an ordinal $y$ such that $P \leftrightarrow (\alpha \leq y)$ . This definition generalizes existing concepts:

$1$-decidability (or $\omega$ -decidability) corresponds to standard decidability.
$(\omega + 1)$ -decidability (equivalent to $\omega \cdot 2$ -decidability) corresponds to semidecidability.

The authors formalize all results in Cubical Agda, leveraging native support for QIITs and univalence. They employ specific techniques to handle the complexity of defining functions on QIITs, such as defining relations on point constructors first and extracting functions later to avoid combinatorial explosion in path constructor handling.

Key Contributions and Results

Hierarchy of Decidability:
- The paper establishes that $\alpha$ -decidability generalizes decidability and semidecidability.
- It is shown that for any ordinal $\alpha$ , $(\alpha+1)$ -decidability is equivalent to $(\alpha+\omega)$ -decidability. Consequently, the hierarchy can be effectively indexed by limit ordinals (non-successor ordinals).
- The authors prove that if $P$ is $\alpha$ -decidable and $Q$ is $\alpha$ -decidable, then $P \land Q$ is $\alpha$ -decidable. This relies on constructing a binary minimum function for non-successor ordinals, which is not generally possible for arbitrary ordinals without implying the Limited Principle of Omniscience (LPO).
Disjunction and Maxima:
- While conjunction is closed at the same level, binary disjunction is not closed for arbitrary $\alpha$ . However, the authors prove that $(\omega \cdot k + n)$ -decidable propositions are closed under binary disjunction. This requires constructing a binary maximum function relative to ordinals of the form $\omega \cdot k$ .
- The existence of global binary maxima for non-successors is shown to imply LPO, a constructive taboo.
Countable Quantifiers and Families:
- Countable Meets: For a family of semidecidable propositions $P: \mathbb{N} \to \text{Prop}$ , the countable meet $\forall i. P(i)$ is proven to be $\omega^2$ -decidable. This result is applied to the Twin Prime Conjecture, characterizing it as $\omega^2$ -decidable.
- Countable Joins: The countable join $\exists i. P(i)$ of semidecidable propositions is shown to be $(\omega \cdot 3)$ -decidable.
- Quantifier Alternations: The paper analyzes formulas with alternating quantifiers. For a family $P(n, m)$ where $P(n, m) \to P(n, m+1)$ , the proposition $\exists m. \forall n. P(n, m)$ is shown to be $(\omega^2 + \omega)$ -decidable. This provides a precise ordinal bound for the search for counter-examples to the Twin Prime Conjecture.
Relationship with Choice Principles:
- The authors investigate the impact of Countable Choice (AC). Assuming AC, the countable join of semidecidable propositions becomes semidecidable (i.e., $(\omega \cdot 3)$ -decidable collapses to $(\omega \cdot 2)$ -decidable).
- However, even with AC, $\omega^2$ -decidable propositions do not collapse to semidecidable ones unless Markov's Principle implies LPO.
- The paper introduces Sierpiński-semidecidability (based on the Sierpiński type, the free $\omega$ -complete partial order) as an alternative notion of semidecidability that is closed under countable joins without assuming Countable Choice. It is shown that Sierpiński-semidecidability is weaker than standard semidecidability.

Significance and Claims
The authors position this work as the first step towards a theory of generalized decidability. They claim to provide a framework where the "duration" of algorithms (in a constructive, abstract sense) can be precisely specified and proven using ordinal arithmetic.

The paper modestly notes that it does not solve open problems like the Twin Prime Conjecture itself; rather, it provides a formal language to describe the complexity of such problems. It highlights that the hierarchy of decidability is not fully understood, specifically noting that it remains an open question whether $\alpha$ -decidability implies $\beta$ -decidability for all $\alpha \leq \beta$ (though partial results are provided). The work also leaves open the question of whether Brouwer tree ordinals are the optimal notion for this theory or if alternative ordinal constructions could yield different, potentially richer, hierarchies.

All results are rigorously formalized in Cubical Agda, ensuring that the constructive nature of the proofs is maintained and that the definitions of ordinals and their properties are computationally sound within the type theory.