Basic bounded arithmetic
Jan Krajı́ček · Cambridge University Press eBooks · 1995
Bounded arithmetic was proposed in Parikh (1971), in connection with length-ofproofs questions. He called his system PB, presumably as the alphabetical successor to PA, but we shall stay with the established name I Δ 0 (for “induction for Δ 0 formulas”). This theory and its extensions by axioms saying that some particular recursive function is total were studied and developed in the fundamental work of J. Paris and A. Wilkie, and their students C. Dimitracopoulos, R. Kaye, and A. Woods. They studied this theory both from the logical point of view, in connections with models of arithmetic, and in connection with computational complexity theory, mostly reflected by the definability of various complexity classes by subclasses of bounded formulas. They also investigated the relevance of Gödel's theorem to these weak subtheories of PA and closely related interpretability questions. Further impetus to the development of bounded arithmetic came with Buss (1986), who formulated a bounded arithmetic system S 2 , a conservative extension of the system I Δ 0 + Ω 1 investigated earlier by J. Paris and A. Wilkie, and its various subsystems and second order extensions. The particular choice of the language and the definition of suitable subtheories of S 2 allowed him to formulate a very precise relation between the quantifier complexity of a bounded formula and the complexity of the relation it defines, measured in terms of the levels of the polynomial time hierachy PH.