Recursive Equivalence

1. Introductory remarks Classical set theory and the theory of computable (recursive) functions are the basic areas between which the theory of recursive equivalence forms a bridge. Recursive functions of k arguments are those functions from the k = n cartesian product xN = Nx ...xN (k times) of the natural numbers N = {0,1,2,...} into N which are defined on the whole of JV and whose values can be calculated by an abstract computer. Partial recursive functions are computable functions whose domain is not necessarily the whole of xN. Originally J. C. E. Dekker [37] studied only the analogue of cardinal numbers obtained by replacing arbitrary one-one functions in that theory by partial recursive one-one functions (theory of recursive equivalence types). But since that time several other algebraic systems with more structure have been treated, in particular, linearly ordered sets [27], vector spaces [49] and groups [77]. Other generalizations have been obtained by replacing partial recursive functions by arithmetic partial functions [109] and finally the analogy with set theory without the full axiom of choice has been explored [59]. Apart from the connections with classical set theory recursive equivalence also has connections with other parts of logic. In particular Tarski's work on Cardinal and Ordinal Algebras profoundly influenced the original development of the theories of recursive equivalence types and constructive order types. One of the considerations of the theory of recursive equivalence types (R.E.T.s) was the possibility of obtaining non-standard models of formal Peano arithmetic (i.e. interpretations not isomorphic to the natural numbers). Recently Nerode [113] has produced non-standard models in this context but not without considerable effort. In the order analogue case (constructive order types [27]) an original motivation (Kreisel) was to characterize "natural" well-orderings. No really significant progress has been made in giving natural well-orderings although all of the existing results in this area (see [35] for details) can be formulated very nicely in the context of constructive order types. Despite this fact that original conjectures as to the development of the subject turned out to be unratified it has in fact happened that a viable and rapidly expanding research area has developed. This area has come almost exclusively within the province of recursive function theory. In this exploration the methods used have been not only familiar ones in recursion theory but also algebraic and topological with the Baire category theorem playing a significant role. In recursion theory one often asks the question: