💻 computer science

Four Paradoxes and a Proof Assistant: Burali-Forti, Diaconescu, Reynolds, and Hurkens in the coq-paradoxes library

This article analyzes the four paradoxes mechanized in the coq-paradoxes library to demonstrate how they collectively define the necessary design boundaries of the Rocq kernel—specifically regarding impredicativity, large elimination, and universe constraints—by illustrating the precise reasons the system must reject certain constructions to maintain consistency.

Original authors: Bernardo Alonso

Published 2026-05-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Bernardo Alonso

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 have a very strict, very smart robot architect named Rocq. Its job is to build logical structures (math proofs) that are guaranteed to be safe and consistent. It never crashes, never lies, and never produces a contradiction.

But how do you know the robot is doing its job correctly? You don't just watch it build; you try to trick it. You try to feed it a blueprint that looks like it should work but actually contains a hidden trap that would cause the whole building to collapse.

This paper is about a special library of "trap blueprints" called coq-paradoxes. It contains four specific attempts to break the robot's logic. The paper argues that these aren't just puzzles or curiosities; they are actually the robot's safety manual written in reverse. They show exactly where the robot's rules are drawn to prevent disaster.

Here is a breakdown of the four traps and what they teach us, using simple analogies:

1. The Burali-Forti Trap: The "Box That Contains Itself"

The Trap: Imagine a library where every book has a label describing its own contents. The paradox tries to create a "Master Catalog" that lists every single book in the library, including the Master Catalog itself.
The Problem: If the catalog is a book, it must list itself. But if it lists itself, it changes the size of the library, which changes the catalog, which changes the library... it's a loop that breaks the rules of size.
The Lesson: The robot (Rocq) has a rule about Universe Hierarchy. It says, "A box cannot be inside a box that is the same size as itself." The robot refuses to build the Master Catalog because the math says the "inner box" must be smaller than the "outer box." This trap proves that the robot is correctly enforcing a strict size limit to prevent infinite loops.

2. The Diaconescu Trap: The "Magic Coin Flipper"

The Trap: Imagine you have a machine that can pick a "winner" from any group of tied options (like picking a representative from a group of identical twins). The paradox says: "If you give me this machine, I can force it to tell me the answer to any yes/no question (like 'Is the sky blue?') without actually knowing the answer."
The Problem: In a constructive system (where you must build the answer, not just guess it), having a machine that picks winners from ties is too powerful. It secretly forces the system to accept "Either A is true OR A is false" for everything, even things we can't prove yet.
The Lesson: The robot has a rule about Large Elimination. It says, "You can pick a winner from a group of numbers, but you cannot use that to magically decide a philosophical truth." This trap shows that if the robot allowed this kind of "magic choice," it would accidentally break the system's ability to distinguish between things we know and things we don't.

3. The Reynolds Trap: The "Dictionary That Can't Exist"

