×

Decidability of the universal and positive theories of a free group. (English. Russian original) Zbl 0578.20001

Math. USSR, Izv. 25, 75-88 (1985); translation from Izv. Akad. Nauk SSSR, Ser. Mat. 48, No. 4, 735-749 (1984).
It is proved that both the universal theory and the positive theory of a free group of finite rank are decidable (Theorems 1 and 2). In the proofs, the author uses essentially an algorithm that determines the solvability of equations in a free group [the author, Izv. Akad. Nauk SSSR, Ser. Mat. 46, No. 6, 1199-1273 (1982; Zbl 0511.20019), a new proof of Theorem 10.3 is given here with new, significantly increased, bounds in order to eliminate a gap in this paper] and the reviewer’s old result about positive formulae on free groups [Algebra Logika 5, No. 4, 25-42 (1966; Zbl 0216.29402)].
Reviewer: Yu.I.Merzlyakov

MSC:

20A10 Metamathematical considerations in group theory
20E05 Free nonabelian groups
03C07 Basic properties of first-order languages and structures
20F05 Generators, relations, and presentations of groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
03C60 Model-theoretic algebra
20A05 Axiomatics and elementary properties of groups
PDFBibTeX XMLCite
Full Text: DOI