Decidability of the existential theory of the set of natural numbers with order, divisibility, power functions, power predicates, and constants
HTML articles powered by AMS MathViewer
- by Véronique Terrier PDF
- Proc. Amer. Math. Soc. 114 (1992), 809-816 Request permission
Abstract:
We construct an algorithm to test if a system of conditions of the types $\mu < \eta ,\mu /\eta ,\mu = {\eta ^a},{P_a}(\mu ),\neg (\mu < \eta ),\neg (\mu /\eta ),\neg (\mu = {\eta ^a})$, and $\neg ({P_a}(\mu ))$ has a solution in natural numbers. ($a \in N$, and ${P_a}$ denotes the set $\{ {n^a}:n \in N\}$.)References
- 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
- 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., Northern Illinois Univ., De Kalb, Ill., 1974) Amer. Math. Soc., Providence, R.I., 1976, pp. 323–378. (loose erratum). MR 0432534
- 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, DOI 10.1090/S0002-9939-1979-0545589-6 N. K. Kosovskii, On solutions of systems consisting of both word equations and word length inequalities, J. Soviet Math. 8 (1977), 262-265.
- L. Lipshitz, The Diophantine problem for addition and divisibility, Trans. Amer. Math. Soc. 235 (1978), 271–283. MR 469886, DOI 10.1090/S0002-9947-1978-0469886-1 T. Skolem, Uber einige Satzfunctionen in der Arithmetik, Skrifte Vidensk. Kristiana I, no. 7, 1930, pp. 1-28. V. Terrier, Decidability of the existential theory of $N$ with order, divisibility and functions $\{ x \to ax:a \in N\}$, preprint. (French)
Additional Information
- © Copyright 1992 American Mathematical Society
- 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