Solovayʹs theorem cannot be simplified Original Research Article

In this paper we consider three potential simplifications to a result of Solovayʹs concerning the Turing degrees of nonstandard models of arbitrary completions of first-order Peano arithmetic (PA). Solovay characterized the degrees of nonstandard models of completions T of PA, showing that they are the degrees of sets X such that there is an enumeration View the MathML source of an “appropriate” Scott set and there is a family of functions View the MathML source, View the MathML source uniformly in n, such that View the MathML source is an index for View the MathML source and for all s, View the MathML source is an index for a subset of View the MathML source. The simplifications under consideration are attempts to restrict the families of functions View the MathML source that appear in Solovayʹs result, known henceforth as Solovay families. We show that none of these potential simplifications may be made, by proceeding as follows. First, we construct a nonstandard model View the MathML source of PA such that there is no Solovay family View the MathML source for Th(View the MathML source) relative to View the MathML source in which all the functions View the MathML source are constant. Second, for each k we construct a nonstandard model View the MathML source of PA such that there is no Solovay family View the MathML source for Th(View the MathML source) relative to View the MathML source in which all the functions View the MathML source change values at most k many times. Third, we construct a nonstandard model View the MathML source of PA such that there is no Solovay family View the MathML source for Th(View the MathML source) relative to View the MathML source with a computable function f such that for all n, View the MathML source changes values at most f(n) times. Our constructions answer three questions asked by Julia Knight. Our solutions make use of several consistency results that seem to be of independent interest.