Сложность решеток квазимногообразий для классов дифференциальных группоидов
179 42
Кілттік сөздер:
решетка квазимногообразий, иррациональность, 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.
Жүктелулер
Как цитировать
Lutsak, S. M. (2018). Сложность решеток квазимногообразий для классов дифференциальных группоидов. Қазұу Хабаршысы. Математика, механика, информатика сериясы, 93(1), 32–45. вилучено із https://bm.kaznu.kz/index.php/kaznu/article/view/432
Шығарылым
Бөлім
Математика
