О квазимногообразиях метрических алгебр тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

□□305400В

На правах рукописи УДК 512.57

Худяков Владимир Александрович

О КВАЗИМНОГООБРАЗИЯХ МЕТРИЧЕСКИХ АЛГЕБР

(01.01.06 - математическая логика, алгебра и теория чисел)

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Абакан - 2007

003054008

Работа выполнена на кафедре алгебры и математической логики Новосибирского государственного университета и в Хакасском государственном университете

Научные руководители:_

доктор физико-математических наук, доцент В. А. Горбунов доктор физико-математических наук, профессор Е. А. Палютин Официальные оппоненты:

доктор физико-математических наук, профессор А. Г. Пинус кандидат физико-математических наук, доцент М. П. Тропин Ведущая организация

Иркутский государственный

педагогический университет

Защита диссертации состоится 1 марта 2007 г. в ^ мин. на заседании диссертационного совета К 212.174.01 Новосибирского государственного университета по адресу: 630090, Новосибирск-90, ул. Пирогова, 2.

С диссертацией можно ознакомиться в библиотеке Хакасского государственного университета.

Автореферат разослан " Ж» января 2007 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент

1 Общая характеристика работы

Диссертация посвящена изучению строения квазиэква-циональных классов метрических алгебр. В следствие невозможности классического определения формулы для метрических алгебр работа разбита на две части. В первой части рассматривается сведение к формулам логики ¿хоо- Вторым способом представления метрической алгебры является многосортная алгебра. Соответственно возникают многосортные формулы языка Ьп- Однако, вевязи с тем, что полученные результаты оказалось возможным обобщить па случай произвольных многосортных алгебраических систем, они приведены именно в общей форме.

Данная работа в некотором смысле является развитием идей, предложенных Горбуновым [1|, для описания свойств эквадиональпых и квазиэквацио-нальных классов алгебраических систем. Краеугольными камнями данного подхода являются понятия "определяющие соотношения"и "конгруэнция".

Задание бесконечной системы в явном виде возможно только указанием алгоритма построения формул ее диаграммы. Определяющие соотношения, предложенные Мальцевым [7,8], являются одним из таких способов.

Если К — произвольный класс алгебраических систем некоторой фиксированной сигнатуры и Л 6 К. То говорят, что пара (X, Д), состоящая из некоторых множества переменных X и атомарных формул Д определяет систему Л в классе К, если существует некоторое отождествление / : X А переменных элементам носителя, для которого выполненены следующие условия:

— множество /(X) порождает Л все формулы из Д выполняются в Л при данной подстановке,

для любых системы ВёКи отображения д : X В, если все формулы из Д выполняются в В при интерпретации д, то существует гомоморфизм К : Л —У В такой, что Л(/(х)) = д(х).

Если пара определяет в классе некоторую систему, то данная система единственна с точностью до изоморфизма.

Мальцев также показал [7], что некоторый класс является предмногообразием в том и только том случае, когда всякая определяющая пара определяет в этом классе систему.

Изучая связь преобразований определяющих пар и отношений между определенными ими системами (теоремы Дика и Тице), нетрудно прийти к выводу, что в теории квазимногообразий роль свободных систем играют конечноопределенные сиситемы. т.е. системы, определенные конечным числом переменных и конечным числом атомарных формул. Дальнейшее развитие теория определяющих соотношений получила при изучении квазиэквациональной логики (Сэлман [14], Квакенбуш [13], Келли [12]).

Как нетрудно видеть, описание конечноопределенных систем в квазимногообразиях, не предстваляет большой сложности. Однако они составлют лишь "верхушку" класса. Чтобы добраться до остальных, требуется рассматривать их гомоморфные образы, что и приводит нас вплотную к понятию конгруэнции.

На этапе становления универсальной алгебры определение конгруэнции прямо переносилось с алгебр (где под конгруэнцией понимается отношение эквивалентности, сохраняющее оновные операции) на системы

произвольной сигнатуры (см. Мальцев [6], Кон [5]). Очевидно, что при таком определении конгруэнция не зависит от основных отношений системы, поэтому фактор-системами являлись в точности только сильные гомоморфные образы, т.е. не было прямой связи между конгруэнциями и произвольными гомоморфизмами. Данное обстоятельство в значительной мере сдерживало применение идей и методов универсальной алгебры, отработаных на системах исключительно функциональной сигнатуры, в теории алгебраических систем, допускающих предикатные символы (Биркгоф [10]).

В 1980 г. Горбуновым и Тумановым [2, 3] было предложено новое определение конгруэнции на алгебраической системе, в котором были учтены и основные отношения.

Пусть Л — произвольная система некоторой сигнатуры ст. Совокупность отношений в = (0(~),в(р) : р предикатный символ из <т) называется конгруэнцией на А. если

б!'«) — отношение эквивалентности на А,

— сохраняет основные операции системы Л,

■— 9(р) замкнутое относительно отношение,

арность которого совпадает с арностью р £ а,

— в(р) содержит все р-ребра системы А.

Смысл данного определения состоит в следующем: первая компонента конгруэнции (отвечающая равенству) "склещзает"элементы системы, а оставшиеся определяют,, ребра в полученном фактор-множестве. Условия, записанные выше, гарантируют корректность этих действий.

Оказалось, что для такого определения конгруэнции выполнены классические алгебраические теоремы о го-

моморфизме и изоморфизме. И более того, алгебраические операции построения надпрямого предела и подпрямого произведения получили свое отражение в решеточных операциях решеток конгруэнций. Над-прямому пределу соотвсствует сумма соответствующих конгруэнций по направленному вверх множеству, а подпрямому произведению — пересечение конгруэнций.

Выявление этого соответствия позволило создать алгебраическую теорию квазимногообразий.

Применение этой теории дало возможность по-новому взглянуть на старые проблемы теории графов ¡11], в частности получить решение проблемы раскраски. Сведение квазимногообразий частичных алгебр к \/3-классам алгебраических систем [4, 9] также дало положительные результаты.

