Computability theory and algebra

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...

Full description

Saved in:
Bibliographic Details
Main Author: Wu, Huishan
Other Authors: Wu Guohua
Format: Theses and Dissertations
Language:English
Published: 2017
Subjects:
Online Access:http://hdl.handle.net/10356/72708
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-72708
record_format dspace
spelling sg-ntu-dr.10356-727082023-02-28T23:36:59Z Computability theory and algebra Wu, Huishan Wu Guohua School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Mathematical logic 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. ​Doctor of Philosophy (SPMS) 2017-10-10T07:18:17Z 2017-10-10T07:18:17Z 2017 Thesis Wu, H. (2017). Computability theory and algebra. Doctoral thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/72708 10.32657/10356/72708 en 147 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Mathematics::Mathematical logic
spellingShingle DRNTU::Science::Mathematics::Mathematical logic
Wu, Huishan
Computability theory and algebra
description 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.
author2 Wu Guohua
author_facet Wu Guohua
Wu, Huishan
format Theses and Dissertations
author Wu, Huishan
author_sort Wu, Huishan
title Computability theory and algebra
title_short Computability theory and algebra
title_full Computability theory and algebra
title_fullStr Computability theory and algebra
title_full_unstemmed Computability theory and algebra
title_sort computability theory and algebra
publishDate 2017
url http://hdl.handle.net/10356/72708
_version_ 1759854052927078400