Count\((q)\) versus the pigeon-hole principle (Q1360313)

The paper contributes to the area which studies the status of elementary counting principles (like pigeon-hole principle) in Bounded Arithmetic. Such questions are in a nontrivial way connected to some questions (like the well-known P-NP problem) in complexity theory. The author continues his previous work on solving the so-called \(\text{Count}(q)\) versus \(\text{Count}(p)\) problem; the main onstruction is here simplified. A complete classification of the mentioned \(\text{Count}(q)\) versus \(\text{Count}(p)\) problem is obtained as a corollary of the main technical theorem (which shows the existence of a certain model satisfying the \(\text{Count}(p)\) principle). Another corollary shows that the pigeon-hole principle for injective maps does not follow from any of the \(\text{Count}(q)\) principles; this solves an open question.