• Возникает гипотеза (Горбунов), что если в классе систем "хорошо"определены конгруэнции (либо он "хорошо"сводится к классу с таким свойством), то к нему в "достаточно полной мсре"примснимы результаты алгебраической теории классических квазимногообразий

Результаты диссертации являются следствием проверки данной гипотезы и усиливают ее прадоподобность.

2 Обзор диссертации

Диссертация состоит из введения и двух глав. В первой главе даются определения, необходимые для представления метрических алгебр, как алгебраических систем расширенной специальными предикатными символами сигнатуры, и вводится понятие непрерывного квазимногообразия метрических алгебр. Далее доказываются некоторые факты о данных классах.

Теорема 1.1 Класс К метрических алгебр является непрерывным квазимпогообразием тогда и только

тогда, когда он замкнут относительно операторов 1А Р и Э.

На самом деле верным оказывается и более сильное утверждение:

Теорема 1.2 Пусть А — класс систем, а котором выполняется некоторое непрерывное семейство ква-зитогясдеств, тогда СУ'(А) = Г^'ЗР(А).

Основным результатом диссертации, также приведенном в первой главе, является полная характеризация решеток вида Сопк-Д, где К — непрерывное квазимногообразие иЛбК. Которую дают

Теорема 1.3 Пусть К — непрерывное квазимио-гообразие, А 6 К. Тогда Сопк»4 — непрерывная по Скотту решетка. и

Теорема 1.4 Пусть Ь непрерывная по Скотту решетка. Тогда найдется непрерывное квазилтогооб-разие К такое, что Сопк-^Ы0) = Ь.

Для непрерывных квазимногообразий также доказывается аналог теоремы Биркгофа о подпрямом разложении

Теорема 1.5 Пусть К — непрерывное квазимногообразие. Тогда любая система из К представима в виде подпрямого произведения 'К-неразложимых.

Вторая глава посвящена рассмотрению классов многосортных алгебраических систем. В этой главе дается обобщение понятия конгруэнции на многосортные системы. Данное обобщение оказывается достаточно хорошим. Для него выполнены теорема о гомоморфизме и теоремы об изоморфизме.

Теорема 2.1 Пусть tp — {stp : s 6 S} —

гофмоморфизм из системы Л па систему В, в = кег <р и ф — канонический, гомоморфизм из Л на Л/в. Тогда семейство отобраэюений \ — {.?Х s £ S}, пререводящее ¡а/9 в s^(sa), является изоморфизмом между Л/в и В, кроме того, tp —

