Computable embeddability for algebraic structures
Bazhenov N. Mustafa M.
1 July 2022World Scientific
Asian-European Journal of Mathematics
2022#15Issue 7
In computability theory, the standard tool to classify preorders is provided by the computable reducibility. If R and S are preorders with domain ω, then R is computably reducible to S if and only if there is a computable function f such that for all x and y, xRy f(x)Sf(y). We study the complexity of preorders which arise in a natural way in computable structure theory. We prove that the relation of computable isomorphic embeddability among computable torsion abelian groups is a Σ03 complete preorder. A similar result is obtained for computable distributive lattices. We show that the relation of primitive recursive embeddability among punctual structures (in the setting of Kalimullin et al.) is a Σ02 complete preorder.
Computable reducibility , computable structure theory , distributive lattice , isomorphic embedding , preorder , primitive recursion , punctual structure , torsion abelian group
Text of the article Перейти на текст статьи
Sobolev Institute of Mathematics, 4 Akad. Koptyug Avenue, Novosibirsk, 630090, Russian Federation
Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbay Batyr Avenue, Nur-Sultan, 010000, Kazakhstan
Sobolev Institute of Mathematics
Department of Mathematics
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026