Квазимногообразие

Квазимногообра́зие (от лат. quas(i) «наподобие», «нечто вроде») в универсальной алгебре — класс алгебраических систем фиксированной сигнатуры, аксиоматизируемый набором квазитождеств (хорновскими дизъюнктами).

В отличие от многообразий — классов алгебраических систем, аксиоматизируемых тождествами — особую роль в теории квазимногообразий играют теоретико-модельные методы, тогда как многообразия в основном рассматриваются для алгебр (алгебраических систем без отношений в сигнатуре) и изучаются общеалгебраическими методами.

Определения

Для алгебраической системы [math]\displaystyle{ \mathfrak A = \langle A, F, R\rangle }[/math] с набором операций [math]\displaystyle{ F = \langle f_1:A^{n_1} \to A, \dots f_i:A^{n_i} \to A, \dots \rangle }[/math] и отношений [math]\displaystyle{ R= \langle r_1 \subseteq A^{m_1}, \dots r_i \subseteq A^{m_i}, \dots \rangle }[/math] квазиатомарными считаются формулы вида:

1. [math]\displaystyle{ r_i(f_{j1}(x_1, \dots, x_{n_j}), \dots, f_{km_i}(x_{k1}, \dots, x_{n_k})) }[/math] (или в нотации отношений: [math]\displaystyle{ (f_{j1}(x_1, \dots x_{n_j}), \dots, f_{km_i}(x_{k1}, \dots, x_{n_k})) \in r_i }[/math]),
2. [math]\displaystyle{ f_{j}(x_1, \dots, x_{n_j}) = f_{k}(x_1, \dots, x_{n_k}) }[/math],

где [math]\displaystyle{ r_i \in R }[/math], [math]\displaystyle{ f_i \in F }[/math], а [math]\displaystyle{ x_i }[/math] — символы переменных. (Иногда равенство включают в сигнатуру алгебраической системы как отношение и в этом случае достаточно формул первого вида.)

Квазитождества — формулы вида:

[math]\displaystyle{ \forall x_1, \dots, x_k\, \big(\mathcal F_1 \land \dots \land \mathcal F_m \Rightarrow \mathcal F_{m+1}\big) }[/math]

где [math]\displaystyle{ \mathcal F_i }[/math] — квазиатомарные формулы с переменными [math]\displaystyle{ x_1, \dots x_k }[/math]. Квазимногообразие — класс алгебраических систем, задаваемый набором квазитождеств.

Характеристические свойства

Всякое многообразие алгебраических систем является квазимногообразием вследствие того, что всякое тождество (из квазиатомарной формулы) [math]\displaystyle{ \forall x_1, \dots, x_n\, \mathcal F(x_1, \dots x_n) }[/math] можно заменить, например, равносильным ему квазитождеством [math]\displaystyle{ \forall x_1, \dots, x_n\,\big(x_1=x_1\Rightarrow\mathcal F(x_1, \dots, x_n)\big) }[/math].

Если квазимногообразие конечно аксиоматизируемо, то оно конечно определимо.

Единичная алгебраическая система для заданной сигнатуры [math]\displaystyle{ \langle F, R \rangle }[/math], то есть система с носителем из одного элемента [math]\displaystyle{ e }[/math], при которой [math]\displaystyle{ \forall(f\in F)f(e, \dots e_i, \dots)=e }[/math] и [math]\displaystyle{ \forall(r\in R)(e, \dots e_i, \dots) \in r }[/math], является квазимногообразием (и, более того, многообразием). Наименьшее квазимногообразие заданной сигнатуры является многообразием, задаётся тождествами [math]\displaystyle{ \forall(x,y\in A)(x=y) }[/math] и [math]\displaystyle{ \forall(x_1, \dots x_k \in A)(x_1, \dots x_k)\in r }[/math] и состоит из единственной единичной системы. Наибольшее квазимногообразие заднной сигнатуры также является многообразием — классом всех систем заданной сигнатуры, задаваемым тождеством [math]\displaystyle{ \forall(x)(x=x) }[/math].

Всякое квазимногообразие включает произвольное фильтрованное произведение входящих в него систем.

Чтобы класс систем являлся квазимногообразием необходимо и достаточно, чтобы он был одновременно локально замкнут, мультипликативно замкнут (содержал любое декартово произведение своих систем) и содержал единичную систему. Локальная и мультипликативная замкнутость для этого признака могут быть эквивалентно заменены на замкнутость относительно фильтрованных произведений и наследственность^{[уточнить]}.

История

Первым результатом применения квазитождеств в общей алгебре считается результат Анатолия Мальцева 1939 года, в котором построена бесконечная серия квазитождеств, характеризующая класс вложимых в группы полугрупп. В работе 1943 года Чена Маккинси связал с квазитождествами некоторые алгоритмические проблемы алгебры, а одним из результатов решения Робертом Дилуорсом в 1945 году задачи о существовании недистрибутивных решёток с единственным дополнением, стало доказательство факта, что квазимногообразия имеют свободные системы.

Теорема Новикова (1955) о неразрешимости проблемы равенства слов в группах фактически означает неразрешимость хорновой теории групп, то есть также может быть отнесена к результатам, относящимся к квазимногообразниям.

Становление теории квазимногообразий как самостоятельной ветви универсальной алгебры относится к работам Мальцева, Табаты и Фудзивары конца 1950-х — начала 1960-х годов. Доклад Мальцева на Международном конгрессе математиков 1966 года в Москве, в котором были сформулированы некоторые важные проблемы, относящиеся к квазимногообразиям, способствовал росту интереса математиков к этой ветви.

Особый всплеск интереса к теории квазимногообразий проявился в 1970-е годы, когда началось широкое применение хорновой логики в логическом программировании (прежде всего, в работах, связанных с языком программирования Пролог) и в теории баз данных.

Литература

• Горбунов В. А. Алгебраическая теория квазимногообразий. — Новосибирск: Научная книга, 1999. — 368 с. — (Сибирская школа алгебры и логики). — ISBN 5-88119-015-7.
• Аратмонов В. А.; Салий В. Н.; Скорняков Л. А.; Шеврин Л. Н.; Шульгейфер Е. Г. Универсальные алгебры // Общая алгебра / под общей редакцией Скорнякова Л. А.. — М.: Наука, 1991. — Т. 2. — С. 295—367. — 480 с. — (Справочная математическая библиотека). — 25 500 экз. — ISBN 5-02-014427-4.
• Мальцев А. И. Алгебраические системы. — М.: Наука, 1970. — 392 с. — 17 500 экз.