💻 computer science

Proving and Computing: The Infinite Pigeonhole Principle and Countable Choice

This paper demonstrates the expressive power of combining structural corecursion with classical control operators like `callcc` by presenting a novel corecursive proof of the Infinite Pigeonhole Principle and an implementation of the Axiom of Countable Choice that justifies termination through coiteration alone, contrasting with traditional continuation-passing approaches relying on external termination arguments.

Original authors: Zena M. Ariola, Paul Downen, Hugo Herbelin

Published 2026-03-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Zena M. Ariola, Paul Downen, Hugo Herbelin

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 an endless hallway. The hallway is lined with doors, and behind every door is either a Red Ball or a Blue Ball. You don't know the pattern; it could be random, it could be chaotic, or it could be a secret code.

Your mission, based on a famous mathematical rule called the Infinite Pigeonhole Principle, is to find a "secret tunnel" through this hallway. You need to find a path where you only see Red Balls, or a path where you only see Blue Balls. Since the hallway is infinite, math guarantees that at least one of these colors must appear over and over again forever.

The paper you asked about is about how to build a robot that can find this secret tunnel. But there's a catch: the robot has to be smart enough to change its mind if it starts walking down the wrong path.

Here is the breakdown of the paper's ideas using simple analogies:

1. The Two Ways to Build a Robot: Recursion vs. Corecursion

Think of programming as building a machine.

Recursion (The Standard Way): Imagine you are counting down a stack of plates. You take one off, count it, and move to the next. You know exactly when you will stop because the stack is finite. This is how most computer programs work: they take an input, break it down, and eventually give you an answer.
Corecursion (The "Infinite" Way): Now, imagine you are building a never-ending conveyor belt of toys. You don't know when it will stop because it never stops. You just keep adding the next toy to the belt as long as the machine is running. This is Corecursion. It's used to handle infinite data, like a live video stream or a continuous weather feed.

The authors of this paper are experts in Corecursion. They want to show that this "infinite conveyor belt" technique is incredibly powerful, especially when combined with a special "superpower" called Classical Logic.

2. The Superpower: The "Time-Travel" Button (Control)

In the world of standard math and programming, once you make a decision, you can't take it back. But the authors use a tool called callcc (which stands for "call with current continuation").

Think of this as a Time-Travel Button or a Save-Game Feature in a video game.

You start walking down the hallway.
You hit the "Save" button (this is callcc).
You walk forward.
Suddenly, you realize, "Oh no! I'm walking into a wall of Blue Balls, but I was supposed to find Red!"
Because you hit the Save button, you can rewind to that exact moment, erase your memory of the Blue Balls, and say, "Okay, let's try looking for Blue Balls instead!"

This ability to "backtrack" and change your mind is what makes Classical Logic work in a computer. It allows the program to guess, check, and if the guess is wrong, instantly rewind and try a different path without crashing.

3. The Main Mission: The Infinite Pigeonhole Principle

Let's go back to our Red/Blue Ball hallway.

