×

On the consistency problem for modular lattices and related structures. (English) Zbl 1373.06006

The consistency problem for a class \(\mathcal C\) of algebraic structures is the question if there is an algorithm which decides, for every given conjunction \(\pi\) of equations, whether there is a structure \(A\) in \(\mathcal C\) and a nontrivial assignment into \(A\) that satisfies \(\pi\). (For \(\mathcal C\) a quasivariety, the complement of this problem is commonly known as the triviality problem.) The consistency problem has been shown to be unsolvable for \(\mathcal C\) the class of all groups [S. I. Adyan [Dokl. Akad. Nauk SSSR 103, 533–535 (1955; Zbl 0065.00901); Tr. Mosk. Mat. O.-va 6, 231–298 (1957; Zbl 0080.24101); M. O. Rabin, Ann. Math. (2) 67, 172–194 (1958; Zbl 0079.24802)]. On this basis, it is shown to be unsolvable for any class of modular lattices subject to some constraints (in particular, for the class of subspace lattices of the finitely-dimensional vector space over any field of characteristic 0) and, as a consequence, for some related classes of representable relation algebras and of rings with unit. Also, two related problems, one concerning functional and embedded multivalued database dependencies, the other, simple expressions in Grassmann-Cayley algebras, are shown to be undecidable.

MSC:

06C05 Modular lattices, Desarguesian lattices
08A50 Word problems (aspects of algebraic structures)
03B25 Decidability of theories and sets of sentences
03G15 Cylindric and polyadic algebras; relation algebras
15A75 Exterior algebra, Grassmann algebras
16Z05 Computational aspects of associative rings (general theory)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 1. S. Abramsky and B. Coecke, A categorical semantics of quantum protocols, in Proc. 19th Annual IEEE Symp. Logic in Computer Science (LiCS’04) (IEEE Computer Science Press, 2004) (Extended version at arXiv:quant-ph/0402130 [arXiv] ).
[2] 2. S. I. Adyan, Algorithmic unsolvability of problems of recognition of certain properties of groups. (Russian), Dokl. Akad. Nauk SSSR (N.S.)103 (1955) 533-535. · Zbl 0065.00901
[3] 3. S. I. Adyan, Unsolvability of some algorithmic problems in the theory of groups. (Russian), Trudy Moskov. Mat. Obšč6 (1957) 231-298.
[4] 4. B. Artmann, On coordinates in modular lattices with a homogeneous basis, Illinois J. Math.12 (1968) 626-648. · Zbl 0164.00603
[5] 5. M. R. Bridson and H. Wilton, The triviality problem for profinite completions, Invent. Math.202 (2015) 839-874. genRefLink(16, ’S0218196716500697BIB005’, ’10.1007
[6] 6. R. Freese, Projective geometries as projective modular lattices, Trans. Amer. Math. Soc.251 (1979) 329-342. genRefLink(16, ’S0218196716500697BIB006’, ’10.1090
[7] 7. R. Freese, The variety of modular lattices is not generated by its finite members, Trans. Amer. Math. Soc.255 (1979) 277-300. genRefLink(16, ’S0218196716500697BIB007’, ’10.1090
[8] 8. R. Freese, Free modular lattices, Trans. Amer. Math. Soc.261 (1980) 81-91. genRefLink(16, ’S0218196716500697BIB008’, ’10.1090
[9] 9. R. Freese and J. B. Nation, Finitely presented lattices, Proceedings of the American Mathematical Society77 (1979) 174-178, [https://doi.org/10.1090/S0002-9939-1979-0542080-8] . genRefLink(16, ’S0218196716500697BIB009’, ’10.1090 · Zbl 0387.06007
[10] 10. V. A. Gorbunov, Algebraic Theory of Quasivarieties (Novosibirsk, 1998). · Zbl 0986.08001
[11] 11. R. M. Guralnick, W. M. Kantor, M. Kassabov and A. Lubotzky, Presentations of finite simple groups: A computational approach, J. Eur. Math. Soc.13 (2011) 391-458. genRefLink(16, ’S0218196716500697BIB011’, ’10.4171 · Zbl 1256.20008
[12] 12. M. Hannula and J. Kontinen, A finite axiomatization of conditional independence and inclusion axioms, arXiv:1309.4927v2 [math.LO]. · Zbl 1344.68064
[13] 13. J. Harding, A link between quantum logic and categorical quantum mechanics, Int. J. Theor. Phys.48 (2009) 769-802. genRefLink(16, ’S0218196716500697BIB013’, ’10.1007
[14] 14. J. Harding, Decidability of the equational theory of the continuous geometry CG(), J. Philos. Logic42(3) (2013) 461-465, [http://dx.doi.org/10.1007/S10992-013-9270-X] . genRefLink(16, ’S0218196716500697BIB014’, ’10.1007
[15] 15. C. Herrmann, Rahmen und erzeugende Quadrupel in modularen Verbänden, Algebra Universalis14 (1982) 357-387. genRefLink(16, ’S0218196716500697BIB015’, ’10.1007
[16] 16. C. Herrmann, On the arithmetic of projective coordinate systems,, Trans. Amer. Math. Soc.284 (1984) 759-785, [https://doi.org/10.1090/S0002-9947-1984-0743743-8] . genRefLink(16, ’S0218196716500697BIB016’, ’10.1090 · Zbl 0544.06008
[17] 17. C. Herrmann, Frames of permuting equivalences, Acta Sci. Math.51(1-2) (1987) 93-101. · Zbl 0628.06004
[18] 18. C. Herrmann, On the undecidability of implications between embedded multivalued database dependencies, Information and Computation122 (1995) 221-235. genRefLink(16, ’S0218196716500697BIB018’, ’10.1006
[19] 19. C. Herrmann and M. Ziegler, Computational complexity of quantum satisfiability, in Proc. 26th Annual IEEE Symp. Logic in Computer Science (2011), pp. 175-184.
[20] 20. C. Herrmann and M. Ziegler, Computational complexity of quantum satisfiability, J. ACM63(2) (2016) Article ID: 19. genRefLink(16, ’S0218196716500697BIB020’, ’10.1145
[21] 21. W. Hodges, Model Theory (Cambridge University Press, 1993). · Zbl 0789.03031
[22] 22. B. Jónsson, On the representation of lattices, Math. Scando.1 (1953) 193-206. genRefLink(16, ’S0218196716500697BIB022’, ’10.7146 · Zbl 0053.21304
[23] 23. B. Jónsson, Representation of modular lattices and of relation algebras, Trans. Amer. Math. Soc.92 (1959) 449-464. genRefLink(16, ’S0218196716500697BIB023’, ’10.2307 · Zbl 0105.25302
[24] 24. P. C. Kanellakis, Elements of relational database theory, in Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, ed. J. van Leeuwen (Elsevier, Amsterdam, 1990), pp. 1073-1156. genRefLink(16, ’S0218196716500697BIB024’, ’10.1016 · Zbl 0900.68090
[25] 25. O. G. Kharlampovich and M. V. Sapir, Algorithmic problems in varieties, Internat. J. Algebra Comput.5(4-5) (1995) 379-602. [Abstract] · Zbl 0837.08002
[26] 26. L. Lipshitz, The undecidability of the word problems for projective geometries and modular lattices, Trans. Amer. Math. Soc.193 (1974) 171-180. genRefLink(16, ’S0218196716500697BIB026’, ’10.1090
[27] 27. Sh. Ma, W. Fan and L. Bravo, Extending inclusion dependencies with conditions, Theoret. Comput. Sci.515 (2014) 64-95. genRefLink(16, ’S0218196716500697BIB027’, ’10.1016
[28] 28. J. C. C. McKinsey, The decision problem for some classes of sentences without quantifiers, J. Symbolic Logic8 (1943) 61-76. genRefLink(16, ’S0218196716500697BIB028’, ’10.2307 · Zbl 0063.03864
[29] 29. J. von Neumann, Continuous Geometry, Princeton Mathematical Series, Vol. 25 (Princeton University, 1960).
[30] 30. M. O. Rabin, Recursive unsolvability of group theoretic problems, Ann. of Math. (2)67 (1958) 172-194. genRefLink(16, ’S0218196716500697BIB030’, ’10.2307
[31] 31. Th. Skolem, Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit und Beweisbarkeit mathematischer Sätze nebst einem Theorem über dichte Mengen. Skr. Vidensk. Krist.I(4) (1920) 1-36.
[32] 32. B. Sturmfels, Algorithms in Invariant Theory (Springer, New York, 2008). · Zbl 1154.13003
[33] 33. F. Wehrung, Congruences of lattices and ideals of rings, Chap. 8 in Lattice Theory: Special Topics and Applications, eds. G. Grätzer and F. Wehrung (Birkhäuser, Cham, 2014), pp. 297-335. genRefLink(16, ’S0218196716500697BIB033’, ’10.1007 · Zbl 1345.06006
[34] 34. R. Wille, Über modulare Verbände, die von einer endlichen halbgeordneten Menge frei erzeugt werden, Math. Z.131 (1973) 241-249. genRefLink(16, ’S0218196716500697BIB034’, ’10.1007
[35] 35. A. Wiman, Ueber die Darstellung der symmetrischen und alternirenden Vertauschungsgruppen als Collineationsgruppen von möglichst geringer Dimensionenzahl, Math. Ann.52(2-3) (1899) 243-272. genRefLink(16, ’S0218196716500697BIB035’, ’10.1007 · JFM 30.0126.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.