The complexity of quasivariety lattices for the classes of differential groupoids
121 40
Keywords:
quasivariety lattice, unreasonability, Q-universalityAbstract
In this work we explore the complexity of structure of (relative) quasivariety lattices for the classes of differential groupoids. A question, what is the complexity of quasivariety lattice and what quasivariety lattices are complex according to this or that measure of complexity and which are not, studied by many authors. Two complexity measures of the structure of quasivariety lattices are known: unreasonability (non-computability the set of all finite sublattices of the quasivariety lattices) and Q-universality. Unreasonability of the quasivariety lattice means that there is no algorithm which would determine by the given finite lattice, this lattice is embeddable into the considered quasivariety lattice or not. Other complexity measure of the structure of quasivariety lattices is expressed by the concept of Q-universality. It means that the quasivariety lattice for any quasivariety of finite signature is a homomorphic image of some sublattice of the considered Q-universal lattice of quasivarieties. Two years ago it was established a connection between unreasonability and Q-universality; it was also posed the following problem. Does any Q-universal class of algebraic structures of a fixed signature contain a unreasonable subclass? Is there a class of algebraic structures which is not Q-universal but which is nevertheless unreasonable? We find a non-trivial identity holding in quasivariety lattices for the classes of differential groupoids. It is proved that there are continuum many unreasonable classes of the differential groupoids which are not Q-universal.
References
[1] Adams, Miсhaеl, and Kira Adaricheva, and Wieslaw Dziobiak, and Aleksandr Kravchenko. “Open questions related to the problem of Birkhoff and Maltsev.” Stud. Log. 78 (2004): 357–378.
[2] Adams, Miсhaеl, and Wieslaw Dziobiak. “Q-universal quasivarieties of algebras.” Proc. Amer. Math. Soc. 120 (1994): 1053–1059.
[3] Adams, Miсhaеl, and Wieslaw Dziobiak. “Lattice of quasivarieties of 3-element algebras.” J. Algebra 166 (1994): 181–210.
[4] Adams, Miсhaеl, and Wieslaw Dziobiak. “Quasivarieties of distributive lattices with a quantifier.” Discrete Math. 135 (1994): 15–28.
[5] Adams, Miсhaеl, and Wieslaw Dziobiak. “Finite-to-finite universal quasivarieties are Q-universal.” Algebra Universalis 46 (2001): 253–283.
[6] Adams, Miсhaеl, and Wieslaw Dziobiak. “The lattice of quasivarieties of undirected graphs.” Algebra Universalis 47 (2002): 7–11.
[7] Adams, Miсhaеl, and Wieslaw Dziobiak. “Q-universal varieties of bounded lattices.” Algebra Universalis 48 (2002): 333–356.
[8] Birkhoff, Garrett. “Universal algebra.” Proceedings of the First Canadian Mathematical Congress, Montreal, 1945. Toronto: the University of Toronto Press (1946): 310–326.
[9] Burris, Stanley, and Hanamantagouda P. Sankappanavar. A course in universal algebra. New York, Heidelberg, Berlin: Springer-Verl., 1981.
[10] Dziobiak, Wieslaw. Selected topics in quasivarieties of algebraic systems. Manuscript, 1997.
[11] Grätzer, George. General lattice theory. Berlin: Akademie-Verlag, 1978.
[12] Kravchenko, Aleksandr. “Q-universal quasivarieties of graphs.” Algebra and Logic 41 (2002): 311–325.
[13] Kravchenko, Aleksandr. “On the lattices of quasivarieties of differential groupoids.” Comment. Math. Univ. Carolin. 49 (2008): 11–17.
[14] Kravchenko, Aleksandr. “Complexity of quasivariety lattices for varieties of unary algebras. II.” Sib. electron. mathem. rep. 13 (2016): 388–394.
[15] Nurakunov, Anvar. “Unreasonable lattices of quasivarieties.” Internat. J. Algebra Comput. 22 (2012): 1–17.
[16] Nurakunov, Anvar, and Murzabek Imanaliev. “Complexity of quasivariety lattices of pointed Abelian Groups.” Doklady Mathematics 85 (2012): 391–393.
[17] Nurakunov, Anvar, and Marina Semenova, and Anna Zamojska-Dzienio. “On lattices connected with various types of classes of algebraic structures.” Uchenye zapiski kazanskogo universiteta. Seriya fiziko-matematicheskie nauki 154 (2012): 167–179.
[18] Sapir, Mark. “The lattice of quasivarieties of semigroups.” Algebra Universalis 21 (1985): 172–180.
[19] Schwidefsky, Marina, and Anna Zamojska-Dzienio. “Lattices of subclasses. II.” Internat. J. Algebra Comput. 24 (2014): 1099–1126.
[20] Semenova, Marina, and Friedrich Wehrung. “Sublattices of lattices of order-convex sets. II. Posets of finite height.” Internat. J. Algebra Comput. 13 (2003): 543–564.
[21] Sheremet, Mihail. “Quasivarieties of Cantor algebras.” Algebra Universalis 46 (2001): 193–201.
[22] Gorbunov V. (1995) Stroenie reshetok mnogoobrazij i reshetok kvazimnogoobrazij: skhodstvo i razlichie. I [The structure of variety lattices and quasivariety lattices: similarities and differences. I]. Algebra and Logic, vol. 34, no 2, pp. 142–168.
[23] Gorbunov V. (1995) Stroenie reshetok mnogoobrazij i reshetok kvazimnogoobrazij: skhodstvo i razlichie. II [The structure of variety lattices and quasivariety lattices: similarities and differences. II]. Algebra and Logic, vol. 34, no 4, pp. 369–397.
[24] Gorbunov V. (1995) Stroenie reshetok mnogoobrazij i reshetok kvazimnogoobrazij: skhodstvo i razlichie. III [The structure of variety lattices and quasivariety lattices: similarities and differences. III]. Algebra and Logic, vol. 34, no 6, pp. 646–666.
[25] Gorbunov, Viktor. Algebraic Theory of Quasivarieties. New York: Plenum, 1998.
[26] Gorbunov V., Tumanov V. (1982) Stroenie reshetok kvazimnogoobrazij [The structure of quasivariety lattices]. Tr In-ta matematiki SO AN SSSR, vol. 2, pp. 12–44.
[27] Kravchenko A. (2001) slozhnost reshetok kvazimnogoobrazij dlya mnogoobrazij unarnyh algebr [The complexity of quasivariety lattices for the varieties of unary algebras]. Matem. tr., vol. 4, no. 2, pp. 113–127.
[28] Kravchenko A. (2009) Slozhnost reshetok kvazimnogoobrazij dlya mnogoobrazij differencialnyh gruppoidov [The complexity of quasivariety lattices for the varieties of differential groupoids]. Matem. tr., vol. 12, no. 1, pp. 26–39.
[29] Kravchenko A. (2012) Slozhnost reshetok kvazimnogoobrazij dlya mnogoobrazij differencialnyh gruppoidov. II [The complexity of quasivariety lattices for the varieties of differential groupoids. II]. Matem. tr., vol. 15, no. 2, pp. 89–99.
[30] Kravchenko A. (2012) Minimalnye kvazimnogoobraziya differencialnyh gruppoidov s nenulevym umnozheniem [Minimum quasivarieties of differential groupoids with nonzero multiplication]. Sib. electron. mathem. rep., vol. 9, pp. 201–207.
[31] Kravchenko A., Semenova M. (2011) Universalnaya algebra i teoriya reshetok [Universal algebra and lattice theory]. Новосибирск: НГУ, 74 p.
[32] Maltsev A. (1968) O nekotoryh pogranichnyh voprosah algebry i matematicheskoj logiki [On some boundary problems of algebra and mathematical logic]. Trudy mezhdunarodnogo matematicheskogo kongressa (Moskva, 1966), M.: Mir, pp. 217–231.
[33] Maltsev, Anatolij. Algebraic systems. Berlin, Heidelberg: Springer-Verlag, 1973.
[34] Nurakunov A. (2014) Reshetki kvazimnogoobrazij tochechnyh abelevyh grupp [Quasivariety lattices of pointed Abelian groups]. Algebra and Logic, vol. 53, no. 3, pp. 372–400.
[35] Nurakunov A., Imanaliev M. (2012) Slozhnost reshetok kvazimnogoobrazij tochechnyh abelevyh grupp [The complexity of quasivariety lattices of pointed Abelian groups]. Doklady akademii nauk, vol. 444, no. 5, pp. 480–482.
[36] Semenova M., Zamojska-Dzhenio A. (2012) O reshetkah podklassov [On lattices of subclasses]. Sib. Mat. Zh., vol. 53, no. 5, pp. 1111–1132.
[37] Tumanov V. (1983) Konechnye distributivnye reshetki kvazimnogoobrazij [Finite distributive lattice of quasivarieties]. Algebra and logic, vol. 22, no. 2, pp. 168–181.
[38] Shvidefski M. (2015) O slozhnosti reshetok kvazimnogoobrazij [On the complexity of quasivariety lattices]. Algebra and logic, vol. 54, no. 3, pp. 381–398.
[2] Adams, Miсhaеl, and Wieslaw Dziobiak. “Q-universal quasivarieties of algebras.” Proc. Amer. Math. Soc. 120 (1994): 1053–1059.
[3] Adams, Miсhaеl, and Wieslaw Dziobiak. “Lattice of quasivarieties of 3-element algebras.” J. Algebra 166 (1994): 181–210.
[4] Adams, Miсhaеl, and Wieslaw Dziobiak. “Quasivarieties of distributive lattices with a quantifier.” Discrete Math. 135 (1994): 15–28.
[5] Adams, Miсhaеl, and Wieslaw Dziobiak. “Finite-to-finite universal quasivarieties are Q-universal.” Algebra Universalis 46 (2001): 253–283.
[6] Adams, Miсhaеl, and Wieslaw Dziobiak. “The lattice of quasivarieties of undirected graphs.” Algebra Universalis 47 (2002): 7–11.
[7] Adams, Miсhaеl, and Wieslaw Dziobiak. “Q-universal varieties of bounded lattices.” Algebra Universalis 48 (2002): 333–356.
[8] Birkhoff, Garrett. “Universal algebra.” Proceedings of the First Canadian Mathematical Congress, Montreal, 1945. Toronto: the University of Toronto Press (1946): 310–326.
[9] Burris, Stanley, and Hanamantagouda P. Sankappanavar. A course in universal algebra. New York, Heidelberg, Berlin: Springer-Verl., 1981.
[10] Dziobiak, Wieslaw. Selected topics in quasivarieties of algebraic systems. Manuscript, 1997.
[11] Grätzer, George. General lattice theory. Berlin: Akademie-Verlag, 1978.
[12] Kravchenko, Aleksandr. “Q-universal quasivarieties of graphs.” Algebra and Logic 41 (2002): 311–325.
[13] Kravchenko, Aleksandr. “On the lattices of quasivarieties of differential groupoids.” Comment. Math. Univ. Carolin. 49 (2008): 11–17.
[14] Kravchenko, Aleksandr. “Complexity of quasivariety lattices for varieties of unary algebras. II.” Sib. electron. mathem. rep. 13 (2016): 388–394.
[15] Nurakunov, Anvar. “Unreasonable lattices of quasivarieties.” Internat. J. Algebra Comput. 22 (2012): 1–17.
[16] Nurakunov, Anvar, and Murzabek Imanaliev. “Complexity of quasivariety lattices of pointed Abelian Groups.” Doklady Mathematics 85 (2012): 391–393.
[17] Nurakunov, Anvar, and Marina Semenova, and Anna Zamojska-Dzienio. “On lattices connected with various types of classes of algebraic structures.” Uchenye zapiski kazanskogo universiteta. Seriya fiziko-matematicheskie nauki 154 (2012): 167–179.
[18] Sapir, Mark. “The lattice of quasivarieties of semigroups.” Algebra Universalis 21 (1985): 172–180.
[19] Schwidefsky, Marina, and Anna Zamojska-Dzienio. “Lattices of subclasses. II.” Internat. J. Algebra Comput. 24 (2014): 1099–1126.
[20] Semenova, Marina, and Friedrich Wehrung. “Sublattices of lattices of order-convex sets. II. Posets of finite height.” Internat. J. Algebra Comput. 13 (2003): 543–564.
[21] Sheremet, Mihail. “Quasivarieties of Cantor algebras.” Algebra Universalis 46 (2001): 193–201.
[22] Gorbunov V. (1995) Stroenie reshetok mnogoobrazij i reshetok kvazimnogoobrazij: skhodstvo i razlichie. I [The structure of variety lattices and quasivariety lattices: similarities and differences. I]. Algebra and Logic, vol. 34, no 2, pp. 142–168.
[23] Gorbunov V. (1995) Stroenie reshetok mnogoobrazij i reshetok kvazimnogoobrazij: skhodstvo i razlichie. II [The structure of variety lattices and quasivariety lattices: similarities and differences. II]. Algebra and Logic, vol. 34, no 4, pp. 369–397.
[24] Gorbunov V. (1995) Stroenie reshetok mnogoobrazij i reshetok kvazimnogoobrazij: skhodstvo i razlichie. III [The structure of variety lattices and quasivariety lattices: similarities and differences. III]. Algebra and Logic, vol. 34, no 6, pp. 646–666.
[25] Gorbunov, Viktor. Algebraic Theory of Quasivarieties. New York: Plenum, 1998.
[26] Gorbunov V., Tumanov V. (1982) Stroenie reshetok kvazimnogoobrazij [The structure of quasivariety lattices]. Tr In-ta matematiki SO AN SSSR, vol. 2, pp. 12–44.
[27] Kravchenko A. (2001) slozhnost reshetok kvazimnogoobrazij dlya mnogoobrazij unarnyh algebr [The complexity of quasivariety lattices for the varieties of unary algebras]. Matem. tr., vol. 4, no. 2, pp. 113–127.
[28] Kravchenko A. (2009) Slozhnost reshetok kvazimnogoobrazij dlya mnogoobrazij differencialnyh gruppoidov [The complexity of quasivariety lattices for the varieties of differential groupoids]. Matem. tr., vol. 12, no. 1, pp. 26–39.
[29] Kravchenko A. (2012) Slozhnost reshetok kvazimnogoobrazij dlya mnogoobrazij differencialnyh gruppoidov. II [The complexity of quasivariety lattices for the varieties of differential groupoids. II]. Matem. tr., vol. 15, no. 2, pp. 89–99.
[30] Kravchenko A. (2012) Minimalnye kvazimnogoobraziya differencialnyh gruppoidov s nenulevym umnozheniem [Minimum quasivarieties of differential groupoids with nonzero multiplication]. Sib. electron. mathem. rep., vol. 9, pp. 201–207.
[31] Kravchenko A., Semenova M. (2011) Universalnaya algebra i teoriya reshetok [Universal algebra and lattice theory]. Новосибирск: НГУ, 74 p.
[32] Maltsev A. (1968) O nekotoryh pogranichnyh voprosah algebry i matematicheskoj logiki [On some boundary problems of algebra and mathematical logic]. Trudy mezhdunarodnogo matematicheskogo kongressa (Moskva, 1966), M.: Mir, pp. 217–231.
[33] Maltsev, Anatolij. Algebraic systems. Berlin, Heidelberg: Springer-Verlag, 1973.
[34] Nurakunov A. (2014) Reshetki kvazimnogoobrazij tochechnyh abelevyh grupp [Quasivariety lattices of pointed Abelian groups]. Algebra and Logic, vol. 53, no. 3, pp. 372–400.
[35] Nurakunov A., Imanaliev M. (2012) Slozhnost reshetok kvazimnogoobrazij tochechnyh abelevyh grupp [The complexity of quasivariety lattices of pointed Abelian groups]. Doklady akademii nauk, vol. 444, no. 5, pp. 480–482.
[36] Semenova M., Zamojska-Dzhenio A. (2012) O reshetkah podklassov [On lattices of subclasses]. Sib. Mat. Zh., vol. 53, no. 5, pp. 1111–1132.
[37] Tumanov V. (1983) Konechnye distributivnye reshetki kvazimnogoobrazij [Finite distributive lattice of quasivarieties]. Algebra and logic, vol. 22, no. 2, pp. 168–181.
[38] Shvidefski M. (2015) O slozhnosti reshetok kvazimnogoobrazij [On the complexity of quasivariety lattices]. Algebra and logic, vol. 54, no. 3, pp. 381–398.
Downloads
How to Cite
Lutsak, S. M. (2018). The complexity of quasivariety lattices for the classes of differential groupoids. Journal of Mathematics, Mechanics and Computer Science, 93(1), 32–45. Retrieved from https://bm.kaznu.kz/index.php/kaznu/article/view/432
Issue
Section
Mathematics
