О многообразиях группоидов отношений с диофантовыми операциями

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

О МНОГООБРАЗИЯХ ГРУППОИДОВ ОТНОШЕНИЙ С ДИОФАНТОВЫМИ ОПЕРАЦИЯМИ
© Явкаев Д.Г.* *, Бредихин Д. А. *
Саратовский государственный технический университет им. Гагарина
Ю.А., г. Саратов
В работе находятся базисы тождеств многообразий, порожденных классами группоидов бинарных отношений c диофантовыми операциями.
Ключевые слова алгебры отношений, диофантовые операции, тождества, многообразия, группоиды.
Введение
Множество бинарных отношений Ф, замкнутое относительно некоторой совокупности Q операций над ними, образует алгебру (Ф, Q), называемую алгеброй отношений. Теория алгебр отношений является существенной составной частью современной общей алгебры и алгебраической логики. Основы абстрактно-алгебраического подхода к изучению алгебр отношений были заложены в работах А. Тарского (A. Tarski) [1, 2].
Как правило, операции над отношениями задаются с помощью формул логики предикатов первого порядка. Такие операции называются логическими. Логические операции могут быть классифицированы по виду задающих их формул. Операция называется диофантовой [3] (в другой терминологии примитивно-позитивной [4]), если она может быть задана с помощью формулы, которая в своей предваренной нормальной форме содержит лишь операции конъюнкции и кванторы существования.
Отношение теоретико-множественного включения с согласовано с диофантовыми операциями, поэтому всякую алгебру отношений с диофантовыми операциями можно рассматривать как упорядоченную (Ф, Q, с) отношением включения с. Диофантовы операции допускают описания с помощью графов [3−5]. Эквациональные и квазиэквациональные теории алгебр отношений с диофантовыми операциями описаны в работах [5−7].
Предметом нашего рассмотрения будут алгебры отношений с одной бинарной диофантовой операцией, то есть группоиды бинарных отношений. Классификацию бинарных диофантовых операций над отношениями можно найти в [8]. Рассмотрение бинарных операций над отношениями играет в алгебраической логике предикатов роль, аналогичную роли бинарных булевых функций в пропозициональной логике высказываний. Поэтому естественен интерес к алгебраическим свойствам указанных операций, в частно-
* Студент 4 курса Физико-технического факультета. Научный руководитель: Бредихин Д. А.
* Профессор кафедры Математики и моделирования, доктор физико-математических наук.
122 ПРИОРИТЕТНЫЕ НАУЧНЫЕ НАПРАВЛЕНИЯ: ОТ ТЕОРИИ К ПРАКТИКЕ
сти, к свойствам, выразимым тождествами. Это приводит к необходимости изучения многообразий, порожденных различными классами группоидов бинарных отношений. Некоторые результаты в этом направлении можно найти в работах [8−17].
1. Формулировка результатов
Группоидом называется универсальная алгебра (А, •) с одной бинарной операцией.
Упорядоченный группоид — это алгебраическая система (А, •, & lt-), где (А, •) — группоид, а & lt- - отношение порядка, согласованное с операцией группоида.
Сосредоточим свое внимание на следующих двух диофантовых операциях над бинарными отношениями, определяемых формулами
P*a={(x, y) е X х X: (3y, w) (x, z) ерл (z, w^ea}, p"a = {(x, у) e X х X: (3z, x) (x, z) ep^(w, y) ea},
где p и a- бинарные отношения, заданные на множестве X. Алгебры отношений вида (Ф, *), (Ф, •) являются группоидами бинарных отношений.
Для заданного множества Q операций над бинарными отношениями обозначим через R{Q} (R{Q}, с) класс алгебр (упорядоченных алгебр), изоморфных алгебрам (упорядоченным алгебрам) отношений с операциями из Q. Пусть Var{Q.} (Var{Q}, с) — многообразие, порожденное классом A{Q} (R{Q}, с).
В следующих теоремах находятся базисы тождеств многообразий, порожденных соответствующими классами группоидов бинарных отношений.
Теорема 1. Группоид (А, •) принадлежит многообразию Var{*} тогда и только тогда, когда он удовлетворяет тождествам:
(xy) у = xy, (1)
x (yx) = xy, (2)
(xy) z = x (zy), (3)
(xy)(uv) = (xv)(uy). (4)
Теорема 2. Упорядоченный группоид (А, •, & lt-) принадлежит многообразию Var{*, с} тогда и только тогда, когда он удовлетворяет тождествам (1)-(4) и тождеству
(xy)z & lt- xz. (5)
Теорема 3. Группоид (А, •) принадлежит многообразию Var{•} тогда и только тогда, когда он удовлетворяет тождествам:
Физико-математические науки
123
(ХУ) У = xy, x (xy) = xy, x (yz) = (xz) y, (xy)(uv) = (uy)(xv).
(6)
(7)
(8) (9)
Теорема 4. Упорядоченный группоид (А, •, & lt-) принадлежит многообразию Var{•, с} тогда и только тогда, когда он удовлетворяет тождествам (6)-(9) и тождеству
Список литературы:
1. Tarski A. On the calculus of relations // J. Symbolic Logic. — 1941. -Vol. 4. — P. 73−89.
2. Tarski A. Some methodological results concerning the calculus of relations // J. Symbolic Logic. — 1953. — Vol. 18. — P. 188−189.
3. Бредихин Д. А. Об алгебрах отношений с диофантовыми операциями // Докл. АН. — 1998. — Т 360. — С. 594−595.
4. Boner P., Poschel F. R. Clones of operations on binary relations // Contributions to general algebras. — 1991. — Vol. 7. — P. 50−70.
5. Бредихин Д. А. Эквациональная теория алгебр отношений с позитивными операциями // Изв. вузов. Математика. — 1993. — № 3. — С. 23−30.
6. Andreka H., Bredikhin D.A. The equational theory of union-free algebras of relations // Alg. Univers. — 1994. — Vol. 33. — P. 516−532.
7. Бредихин Д. А. О квазитождествах алгебр отношений с диофантовы-ми операциями // Сиб. мат. журн. — 1997. — T. 38. — С. 29−41.
8. Bredikhin D.A. On relation algebras with general superpositions // Colloq. Math. Soc. J. Bolyai. — 1994. — Vol. 54. — P. 11−124.
9. Bredikhin D.A. Varietes of groupoids associated with involuted restrictive bisemigroups of binary relations // Semigroup Forum. — 1992. — Vol. 44. — P. 87−192.
10. Бредихин Д. А. О многообразии группоидов бинарных отношений // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. -2013. — Т 13, вып. 1, ч. 1. — С. 93−98.
11. Henkin L., Monk J.D., Tarski A. Cylindric Algebras. — North-Holland, Amsterdam, 1971. — 311 p.
12. Бредихин Д. А. Об одном классе алгебр отношений с бинарной дио-фантовой операцией // Компьютерные науки и информационные технологии: материалы Междунар. науч. конф., г. Саратов, 1−4 июля 2012 г. / СГУ -Саратов, 2012. — С. 58−60. — Библиогр.: с. 59−60 (9 назв.).
13. Бредихин Д. А., Явкаев Д. Г. О группоидах бинарных отношений с диофантовыми операциями // Алгебра и теория чисел: современные проблемы и приложения: тез. докл. X междунар. конф., г. Волгоград, 10−16 сент. 2012 г. — Волгоград, 2012. — С. 8.
x (yz) & lt- xy.
(10)
124 ПРИОРИТЕТНЫЕ НАУЧНЫЕ НАПРАВЛЕНИЯ: ОТ ТЕОРИИ К ПРАКТИКЕ
14. Бредихин Д. А. О полурешеточно упорядоченных группоидах отношений // Алгебра и теория чисел: современные проблемы и приложения: тез. докл. XI междунар. конф., г. Саратов, 9−14 сент. 2013 г. — Саратов, 2013. -С. 10−11. — Библиогр.: с. 11 (3 назв.).
15. Бредихин Д. А. О группоидах бинарных отношений с диофантовыми операциями // Математика. Механика: сб. науч. тр. / СГУ — Саратов, 2012. -Вып. 14. — С. 7−9.
16. Бредихин Д. А. О многообразиях группоидов отношений с диофан-товыми операциями // Известия Саратовского университета. Новая серия. Сер.: Математика. Механика. Информатика. — 2013. — Т. 13, N 4−2. — С. 2834. — Библиогр.: с. 34 (10 назв.). — ISSN 1816−9791.
17. Бредихин Д. А. Об аксиоматике упорядоченных группоидов бинарных отношений // Компьютерные науки и информационные технологии: материалы междунар. науч. конф., г. Саратов, 30 июня — 3 июля 2014 г. / СГУ — Саратов, 2014. — С. 64−65.

ПоказатьСвернуть
Заполнить форму текущей работой