Models of bounded arithmetic and variants of the pigeonhole principle

Abstract

We give an elementary proof that theory $T^1_2(R)$ augmented by the weak pigeonhole principle for all $\Delta^{\mathrm{b}}_1(R)$-definable relations does not prove the bijective pigeonhole principle for $R$. This can be derived from known more general results but our proof yields a model of $T^1_2(R)$ in which $\mathsf{ontoPHP}^{n+1}_n(R)$ fails for some nonstandard element $n$ while $\mathsf{PHP}^{m+1}_m$ holds for all $\Delta^{\mathrm{b}}_1(R)$-definable relations and all $m \leq n^{1-\varepsilon}$, where $\varepsilon > 0$ is a fixed standard rational parameter. This can be seen as a step towards solving an open question posed by Ajtai (1990).