Julia F. Knight Department of Mathematics University of Notre Dame P.O. Box 398 Notre Dame, IN 46556 knight.1@nd.edu Title: Complexity and Arithmetic We identify a model A of arithmetic with its atomic diagram, and we measure the complexity of A by its Turing degree. The standard model has copies in all degrees. By a result of Solovay [So1], simplified by Marker [M-M], the degrees of non-standard models of TA (true arithmetic) are the degrees of "enumerations" of "Scott sets" containing the arithmetical sets. Solovay [So2] also characterized the degrees of models of other completions of PA (first order Peano arithmetic). (See [K].) There were some natural questions on complexity of models of arithmetic asked before [So1] and [So2]. Lerman [L] asked whether there is a non-standard model A of TA with no enumeration of just the arithmetical sets computable in A. Lachlan and Soare [L-S] showed that there is such a model (see also McAllister [Mc]). Abramson and Knight asked whether there is a non-standard model A of TA whose degree is minimal over the arithmetical degrees. A new result implies that there is no such model. References [K] Knight, J. F., "True approximations and models of arithmetic", to appear in Colloquium '97, ed. by Cooper and Truss. [L] Lerman, M., "Upper bounds for the arithmetical degrees," APAL, vol. 29(1985), pp. 225-254. [M-M] Macintyre, A., and D. Marker, "Degrees of recursively saturated models," Trans. of the Amer. Math. Soc., vol 282(1984), pp. 539-554. [Mc] [McA2] McAllister, A. M., "Completions of PA: models and enumerations of representable sets", JSL, vol. 63 (1998), pp. 1063-1082. [So1] Solovay, R., preprint circulated in 1982. [So2] Solovay, R., personal correspondence, 1991.