Decidability of the existential theory of the set of natural numbers with order, divisibility, power functions, power predicates, and constants
Author:
Véronique Terrier
Journal:
Proc. Amer. Math. Soc. 114 (1992), 809816
MSC:
Primary 03B25; Secondary 03F30
MathSciNet review:
1072092
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We construct an algorithm to test if a system of conditions of the types , and has a solution in natural numbers. (, and denotes the set .)
 [B]
A.
P. Bel′tjukov, Decidability of the universal theory of
natural numbers with addition and divisibility, Zap. Naučn.
Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 60
(1976), 15–28, 221 (Russian, with English summary). Studies in
constructive mathematics and mathematical logic, VII. MR 0538174
(58 #27419)
 [DMR]
Martin
Davis, Yuri
Matijasevič, and Julia
Robinson, Hilbert’s tenth problem: Diophantine equations:
positive aspects of a negative solution, Mathematical developments
arising from Hilbert problems (Proc. Sympos. Pure Math., Vol. XXVIII,
Northern Illinois Univ., De Kalb, Ill., 1974) Amer. Math. Soc.,
Providence, R. I., 1976, pp. 323–378. (loose erratum). MR 0432534
(55 #5522)
 [Kop]
Moshe
Koppel, Some decidable Diophantine problems:
positive solution to a problem of Davis, Matijasevič and
Robinson, Proc. Amer. Math. Soc.
77 (1979), no. 3,
319–323. MR
545589 (81a:10069), http://dx.doi.org/10.1090/S00029939197905455896
 [Kos]
N. K. Kosovskii, On solutions of systems consisting of both word equations and word length inequalities, J. Soviet Math. 8 (1977), 262265.
 [L]
L.
Lipshitz, The Diophantine problem for addition
and divisibility, Trans. Amer. Math. Soc.
235 (1978),
271–283. MR 0469886
(57 #9666), http://dx.doi.org/10.1090/S00029947197804698861
 [S]
T. Skolem, Uber einige Satzfunctionen in der Arithmetik, Skrifte Vidensk. Kristiana I, no. 7, 1930, pp. 128.
 [T]
V. Terrier, Decidability of the existential theory of with order, divisibility and functions , preprint. (French)
 [B]
 A. P. Bel'tyukov, Decidability of the universal theory of natural numbers with addition and divisibility, Zapiski Nauch. Sem. Lenin. Otdeleniya Math. Inst. im. V. A. Steklova Akad. Nauk SSSR, vol. 60, 1976, pp. 1528. MR 0538174 (58:27419)
 [DMR]
 M. Davis, Ju. V. Matijasevic, and J. Robinson, Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution (Proc. Sympos. on the Hilbert problems, DeKalb, Illinois, May 1974), vol. 28, Amer. Math. Soc., Providence, RI, 1976, pp. 323378. MR 0432534 (55:5522)
 [Kop]
 M. Koppel, Some decidable diophantine problem: positive solution to a problem of Davis, Matijasevic and Robinson, Proc. Amer. Math. Soc. 77 (1979), 319323. MR 545589 (81a:10069)
 [Kos]
 N. K. Kosovskii, On solutions of systems consisting of both word equations and word length inequalities, J. Soviet Math. 8 (1977), 262265.
 [L]
 L. Lipshitz, The diophantine problem for addition and divisibility, Tran. Amer. Math. Soc. 235 (1978), 271283. MR 0469886 (57:9666)
 [S]
 T. Skolem, Uber einige Satzfunctionen in der Arithmetik, Skrifte Vidensk. Kristiana I, no. 7, 1930, pp. 128.
 [T]
 V. Terrier, Decidability of the existential theory of with order, divisibility and functions , preprint. (French)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC:
03B25,
03F30
Retrieve articles in all journals
with MSC:
03B25,
03F30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029939199210720926
PII:
S 00029939(1992)10720926
Keywords:
Decision problems in arithmetic,
decidability
Article copyright:
© Copyright 1992
American Mathematical Society
