Сложность решеток квазимногообразий для классов дифференциальных группоидов
65 27
Ключевые слова:
решетка квазимногообразий, иррациональность, Q-универсальностьАннотация
В работе выполнено исследование сложности строения решеток (относительных) квазимногообразий для классов дифференциалных группоидов. Вопрос о том, что считать сложностью решетки квазимногообразий и какие решетки квазимногообразий являются сложными согласно той или иной мере сложности, а какие - нет, изучался многими авторами. Хорошо известны две меры сложности строения решеток квазимногообразий: иррациональность (невычислимость множества всех их конечных подрешеток) и Q-универсальность. Иррациональность решетки квазимногообразий означает, что не существует алгоритма, который по заданной конечной решетке определял бы, вложима эта решетка в рассматриваемую решетку квазимногообразий или нет. Другая мера сложности строения решеток квазимногообразий выражается понятием Q-универсальности. Это значит, что решетка квазимногообразий для любого квазимногообразия конечной сигнатуры является гомоморфным образом некоторой подрешетки рассматриваемой Q-универсальной решетки квазимногообразий. Два года назад была установлена связь между иррациональностью и Q-универсальностью и поставлена проблема. Верно ли, что любой Q-универсальный класс систем фиксированной сигнатуры содержит иррациональный подкласс? Существует ли не Q-универсальный класс, но, тем не менее, являющийся иррациональным? Автором доказана выполнимость нетривиального тождества на решетках квазимногообразий для классов дифференциалных группоидов. Установлено, что существует континуум иррациональных классов дифференциалных группоидов, не являющихся Q-универсальными.
Библиографические ссылки
[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.
Загрузки
Опубликован
2018-06-27
Как цитировать
Lutsak, S. M. (2018). Сложность решеток квазимногообразий для классов дифференциальных группоидов. Вестник КазНУ. Серия математика, механика, информатика, 93(1), 32–45. извлечено от https://bm.kaznu.kz/index.php/kaznu/article/view/432
Выпуск
Раздел
Математика
