🔢 mathematics

The reverse mathematics of the pigeonhole hierarchy

This paper establishes that the hierarchy of infinite pigeonhole principles, when restricted to various levels of the arithmetic hierarchy, is strict over $\mathsf{RCA}_0$ by employing an iterated jump control construction and analyzing its first-order consequences from both computability-theoretic and reverse mathematical perspectives.

Original authors: Quentin Le Houérou, Ludovic Levy Patey, Ahmed Mimouni

Published 2026-07-31

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Quentin Le Houérou, Ludovic Levy Patey, Ahmed Mimouni

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, but instead of looking for fingerprints, you are hunting for the absolute minimum amount of "logic power" needed to prove a mathematical truth. This field is called Reverse Mathematics. Usually, mathematicians start with a set of powerful rules (axioms) and try to prove a theorem. Reverse mathematicians do the opposite: they start with a theorem and ask, "What is the weakest possible set of rules that can still prove this?" They want to find the "Goldilocks" zone of logic—not too weak, not too strong, just right.

At the heart of this investigation is a simple idea called the Pigeonhole Principle. You've probably heard the version: "If you have 10 pigeons and 9 holes, at least one hole must contain more than one pigeon." In the infinite world of math, this translates to: "If you color every whole number with one of a few colors, there must be an infinite group of numbers that are all the same color." While this sounds obvious, the way you prove it depends on how complicated the "colors" (or the rules for assigning them) are. Some colors are simple and easy to spot; others are hidden behind layers of complexity. The big question is: Does a more complex color require a more powerful logical system to find the matching group?

This paper, written by Quentin Le Houérou, Ludovic Lévy-Patey, and Ahmed Mimouni, dives deep into this question. They treat the Pigeonhole Principle not as a single rule, but as a hierarchy—a ladder of difficulty. They ask: If the "pigeons" are defined by increasingly complex mathematical rules, do we need to climb higher up the ladder of logical power to find our infinite group?

The Great Ladder of Logic

The authors discovered that the answer is a definitive yes. They proved that the hierarchy of pigeonhole principles is strict. This means that each step up the ladder of complexity requires a genuinely stronger logical system. You cannot skip a rung. If you have a set of numbers defined by a slightly more complex rule (what they call a $\Sigma^0_{n+1}$ set), you cannot find an infinite group of them using the same logical tools that work for the simpler rule below it (the $\Sigma^0_n$ set).

To visualize this, imagine trying to find a specific type of needle in a haystack.

Level 1: The needles are bright red. You can find them with a simple flashlight (basic logic).
Level 2: The needles are invisible to the naked eye but glow in the dark. You need a special UV light (a slightly more complex logical system).
Level 3: The needles are invisible even in UV light; they only appear if you shake the hay in a specific way. You need a whole new gadget (an even stronger logical system).

The paper proves that you cannot use the UV light to find the Level 3 needles. Each level of complexity demands its own unique tool. The authors didn't just guess this; they built a rigorous mathematical construction, using a technique called iterated jump control. Think of this as a sophisticated "filtering machine." They constructed specific mathematical worlds (called $\omega$ -models) where the rules of the lower levels hold true, but the rules of the higher levels fail. By showing that you can build a world where the "Level 2" tools work but the "Level 3" tools don't exist, they proved that the levels are truly distinct. This separation in these mathematical worlds confirms that the hierarchy is strict over the base system, RCA0.

Breaking the "Big Five"