Теорема 2.2 Пусть вив1— конгруэнции на алгебраической системе Л такие, что в С в'. Тогда в/в' является конгруэнцией на Л/9, а семейство отображений tp = {sip s £ S}, определенных no правилу sip{{sa/9)/{9'/9)) — а/в', — изоморфизмом между {Л/9)/{9'/в) и Л/9. Более того, любая конгруэнция, на Л/в представима в виде в'/в для некоторой конгруэнции в' Э 9.

Теорема 2.3 Пусть 9 — конгруэнция на Л и В ^ Л тогда ограничение в на В, т.е. в П lg является конгруэцией на В, а семейство отображений <р = {s<р : s € S}, определенное по правилу 8<^(5Ь/(в П 1В)) = Ь/(9 П lfl/j) — изоморфизмом между В/{в П 1в) «65/(01-11«,).

Решетки конгруэнций также обладают хорошей структурой:

Теорема 2.4 Для всякого квазимногообразия К и системы Л £ К решетка относительных конгруэнций СопкЛ является алгебраической.

Очевидным образом верно также и обратное утверждение. В совокупости получаем полную харатеризацию таких решеток решеток.

Продолжая аналогии с классами односортных систем для классов многосортных систем верны формулы:

Q(A) = LsPsS(A)

V(A) = HPsS(A),

(теоремы 2.7 и 2.8), а для квазимногообразий и многообразий теорема Биркгофа о подпрямом разложении (теорема 2.6).

Список литературы

[1 ] Горбунов В. А., Алгебраическая теория квазимногообразий (Сибирская школа алгебры и логики), Новосибирск, Научная книга, ИДМИ, 1999.

[2 ] Горбунов В. А., Туманов В. И., О строении решеток квазимногообразий, Докл. Акад. паук СССР, 254, No. 2, 272-275, 1980.

[3 ] Горбунов В. А., Туманов В. И., Строение решеток квазимногообразий, Труды йнта матем. СО АН СССР, 2, 12-44, Новосибирск, Наука, 1982.

[4 ] Горбунов В. А., Шеремет М. С., Хорновы классы предикатных систем и многообразия частичных алгебр, Алгебра и логика, 39, No. 1, 23-36, 2000.

[5 ] Кон П. М., Универсальная алгебра, М., Мир, 1968.

[6 ] Мальцев А. И., Алгебраические системы, М., Наука, 1970.

[7 ] Мальцев А. И., Квазипримитивные классы абстрактных алгебр, Докл. Акад. наук СССР, 108, No. 2, 187-189, 1956.

[8 ] Мальцев А. И., Определяющие соотношения в категориях, Докл. Акад. наук СССР, 119, No. 6, 1095-1098, 1958.

[9 ] Шеремет М. С., Характеризация квазимногообразий частичных алгебр с помощью пределов и произведений, Сиб. Электр. Мат. Известия, 1, 35 37, 2004.

[10 ] Birkhoff G., Lattices and their applications, Lattice Theory and Its Applications (Darmstadt, 1991), 7-25, Res. Exp. Math., 23, Heldermann, Lemgo, 1995.

[11 ] Gorbunov V., Kravchenko A., Antivarieties and colour-families of graphs Algebra Universalis, 46, No. 1-2, 43-67, 2001.

[12 ] Kelly D., Comlete rules of inference for universal sentences, Studia Sci. Math. Hungar., 19, No. 2 4, 347361, 1984.

[13 [ Quackenbush R., Completes theorems for universal and implicational ogics of algebras via congruences, Proc. Am. Math. Soc., 103, No. 4, 1015 1021, 1988.

[14 ] Selman A., Completeness of calculi for axiomatical-ly defined classes of algebras, Algebra Universalis, 2, No. 1, 20-32, 1972.

Работы автора по теме диссертации

[15 ] Худяков В. А., О квазимногообразиях метрических алгебр, Алгебра и логика., 42, Ж 6, 747-762, (2003).

[10 ] Khudyakov V. A., About Quasivarieties of Metic Algebras, Algebra Logic. 42, №. 6, 419-427, (2003).

Худяков Владимир Александрович

О КВАЗИМНОГООБРАЗИЯХ МЕТРИЧЕСКИХ АЛГЕБР

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 25.01.2007. Формат 60x84 1/16. Печать — копп-приптер. Бумага офсетная. Физ.печ.д. 0,5. Усл.печ.л. 0,46. Уч.-изд.л. 0,4. Тираж 100 экз. Заказ №20.

Отпечатано в типографии Хакасского государственного университета им. Н. Ф. Катанова 655017, г. Абакан, пр. Ленина, 94