Proper divisibility in computable rings
type: Item
instance of: scholarly article
title: Proper divisibility in computable rings
zbMATH Open document ID: 1370.03021
author: Noam Greenberg
author: Alexander Melnikov
published in: Journal of Algebra
publication date: 2017-01-16T00:00:00Z
review text: The authors analyze results of ring theory from the viewpoints of reverse mathematics and computability theory. Let A denote the statement: An integral domain \(R\) is a unique factorization domain if and only if every irreducible element of \(R\) is prime and the divisibility relation in \(R\) is well-founded. Let B denote the statement: If \(R\) is an integral domain with a well-founded divisibility relation then every element of \(R\) is the product of irreducible elements. The authors prove that both A and B are equivalent to \(\text{ACA}_0\) over the base system \(\text{RCA}_0\). The authors also prove the following computability theoretic bounds. There is a computable non-atomic integral domain \(R\) such that every infinite chain of proper divisibility in \(R\) computes \({\emptyset}^\prime\). There is a computable non-atomic integral domain such that \({\emptyset}^\prime\) does not compute any infinite chain of proper divisibility in \(R\). The central proof technique involves coding \(\Sigma^0_2\) binary trees into computable integral domains. Other articles on computable ring theory of the last decade include [\textit{C. J. Conidis}, Trans. Am. Math. Soc. 362, No. 12, 6523--6550 (2010; Zbl 1215.03017); \textit{R. G. Downey} and \textit{A. M. Kach}, Notre Dame J. Formal Logic 52, No. 2, 163--172 (2011; Zbl 1260.03082); \textit{R. G. Downey} et al., J. Algebra 314, No. 2, 872--887 (2007; Zbl 1127.03037); \textit{D. Dzhafarov} and \textit{J. Mileti}, ``The complexity of primes in computable UFDs'', Notre Dame J. Formal Logic (to appear)].
reviewed by: Jeffry L. Hirst
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 13G05
Mathematics Subject Classification ID: 03D80
Mathematics Subject Classification ID: 16U10
Mathematics Subject Classification ID: 03F35
zbMATH DE Number: 6674998
zbMATH Keywords: constructive (effective) algebra
zbMATH Keywords: reverse mathematics
zbMATH Keywords: integral domain theory
zbMATH Keywords: ring
zbMATH Keywords: integral domain
zbMATH Keywords: unique factorization
zbMATH Keywords: UFD
zbMATH Keywords: ACCP
zbMATH Keywords: divisibility relation
zbMATH Keywords: computability
zbMATH Keywords: computable ring
zbMATH Keywords: ACA
MaRDI profile type: Publication
full work available at URL: j.jalgebra.2016.11.010
OpenAlex ID: W2555592914
cites work: Jump degrees of torsion-free abelian groups
cites work: Computable structures and the hyperarithmetical hierarchy
cites work: Chain conditions in computable rings
cites work: AP-domains and unique factorization.
cites work: Iterated effective embeddings of abelian p-groups
cites work: Euclidean functions of computable Euclidean domains
cites work: Ideals in computable rings
cites work: Q4956005
cites work: Q3958432
cites work: Countable algebra and set existence axioms
cites work: Effective procedures in field theory
cites work: Q3130249
cites work: Q4773810
cites work: Q4249727
cites work: CONSTRUCTIVE ALGEBRAS I
cites work: Recursively enumerable vector spaces
cites work: Effective content of field theory
cites work: Q4749832
cites work: Computable Algebra, General Theory and Theory of Computable Fields
cites work: Q5573961
cites work: Recursive properties of Euclidean domains
cites work: Q3395521
cites work: Q4040892
cites work: Q5808440
cites work: Q4934287
DOI: 10.1016/J.JALGEBRA.2016.11.010
description: scientific article; zbMATH DE number 6674998