Computability and Structure

Abstract

This dissertation contains results in the area of constructive mathematics with emphasis to computable algebra and computable analysis. Mal'cev [66] and Rabin [86] initiated the study of computable groups, and Turing [96, 95] started the investigation of effective procedures in analysis. The thesis in hand is divided into two parts. Part I contains results on computable abelian groups. More specifically, we introduce a new computably-theoretic concept of limitwise monotonic sequence and apply this notion to study effectively presentable torsion abelian groups and other structures. We completely describe higher computable categoricity in the class of homogeneous completely decomposable groups. For this description we need new computably-theoretic and algebraic methods. We show that a functor from the class of countable trees into the class of abelian groups defined in [50] is injective on a certain subclass of trees. This fact has recently found an application in computable group theory [35]. We also study α jump degrees of torsion-free abelian groups, and show that for every computable α there exist a torsion-free abelian group having a proper α jump degree. Part II is devoted to the study of computable separable metric and Banach spaces, with a strong influence of certain ideas from computable model theory and algorithmic randomness. We consider computable metric spaces associated to Banach spaces and show that every separable Hilbert space possesses a unique computable structure, up to a computable isometry, and C[0; 1] and l1 possess more than one. We study computable metric spaces which are not associated to Banach spaces and show that Cantor space and the Urysohn space have a unique computable structure, up to a computable isometry, and also describe computable subspaces of Rn having a unique computable structure. Finally, we generalize the concept of K-triviality [80] to an arbitrary computable metric space, and show that two possible adequate generalizations of K-triviality actually coincide.