Proper divisibility in computable rings (Q504325)

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