Some Decidability and Definability Problems for the Predicate of the Divisibility on Two Consecutive Numbers

  • Михаил Романович Старчак Saint Petersburg State University, Saint Petersburg, Russia

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.

Author Biography

Михаил Романович Старчак, Saint Petersburg State University, Saint Petersburg, Russia

Mikhail R. Starchak, postgraduate student, department of informatics SPbSU, 199034 Saint Petersburg, University emb., 7/9, mikhstark@gmail.com

References

1. Бельтюков А. П. Разрешимость универсальной теории натуральных чисел со сложением и
делимостью // Записки научных семинаров ЛОМИ. 1975. Т. 60. С. 15–28.
2. 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
3. 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.
4. 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
5. Haase C. On the complexity of model checking counter automata. Ph.D. Thesis. University of Oxford.
2012.
6. 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
7. 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
8. 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.
2017. Vol. 17, no. 4. P. 21–25.
9. 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
10. Richard D. What are Weak Arithmetics? // Theoretical Computer Science. 2001. Vol. 257. P. 17–29.
11. Robinson J. Definability and decision problems in arithmetic // The Journal of Symbolic Logic. 1949.
Vol. 14. P. 98–114. doi:10.2307/2266510
12. Mostowski A. On direct products of theories // The Journal of Symbolic Logic. 1952. Vol. 17, no. 1.
P. 1–31. doi:10.2307/2267454
13. Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970. Т. 191, № 2.
С. 278–282.
14. Матиясевич Ю. В. Десятая проблема Гильберта. М.: Физматлит. 1993.
15. 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
16. Woods A. Some problems in logic and number theory. PhD Thesis. University of Manchester. 1981.
17. 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
18. 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.
19. Косовский Н. К. О решении систем, состоящих одновременно из уравнений в словах и неравенств в длинах слов // Записки научных семинаров ЛОМИ. 1974. Т. 40. С. 24–29.
Published
2018-12-28
How to Cite
СТАРЧАК, Михаил Романович. Some Decidability and Definability Problems for the Predicate of the Divisibility on Two Consecutive Numbers. Computer Tools in Education, [S.l.], n. 6, p. 5-15, dec. 2018. ISSN 2071-2359. Available at: <http://cte.eltech.ru/ojs/index.php/kio/article/view/1552>. Date accessed: 22 july 2019. doi: https://doi.org/10.32603/2071-2340-2018-6-5-15.
Section
Computer science