|
Чебышевский сборник, 2014, том 15, выпуск 1, страницы 55–64
(Mi cheb325)
|
|
|
|
О многообразии алгебр отношений с операцией двойной цилиндрофикации
Д. А. Бредихин Саратовский государственный технический университет им. Гагарина Ю. А.
Аннотация:
Множество бинарных отношений, замкнутое относительно некоторой совокупности операций над ними, образует алгебру, называемую алгеброй отношений.
Альфред Тарский был первым из математиков, кто начал рассматривать алгебры отношений с точки зрения теории универсальных алгебр. Одним из важных направлений в исследованиях алгебр отношений является изучение их свойств, выраженных в виде тождеств.
Это приводит к необходимости изучения многообразий, порожденных различными классами алгебр отношений.
Для заданного множества $\Omega$ операций над бинарными отношениями обозначим через $R\{\Omega\}$ класс алгебр, изоморфных алгебрам отношений с операциями из $\Omega$. Пусть $Var\{\Omega\}$ – многообразие, порожденное классом $R\{\Omega\}$.
Как правило, операции над отношениями задаются с помощь формул логики предикатов первого порядка. Такие операции называются логическими.
Важным классом логических операций является класс диофантовых операций. Операция называется диофантовой (в другой терминологии — примитивно-позитивной), если она может быть задана с помощью формулы, которая в своей предваренной нормальной форме содержит лишь операцию конъюнкции и кванторы существования.
Диофантову операцию назовем атомарной, если она может быть задана с помощью формулы, которая в своей предваренной нормальной форме содержит лишь кванторы существования. Ясно, что такие формулы могут содержать лишь одну атомарную подформулу, и, следовательно, всякая атомарная операция является унарной. Существует девять атомарных диофантовых операций (исключая тождественную).
Сосредоточим свое внимание на диофантовой операции умножения отношений $\circ$ и атомарной операции двойной цилиндрофикации, определяемых следующим образом. Для заданных отношений
$\rho$ и $\sigma$ на множестве $U$, положим
$$
\rho\circ\sigma=\{(u, v):\, (\exists w) (u, w)\in \rho (w, v)\in \sigma\},\quad \nabla(\rho)=\{(u,v):\,(\exists w,z) (w,z)\in \rho\}.
$$
В работе найден базис тождеств многообразия $Var\{\circ, \nabla \}$:
алгебра $(A, \cdot, {}^\ast)$ типа $(2,1)$ тогда и только тогда принадлежит многообразию
$Var\{\circ, \nabla \}$, когда она удовлетворяет тождествам:
$(xy)z=x(yz)$, $x^{\ast\ast}=x^\ast$, $(x^\ast)^2=x^\ast$, $x^\ast y^\ast=y^\ast x^\ast$, $x^\ast(xy)^\ast=(xy)^\ast y^\ast=(xy)^\ast$, $(xy^\ast z)^\ast=x^\ast y^\ast z^\ast=x^\ast yz$, $xyz^\ast=xyx^\ast z^\ast$, $x^\ast y z=x^\ast z^\ast yz$.
Ключевые слова:
алгебра отношений, многообразия, базисы тождеств, операции цилиндрофикации.
Поступила в редакцию: 07.02.2014
Образец цитирования:
Д. А. Бредихин, “О многообразии алгебр отношений с операцией двойной цилиндрофикации”, Чебышевский сб., 15:1 (2014), 55–64
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cheb325 https://www.mathnet.ru/rus/cheb/v15/i1/p55
|
|