In the world of Reverse Mathematics, there is a famous observation called the "Big Five." It turns out that almost every mathematical theorem you can think of falls into one of five specific categories of logical strength. However, the Pigeonhole Principle (and its cousin, Ramsey's Theorem) has always been a rebel, refusing to fit neatly into these five boxes.

This paper settles a long-standing debate about how these rebels behave. Previously, some researchers wondered if the different levels of the Pigeonhole hierarchy were actually just different ways of saying the same thing, or if they were truly distinct. The authors proved they are distinct. They also showed that a specific version of the principle (called $\Sigma^0_2$ -Subset) is strong enough to prove a theorem about topological spaces (the Ginsburg-Sands theorem), but it doesn't require too much extra power to do so. In fact, they proved that adding this principle to the base system doesn't accidentally unlock any new "first-order" truths (basic arithmetic facts) that weren't already there. It's like adding a new tool to your toolbox that helps you build a specific type of house, but doesn't suddenly give you the ability to build a spaceship.

The "Weak" vs. "Strong" Showdown

One of the most exciting parts of the paper is how they separated two very similar-looking principles: $\Delta^0_n$ -Subset and $\Sigma^0_n$ -Subset.

$\Delta^0_n$ is like a rule where you can check if a number belongs to the group by asking two questions: "Is it in?" and "Is it out?" If both answers are clear, you know the truth.
$\Sigma^0_n$ is trickier. It's like a rule where you can only check "Is it in?" and you have to wait forever to be sure if it's "out."

The authors proved that the "tricky" version ( $\Sigma^0_n$ ) is strictly harder than the "clear" version ( $\Delta^0_n$ ). They did this by showing that the "tricky" version can break certain "hyperimmune" functions—mathematical functions that grow so fast they can't be tamed by the simpler logical systems. The "clear" version, however, is too weak to break these fast-growing functions. This separation is a major victory because it confirms that the complexity of the definition of the set directly translates to the complexity of the logic needed to solve it.

What's Left in the Mystery Box?

While the authors solved the main mystery of the hierarchy's strictness, they left a few doors open for future detectives. They didn't prove whether the Pigeonhole Principle implies the very strongest induction rules (like $I\Sigma^0_2$ ) or whether it can solve certain deep problems about the order of numbers. They also didn't settle whether a specific version of the principle ( $\Delta^0_2$ -Subset) is conservative over a slightly different base system. These are the next clues for the next generation of mathematicians to chase.

In short, this paper maps out the terrain of infinite logic with incredible precision. It shows us that the Pigeonhole Principle isn't just one simple trick; it's a vast, multi-layered landscape where every step up requires a new kind of mental muscle. And thanks to this work, we now know exactly how strong that muscle needs to be at every single step.

Technical Summary: The Reverse Mathematics of the Pigehole Hierarchy

Problem Statement
The infinite pigeonhole principle for $k$ colors ( $RT^1_k$ ) asserts that for every $k$ -partition of the natural numbers, there exists an infinite subset contained entirely within one of the partition classes. While $RT^1_2$ is the foundational basis of Ramsey's theory, its computational content and reverse mathematical strength vary significantly when instances are restricted to specific levels of the arithmetical hierarchy.

The paper investigates the hierarchy of pigeonhole principles defined by restricting instances to $\Sigma^0_n$ and $\Delta^0_n$ sets (denoted $\Sigma^0_n$ -Subset and $\Delta^0_n$ -Subset). The central problem is to determine the precise logical strength and computational content of these principles. Specifically, the authors address whether the hierarchy is strict (i.e., whether $\Sigma^0_n$ -Subset is strictly stronger than $\Delta^0_n$ -Subset and $\Delta^0_{n+1}$ -Subset) and characterize the first-order consequences of these principles over the base theory $RCA_0$ . Previous work by Benham et al. [2] established connections between these principles and topological theorems (Ginsburg-Sands theorem) but left open questions regarding the strictness of the hierarchy and the existence of specific basis theorems (e.g., weakly low basis) for higher levels.

Methodology
The authors employ effective forcing techniques within the framework of reverse mathematics and computability theory. The core methodology relies on iterated jump control, a technique developed by Monin and Patey [32, 34], which allows for the construction of solutions that preserve specific computability-theoretic weaknesses (such as lowness or hyperimmunity) of the ground model.

Key technical components include:

Forcing with Trees and Scott Ideals: The authors utilize variants of Mathias forcing where reservoirs belong to Scott ideals (collections of sets closed under Turing reducibility and effective join). To achieve higher-order jump control, they introduce largeness towers and Scott towers, which are hierarchies of Scott ideals and associated "large" classes (partition regular classes) that ensure the reservoirs maintain sufficient positive information about the constructed sets.
Forcing Questions: A critical innovation is the definition of forcing questions with specific definitional complexities. A forcing question for a class of formulas $\Gamma$ $Γ$ allows the construction to decide $\Gamma$ $Γ$ -properties without increasing the complexity of the solution's jump. The authors define:
- Main Forcing ( $MA^A_n$ ): Used when the instance set $A$ belongs to a specific partition regular class.
- Witness Forcing ( $WA^A_n$ ): Used when $A$ does not belong to the class, requiring a "witness" (a large class excluding $A$ ) to guide the construction.
- Disjunctive Forcing ( $DA^A_n$ ): A novel notion used to simultaneously preserve hyperimmunities at different jump levels. It involves conditions with two stems sharing a reservoir, allowing the construction to decide between two outcomes (preserving hyperimmunity for one side or the other).
Compactness and Merging: The authors prove that their forcing questions are compact (allowing bounds on existential quantifiers) and merging (allowing the combination of forcing conditions to preserve induction schemes). These properties are essential for proving conservation theorems and separation results.

Key Contributions and Results

Strictness of the Hierarchy:
The paper proves that the hierarchy of pigeonhole principles is strict over $RCA_0$ . Specifically, for every $n \ge 1$ :
$\Sigma^0_n\text{-Subset} < \Delta^0_{n+1}\text{-Subset} < \Sigma^0_{n+1}\text{-Subset}$
This is achieved by constructing $\omega$ -models that satisfy the lower principle but fail the higher one. The separation relies on hyperimmunity preservation: $\Delta^0_n$ -Subset preserves hyperimmunity at levels $\{n-2, n-1\}$ , whereas $\Sigma^0_n$ -Subset does not.
Basis Theorems:
The authors establish new basis theorems for the pigeonhole principles:
- Weakly Low Basis: For every $n \ge 1$ , every computable instance of $\Sigma^0_{n+1}$ -Subset admits a solution $H$ such that $H^{(n)}$ is computable from any PA degree over $\emptyset^{(n)}$ . This disproves a conjecture by Benham et al. [2] and generalizes previous results for $\Delta^0_2$ -Subset.
- Iterated Lowness: Every $\Sigma^0_{n+1}$ instance admits a solution of $low^{n+1}$ degree.
- Hyperimmunity Preservation: For $\Delta^0_{n+1}$ -Subset, the authors prove that for any $\emptyset^{(n-1)}$ -hyperimmune function $f$ and $\emptyset^{(n)}$ -hyperimmune function $g$ , there exists a solution $H$ such that $f$ remains $H^{(n-1)}$ -hyperimmune and $g$ remains $H^{(n)}$ -hyperimmune.
Conservation Theorems:
The paper proves that adding $\Sigma^0_n$ -Subset to $RCA_0 + I\Sigma^0_n$ does not increase the first-order strength of the theory.
- Main Theorem: For $n \ge 2$ , $RCA_0 + I\Sigma^0_n + \Sigma^0_n\text{-Subset}$ is $\Pi^1_1$ -conservative over $RCA_0 + I\Sigma^0_n$ .
- Application: This implies that the Ginsburg-Sands theorem for $T_1$ -spaces is $\Pi^1_1$ -conservative over $RCA_0 + I\Sigma^0_2$ .
- Non-Conservation: Conversely, the paper shows that $RCA_0 + \Delta^0_{n+2}\text{-Subset}$ is not $\Pi^1_1$ -conservative over $RCA_0 + B\Sigma^0_{n+1}$ , highlighting a distinction between the $\Sigma^0$ and $\Delta^0$ levels regarding their interaction with bounded induction.

Significance
The paper claims to resolve multiple open questions regarding the computational content of Ramsey-type theorems. By extending the iterated jump control framework to higher levels of the arithmetical hierarchy, the authors provide a unified analysis of the pigeonhole principle that:

Clarifies the structure of Ramsey theory: It demonstrates that the complexity of Ramsey's theorem for pairs ( $RT^2_2$ ) is deeply rooted in the $\Delta^0_2$ -Subset principle, and that the hierarchy of pigeonhole principles is strictly increasing in strength.
Advances forcing techniques: The introduction of disjunctive forcing and the refinement of forcing questions for iterated jumps provide new tools for analyzing combinatorial principles that require simultaneous preservation of multiple computability-theoretic properties.
Connects to topology: It solidifies the link between the Ginsburg-Sands theorem and the pigeonhole principle, showing that the topological theorem's strength is exactly captured by the combination of cohesiveness and $\Sigma^0_2$ -Subset.

The authors note that while the strictness of the hierarchy is now established, questions remain regarding the first-order consequences of $\Sigma^0_n$ -Subset (specifically whether it implies $I\Sigma^0_2$ ) and the conservation status of $\Delta^0_2$ -Subset over $B\Sigma^0_2$ . The paper positions these results as part of a broader meta-mathematical program to understand the computational content of combinatorial theorems.

The Great Ladder of Logic

Breaking the "Big Five"

The "Weak" vs. "Strong" Showdown

What's Left in the Mystery Box?

More like this