Computable structure theory using admissible recursion theory on ω1 using admissibility
Noam Greenberg, Julia F. Knight · Cambridge University Press eBooks · 2013
We use the theory of recursion on admissible ordinals to develop an analogue of classical computable model theory and effective algebra for structures of size ℵ 1 , which, under our assumptions, is equal to the continuum. We discuss both general concepts, such as computable categoricity, and particular classes of examples, such as fields and linear orderings. §1. Introduction . Our aim is to develop computable structure theory for uncountable structures. In this paper we focus on structures of size ℵ 1 . The fundamental decision to be made, when trying to formulate such a theory, is the choice of computability tools that we intend to use. To discover which structures are computable, we need to first describe which subsets of the domain are computable, and which functions are computable. In this paper, we use admissible recursion theory (also known as α-recursion theory) over the domain ω 1 . We believe that this choice yields an interesting computable structure theory. It also illuminates the concepts and techniques of classical computable structure theory by observing similarities and differences between the countable and uncountable settings. In particular, it seems that as is the case for degree theory and for the study of the lattice of c.e. sets, the difference between true finiteness and its analogue in the generalised case, namely countability in our case, is fundamental to some constructions and reveals a deep gap between classical computability and attempts to generalise it to the realm of the uncountable.