🔢 mathematics

An independence of the MIN principle from the PHP principle

The paper demonstrates that the bounded arithmetic theory $\textsf{T}^1_2(\triangleleft)$ , even when augmented with the pigeonhole principle for all $\Delta^b_1(\triangleleft)$ formulas, is insufficient to prove the minimization principle $\textsf{MIN}(\triangleleft)$ for strict linear orderings on finite intervals.

Original authors: Mykyta Narusevych

Published 2026-05-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mykyta Narusevych

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 mathematician trying to build a very specific kind of universe. In this universe, there are two main rules you must follow, and one "impossible" rule you want to break.

This paper is about proving that you can build a universe where the first two rules work perfectly, but the third rule fails.

Here is the breakdown of the players and the game, using simple analogies.

The Three Rules of the Game

The "Math" Rule (Induction): This is the foundation of our universe. It says that if you have a property that works for the number 0, and if it works for a number $x$ , it must also work for the next number. Basically, the universe must behave logically and consistently, like a well-organized library where every book has its place.
The "Pigeonhole" Rule: This is a famous logic rule. Imagine you have 10 pigeons and 9 holes. If you try to put every pigeon in a hole, at least one hole must have two pigeons. You cannot fit 10 distinct items into 9 distinct slots without a collision. The paper asks: Can we build a universe where this rule holds true for any computer program we can write?
The "Minimization" Rule (The Target): This rule says that if you have a list of numbers arranged in a strict order (like a line of people waiting for a bus), there must be a "first" person at the very front. The paper wants to prove that we can build a universe where this rule is false. In this universe, you can have a line of people where everyone is behind someone else, but there is no one at the very front. It's like a line that stretches backward forever, with no beginning.

The Goal

The author wants to show that Rule 2 (Pigeonhole) is not strong enough to force Rule 3 (Minimization) to be true, even if Rule 1 (Math) is perfectly followed.

In the world of logic, this is a big deal because usually, if you have the Pigeonhole rule, you expect to be able to prove the Minimization rule. This paper says, "Nope, you can have the Pigeonhole rule without the Minimization rule."

The Construction: A Three-Player Game

To prove this, the author doesn't just write an equation; they imagine a game played by three characters over an infinite amount of time. They are building a "partial" universe step-by-step, adding pieces of a puzzle (which represents the ordering of numbers) as they go.

Player MIN (The Villain):
- Goal: To make sure there is no first person in the line.
- Strategy: Every time the line looks like it has a beginning, Player MIN sneaks in a new person who stands in front of the current first person. They keep doing this forever. By the end of the game, the line has no start.
Player IND (The Referee):
- Goal: To make sure the universe still follows the basic Math rules (Induction).
- Strategy: Player IND watches the line being built. If Player MIN's tricks start to break the logic of the universe (making it impossible to count or order things logically), Player IND steps in to fix the structure. The paper proves that Player IND can always win, meaning the universe stays logical even while the line has no start.
Player PHP (The Enforcer):
- Goal: To make sure the Pigeonhole rule never breaks.
- Strategy: This is the hardest part. Player PHP has to ensure that no matter how Player MIN arranges the line, you can never find a "magic" computer program that tries to squeeze more items into fewer slots without a collision.
- The Trick: Player PHP uses a combinatorial trick (like a complex game of chess). They look at all the possible ways the line could be extended. They prove that if you try to break the Pigeonhole rule, the "space" required to do so is too big to fit in the universe. It's like trying to fit a giant elephant into a shoebox; the math shows the shoebox is simply too small, so the elephant (the broken rule) can't get in.

The "Tree" Analogy

To prove Player PHP wins, the author uses a concept called MIN-trees.

Imagine you are trying to find a specific path through a massive forest (the universe).

The Pigeonhole Principle is like a rule that says, "You can't have two paths that merge into the same spot if they started from different places."
The Author's Proof involves growing a tree of possibilities. They show that if you try to build a path that breaks the Pigeonhole rule, the tree of possibilities grows so huge that it runs out of "room" in the universe.
Because the tree gets too big, the "bad" path (the one that breaks the rule) cannot exist. Therefore, the Pigeonhole rule must hold.

