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

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

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

ОпределенияПравить

Для алгебраической системы $\mathfrak{A}=⟨<!--\; ⟨\; -->A,F,R⟩<!--\; ⟩\; -->$${\mathfrak {A}}=\langle A,F,R\rangle$  с набором операций $F=⟨<!--\; ⟨\; -->f_1:A^{n_1}\to <!--\; \to \; -->A,\dots <!--\; \dots \; -->f_i:A^{n_i}\to <!--\; \to \; -->A,\dots <!--\; \dots \; -->⟩<!--\; ⟩\; -->$$F=\langle f_{1}:A^{n_{1}}\to A,\dots f_{i}:A^{n_{i}}\to A,\dots \rangle$  и отношений $R=⟨<!--\; ⟨\; -->r_1\subseteq <!--\; \subseteq \; -->A^{m_1},\dots <!--\; \dots \; -->r_i\subseteq <!--\; \subseteq \; -->A^{m_i},\dots <!--\; \dots \; -->⟩<!--\; ⟩\; -->$$R=\langle r_{1}\subseteq A^{m_{1}},\dots r_{i}\subseteq A^{m_{i}},\dots \rangle$  квазиатомарными считаются формулы вида:

1. $r_i(f_{j1}(x_1,\dots <!--\; \dots \; -->,x_{n_j}),\dots <!--\; \dots \; -->,f_{k{m}_i}(x_{k1},\dots <!--\; \dots \; -->,x_{n_k}))$$r_{i}(f_{j1}(x_{1},\dots ,x_{n_{j}}),\dots ,f_{km_{i}}(x_{k1},\dots ,x_{n_{k}}))$  (или в нотации отношений: $(f_{j1}(x_1,\dots <!--\; \dots \; -->x_{n_j}),\dots <!--\; \dots \; -->,f_{k{m}_i}(x_{k1},\dots <!--\; \dots \; -->,x_{n_k}))\in <!--\; \in \; -->r_i$$(f_{j1}(x_{1},\dots x_{n_{j}}),\dots ,f_{km_{i}}(x_{k1},\dots ,x_{n_{k}}))\in r_{i}$ ),
2. $f_j(x_1,\dots <!--\; \dots \; -->,x_{n_j})=f_k(x_1,\dots <!--\; \dots \; -->,x_{n_k})$$f_{j}(x_{1},\dots ,x_{n_{j}})=f_{k}(x_{1},\dots ,x_{n_{k}})$ ,

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

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

$\mathrm{\forall <!--\; \forall \; -->}{x}_1,\dots <!--\; \dots \; -->,x_k({\mathcal{F}}_1\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->{\mathcal{F}}_m\Rightarrow <!--\; \Rightarrow \; -->{\mathcal{F}}_{m+1})$$\forall x_{1},\dots ,x_{k}\,{\big (}{\mathcal {F}}_{1}\land \dots \land {\mathcal {F}}_{m}\Rightarrow {\mathcal {F}}_{m+1}{\big )}$ 

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

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

Всякое многообразие алгебраических систем является квазимногообразием вследствие того, что всякое тождество (из квазиатомарной формулы) $\mathrm{\forall <!--\; \forall \; -->}{x}_1,\dots <!--\; \dots \; -->,x_n\mathcal{F}(x_1,\dots <!--\; \dots \; -->x_n)$$\forall x_{1},\dots ,x_{n}\,{\mathcal {F}}(x_{1},\dots x_{n})$  можно заменить, например, равносильным ему квазитождеством $\mathrm{\forall <!--\; \forall \; -->}{x}_1,\dots <!--\; \dots \; -->,x_n(x_1=x_1\Rightarrow <!--\; \Rightarrow \; -->\mathcal{F}(x_1,\dots <!--\; \dots \; -->,x_n))$$\forall x_{1},\dots ,x_{n}\,{\big (}x_{1}=x_{1}\Rightarrow {\mathcal {F}}(x_{1},\dots ,x_{n}){\big )}$ .

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

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

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

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

ИсторияПравить

Первым результатом применения квазитождеств в общей алгебре считается результат Анатолия Мальцева 1939 года, в котором построена бесконечная серия квазитождеств, характеризующая класс вложимых в группы полугрупп. В работе 1943 года Чена Маккинси^[en] связал с квазитождествами некоторые алгоритмические проблемы алгебры, а одним из результатов решения Робертом Дилуорсом^[en] в 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 экз.