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

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

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

Определения

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

1. $r_i(f_{j1}(x_1,\dots ,x_{n_j}),\dots ,f_{k{m}_i}(x_{k1},\dots ,x_{n_k}))$ (или в нотации отношений: $(f_{j1}(x_1,\dots x_{n_j}),\dots ,f_{k{m}_i}(x_{k1},\dots ,x_{n_k}))\in r_i$),
2. $f_j(x_1,\dots ,x_{n_j})=f_k(x_1,\dots ,x_{n_k})$,

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

Шаблон:ЯкорьКвазитождества — формулы вида:

$\mathrm{\forall }{x}_1,\dots ,x_k({ℱ}_1\wedge \dots \wedge {ℱ}_m\Rightarrow {ℱ}_{m+1})$

где ${ℱ}_i$ — квазиатомарные формулы с переменными $x_1,\dots x_k$. Квазимногообразие — класс алгебраических систем, задаваемый набором квазитождеств.

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

Всякое многообразие алгебраических систем является квазимногообразием вследствие того, что всякое тождество (из квазиатомарной формулы) $\mathrm{\forall }{x}_1,\dots ,x_nℱ(x_1,\dots x_n)$ можно заменить, например, равносильным ему квазитождеством $\mathrm{\forall }{x}_1,\dots ,x_n(x_1=x_1\Rightarrow ℱ(x_1,\dots ,x_n))$Шаблон:Sfn.

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

Единичная алгебраическая система для заданной сигнатуры $⟨F,R⟩$, то есть система с носителем из одного элемента $e$, при которой $\mathrm{\forall }(f\in F)f(e,\dots e_i,\dots )=e$ и $\mathrm{\forall }(r\in R)(e,\dots e_i,\dots )\in r$, является квазимногообразием (и, более того, многообразием). Наименьшее квазимногообразие заданной сигнатуры является многообразием, задаётся тождествами $\mathrm{\forall }(x,y\in A)(x=y)$ и $\mathrm{\forall }(x_1,\dots x_k\in A)(x_1,\dots x_k)\in r$ и состоит из единственной единичной системы. Наибольшее квазимногообразие заднной сигнатуры также является многообразием — классом всех систем заданной сигнатуры, задаваемым тождеством $\mathrm{\forall }(x)(x=x)$.Шаблон:Sfn

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

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

История

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга