Abstract
We obtain conditions for the Σ-definability of a subset of the set of naturals in the hereditarily finite admissible set over a model and for the computability of a family of such subsets. We prove that: for each e-ideal I there exists a torsion-free abelian group A such that the family of e-degrees of Σ-subsets of ω in \(\mathbb{H}\mathbb{F}(A)\) coincides with I; there exists a completely reducible torsion-free abelian group in the hereditarily finite admissible set over which there exists no universal Σ-function; for each principal e-ideal I there exists a periodic abelian group A such that the family of e-degrees of Σ-subsets of ω in \(\mathbb{H}\mathbb{F}(A)\) coincides with I.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Morozov A. S. and Puzarenko V. G., “Σ-subsets of naturals,” Algebra i Logika, 43, No. 3, 291–320 (2004).
Rudnev V. A., “Existence of an inseparable pair in the recursive theory of admissible sets,” Algebra i Logika, 27, No. 1, 48–56 (1988).
Puzarenko V. G., “Computability over models of decidable theories,” Algebra i Logika, 39, No. 2, 170–197 (2000).
Morozov A. S., “A Σ-set of natural numbers not enumerable by natural numbers,” Siberian Math. J., 41, No. 6, 1162–1166 (2000).
Khisamiev A. N., “On the Ershov upper semilattice \(\mathfrak{L}_E \),” Siberian Math. J., 45, No. 1, 173–187 (2004).
Barwise J., Admissible Sets and Structures, Springer-Verlag, Berlin (1975).
Ershov Yu. L., Definability and Computability [in Russian], Nauchnaya Kniga, Novosibirsk (1996).
Rogers H., Theory of Recursive Functions and Effective Computability [Russian translation], Mir, Moscow (1972).
Kargapolov M. I. and Merzlyakov Yu. I., Fundamentals of the Theory of Groups [in Russian], Nauka, Moscow (1982).
Kalimullin I. Sh. and Puzarenko V. G., “The computable principles on admissible sets,” Mat. Trudy, 7, No. 2, 35–71 (2004).
Rudnev V. A., “A universal recursive function on admissible sets,” Algebra i Logika, 25, No. 4, 425–435 (1986).
Author information
Authors and Affiliations
Additional information
Original Russian Text Copyright © 2006 Khisamiev A. N.
The author was supported by the President of the Russian Federation (Grant MK1807.2005.1), the Russian Foundation for Basic Research (Grant 05-01-00819), the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2112.2003.1), and the Program “Universities of Russia” (Grant UR.04.01.019).
__________
Translated from Sibirskiĭ Matematicheskiĭ Zhurnal, Vol. 47, No. 3, pp. 695–706, May–June, 2006.
Rights and permissions
About this article
Cite this article
Khisamiev, A.N. On Σ-subsets of naturals over abelian groups. Sib Math J 47, 574–583 (2006). https://doi.org/10.1007/s11202-006-0068-8
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11202-006-0068-8