Elementary Differences Between the Isols and the Co-Simple Isols
Louise Hay · Transactions of the American Mathematical Society · 1967
LOUISE HAY(2) 1. Introduction.Let E denote the nonnegative integers.For a, j8e£, a is recursively equivalent to ß if there is a 1-1 partial recursive function p with a £ domain p and p(a)=ß; the equivalence class of a is denoted by .A set a is isolated if it has no infinite recursively enumerable (r.e.) subset.The equivalence classes of isolated sets are called isols, and their collection is denoted by A. The elements of A can be considered an "effective" analogue of the Dedekind finite cardinals; their properties were extensively studied by Dekker, Myhill, and Nerode (see, e.g., [2] and [6]).Isols .Given a system (M, +, ■), a formula B(xx,..., xn) of L whose only free variables areXx,...,xn and elements Xlt..., Xn of M, we say B(Xt,..., Xn) is true in M if, when the quantified variables are interpreted as ranging over A7, the result is a true statement in the theory of (M, +, • ).The first-order theories of (A, +, • ) and (A2, +, • ) are both expressible in L, and we propose to exhibit a class of (closed) sentences {S0} of L which are true in A but false in A2.We shall follow the usual practice of identifying E with the finite elements of A and A2 and of thus considering the system (E, +, ■ ) as a subsystem of (A, +, -)and(A2, +, •).To define the sentences Se we shall require a formula of L which defines E in A and in A2, i.e., a formula with one free variable which, when interpreted in A and A2 respectively, is true of exactly the finite elements of those systems.Such a