Finite Combinatorics and Fragments of Arithmetic

In fragments of first order arithmetic, definable maps on finite domains could behave very differently from finite maps. Here combinatorial properties of ${\mathrm{\Sigma }}_{n+1}$-definable maps on finite domains are compared in the absence of $B{\mathrm{\Sigma }}_{n+1}$. It is shown that $\mathrm{G}\mathrm{P}\mathrm{H}\mathrm{P}({\mathrm{\Sigma }}_{n+1})$ (the ${\mathrm{\Sigma }}_{n+1}$-instance of Kaye’s General Pigeonhole Principle) lies strictly between $\mathrm{C}\mathrm{A}\mathrm{R}\mathrm{D}({\mathrm{\Sigma }}_{n+1})$ and $\mathrm{W}\mathrm{P}\mathrm{H}\mathrm{P}({\mathrm{\Sigma }}_{n+1})$ (Weak Pigeonhole Principle for ${\mathrm{\Sigma }}_{n+1}$-maps), and also that $\mathrm{F}\mathrm{R}\mathrm{T}({\mathrm{\Sigma }}_{n+1})$ (Finite Ramsey’s Theorem for ${\mathrm{\Sigma }}_{n+1}$-maps) does not imply $\mathrm{W}\mathrm{P}\mathrm{H}\mathrm{P}({\mathrm{\Sigma }}_{n+1})$.