Computability theory and algebra

• Main Author: Wu, Huishan
• Other Authors: Wu Guohua
• Format: Theses and Dissertations
• Language: English
• Published: 2017
• Subjects: DRNTU::Science::Mathematics::Mathematical logic
• Online Access: http://hdl.handle.net/10356/72708
• Institution: Nanyang Technological University

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.