On the Additive Theory of Prime Numbers

• Autorzy: Cégielski P. , Richard D. , Vsemirnov M.
• Języki publikacji: EN

Abstrakty

EN

The undecidability of the additive theory of prime numbers (with identity) as well as the theory Th (N, +, n→pn), where pn denotes the (n+1)-th prime, are open questions. In a first part, we show the undecidability of Th(N, +, n→nf(n)) where f is a good approximation of the enumeration n → pn/n. In a second part, as a possible approach, we extend the former theory by adding some extra function. In this direction we show the undecidability of the existential part of the theory Th (N, +, n→pn, n→rn)), where rn is the remainder of pn divided by n in the euclidian division.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 1-3
• Strony: 83--96
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Cégielski P.

autor

Richard D.

autor

Vsemirnov M.

• LACL, EA 4213, Université Paris Est-IUT, Route forestiere Hurtault, F-77300 Fontainebleau, France,

Bibliografia

• [1] P.T. BATEMAN, C.G. JOCKUSCH, and A.R. WOODS, Decidability and Undecidability of theories with a predicate for the prime, The Journal of Symbolic Logic, vol. 58, (1993) pp.672-687.
• [2] M. BOFFA, More on an undecidability result of BATEMAN, JOCKUSCH and WOODS, The Journal of Symbolic Logic, vol. 63, (1998) p. 50.
• [3] P. CEGIELSKI, Definability, decidability, complexity, Annals of mathematics and Artificial Intelligence, Baltzer, M. NIVAT and S. GRIGORIEFF ed., vol. 16, 1996, nos 1-4, pp.311-342.
• [4] P. CEGIELSKI, Y. MATIIASSEVITCH, and D. RICHARD, Definability and decidability issues in extensions of the Integers with the divisibility predicate, The Journal of Symbolic Logic, vol. 61, Number 2, June 1996, pp.515-540.
• [5] L.E. DICKSON, A new extension of DIRICHLET's theorem on prime numbers, Messenger of Mathematics, vol. 33 (1903-04), pp. 155-161.
• [6] H.B. ENDERTON, A Mathematical Introduction to Logic, Academic Press, (1972), XIII + 295p.
• [7] T. LAVENDHOMME & A. MAES, Note on the undecidability of h!,+, Pm,ri, Definability in arithmetics and computability, pp.61-68, Cahier du Centre de logique, Belgium, 11 (2000).
• [8] Yuri MATIYASEVICH, Hilbert's tenth Problem, The MIT Press, Foundations of computing, 1993, XXII+262p.
• [9] P. RIBENBOIM, The new book of Prime Records, Springer, 1996, XIV+541p.
• [10] A. SCHINZEL & W. SIERPIEńSKY, Sur certaines hypothses concernant les nombres premiers, Acta Arithmetica, vol. 4, 1958, 185-208 and 5, 1959, 259.
• [11] AlanWOODS, Some problems in logic and number theory, and their connection, Ph.D. thesis, University of Manchester,Manchester, 1981.