An independence of the minimization principle from the pigeonhole principle

Abstract

The minimization principle $\mathsf{MIN}(\triangleleft)$, studied in bounded arithmetic in Chiari & Krajíček (1998), says that a strict linear ordering $\triangleleft$ on any finite interval $[0,\dots,n)$ has a least element. We prove that the relativized bounded arithmetic theory $\mathsf{T}^1_2(\triangleleft)$ augmented by pigeonhole-principle instances for all $\Delta^{\mathrm{b}}_1(\triangleleft)$ formulas does not prove $\mathsf{MIN}(\triangleleft)$.