zbMATH — the first resource for mathematics

Diophantine theory of free inverse semigroups. (Russian) Zbl 0584.03005
An elementary sentence is diophantine if it has the following form: \(\exists x_ 1...x_ n\) \(F(x_ 1,...,x_ n)\) where \(F(x_ 1,...,x_ n)\) is a conjunction of atomic formulae. Let I denote a free inverse semigroup over a set A with at least two elements \(a_ 1\), \(a_ 2\). It is proved that any diophantine theory of I (i.e. any family of all diophantine sentences that hold in I) of signature \(<\cdot,^{-1},a_ 1,a_ 2>\) is undecidable.
Reviewer: M.Demlová

03B25 Decidability of theories and sets of sentences
20M05 Free semigroups, generators and relations, word problems
Full Text: EuDML