Effective presentations, reductions, and degrees
Heer Tern Koh · 2025
The primary focus of this thesis is in computability theory, investigating the broad question "How much of mathematics can be done algorithmically?" More specifically, we focus on studying this question in the context of mathematical structures. In Part I, we study the different notions of effectively presented topological spaces and groups. Within the literature, the most common notions of presentations for Polish spaces are computably, left-c.e., and right-c.e. presented spaces. While these notions have been around for quite some time, only recently has there been an interest in attempting to compare and separate these notions. In this thesis, we study the various notions mentioned above for both Polish groups and Polish spaces, separating them up to homeomorphism. In particular, we prove that there exists Polish spaces and groups that are left-c.e. and right-c.e. presentable but not homeomorphic to any computably presented Polish space and group respectively. In Part II, we present some results regarding a relatively recent research program in the study of primitive recursion. Under this program, one of the areas of interest is in the degree structure induced by the reduction "being primitively recursively isomorphic", referred to as the punctual degrees (of an algebraic structure). We mainly study density and non-density of the punctual degrees of various structures, like the dense linear order, equivalence relations, and the class of discrete linear orders. Additionally, following the pattern of computable structure theory, we also present results regarding an analogue of relativised categoricity for punctual structures (to be defined). Finally, in Part III, we study the computably enumerable tt degrees (to be defined), and resolve a question of Cai et al.: there exists a tt minimal pair such that both degrees are wtt complete. Even though the result itself seems like a small improvement to existing results, a substantial change in the strategy of the proof seems to be necessary.