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})$.
Categories: math.LO