Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/72708
Title: Computability theory and algebra
Authors: Wu, Huishan
Keywords: DRNTU::Science::Mathematics::Mathematical logic
Issue Date: 2017
Source: Wu, H. (2017). Computability theory and algebra. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: This thesis mainly focuses on classical computability theory and effective aspects of algebra. In particular, we will work on bounded low/high sets, degrees of orders on torsion-free abelian groups, and reverse mathematics of several classic results in modules. In Part I, we will study bounded-low sets and bounded-high sets in terms of the high/low hierarchy. Anderson and Csima proposed in [1] the notion of bounded-jump on wtt-degrees, and proved an analogue of Shoenfield's jump inversion theorem. In [2], Anderson, Csima and Lange compared the bounded jump with Turing jump and proved the existence of high bounded-low sets and low bounded-high sets. Observing that superlow sets are all bounded-low, Anderson, Csima and Lange asked in [2] whether there exist bounded-low c.e. sets which are low but not superlow, and whether there exist superhigh sets which are not bounded-high. In Part I, we will provide positive answers to these questions. We will also prove that there are bounded-high sets which are high but not superhigh, and that there are bounded-low c.e. sets which are high but not superhigh. In Part II, we study Turing degrees of orders on computable torsion-free abelian groups with infinite rank. Recently, Kach, Lange and Solomon [3] built a noncomputable c.e. set C and a computable torsion-free abelian group G with computable orders such that every C-computable order on the constructed group is computable. Motivated by this result, we call a degree a group-order-computable if there is a computable torsion-free abelian group G with infinite rank which admits computable orders such that every a-computable order on G is computable; in this case, say a is group-order-computable via G. Following this definition, we call a degree a weakly group-order-computable if there is a computable torsion-free abelian group G with infinite rank such that every a-computable group order on G is computable. We will prove that a Turing degree a is group-order-computable iff a is weakly group-order-computable iff a is not a PA degree. In particular, all c.e. degrees except 0' are group-order-computable. The objective to study group-order-computable degrees is indeed to explore degrees of orders on computable torsion-free abelian groups, because for a nonzero degree a, if it is group-order-computable via G, then G has no orders of degree a. We show that for any nonzero c.e. degree a, there is a computable torsion-free abelian group G and a nonzero c.e. degree c < a such that G has orders of degree >= a and c is group-order-computable via G, which means that G has no incomputable orders of degree <= c. In Part III, we study the reverse mathematics of classic results of divisible abelian groups and modules. We will prove that over RCA_0, the decomposition theorem of divisible abelian groups and the decomposition theorem of torsion abelian groups are both equivalent to ACA_0. We then consider projective modules and injective modules over {\Sigma}^{0}_{1}-principal ideal domains ({\Sigma}^{0}_{1}-PIDs). We will also show that ACA_0 proves the following theorems: every projective module over a {\Sigma}^{0}_{1}-PID is free; every submodule of a projective module over a {\Sigma}^{0}_{1}-PID is projective; every divisible module over a {\Sigma}^{0}_{1}-PID is injective; every quotient of an injective module over a {\Sigma}^{0}_{1}-PID is injective.
URI: http://hdl.handle.net/10356/72708
DOI: 10.32657/10356/72708
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
Computability Theory and Algebra.pdfMain thesis800.71 kBAdobe PDFThumbnail
View/Open

Page view(s) 50

242
Updated on Nov 29, 2020

Download(s) 10

46
Updated on Nov 29, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.