The Result

The paper concludes that the "Villain" (Player MIN) and the "Enforcer" (Player PHP) can coexist.

You can have a universe where the Pigeonhole Principle is always true (you can't squeeze 10 pigeons into 9 holes).
AND you can have a universe where the Minimization Principle is false (a line with no first person).

This proves that the Pigeonhole Principle is weaker than the Minimization Principle in this specific logical setting. You cannot use the Pigeonhole rule to prove that every line must have a beginning.

Why This Matters (According to the Paper)

The paper doesn't talk about real-world applications like medicine or engineering. Instead, it talks about the "strength" of different logical systems.

It helps mathematicians understand the hierarchy of logic.
It shows that some logical rules (like Minimization) require more "power" to prove than others (like Pigeonhole).
It provides a new method (the "game" and the "tree" counting) to separate these logical systems, which might help solve other long-standing puzzles in the field of logic and computer science.

In short: The author built a logical universe where you can't find the start of a line, even though you know you can't fit too many pigeons in too few holes. This proves that knowing you can't fit the pigeons doesn't automatically tell you where the line starts.

Technical Summary: Independence of the MIN Principle from the PHP Principle

Problem Statement
The paper addresses a central theme in propositional proof complexity and bounded arithmetic: understanding the relative strength of proof systems and establishing lower bounds on proof length. Specifically, the author investigates the logical independence of the Minimization Principle (MIN) from the Pigeonhole Principle (PHP) within the framework of relativized bounded arithmetic.

The minimization principle, $MIN(\triangleleft)$ , asserts that any strict linear ordering $\triangleleft$ on a finite interval $[0, \dots, n)$ possesses a least element. This principle is known to be provable in the theory $T^2_2(\triangleleft)$ but not in the weaker fragment $T^1_2(\triangleleft)$ . The pigeonhole principle, $PHP$, states that no injective mapping exists from a set of size $n+1$ to a set of size $n$ . While $PHP$ is unprovable even in strong theories like $T_2(\alpha)$ , its status relative to $MIN$ in weaker extensions is less clear.

The core question is whether the theory $T^1_2(\triangleleft)$ , augmented with all instances of the pigeonhole principle for $\Delta^b_1(\triangleleft)$ formulas (denoted $PHP(\Delta^b_1(\triangleleft))$ ), is sufficient to prove $MIN(\triangleleft)$ . The paper aims to demonstrate that this extension is insufficient, thereby establishing that $T^1_2(\triangleleft) + PHP(\Delta^b_1(\triangleleft))$ does not prove $MIN(\triangleleft)$ .

Methodology
The proof employs a model-theoretic construction reminiscent of forcing, structured as a game played between three parties over a countable nonstandard model $M$ of true arithmetic. The goal is to construct an expansion of a substructure $I \subset M$ by defining a binary relation $\triangleleft$ that satisfies specific properties while violating others.

The Game Framework:
The construction is viewed as a game $G_O$ played for countably many steps between three players:
- $P_{MIN}$ : Aims to construct a strict linear ordering on $[0, \dots, n)$ that has no least element, thereby falsifying $MIN(\triangleleft)$ .
- $P_{IND}$ : Aims to ensure the resulting structure satisfies polynomial induction ( $\Sigma^b_1(\triangleleft)$ -induction), preserving the theory $T^1_2(\triangleleft)$ .
- $P_{PHP}$ : Aims to ensure the structure satisfies all instances of the pigeonhole principle for $\Delta^b_1(\triangleleft)$ formulas.
The game proceeds in rounds where players extend a partial ordering condition $o \in O$ (a finite sequence of distinct numbers). The final relation $\triangleleft$ is the union of these conditions.
Winning Strategies:
- $P_{MIN}$ Strategy: Uses an external countable queue to ensure every element is eventually inserted and every element has a smaller predecessor, guaranteeing a total order with no minimum.
- $P_{IND}$ Strategy: Relies on a classical result by Paris and Wilkie (extended by Riis), ensuring that for any $\Sigma^b_1$ formula, if a witness exists, a "settling" condition can be found that guarantees the least number principle.
- $P_{PHP}$ Strategy (The Core Contribution): This is the most technically demanding part. The player must ensure that for any $\Delta^b_1(\triangleleft)$ formula $\phi$ , the relation defined by $\phi$ is not an injection from a larger set $p$ to a smaller set $h$ .
Combinatorial Analysis (The "Array" Method):
To prove $P_{PHP}$ has a winning strategy, the author introduces the concept of $(o, p, h)$ -PHP-arrays. These are definable families of conditions representing the possible outcomes of oracle computations for $\Delta^b_1$ formulas.
- The proof establishes a lower bound on the size of such arrays by extending them to uniform trees (analogous to decision trees for oracle queries).
- It establishes an upper bound on the size of any set of pairwise incompatible conditions in the forcing poset.
- By comparing these bounds, the author derives a contradiction if $p > h$ : the existence of a valid array implies $p \le h$ . Consequently, if $p > h$ , the player $P_{PHP}$ can always force a violation of injectivity (either by finding a collision or a missing value), ensuring the PHP principle holds.

Key Contributions and Results

Main Theorem: The paper proves that $T^1_2(\triangleleft) + PHP(\Delta^b_1(\triangleleft)) \nvdash \forall n MIN(\triangleleft)_n$ $T_{2}^{1} (◃) + P H P (Δ_{1}^{b} (◃)) ⊬ \forall n M I N (◃)_{n}$ .
- This result separates the strength of $T^2_2(\triangleleft)$ (which proves $MIN$) from the extension of $T^1_2$ by the pigeonhole principle.
- It implies that in the relativized setting, the theory $T^1_2(\triangleleft) + PHP(\Delta^b_1(\triangleleft))$ and $T^2_2(\triangleleft)$ are incomparable in strength: the former does not prove $MIN$, while the latter does not prove the ordinary PHP.
Combinatorial Technique: The paper develops a refined combinatorial method involving PHP-arrays and MIN-trees. This technique allows for precise counting of condition sizes in the forcing construction, improving upon previous lower-bound arguments to provide exact size estimates.
Additional Separations: The methodology is applied to demonstrate further independence results:
- Models of $T^1_2(\alpha) + PHP(\Delta^b_1(\alpha))$ can be constructed that fail the Dual Weak Pigeonhole Principle (dWPHP).
- Models can be constructed that fail the Tournament Principle (TOUR).
- The construction can be modified to produce models where the ordering $\triangleleft$ is a dense linear ordering on specific subsets.

Significance and Claims
The paper claims to provide a new route towards understanding open problems in bounded arithmetic, such as the separation of adjacent theories $T^i_2$ and $T^{i+1}_2$ , and the $R(\log)$ problem. By showing that adding the pigeonhole principle to $T^1_2$ does not yield the minimization principle, the work highlights the limitations of combinatorial principles in strengthening weak arithmetic theories.

The author notes that while the weak pigeonhole principle (WPHP) is known to be insufficient for proving strong principles like MIN (via results in [12]), this paper extends that understanding to the strong pigeonhole principle restricted to $\Delta^b_1$ formulas. The significance lies in demonstrating that even the strong PHP, when restricted to polynomial-time computable graphs, does not bridge the gap to $T^2_2$ 's strength regarding minimization.

The paper concludes by formulating an open problem: whether the same combinatorial methods can separate $T^1_2(\triangleleft) + PHP'(\Delta^b_1(\triangleleft))$ (a variant allowing multifunctions) from $MIN(\triangleleft)$ . The author expresses uncertainty, noting the difficulty in establishing lower bounds for arrays where row elements are not necessarily incompatible.