The Problem: You need to output a list of door numbers that only contain Red Balls (or only Blue Balls).
The Trap: If you just look at the first few doors, you might see Red, Red, Red. You guess, "It's a Red tunnel!" You start listing those doors. But then, suddenly, you hit a Blue ball. Your list is now wrong!
The Solution (The Paper's Method):
1. The robot starts by guessing "Red."
2. It saves its progress (hits the Time-Travel button).
3. It walks forward. As long as it sees Red, it adds the door number to the list.
4. The Twist: If it hits a Blue ball, it doesn't stop. It hits the Time-Travel button, rewinds to the start, and says, "Okay, my guess was wrong. Let's try to find a Blue tunnel instead."
5. It starts listing Blue doors.
6. The Magic: If it later sees another Red ball, it can rewind again and switch back to looking for Red.

Because the hallway is infinite, the robot will eventually settle on the color that appears forever. The "Time-Travel" button allows it to be flexible and correct its own mistakes in real-time.

4. Why is this better than the old way?

The paper compares their method to a previous method by other researchers (Escardó and Oliva).

The Old Way (The "Blind" Approach): Imagine a robot that picks a color (say, Red) and refuses to change its mind. If it hits a Blue ball, it has to do a complex, indirect mathematical trick to prove that a Blue tunnel must exist somewhere else. It's like solving a maze by looking at a map from space rather than walking through it. It works, but it's rigid and hard to understand.
The New Way (The "Flexible" Approach): The authors' robot is like a human explorer. It walks, gets confused, says "Oops," and turns around. It uses the Time-Travel button to physically retrace its steps. This is much more direct, efficient, and easier to turn into actual computer code.

5. The "Countable Choice" Bonus

The paper also tackles a second problem called the Axiom of Countable Choice.

The Analogy: Imagine you have an infinite line of people. Behind every person is a locked box. You know that every box contains a prize, but you don't know which specific prize is in which box. You need to write down a list: "Person 1 gets Prize A, Person 2 gets Prize B," etc.
The Challenge: In standard math, you can't just "pick" a prize from a box without opening it. But with the authors' "Time-Travel" robot, it can peek into the boxes, make a guess, and if the guess is wrong, rewind and try a different prize. It builds the list of prizes dynamically, ensuring that every person gets a valid prize, all while using the infinite conveyor belt (Corecursion) to keep the list going forever.

Summary

This paper is about teaching computers how to be flexible explorers in an infinite world.

Instead of being rigid and stuck on one path, the computer uses Corecursion (an infinite conveyor belt) to keep generating data.
It uses Classical Logic (a Time-Travel button) to backtrack and change its mind when it hits a dead end.
This allows it to solve complex puzzles (like finding a constant color in an infinite stream) much more naturally and efficiently than previous methods.

The authors are essentially saying: "Don't just build a robot that follows a script. Build a robot that can think, guess, make mistakes, and instantly fix them, all while walking down an infinite hallway."

Technical Summary: Proving and Computing: The Infinite Pigeonhole Principle and Countable Choice

Authors: Zena M. Ariola, Paul Downen, and Hugo Herbelin
Context: A tribute to Stefano Berardi, focusing on the intersection of classical logic, control operators, and coinduction.

1. Problem Statement

The paper addresses the limitations of structural corecursion in modern functional programming and proof assistants (like Rocq/Coq and Agda). While structural recursion is a standard, well-understood technique for finite data, its dual—structural corecursion for infinite data (streams)—is often restricted to pure functional settings.
The authors identify two specific challenges:

Expressiveness Gap: Standard corecursion (coiteration) cannot easily handle algorithms that require "backtracking" or changing strategy based on future observations of an infinite stream.
Classical Logic Implementation: Many classical principles, such as the Infinite Pigeonhole Principle (IPP) and the Axiom of Countable Choice (ACC), traditionally rely on general recursion with externally postulated termination or double-negation translations. The authors aim to provide direct computational interpretations of these principles using classical control operators (specifically callcc) combined with corecursion, thereby justifying termination through coinduction alone.

2. Methodology

The authors utilize the Rocq proof assistant (formerly Coq) to formalize their approach. Their methodology involves:

Defining Streams with Laziness: They address extraction issues in call-by-value languages (like OCaml) by explicitly delaying the tail of streams (unit -> stream A) to prevent eager evaluation of infinite computations.
Hierarchy of Corecursion Patterns: They define and compare three patterns of corecursion:
1. Coiteration (Anamorphism): Generates streams from a seed; cannot stop early.
2. Minimal Corecursion (Apomorphism): Allows the corecursion to stop and return a pre-defined stream remainder.
3. Classical Corecursion: Introduces first-class continuations (callcc). This allows the corecursive step to capture the caller's context, enabling the program to "pause," backtrack, and resume the computation with a different state or strategy.
Program Extraction: They extract Rocq proofs into OCaml (using delimited control libraries) and Scheme to demonstrate executable behavior.
Proof Construction: They construct proofs where the computational content (the program) is directly derived from the logical derivation, ensuring the extracted code is a faithful implementation of the proof.

3. Key Contributions

A. Classical Corecursion with callcc
The paper introduces a novel corecursive pattern that combines coinduction with the callcc control operator. Unlike standard corecursion, which proceeds linearly, this pattern allows the generation of a stream to be interrupted and restarted. The callcc operator captures the continuation of the "tail" request, allowing the program to:

Make a guess about the stream's properties.
If the guess is proven wrong by future data, backtrack to the captured continuation.
Resume the stream generation with a corrected strategy without restarting the entire computation from scratch.

B. Computational Proof of the Infinite Pigeonhole Principle (IPP)
The authors provide a direct, corecursive proof of the IPP, which states that any infinite sequence of Boolean values contains an infinite constant subsequence.

The Algorithm: The program infinite_bool guesses that the first element of the stream occurs infinitely often. It generates indices for this value. If it encounters the opposite value, it uses callcc to backtrack, switch the target value to the opposite, and resume generating indices from the current position.
Comparison: They contrast this with the Escardó and Oliva proof in Agda, which uses a double-negation translation and general recursion. The authors' approach is "symmetric" (it can switch between true and false based on observation) and relies on coiteration for termination justification, whereas the Agda proof is "asymmetric" and relies on general recursion.

C. Implementation of the Axiom of Countable Choice (ACC)
The paper demonstrates that the Double-Negated Axiom of Countable Choice (a classical principle) can be implemented using only coiteration and control, eliminating the need for general recursion.

They interpret the logical statement $\forall n. \neg\neg \exists x. R(n, x) \to \neg\neg \exists f. \forall n. R(n, f(n))$ as a stream transformation.
By viewing the stream of double-negated existentials as a coinductive object, they show that callcc can distribute the double negation over the stream, effectively constructing the choice function $f$ through coiteration.

4. Results

Executable Programs: The authors successfully extracted OCaml and Scheme code that implements the IPP solver. The code demonstrates dynamic adaptation: if a user requests a small number of indices, the program might return indices for one Boolean value; if the request is expanded, the program backtracks and corrects the stream to provide a consistent set of indices for the other value if the first guess was insufficient.
Termination Justification: The extracted programs terminate (produce finite prefixes) not because of a global termination metric, but because the coinductive structure guarantees that the stream is well-formed, and the control operators manage the state transitions correctly.
Comparison with Escardó/Oliva: The authors show that their corecursive approach yields different (and often more flexible) results than the Agda-based indirect proof. Specifically, their approach can handle "irregular" streams where the infinite constant subsequence is not the one starting at index 0, by dynamically switching strategies.

5. Significance

Bridging Logic and Computation: The work provides a concrete computational interpretation of classical reasoning principles (like the Law of Excluded Middle and Countable Choice) using control operators, moving beyond abstract double-negation translations.
Advancing Corecursion: It elevates structural corecursion from a technique for generating infinite data to a powerful tool for interactive computation and search, capable of handling non-deterministic choices and backtracking in infinite domains.
Proof Extraction: It demonstrates that complex classical proofs can be extracted into efficient, terminating programs without relying on external axioms for termination, provided the logic is enriched with control operators.
Foundational Insight: The paper clarifies the relationship between different formulations of the Infinite Pigeonhole Principle, showing how the choice of data representation (streams vs. functions) and logical formulation (direct vs. double-negated) impacts the resulting algorithm's structure and behavior.

In summary, this paper establishes that classical corecursion (corecursion + callcc) is a robust framework for extracting constructive content from classical proofs, offering a more direct and flexible alternative to traditional continuation-passing style (CPS) or general recursion-based approaches.