The Complexity of Primes in Computable Unique Factorization Domains

Notre Dame Journal of Formal Logic 59 (2):139-156 (2018)
  Copy   BIBTEX


In many simple integral domains, such as Z or Z[i], there is a straightforward procedure to determine if an element is prime by simply reducing to a direct check of finitely many potential divisors. Despite the fact that such a naive approach does not immediately translate to integral domains like Z[x] or the ring of integers in an algebraic number field, there still exist computational procedures that work to determine the prime elements in these cases. In contrast, we will show how to computably extend Z in such a way that we can control the ordinary integer primes in any Π20 way, all while maintaining unique factorization. As a corollary, we establish the existence of a computable unique factorization domain such that the set of primes is Π20-complete in every computable presentation.



    Upload a copy of this work     Papers currently archived: 74,509

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Prime Models of Finite Computable Dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.
Lp -Computability.Ning Zhong & Bing-Yu Zhang - 1999 - Mathematical Logic Quarterly 45 (4):449-456.
Prime Numbers and Factorization in IE1 and Weaker Systems.Stuart T. Smith - 1992 - Journal of Symbolic Logic 57 (3):1057 - 1085.
Difference Sets and Computability Theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
Order-Computable Sets.Denis Hirschfeldt, Russell Miller & Sergei Podzorov - 2007 - Notre Dame Journal of Formal Logic 48 (3):317-347.


Added to PP

9 (#928,983)

6 months
1 (#417,896)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Countable Algebra and Set Existence Axioms.Harvey M. Friedman - 1983 - Annals of Pure and Applied Logic 25 (2):141.
Effective Content of Field Theory.G. Metakides - 1979 - Annals of Mathematical Logic 17 (3):289.
Rekursive Algebren mit Kettenbedingungen.Walter Baur - 1974 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 20 (1-3):37-46.
Rekursive Algebren mit Kettenbedingungen.Walter Baur - 1974 - Mathematical Logic Quarterly 20 (1‐3):37-46.
Euclidean Functions of Computable Euclidean Domains.Rodney G. Downey & Asher M. Kach - 2011 - Notre Dame Journal of Formal Logic 52 (2):163-172.

Add more references