Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
83--96
Opis fizyczny
bibliogr. 11 poz.
Twórcy
autor
autor
autor
- LACL, EA 4213, Université Paris Est-IUT, Route forestiere Hurtault, F-77300 Fontainebleau, France, cegielski@univ-paris.fr
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS5-0014-0028