The complexity of primes in computable unique factorization domains (Q1750293)

A computable ring is a ring whose underlying set is a computable set \(A\subseteq\mathbb N\) and the operations \(+\) and \(\cdot\) are computable functions from \(A\times A\) to \(A\). For many computable integral domains that arise in practice (such as \(\mathbb Z\) or \(\mathbb Z[x]\)) the set of primes forms a computatable set in any natural computable presentation. However, there exists a computable field \(F\) such that the set of primes in \(F[x]\) is not computable. For any computable integral domain, the set of primes is a \(\Pi^0_2\) set. It is proved in the paper that this result is the best possible. Namely, if \(Q\) is a \(\Pi^0_2\) set and \(p_0,p_1,p_2,\dots\) is the list of prime numbers in \(\mathbb N\) in increasing order, then there exists a computable unique factorization domain \(A\) such that \(A\) is an extension of \(\mathbb Z\) and for any \(i\), \(p_i\) is prime in \(A\) iff \(i\in Q\). It follows that there exists a computable unique factorization domain \(A\) such that the set of primes of \(A\) is \(\Pi^0_2\)-complete in every computable presentation of \(A\), uniformly in an index for the presentation.