An independence of the MIN principle from the PHP principle
<|reference_start|>An independence of the MIN principle from the PHP principle: The minimization principle MIN($\prec$) studied in bounded arithmetic in [Chiari, M. and Kraj\'i\v{c}ek, J. Witnessing Functions in Bounded Arithmetic and Search Problems, Journal of Symbolic Logic, 63(3):1095-1115, 1998] says that a strict linear ordering $\prec$ on any finite interval $[0,\dots,n)$ has the minimal element. We shall prove that bounded arithmetic theory $T^1_2(\prec)$ augmented by instances of the pigeonhole principle for all $\Delta^b_1(\prec)$ formulas does not prove MIN($\prec$).<|reference_end|>
@article{narusevych2024an,
    title={An independence of the MIN principle from the PHP principle},
    author={Mykyta Narusevych},
    journal={arXiv preprint arXiv:2406.14930},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.14930},
    primaryClass={math.LO cs.LO}
}