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 | Schools: | School of Physical and Mathematical Sciences | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Computability Theory and Algebra.pdf | Main thesis | 800.71 kB | Adobe PDF | View/Open |
Page view(s) 50
571
Updated on Mar 28, 2024
Download(s) 20
300
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.