Finite Combinatorics and Fragments of Arithmetic

Abstract

In fragments of first order arithmetic, definable maps on finite domains could behave very differently from finite maps. Here combinatorial properties of ${\Sigma }_{n+1}$-definable maps on finite domains are compared in the absence of $B{\Sigma }_{n+1}$. It is shown that $\mathrm{GPHP}({\Sigma }_{n+1})$ (the ${\Sigma }_{n+1}$-instance of Kaye's General Pigeonhole Principle) lies strictly between $\mathrm{CARD}({\Sigma }_{n+1})$ and $\mathrm{WPHP}({\Sigma }_{n+1})$ (Weak Pigeonhole Principle for ${\Sigma }_{n+1}$-maps), and also that $\mathrm{FRT}({\Sigma }_{n+1})$ (Finite Ramsey's Theorem for ${\Sigma }_{n+1}$-maps) does not imply $\mathrm{WPHP}({\Sigma }_{n+1})$.

arXiv comment2nd version, 15 pages, with suggestions from an anonymous referee incorporated