Binary models generated by their tally part (Q1337500)

This paper deals with theories of bounded arithmetic, and with a question of Wilkie and Paris. We introduce and study a class of models of the bounded theory \(\text{PV}_ n\). These models, which are generated by their tally part, have a curious feature: they are end-extendable or satisfy the bounded collection scheme for \(\Sigma^ b_ n\)-formulae only if they are closed under exponentiation. As an application, we show that if the theory \(I\Delta_ 0+\neg\exp\) proves the bounded collection scheme, then the polynomial time hierarchy does not collapse (and, \textit{a fortiori}, \(\text{P}\neq\text{NP}\)).