On “simple” algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup
https://doi.org/10.22405/2226-8383-2020-21-4-56-71
Abstract
e prove algorithmic undecidability of $\exists \forall^2 \exists^3$-theory for a free semigroup of countable rank. This strengthens the classical Quine's (1946) result [1] on algorithmic undecidability of elementary theory of an arbitrary non-cyclic free semigroup.
About the Authors
Valery Georgievch Durnev
P. G. Demidov Yaroslavl’ University
Russian Federation
doctor of phisics and mathematics, professor
Russian Federation
doctor of phisics and mathematics, professor
Oksana Valerievna Zetkina
P. G. Demidov Yaroslavl’ University
Russian Federation
candidate of economic sciences, associate professor
Russian Federation
candidate of economic sciences, associate professor
Alena Igorevna Zetkina
P. G. Demidov Yaroslavl’ University
Russian Federation
assistent
Russian Federation
assistent
Review
For citations:
Durnev V.G., Zetkina O.V., Zetkina A.I. On “simple” algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup. Chebyshevskii Sbornik. 2020;21(4):56-71. (In Russ.) https://doi.org/10.22405/2226-8383-2020-21-4-56-71
Views:
375
Email this article 