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), 809-816

MSC:
Primary 03B25; Secondary 03F30

DOI:
https://doi.org/10.1090/S0002-9939-1992-1072092-6

MathSciNet review:
1072092

Full-text PDF

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****[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****[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**, https://doi.org/10.1090/S0002-9939-1979-0545589-6**[Kos]**N. K. Kosovskii,*On solutions of systems consisting of both word equations and word length inequalities*, J. Soviet Math.**8**(1977), 262-265.**[L]**L. Lipshitz,*The Diophantine problem for addition and divisibility*, Trans. Amer. Math. Soc.**235**(1978), 271–283. MR**0469886**, https://doi.org/10.1090/S0002-9947-1978-0469886-1**[S]**T. Skolem,*Uber einige Satzfunctionen in der Arithmetik*, Skrifte Vidensk. Kristiana I, no. 7, 1930, pp. 1-28.**[T]**V. Terrier,*Decidability of the existential theory of**with order, divisibility and functions*, preprint. (French)

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:
https://doi.org/10.1090/S0002-9939-1992-1072092-6

Keywords:
Decision problems in arithmetic,
decidability

Article copyright:
© Copyright 1992
American Mathematical Society