Вестник КазНУ. Серия математика, механика, информатика (Jun 2017)

Сложность решеток квазимногообразий для классов дифференциальных группоидов

  • S. M. Lutsak

Journal volume & issue
Vol. 93, no. 1
pp. 32 – 45

Abstract

Read online

В работе выполнено исследование сложности строения решеток (относительных) квазимногообразий для классов дифференциалных группоидов. Вопрос о том, что считать сложностью решетки квазимногообразий и какие решетки квазимногообразий являются сложными согласно той или иной мере сложности, а какие - нет, изучался многими авторами. Хорошо известны две меры сложности строения решеток квазимногообразий: иррациональность (невычислимость множества всех их конечных подрешеток) и Q-универсальность. Иррациональность решетки квазимногообразий означает, что не существует алгоритма, который по заданной конечной решетке определял бы, вложима эта решетка в рассматриваемую решетку квазимногообразий или нет. Другая мера сложности строения решеток квазимногообразий выражается понятием Q-универсальности. Это значит, что решетка квазимногообразий для любого квазимногообразия конечной сигнатуры является гомоморфным образом некоторой подрешетки рассматриваемой Q-универсальной решетки квазимногообразий. Два года назад была установлена связь между иррациональностью и Q-универсальностью и поставлена проблема. Верно ли, что любой Q-универсальный класс систем фиксированной сигнатуры содержит иррациональный подкласс? Существует ли не Q-универсальный класс, но, тем не менее, являющийся иррациональным? Автором доказана выполнимость нетривиального тождества на решетках квазимногообразий для классов дифференциалных группоидов. Установлено, что существует континуум иррациональных классов дифференциалных группоидов, не являющихся Q-универсальными.

Keywords