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

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

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

Определения

Для алгебраической системы ${\displaystyle {\mathfrak {A}}=\langle A,F,R\rangle }$ с набором операций ${\displaystyle F=\langle f_{1}:A^{n_{1}}\to A,\dots f_{i}:A^{n_{i}}\to A,\dots \rangle }$ и отношений ${\displaystyle R=\langle r_{1}\subseteq A^{m_{1}},\dots r_{i}\subseteq A^{m_{i}},\dots \rangle }$ квазиатомарными считаются формулы вида:

1. ${\displaystyle r_{i}(f_{j1}(x_{1},\dots ,x_{n_{j}}),\dots ,f_{km_{i}}(x_{k1},\dots ,x_{n_{k}}))}$ (или в нотации отношений: ${\displaystyle (f_{j1}(x_{1},\dots x_{n_{j}}),\dots ,f_{km_{i}}(x_{k1},\dots ,x_{n_{k}}))\in r_{i}}$),
2. ${\displaystyle f_{j}(x_{1},\dots ,x_{n_{j}})=f_{k}(x_{1},\dots ,x_{n_{k}})}$,

где ${\displaystyle r_{i}\in R}$, ${\displaystyle f_{i}\in F}$, а ${\displaystyle x_{i}}$ — символы переменных. (Иногда равенство включают в сигнатуру алгебраической системы как отношение и в этом случае достаточно формул первого вида.)

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

${\displaystyle \forall x_{1},\dots ,x_{k}\,{\big (}{\mathcal {F}}_{1}\land \dots \land {\mathcal {F}}_{m}\Rightarrow {\mathcal {F}}_{m+1}{\big )}}$

где ${\displaystyle {\mathcal {F}}_{i}}$ — квазиатомарные формулы с переменными ${\displaystyle x_{1},\dots x_{k}}$. Квазимногообразие — класс алгебраических систем, задаваемый набором квазитождеств.

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

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

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

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

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

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

Определяющие соотношения

Свободные композиции

Решётки квазимногообразий

История

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

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

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

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

Примечания

1. Горбунов, 1999, Принципиальное отличие состоит в том, что в теории многообразий исследуются алгебры, в то время как в теории квазимногообразий — произвольные алгебраические системы, с. viii.
2. Мальцев, 1970, с. 268.
3. Мальцев, 1970, с. 269—270.
4. Мальцев, 1970, с. 270.
5. Мальцев, 1970, с. 271.
6. Мальцев, 1970, Теорема 2, Следствие 3, с. 271—272.
7. Мальцев А. И. О включении ассоциативных систем в группы // Математический сборник. — 1999. — Т. 6, № 2. — С. 331—336.
8. McKinsey J. The desicion problem for some classes of sentences without quqntifiers // Journal of Symbolic Logic. — 1943. — Т. 8. — С. 61—76.
9. R. P. Dilworth. Lattices with unique complements // Transactions of American Mathematics Society. — 1945. — Т. 56. — С. 123—154.
10. Горбунов, 1999, с. vii—viii.

Литература

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