Abstract:
We develop the theory $S^1_2+\forall a \PHP^a_{a^2}(PV)$, where the surjective weak pigeonhole principle $PHP^a_{a^2}(PV)$ says that there is no polynomial time computable surjection from $a$ onto $a^2$. We show that the $\forall S^b_1$ consequences of this theory can be witnessed in probabilistic polynomial time, but that the converse is unlikely to hold. Furthermore, if the cryptosystem RSA is secure then this theory does not prove the injective weak pigeonhole principle for polynomial time functions. We use this observation to show that if RSA is secure then the theory $PV$+(sharply bounded collection for $PV$ formulas) lies strictly between $PV$ and $S^1_2$ in strength. We also give some unconditional independence results for the relativized version of $S^1_2+\forall a PHP^a_{a^2}(PV)$. In particular, it does not prove the injective weak pigeonhole principle for an undefined function symbol.
We define a hierarchy of theories of arithmetic with a top, and use them to study the structure of a model $M$ of bounded arithmetic by studying the relationships between its initial segments. We show that if the weak pigeonhole principle fails then for suitable $b>a^\mathbb{N}$ the initial segment $M \upharpoonright b$ is definable inside $M \upharpoonright a$ and hence is the unique end-extension of $M \upharpoonright a$ to a model of arithmetic with a top (of this form). Conversely if any model $K$ of arithmetic with a top is definable inside $M$ then either $K$ is isomorphic to an initial segment of $M$ or vice versa, and the weak pigeonhole principle implies that the first of these holds. We also use some tools from general model theory to show that if the weak pigeonhole principle holds in a model of a weak theory of arithmetic with a top, then initial segments have more than one end-extension; in a model of a strong theory of arithmetic with a top, we can construct uncountable end-extensions of countable initial segments.
Table of contents:
