On the structure of initial segments of models of arithmetic (Q1123890)

If M is a model of arithmetic and a is an element of M, then \(<a^ M\) denotes the initial segment of all elements of M which are less than a. The question considered in the paper is: for which functions f(x) the structure \(<a^ M\) (where \(+\) and \(\cdot\) are ternary relations on \(<a^ M)\) determines \(<f(a)^ M?\) The authors improve upon earlier results of Paris, Dimitracopoulos, Hájek and Solovay by showing that for every countable model M of a sufficiently strong theory T (extending \(I\Delta_ 0+\exp)\) and every nonstandard a and c in M there is a model K of T which agrees with M up to a and contains a proof of contradiction of T whose Gödel number is less than \(\exp (a^ c)\), where \(\exp (x)=2^ x\). The paper also contains a variant of the above result dealing with consistency statements for fragments of the form \(I\Sigma_ n\) and a discussion of improvements of upper bounds for proofs of inconsistency under additional assumptions about complexity classes.