zbMATH — the first resource for mathematics

Nonconstructivizability of the reduced part of a strongly constructive torsion-free Abelian group. (English. Russian original) Zbl 0601.20051
Algebra Logic 24, 69-76 (1985); translation from Algebra Logika 24, No. 1, 108-118 (1985).
S. S. Goncharov presented, at the 5th All-Union (USSR) Conference on Mathematical Logic, the following open problem: is the reduced part of a constructive, torsion-free abelian group constructivizable? In the present paper, the authors give a negative answer to this problem.
An abelian group A is called strongly constructive (constructive), if the fundamental set of the group A is the set \(\omega\) of all natural numbers, and there exists an algorithm, which for any (atomic) formula \(\phi (x_ 0,...,x_{s-1})\) of the restricted predicate calculus of the group signature, and any numbers \(n_ 0,...,n_{s-1}\in \omega\), defines whether or not \(\phi (n_ 0,...,n_{s-1})\) is true in A. The group A is called (strongly) constructivizable, if it is isomorphic to some (strongly) constructive group. The authors prove that there exists a strongly constructivizable torsion-free abelian group whose reduced part is nonconstructivizable (Corollary 2).
Reviewer: K.Honda

20K20 Torsion-free groups, infinite rank
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
03D20 Recursive functions and relations, subrecursive hierarchies
Full Text: DOI EuDML
[1] S. S. Goncharov and V. P. Dobritsa, ”An example of a constructive Abelian group with nonconstructivizable reduced subgroup,” 4th All-Union Conf. on Math. Logic, Kishinev (1976), p. 33. · Zbl 0603.20049
[2] N. G. Khisamiev, ”Strongly constructive Abelian P - groups,” Algebra Logika,22, No. 2, 198–217 (1983). · Zbl 0568.20052
[3] A. I. Mal’tsev, ”Positive and negative enumerations,” Dokl. Akad. Nauk SSSR,160, No. 2, 278–280 (1965).
[4] Yu. L. Ershov, Problems of Solubility and Constructive Models [in Russian], Nauka, Moscow (1980).
[5] Yu. L. Ershov, Enumeration Theory [in Russian], Nauka, Moscow (1977).
[6] M. I. Kargapolov and Yu. I. Merzlyakov, Foundations of Group Theory [in Russian], 3rd ed., Nauka, Moscow (1982). · Zbl 0508.20001
[7] A. I. Mal’tsev, Algorithms and Recursive Functions [in Russian], Nauka, Moscow (1965).
[8] A. G. Kurosch, ”Primitive torsionfreie Abelsche Gruppen vom endliche Range,” Ann. Math.,38, No. 1, 175–203 (1937). · Zbl 0016.01501 · doi:10.2307/1968518
[9] A. I. Mal’tsev, ”Torsion-free Abelian groups of finite rank,” Mat. Sb.,4, No. 1, 45–67 (1938).
[10] V. P. Dobritsa, ”On constructivizable Abelian groups,” Sib. Mat. Zh.,22, No. 3, 208–213 (1981). · Zbl 0473.03037
[11] V. P. Dobritsa, ”Some constructivizations of Abelian groups,” Sib. Mat. Zh.,24, No. 2, 18–25 (1983). · Zbl 0528.20038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.