The complexity of the word problem for abelian l-groups (Q1095897): Difference between revisions

Using the easily established fact that any two divisible Abelian linearly ordered groups satisfy the same sentences [\textit{A. Robinson}, Complete theories (1956; Zbl 0070.027)], the author gives a one line proof that any two nontrivial Abelian linearly ordered groups satisfy the same existential sentences. This result was first proved by \textit{J. S. Gurevich} and \textit{A. I. Kokorin} [Algebra Logika Sem. 2, No.1, 37-39 (1963; Zbl 0192.041)]. Any Abelian lattice-ordered group is a subdirect product of Abelian linearly ordered groups [\textit{M. Anderson} and \textit{T. Feil}, Lattice-ordered groups - an introduction, Reidel Pub. Co.]. The main result of the paper under review is: Theorem: Let \(G\leq \prod_{i\in I}G_ i\) be an Abelian lattice-ordered group given as such a subdirect product. Let \(\phi =\exists x_ 1...\exists x_ n\gamma (x_ 1,...,x_ n)\) be an existential sentence in the language of Abelian lattice-ordered groups where \(\gamma\) is written as conjunctions and disjunctions of equations and inequations. Assume that \(G\vDash \phi\). Then there is a finite t (the minimum of \(| I|\) and the number of inequations in \(\gamma)\) and \(a_ 1,...,a_ n\in Z^ t\) with each \(| a_ i| \leq n^{n/2}(n+1)r^ n\) such that \(Z^ t\vDash \gamma (a_ 1,...,a_ n)\) where \(r=rank(\gamma).\) The proof is straightforward but elegant. Coding in the knapsack problem leads to: Corollary: The universal theory of the class of all Abelian lattice-ordered groups of dimension (the maximal cardinal of a pairwise disjoint set) belonging to any given non-trivial subset of \(\omega\cup \{\infty \}\) is co-NP hard. This improves Khisamiev's result that the universal theory of Abelian lattice-ordered groups is decidable [\textit{N. G. Khisamiev} and \textit{A. I. Kokorin}, Algebra Logika Sem. 5, No.1, 41-50 (1966; Zbl 0254.06015)].