Some Decidability and Definability Problems for the Predicate of the Divisibility on Two Consecutive Numbers
Abstract
The predicate of divisibility on two consecutive numbers DW(x,y) ÷ x | y ∧ 1+x | y was introduced by L. van den Dries and A. Wilkie when they studied some properties of subsets of natural numbers, existentially definable with unit, addition and divisibility. Undecidability of the existential theory of natural numbers with multiplication and DW and definability of addition and multiplication in terms of DWand divisibility is proved in the paper. Then the definability of multiplication in the terms of addition and DW is proved. Some definability questions for order and DW are also considered in the paper.
References
Бельтюков А. П. Разрешимость универсальной теории натуральных чисел со сложением и делимостью // Записки научных семинаров ЛОМИ. 1975. Т. 60. С. 15–28.
Lipshitz L. The Diophantine problem for addition and divisibility // Transactions of the American Mathematical Society. 1976. Vol. 235. P. 271–283. doi:10.2307/1998219
Lipshitz L. Some remarks on the Diophantine problem for addition and divisibility // Bull. Soc. Math. Belg. Ser. B. 1981. Vol. 33, no. 1. P. 41–52.
Lechner A., Ouaknine J., Worrell J. On the Complexity of Linear Arithmetic with Divisibility // Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science(LICS). 2015.
P. 667–676. doi:10.1109/LICS.2015.67
Haase C. On the complexity of model checking counter automata. Ph.D. Thesis. University of Oxford.
Bundala D., Ouaknine J. On parametric timed automata and one-counter machines // Information and
Computation. 2017. Vol. 253. P. 272–303. doi:10.1016/j.ic.2016.07.011
Van den Dries L., Wilkie A.J. The laws of integer divisibility, and solution sets of linear divisibility
conditions // The Journal of Symbolic Logic. 2003. Vol. 68, no. 2. P. 503–526. doi:10.2178/jsl/1052669061
Starchak M. R., Kosovskii N. K., Kosovskaya T. M. Some NP-Hard Problems for the Simultaneous
Coprimeness of Values of Linear Polynomials // Global Journal of Computer Science and Technology.
Vol. 17, no. 4. P. 21–25.
Korec I. A list of arithmetical structures complete with respect to the first-order definability //
Theoretical Computer Science. 2001. Vol. 257, no. 1–2. P. 115–151. doi:10.1016/S0304-3975(00)00113-4
Richard D. What are Weak Arithmetics? // Theoretical Computer Science. 2001. Vol. 257. P. 17–29.
Robinson J. Definability and decision problems in arithmetic // The Journal of Symbolic Logic. 1949.
Vol. 14. P. 98–114. doi:10.2307/2266510
Mostowski A. On direct products of theories // The Journal of Symbolic Logic. 1952. Vol. 17, no. 1.
P. 1–31. doi:10.2307/2267454
Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970. Т. 191, № 2.
С. 278–282.
Матиясевич Ю. В. Десятая проблема Гильберта. М.: Физматлит. 1993.
Carmichael L. C. On the numerical factors of the arithmetic forms αn ±βn// Ann. Math. 1913. Vol. 15,
no. 2. P. 30–69. doi:10.2307/1967798
Woods A. Some problems in logic and number theory. PhD Thesis. University of Manchester. 1981.
Richard D. All arithmetical sets of powers of primes are first-order definable in terms of the
successor function and the coprimeness predicate // Discrete Mathematics. 1985. Vol. 53. P. 221–247.
doi:10.1016/0012-365X(85)90144-X
Lipshitz L. Quadratic forms, the five square problem, and diophantine equations // The collected
works of J. Richard Buchi (S. MacLane and Dirk Siefkes, eds.). Springer. 1990. P. 677 ¨ –680.
Косовский Н. К. О решении систем, состоящих одновременно из уравнений в словах и неравенств в длинах слов // Записки научных семинаров ЛОМИ. 1974. Т. 40. С. 24–29.
This work is licensed under a Creative Commons Attribution 4.0 International License.
