[Proof Complexity] new preprint

[Mykyta Narusevych]

Dear colleagues,

A new preprint, "An independence of the MIN principle from the PHP principle", is available at https://arxiv.org/abs/2406.14930.

The minimization principle MIN($\prec$) studied in bounded arithmetic in [Chiari, M. and Krajíč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$).

Any comments or corrections are highly appreciated.

With regards

Mykyta Narusevych