Model-theoretic Characterizations of the Separation Problem of Bounded Arithmetic

Arnold Beckmann

Bounded arithmetic is designed to characterize low complexity computability, i.e., the polynomial hierarchy. The main open problem for bounded arithmetic is the question if bounded arithmetic is finitely axiomatizable, which is equivalent to asking if the levels of bounded arithmetic S_{2}^{i}, T_{2}^{i} etc. collapse. Furthermore, this question is also connected to the open problem whether the polynomial hierarchy collapses. The precise connection is that bounded arithmetic is finitely axiomatized if and only if bounded arithmetic can prove that the polynomial hierarchy collapses (cf. [2]).

In this talk we will give model-theoretic characterizations of the separation problem of bounded arithmetic. The main tool will be restricted consistency statements, whose complexity is captured by a bounded analog of Π_{1}. Our characterizations will be as the following one:

Two levels of bounded arithmetic – say S_{2}^{i} vs. T_{2}^{j} for j ≥ i – are separated by a bounded Π_{1} sentence if and only if there exists a model of the smaller theory (i.e., S_{2}^{i}) without proper bounded-elementary extensions to a model of the stronger theory (i.e., T_{2}^{j}).

Remark for experts: By “bounded Π_{1}” we mean the universal closure of Π_{1}^{b}, and “bounded-elementary extensions” is the restriction of elementary extensions to sharply bounded formulas.

[1] Beckmann, A.: Model-theoretic Characterizations of ∀Π_{1}^{b}-Separations in Bounded Arithmetic. Preprint, 2000.

    http://wwwmath.uni-muenster.de/u/beckmann/publ/artikel9.html

[2] Buss, S.R.: Relating the bounded arithmetic and the polynomial time hierarchies. Annals of Pure and Applied Logic 75: 67-77. 1995.

Address: Department of Mathematics, UCSD, 9500 Gilman Drive, La Jolla, CA 92093-0112, USA

E-mail: abeckman@math.ucsd.edu