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

Belegradek, Oleg

doi:10.1090/S0002-9939-96-03209-1

Degrees of unsolvability of first order decision problems for finitely presented groups
HTML articles powered by AMS MathViewer

by Oleg V. Belegradek PDF

Proc. Amer. Math. Soc. 124 (1996), 623-625 Request permission

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

O. V. Belegradek, The Mal′cev correspondence revisited, Proceedings of the International Conference on Algebra, Part 1 (Novosibirsk, 1989) Contemp. Math., vol. 131, Amer. Math. Soc., Providence, RI, 1992, pp. 37–59. MR 1175761, DOI 10.1007/bf00971121
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.
George S. Sacerdote, Some undecidable problems in group theory, Proc. Amer. Math. Soc. 36 (1972), 231–238. MR 320119, DOI 10.1090/S0002-9939-1972-0320119-6
George S. Sacerdote, On a problem of Boone, Math. Scand. 31 (1972), 111–117. MR 318324, DOI 10.7146/math.scand.a-11417