An independence of the MIN principle from the PHP principle

Abstract

The minimization principle $\text{MIN}(◃)$ studied in bounded arithmetic says that a strict linear ordering $◃$ on any finite interval $[0,\dots ,n)$ has the minimal element. We shall prove that bounded arithmetic theory ${\text{T}}_2^1(◃)$ augmented by instances of the pigeonhole principle for all ${\Delta }_1^b(◃)$ formulas does not prove $\text{MIN}(◃)$.