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

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

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

Определение

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

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

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

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

<math>\forall(x_1, \dots x_k) \mathcal F_1 \and \dots \and \mathcal F_m \Rightarrow \mathcal F_{m+1}</math>

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

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

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

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

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

Отрывок, характеризующий Квазимногообразие

Дождик прошел, только падал туман и капли воды с веток деревьев. Денисов, эсаул и Петя молча ехали за мужиком в колпаке, который, легко и беззвучно ступая своими вывернутыми в лаптях ногами по кореньям и мокрым листьям, вел их к опушке леса.
Выйдя на изволок, мужик приостановился, огляделся и направился к редевшей стене деревьев. У большого дуба, еще не скинувшего листа, он остановился и таинственно поманил к себе рукою.
Денисов и Петя подъехали к нему. С того места, на котором остановился мужик, были видны французы. Сейчас за лесом шло вниз полубугром яровое поле. Вправо, через крутой овраг, виднелась небольшая деревушка и барский домик с разваленными крышами. В этой деревушке и в барском доме, и по всему бугру, в саду, у колодцев и пруда, и по всей дороге в гору от моста к деревне, не более как в двухстах саженях расстояния, виднелись в колеблющемся тумане толпы народа. Слышны были явственно их нерусские крики на выдиравшихся в гору лошадей в повозках и призывы друг другу.
– Пленного дайте сюда, – негромко сказал Денисоп, не спуская глаз с французов.
Казак слез с лошади, снял мальчика и вместе с ним подошел к Денисову. Денисов, указывая на французов, спрашивал, какие и какие это были войска. Мальчик, засунув свои озябшие руки в карманы и подняв брови, испуганно смотрел на Денисова и, несмотря на видимое желание сказать все, что он знал, путался в своих ответах и только подтверждал то, что спрашивал Денисов. Денисов, нахмурившись, отвернулся от него и обратился к эсаулу, сообщая ему свои соображения.
Петя, быстрыми движениями поворачивая голову, оглядывался то на барабанщика, то на Денисова, то на эсаула, то на французов в деревне и на дороге, стараясь не пропустить чего нибудь важного.
– Пг'идет, не пг'идет Долохов, надо бг'ать!.. А? – сказал Денисов, весело блеснув глазами.
– Место удобное, – сказал эсаул.
– Пехоту низом пошлем – болотами, – продолжал Денисов, – они подлезут к саду; вы заедете с казаками оттуда, – Денисов указал на лес за деревней, – а я отсюда, с своими гусаг'ами. И по выстг'елу…
– Лощиной нельзя будет – трясина, – сказал эсаул. – Коней увязишь, надо объезжать полевее…
В то время как они вполголоса говорили таким образом, внизу, в лощине от пруда, щелкнул один выстрел, забелелся дымок, другой и послышался дружный, как будто веселый крик сотен голосов французов, бывших на полугоре. В первую минуту и Денисов и эсаул подались назад. Они были так близко, что им показалось, что они были причиной этих выстрелов и криков. Но выстрелы и крики не относились к ним. Низом, по болотам, бежал человек в чем то красном. Очевидно, по нем стреляли и на него кричали французы.
– Ведь это Тихон наш, – сказал эсаул.
– Он! он и есть!
– Эка шельма, – сказал Денисов.
– Уйдет! – щуря глаза, сказал эсаул.
Человек, которого они называли Тихоном, подбежав к речке, бултыхнулся в нее так, что брызги полетели, и, скрывшись на мгновенье, весь черный от воды, выбрался на четвереньках и побежал дальше. Французы, бежавшие за ним, остановились.
– Ну ловок, – сказал эсаул.
– Экая бестия! – с тем же выражением досады проговорил Денисов. – И что он делал до сих пор?
– Это кто? – спросил Петя.
– Это наш пластун. Я его посылал языка взять.
– Ах, да, – сказал Петя с первого слова Денисова, кивая головой, как будто он все понял, хотя он решительно не понял ни одного слова.
Тихон Щербатый был один из самых нужных людей в партии. Он был мужик из Покровского под Гжатью. Когда, при начале своих действий, Денисов пришел в Покровское и, как всегда, призвав старосту, спросил о том, что им известно про французов, староста отвечал, как отвечали и все старосты, как бы защищаясь, что они ничего знать не знают, ведать не ведают. Но когда Денисов объяснил им, что его цель бить французов, и когда он спросил, не забредали ли к ним французы, то староста сказал, что мародеры бывали точно, но что у них в деревне только один Тишка Щербатый занимался этими делами. Денисов велел позвать к себе Тихона и, похвалив его за его деятельность, сказал при старосте несколько слов о той верности царю и отечеству и ненависти к французам, которую должны блюсти сыны отечества.
– Мы французам худого не делаем, – сказал Тихон, видимо оробев при этих словах Денисова. – Мы только так, значит, по охоте баловались с ребятами. Миродеров точно десятка два побили, а то мы худого не делали… – На другой день, когда Денисов, совершенно забыв про этого мужика, вышел из Покровского, ему доложили, что Тихон пристал к партии и просился, чтобы его при ней оставили. Денисов велел оставить его.
Тихон, сначала исправлявший черную работу раскладки костров, доставления воды, обдирания лошадей и т. п., скоро оказал большую охоту и способность к партизанской войне. Он по ночам уходил на добычу и всякий раз приносил с собой платье и оружие французское, а когда ему приказывали, то приводил и пленных. Денисов отставил Тихона от работ, стал брать его с собою в разъезды и зачислил в казаки.
Тихон не любил ездить верхом и всегда ходил пешком, никогда не отставая от кавалерии. Оружие его составляли мушкетон, который он носил больше для смеха, пика и топор, которым он владел, как волк владеет зубами, одинаково легко выбирая ими блох из шерсти и перекусывая толстые кости. Тихон одинаково верно, со всего размаха, раскалывал топором бревна и, взяв топор за обух, выстрагивал им тонкие колышки и вырезывал ложки. В партии Денисова Тихон занимал свое особенное, исключительное место. Когда надо было сделать что нибудь особенно трудное и гадкое – выворотить плечом в грязи повозку, за хвост вытащить из болота лошадь, ободрать ее, залезть в самую середину французов, пройти в день по пятьдесят верст, – все указывали, посмеиваясь, на Тихона.
– Что ему, черту, делается, меренина здоровенный, – говорили про него.
Один раз француз, которого брал Тихон, выстрелил в него из пистолета и попал ему в мякоть спины. Рана эта, от которой Тихон лечился только водкой, внутренне и наружно, была предметом самых веселых шуток во всем отряде и шуток, которым охотно поддавался Тихон.
– Что, брат, не будешь? Али скрючило? – смеялись ему казаки, и Тихон, нарочно скорчившись и делая рожи, притворяясь, что он сердится, самыми смешными ругательствами бранил французов. Случай этот имел на Тихона только то влияние, что после своей раны он редко приводил пленных.
Тихон был самый полезный и храбрый человек в партии. Никто больше его не открыл случаев нападения, никто больше его не побрал и не побил французов; и вследствие этого он был шут всех казаков, гусаров и сам охотно поддавался этому чину. Теперь Тихон был послан Денисовым, в ночь еще, в Шамшево для того, чтобы взять языка. Но, или потому, что он не удовлетворился одним французом, или потому, что он проспал ночь, он днем залез в кусты, в самую середину французов и, как видел с горы Денисов, был открыт ими.