The small-is-very-small principle

摘要

The central result of this paper is the small-is-very-small principle for restricted sequential theories. The principle says roughly that whenever the given theory shows that a definable property has a small witness, i.e., a witness in a sufficiently small definable cut, then it shows that the property has a very small witness: i.e., a witness below a given standard number. Which cuts are sufficiently small will depend on the complexity of the formula defining the property. We draw various consequences from the central result. E.g., roughly speaking, (i) every restricted, recursively enumerable sequential theory has a finitely axiomatized extension that is conservative with respect to formulas of complexity ≤ n; (ii) every sequential model has, for any n, an extension that is elementary for formulas of complexity ≤ n, in which the intersection of all definable cuts is the natural numbers; (iii) we have reflection for ∑_2~0-sentences with sufficiently small witness in any consistent restricted theory U; (iv) suppose U is recursively enumerable and sequential. Suppose further that every recursively enumerable and sequential V that locally inteprets U, globally interprets U. Then, U is mutually globally interpretable with a finitely axiomatized sequential theory. The paper contains some careful groundwork developing partial satisfaction predicates in sequential theories for the complexity measure depth of quantifier alternations.