Computable algebraic structures and nonstandard arithmetic
Eugene W. Madison · Transactions of the American Mathematical Society · 1968
Rabin [5] has proved a number of interesting theorems concerning computable algebraic structures.Prior to Rabin's paper, A. Froehlich and J. C. Shepherdson [1] proved a wealth of results concerning explicit fields, i.e., computable fields.Loosely speaking, a computable algebraic structure is an algebraic structure whose relations can be viewed as recursive number-theoretic relations.In this paper we are primarily interested in those algebraic structures whose relations can be viewed as arithmetical number-theoretic relations.We shall call such structures arithmetically definable structures (or, more simply, ADstructures).Since every recursive relation is arithmetical, it is immediate that every computable algebraic structure is an AD-structure.Our interest in these structures grows out of an attempt to solve the following general problem:(I) Let {sé; Jf) be an algebraic structure (Jf a copy of the natural numbers and Jf^sé)and Jf* any (strong) nonstandard model of arithmetic.Does there exist a structure sé* in which Jf* is embedded such that {sé* ; Jf*} is elementarily equivalent to {sé; Jf}"] It is implicit in the above question that the structures under consideration are models of sets of sentences of some formulation of first-order logic.For our purposes we take a convenient formulation of first-order logic with extralogical constants E, S, P, N and 0 whose intended interpretations are equality, sum, product, "x belongs to some model of arithmetic" and zero, respectively.Precise definitions of "strong model of arithmetic" and " elementary equivalence" are found in [7] and [6], respectively.A rather natural question related to (I) is: (II) Do we have uniqueness for any of the affirmative cases of I ?With reference to (I), we prove that the answer is in the affirmative for any AD-structure which contains a copy of Jf.So, in particular, (I) holds for the field of algebraic numbers, since Rabin has proved that this field is computable.In §2