The problem of solvability of a positive theory of an arbitrary group is algorithmically unsolvable
https://doi.org/10.22405/2226-8383-2023-24-1-40-49
Abstract
In paper proved that it is impossible to build an algorithm that allows you to determine from an arbitrary finite task of the group whether it is solvable her positive theory. The specified group property is not Markov, so the fundamental Adyan-Rabin theorem does not apply to it.
About the Authors
Valeriy Georgievich Durnev
Yaroslavl State University
Russian Federation
Russian Federation
Alena Igorevna Zetkina
Yaroslavl State University; Voroneg State University
Russian Federation
Russian Federation
References
1. Adyan, S, I. 1955, “Algorithmic intractable problems of recognizing some properties of groups”,
2. Dokl. USSR ACADEMY OF SCIENCES, vol. 103, no. 4, pp. 533-535.
3. Adyan, S, I. 1957, “Insolubility of some algorithmic problems of group theory”, Works of MMO,
4. vol. 6. pp. 231-298.
5. Rabin M. O. 1958, “Recursive unsolvability of group theoretic problems”, Ann. of Math., vol. 67,
6. no. 1, pp. 172-194.
7. Collings D. J. 1992, “On recognizing Hopf groups”, Arh. Math., vol. 20, pp. 235-240.
8. Miller C. F. III. 1992, “Decision problems for groups – servey and reflections”, Math. Sci. Res.
9. Inst. Publ., vol. 23, pp. 1-59.
10. Miller C. F. III & Schupp P.E. 1971, “Embeddings into Hopfian groups”, Journal Algebra,
11. vol. 17, pp. 171-176.
12. Miller C. F. III. 1966, “On group-theoretic decision problems and their classification”, Ann. of
13. Math. Studies, vol. 68. Princeton University Press.
14. Merzlyakov Yu. I. 1966, “Positive formulas on free groups”, Algebra and logic, vol. 5, issue 4.
15. pp. 25-42.
16. Sacerdote G. S. 1973, “Almost all free products of groups have the same positive theory”,
17. Journal Algebra, vol. 27, no. 3, pp. 475-485.
18. Peryazev N. A. 1985, “Positive indistinguishability of algebraic systems and completeness of
19. positive theories”, Mathem. notes, vol. 38, no. 2, pp. 208-212.
20. Peryazev N. A. 1993, “Positive theories of free monoids”, Algebra and logic, vol. 32, no. 2,
21. pp. 148-159.
22. Remeslenikov V. N. 1989, “∃-free groups”, Sib. mate. magazine, vol. 30, no. 6. pp. 193-197.
23. Makanin G. S. 1984, “Solvability of universal and positive free theories groups”, Isv. USSR
24. ACADEMY OF SCIENCES. Matem series, no. 2, pp. 35-749.
25. Matiyasevich Yu. V. 1970, “Diophancy of enumerated sets”, Dokl. USSR ACADEMY OF
26. SCIENCES, vol. 130, no. 3. pp. 495-498.
27. Maltsev A. I. 1960, “About one correspondence between rings and groups”, Mathem. Sat.,
28. vol. 50, no. 2. pp. 257-266.
29. Borisov V. V., 1969, “Simple examples of groups with an unsolvable identity problem” //
30. Mathem. notes. 1969. Vol. 6, issue 5. pp. 521-532.
Review
For citations:
Durnev V.G., Zetkina A.I. The problem of solvability of a positive theory of an arbitrary group is algorithmically unsolvable. Chebyshevskii Sbornik. 2023;24(1):40-49. (In Russ.) https://doi.org/10.22405/2226-8383-2023-24-1-40-49
Views:
313
Email this article 