An independence of the MIN principle from the PHP principle
For researchers in bounded arithmetic and proof complexity, this establishes an independence result between two fundamental combinatorial principles.
The paper proves that the minimization principle MIN(⊲) is not provable from the pigeonhole principle in bounded arithmetic, specifically showing that T₁₂(⊲) with Δᵇ₁(⊲) instances of PHP does not prove MIN(⊲).
The minimization principle $\textsf{MIN}(\triangleleft)$ studied in bounded arithmetic says that a strict linear ordering $\triangleleft$ on any finite interval $[0,\dots,n)$ has the minimal element. We shall prove that bounded arithmetic theory $\textsf{T}^1_2(\triangleleft)$ augmented by instances of the pigeonhole principle for all $Δ^b_1(\triangleleft)$ formulas does not prove $\textsf{MIN}(\triangleleft)$.