Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1068

Preprint Number 1068

Previous Next Preprint server

1068. Christian Herrmann, Yasuyuki Tsukamoto, Martin Ziegler
On the consistency problem for modular lattices and related structures

Submission date: 12 July 2016


The consistency problem for a class of algebraic structures asks for an algorithm to decide for any given conjunction of equations whether it admits a non-trivial satisfying assignment within some member of the class. By Adyan (1955) and Rabin (1958) it is known unsolvable for (the class of) groups and, recently, by Bridson and Wilton (2015) for finite groups. We derive unsolvability for (finite) modular lattices and various subclasses; in particular, the class of all subspace lattices of finite dimensional vector spaces over a fixed or arbitrary field of characteristic $0$. The lattice results are used to prove unsolvability of the consistency problem for (finite) rings and (finite) representable relation algebras. These results in turn apply to equations between simple expressions in Grassmann-Cayley algebra and to functional and embedded multivalued dependencies in databases.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1607.03315: pdf, ps.

Last updated: July 18 2016 16:23 Please send your corrections to: