Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style


Neil Thapen:

The Weak Pigeonhole Principle in Models of Bounded Arithmetic


Mathematical Institute
University of Oxford
24-29 St Giles'
Oxford OX1 3LB
United Kingdom


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:

  1. Introduction

  2. Bounded Arithmetic
    2.1 The theories $S^i_2$ and $PV$
    2.2 A witnessing theorem implies a complete language
    2.3 Arithmetic with a top
    2.4 Bootstrapping $S^1_0$

  3. The Weak Pigeonhole Principle
    3.1 Upper and lower bounds
    3.2 Amplification
    3.3 The complexity of witnessing WPHP

  4. Models of $PV$
    4.1 More about sharply bounded collection
    4.2 WPHP in models of $PV$

  5. Witnessing and independence
    5.1 Unprovability in $S^2_2(\alpha)$
    5.2 Unprovability in $S^1_2(\alpha)+\forall a PHP^a_{a^2}(PV(\alpha))$

  6. Constructing unique end-extensions
    6.1 Categoricity, definability and coding
    6.2 The construction

  7. Definable structures
    7.1 Constructing an isomorphism
    7.2 Corollaries

  8. Generalizing WPHP
    8.1 Categoricity
    8.2 Cardinality

Number of pages: 91

ISSN 1433-8092 | Imprint