Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Degrees of unsolvability
of first order decision problems
for finitely presented groups

Author: Oleg V. Belegradek
Journal: Proc. Amer. Math. Soc. 124 (1996), 623-625
MSC (1991): Primary 03D40, 03D30, 20F10, 20F18
MathSciNet review: 1307493
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that for any arithmetical $m$-degree $\mathbf{d}$ there is a first order decision problem $\mathbf{P}$ such that $\mathbf{P}$ has $m$-degree $\mathbf{d}$ for the free 2-step nilpotent group of rank 2. This implies a conjecture of Sacerdote.

References [Enhancements On Off] (What's this?)

  • B O. V. Belegradek, The Mal$^\prime $cev correspondence revisited, Proc. Int. Conf. on Algebra Dedicated to the Memory of A. I. Mal$^\prime $cev (L. A. Bokut$^\prime $, Yu. L. Ershov, and A. I. Kostrikin, eds.), Contemp. Math., vol. 131, Amer. Math. Soc., Providence, RI, 1992, pp. (37--59), MR 93m:03059.
  • M A. I. Mal$^\prime $tsev, A correspondence between rings and groups, Mat. Sb. (N.S.) 50 (1960), 257--
    266; English transl., The metamathematics of algebraic systems. Collected papers: 1936--1967, North-Holland, 1971, pp. 124--137.
  • S1 G. S. Sacerdote, Some unsolvable decision problems in group theory, Proc. Amer. Math. Soc. 36 (1972), 231--238, MR 47:8660.
  • S2 ------, On a problem of Boone, Math. Scand. 31 (1972), 111--117, MR 47:6871.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 03D40, 03D30, 20F10, 20F18

Retrieve articles in all journals with MSC (1991): 03D40, 03D30, 20F10, 20F18

Additional Information

Oleg V. Belegradek
Affiliation: Kemerovo State University, Kemerovo 650043, Russia

Keywords: First order decision problem, $m$-degree
Received by editor(s): August 19, 1994
Additional Notes: The author was partially supported by the AMS fSU Aid Fund.
Communicated by: Andreas R. Blass
Article copyright: © Copyright 1996 American Mathematical Society