The Trap: Imagine trying to create a dictionary where every possible definition is a word in the dictionary. The paradox tries to build a "Universal Dictionary" that maps every possible sentence to a single word.
The Problem: This is like trying to fit a map of the entire world onto a single postage stamp. The math proves that if you try to compress all possible logical statements into a single type of object, you create a contradiction (similar to how you can't list all possible lists).
The Lesson: The robot has a rule about Impredicativity (allowing a definition to refer to the whole group it belongs to). The robot allows this for "Propositions" (simple true/false statements) but draws a hard line elsewhere. This trap shows that if the robot allowed this kind of "universal dictionary" for complex types, the whole system would collapse.

4. The Hurkens Trap: The "Self-Referential Mirror"

The Trap: This is the most complex one. Imagine a mirror that reflects a reflection, which reflects a reflection, forever. The paradox tries to build a system where you can look at a "small" object (like a boolean true/false) and use it to define a "big" object (like a whole universe of types), and then use that big object to define the small one again.
The Problem: It's a "self-referential loop" that combines the ability to look at big things and small things in a way that creates a logical paradox. It's like a snake eating its own tail, but the tail is made of the snake's own body.
The Lesson: The robot has a rule about Impredicativity in Set. It says, "You can be self-referential with simple true/false statements, but you cannot mix that with big, complex types." This trap proves that if the robot allowed this mix, it would be impossible to keep the system consistent.

The Big Picture: Why This Matters

The paper argues that we shouldn't look at these four files as "failed math." Instead, we should look at them as evidence of the robot's success.

Negative Specification: Think of these files as a "Wanted" poster for a criminal. The criminal is "Inconsistency." The poster doesn't show the criminal; it shows the exact conditions under which the criminal would appear.
The Boundary: The robot (Rocq) has drawn three invisible lines in the sand:
1. Size Limits: You can't put a box inside a box of the same size.
2. Choice Limits: You can't use a simple choice to force a complex truth.
3. Reflection Limits: You can't mix simple self-references with complex types.

Every time a user tries to build a structure that crosses one of these lines, the robot stops them. These four files are the proof that the robot is doing exactly what it was designed to do: refusing to build anything that would eventually fall down.

In short, the paper says: "We tried to break the system with these four clever tricks. The system said 'No.' That 'No' is the most important part of the system, because it keeps everything safe."

Technical Summary: Four Paradoxes and a Proof Assistant

Problem Statement
The paper addresses the foundational boundaries of the Calculus of Inductive Constructions (CIC), the type theory underpinning the Rocq proof assistant (formerly Coq). While the consistency of CIC is well-established, the specific design decisions that prevent inconsistency—particularly regarding impredicativity, universe constraints, and large elimination—are often treated as abstract engineering constraints. The coq-paradoxes library, distributed with Rocq, contains four mechanized derivations of False (Burali-Forti, Diaconescu, Reynolds, and Hurkens) that rely on hypotheses rejected by the Rocq kernel. The central problem is to interpret these derivations not merely as historical curiosities or isolated inconsistencies, but as a "negative specification" that precisely delineates where the kernel must draw its lines to maintain soundness.

Methodology
The paper employs a close reading of the source code within the coq-paradoxes library, specifically analyzing four files: BuraliForti.v, diaconescu.v, Reynolds.v, and Hurkens_Set.v. The methodology involves:

Deconstructing Shared Machinery: Analyzing Logics.v to understand the accessibility predicate (ACC) and well-foundedness infrastructure used by multiple paradoxes.
Tracing Derivations: Following the logical steps in each file to identify the specific hypothesis (e.g., a universal type of relations, a choice principle, or an injection from Prop to a single proposition) that leads to a contradiction.
Mapping to Kernel Rejections: Correlating the point of contradiction in the formalization with the specific mechanism in the Rocq kernel (universe arithmetic, elimination rules, or impredicativity checks) that prevents the construction from compiling.
Synthesizing Design Decisions: Aggregating the findings to extract three unified boundary conditions governing the kernel's behavior.

Key Contributions and Results

The paper analyzes four specific paradoxes, demonstrating how each exposes a distinct vulnerability in the type theory if certain design choices were altered:

Burali-Forti Paradox (BuraliForti.v):
- Mechanism: Assumes a universal type of relations $A_0$ and an injection $i_0$ that maps relations to elements of $A_0$ . This allows the construction of an "ordinal of all ordinals" ( $\Omega$ ) which is embedded in itself.
- Kernel Rejection: The paradox relies on instantiating $A_0$ with itself. The Rocq kernel enforces strict universe stratification ( $Type_j < Type_i$ ) to prevent a type from containing its own image. The construction triggers a "Universe Inconsistency" error because the universe level required for the inner type must be at least as large as the outer type, violating the kernel's cumulative constraints.
- Result: Establishes the necessity of universe hierarchy constraints to prevent self-referential type definitions that lead to fixed-point contradictions.
Diaconescu Paradox (diaconescu.v):
- Mechanism: Uses a typed version of the Axiom of Choice (Tchoice) on an equivalence relation over bool defined by a proposition $P$ . The choice function $f: bool \to bool$ is used to decide $P$ by comparing $f(\text{true})$ and $f(\text{false})$ .
- Kernel Rejection: The argument extracts a computational decision (a function in Set) from an existential proof in Prop. This constitutes "large elimination" from Prop to Set.
- Result: Demonstrates that allowing the Axiom of Choice in Set (or large elimination from Prop to Set) forces the Law of Excluded Middle (LEM) into the constructive system. The kernel restricts large elimination to prevent this import of classical logic into the computational layer.
Reynolds Paradox (Reynolds.v):
- Mechanism: Reformulates Reynolds's result that System F has no set-theoretic model. It assumes an injection $I: Prop \to Heyt$ (where $Heyt$ is a single proposition) and constructs a preinitial algebra (Church encoding) for a functor $\Phi$ . Using Lawvere's fixed-point theorem, it derives a fixed point for negation, leading to False.
- Kernel Rejection: The construction relies on the impredicativity of Prop (quantifying over all propositions within Prop). However, the paradox requires an injection from Prop into a single proposition, which the kernel rejects on universe grounds before the logical contradiction can be reached.
- Result: Highlights the role of impredicativity in Prop. While Prop is impredicative, the kernel prevents the specific structural injections that would allow Cantor's diagonal argument to collapse the universe of propositions.
Hurkens Paradox (Hurkens_Set.v):
- Mechanism: An adaptation of Hurkens's simplification of Girard's paradox. It assumes a retract between Prop and bool (via double negation) and uses the impredicativity of Set (if enabled) combined with large elimination to construct a self-referential well-founded relation that leads to False.
- Kernel Rejection: The paradox requires both impredicativity in Set and large elimination (extracting booleans from propositional content). The default Rocq kernel keeps Set predicative and restricts large elimination from Prop.
- Result: Shows that the combination of impredicativity and large elimination in Set is inconsistent with classical logic (LEM). The kernel's decision to keep Set predicative and restrict elimination is the safeguard.

Significance and Claims

The paper argues that the coq-paradoxes package serves as a negative specification of the Rocq kernel. Rather than merely listing inconsistencies, the package provides a formal proof by failed example of the kernel's soundness.

Three Boundary Conditions: The paper synthesizes the four paradoxes into three specific design decisions enforced by the kernel:
1. Universe Hierarchy: Prevents types from quantifying over themselves in a way that creates fixed points (Burali-Forti).
2. Placement of Impredicativity: Confines impredicative quantification to Prop (and optionally Set with caveats), preventing the Reynolds and Hurkens contradictions.
3. Discipline of Large Elimination: Restricts the extraction of computational content (like bool or functions in Set) from propositional proofs, preventing the Diaconescu and Hurkens contradictions.
Meta-Mathematical Role: The paper claims the package is a unique piece of meta-mathematics written inside the system it documents. It does not prove theorems for application but proves the unsatisfiability of specific hypotheses. The "refusal" of the kernel is shown to be a consequence of uniform policies (universe arithmetic, elimination rules) rather than ad-hoc fixes.
Conclusion: The significance lies in demonstrating that the Rocq kernel's refusal to compile these constructions is not arbitrary but is the precise structural mechanism required to maintain the consistency of CIC. The package validates that the kernel's design decisions are made for the "right reasons," effectively drawing the boundary of the system from the outside in.