Decidable classes of number theoretic sentences.

The thesis is in two parts. In the first, I give a method for constructing decidable classes of number theoretic sentences, and in the second, I apply this method in the construction of particular decidable classes. Let B0,B1,.. be an increasing sequence of finite Boolean algebras of subsets, of the natural numbers, N, such that {lcub}e-1{rcub} B limits for all e > 0. We call the Be limiters. We say that e limits a predicate P if the extension of each component of P belongs to We say that a function p(i) limits a function f if the inverse of each component of f maps Bi, into Bpi. By a constituent, we mean either a predicate or a function. We call a set of constituents B effectively limited if there is an effective procedure for obtaining limits, which are recursive in the case of functions, for each constituent in B. By a sentence with constituents B we mean a sentence generated from B and the equations X = 0,X=1, by substitution, the prepositional operations, bounded and unbounded quantification, and bounded and unbounded u-operations Our main result is that the class of sentences, with a given effectively limited set of recursive constituents, is decidable if b2 is recursive where b2 denotes max{lcub}min B : B Be{rcub}. In the second part, we consider several possible sequences of limiters. In each case, we show that be is recursive, and we find as large an effectively limited class B of recursive constituents as we can, so that the class of sentences with constituents B is decidable. In the case of the simplest possible limiters, our work reveals the connection between the apparently unrelated methods, used by Goodstein and Lee and by Rousseau, to determine decidable classes of equations of the form f = 0, and provides a considerable extension of these classes.