Состав отношений

В математике из бинарных отношений , то состав отношений является формированием нового бинарного отношения R  ; S от двух заданных бинарных отношений R и S . В исчислении отношений , состав отношений, называется относительным умножением , ^[1] и его результат называется относительным продуктом . ^{[2] : 40} Композиция функций - это частный случай композиции отношений, когда все задействованные отношения являются функциями .

Слова дядя и тетя указывают на сложное отношение: чтобы человек был дядей, он должен быть братом родителя (или сестрой тети). В алгебраической логике говорится, что отношение дяди ( xUz ) является композицией отношений «является братом» ( xBy ) и «является родителем» ( yPz ).

${\displaystyle U=BP\quad \equiv \quad xByPz\iff xUz.}$

Начиная с Августа Де Моргана , ^[3] традиционная форма рассуждения по силлогизма была включена в категорию реляционных логических выражений и их состав. ^[4]

Определение [ править ]

Если и - два бинарных отношения, то их состав есть отношение${\displaystyle R\subseteq X\times Y}$${\displaystyle S\subseteq Y\times Z}$${\displaystyle R;S}$

${\displaystyle R;S=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R\land (y,z)\in S\}.}$

Другими словами, определяется правилом, которое говорит, если и только если существует такой элемент , что (т.е. и ). ^{[5] : 13}${\displaystyle R;S\subseteq X\times Z}$${\displaystyle (x,z)\in R;S}$${\displaystyle y\in Y}$${\displaystyle x\,R\,y\,S\,z}$${\displaystyle (x,y)\in R}$${\displaystyle (y,z)\in S}$

Варианты обозначений [ править ]

Точка с запятой как инфиксное обозначение композиции отношений восходит к учебнику Эрнста Шредера 1895 года. ^[6] Гюнтер Шмидт возобновил использование точки с запятой, особенно в реляционной математике (2011). ^{[2] : 40 [7]} Использование точки с запятой совпадает с обозначением функциональной композиции, используемым (в основном компьютерными учеными) в теории категорий , ^[8], а также с обозначением динамического соединения в лингвистической динамической семантике . ^[9]

Маленький кружок использовался для инфиксной записи композиции отношений Джоном М. Хоуи в его книгах, посвященных полугруппам отношений. ^[10] Однако маленький кружок широко используется для обозначения композиции функций, которая меняет последовательность текста на последовательность операций. Маленький кружок использовался на вводных страницах Graphs and Relations ^{[5] : 18,} пока он не был заменен на сопоставление (без инфиксной записи). Сопоставление обычно используется в алгебре для обозначения умножения, поэтому оно также может обозначать относительное умножение.${\displaystyle (R\circ S)}$ ${\displaystyle g(f(x))\ =\ (g\circ f)(x)}$ ${\displaystyle (RS)}$

Кроме того, при обозначении кружков можно использовать индексы. Некоторые авторы ^[11] предпочитают писать и явно, когда это необходимо, в зависимости от того, какое отношение применяется первым: левое или правое. Еще одна разновидность, встречающаяся в информатике, - это обозначение Z : используется для обозначения традиционной (правой) композиции, но ⨾ (жирная открытая точка с запятой с кодовой точкой Unicode U + 2A3E) обозначает левую композицию. ^{[12] [13]}${\displaystyle \circ _{l}}$${\displaystyle \circ _{r}}$${\displaystyle \circ }$

Бинарные отношения иногда рассматриваются как морфизмы в категории Rel, в которой множества являются объектами. В Rel композиция морфизмов - это в точности композиция отношений, как определено выше. Категория Набор множеств - это подкатегория Rel, в которой есть те же объекты, но меньше морфизмов.${\displaystyle R\subseteq X\times Y}$${\displaystyle R\colon X\to Y}$

Свойства [ править ]

• Состав отношений ассоциативен :${\displaystyle R;(S;T)\ =\ (R;S);T.}$
• Обратное соотношение из R  ; S представляет собой ( R  ; S ) ^T = S ^T  ; R ^T . Это свойство делает множество всех бинарных отношений на множестве полугруппой с инволюцией .
• Композиция (частичных) функций (то есть функциональных отношений) снова является (частичной) функцией.
• Если R и S являются инъективны , то R  ; S инъективна, который , наоборот , подразумевает только приемистости R .
• Если R и S являются сюръективны , то R  ; S сюръективна, который , наоборот , подразумевает только сюрьективность S .
• Множество бинарных отношений на множестве X (то есть отношений от X до X ) вместе с (левой или правой) композицией отношений образует моноид с нулем, где тождественное отображение на X является нейтральным элементом , а пустое множество - это ноль элемент .

Композиция в терминах матриц [ править ]

Конечные бинарные отношения представлены логическими матрицами . Элементы этих матриц равны нулю или единице, в зависимости от того, является ли представленное отношение ложным или истинным для строки и столбца, соответствующих сравниваемым объектам. Работа с такими матрицами включает в себя булеву арифметику с 1 + 1 = 1 и 1 × 1 = 1. Тогда запись в матричном произведении двух логических матриц будет равна 1, только если умноженная строка и столбец имеют соответствующую единицу. логическая матрица композиции отношений может быть найдена путем вычисления матричного произведения матриц, представляющих факторы композиции. «Матрицы представляют собой метод вычисления выводов, которые традиционно делаются с помощью гипотетических силлогизмов и соритов». ^[14]

Гетерогенные отношения [ править ]

Рассмотрим гетерогенную отношение R ⊆ × B . Тогда, используя композицию отношения R с обратным ему R ^T , получатся однородные отношения RR ^T (на A ) и R ^T R (на B ).

Если ∀ x ∈ A ∃ y ∈ B xRy ( R - полное отношение ), то ∀ x xRR ^T x, так что RR ^T - рефлексивное отношение, или I ⊆ RR ^T, где I - тождественное отношение { x I x  : x ∈ А }. Аналогично, если R - сюръективное отношение, то

R ^T R ⊇ I = { x I x  : x ∈ B }. В этом случае R ⊆ RR ^T R . Противоположное включение происходит для дифункционального отношения.

Композиция используется для выделения отношений типа Феррера, удовлетворяющих${\displaystyle {\bar {R}}^{T}R}$${\displaystyle R{\bar {R}}^{T}R=R.}$

Пример [ править ]

Пусть = {Франция, Германия, Италия, Швейцария} и B = {французский, немецкий, итальянский} с соотношением R задается АРБ , когда б является национальным языком в . Логическая матрица для R задается

${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}$Используя обратное соотношение R ^T , можно ответить на два вопроса: «Есть ли переводчик?» имеет ответ на универсальное отношение на B . Международный вопрос: «Говорит ли он на моем языке?» на него отвечает эта симметричная матрица, представляющая однородное отношение на A , связана со звездным графом S _3, дополненным циклом в каждом узле.${\displaystyle R^{T}R=B\times B,}$${\displaystyle RR^{T}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}$

Правила Шредера [ править ]

Для данного множества V набор всех бинарных отношений на V образует булеву решетку, упорядоченную по включению (⊆). Напомним, что дополнение меняет включение: в исчислении отношений ^[15] обычно дополнение набора изображается чертой сверху:${\displaystyle A\subset B\implies B^{\complement }\subseteq A^{\complement }.}$${\displaystyle {\bar {A}}=A^{\complement }.}$

Если S - бинарное отношение, позвольте представить обратное отношение , также называемое транспонированием . Тогда правила Шредера таковы:${\displaystyle S^{T}}$

${\displaystyle QR\subseteq S\quad \equiv \quad Q^{T}{\bar {S}}\subseteq {\bar {R}}\quad \equiv \quad {\bar {S}}R^{T}\subseteq {\bar {Q}}.}$

На словах одна эквивалентность может быть получена из другой: выберите первый или второй фактор и переставьте его; затем дополните два других отношения и переставьте их. ^{[5] : 15–19}

Хотя это преобразование включения композиции отношений было детализировано по Эрнсту Шрёдеру , на самом деле Огастес де Морган первым сформулировал преобразование как теорема K в 1860. ^[4] Он написал

${\displaystyle LM\subseteq N\implies {\bar {N}}M^{T}\subseteq {\bar {L}}.}$^[16]

С помощью правил Шредера и дополнения можно найти неизвестное отношение X во включениях отношений, таких как

${\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}$

Например, в соответствии с правилом Шредера и комплементарности дает , который называется левой невязка S на R .${\displaystyle RX\subseteq S\implies R^{T}{\bar {S}}\subseteq {\bar {X}},}$${\displaystyle X\subseteq {\overline {R^{T}{\bar {S}}}},}$

Коэффициенты [ править ]

Подобно тому, как композиция отношений представляет собой тип умножения, в результате которого получается продукт, некоторые композиции сравниваются с делением и производят частные. Здесь представлены три частных: левая невязка, правая невязка и симметричное частное. Левый остаток двух отношений определяется исходя из предположения, что они имеют один и тот же домен (источник), а правый остаток предполагает один и тот же кодомен (диапазон, цель). Симметричное частное предполагает, что два отношения разделяют домен и домен.

Определения:

• Левый остаток: ${\displaystyle A\backslash B\ =\ {\overline {A^{T}{\bar {B}}}}}$
• Правый остаток: ${\displaystyle D/C\ =\ {\overline {{\bar {D}}C^{T}}}}$
• Симметричное частное: ${\displaystyle \operatorname {syq} (E,F)={\overline {E^{T}{\bar {F}}}}\cap {\overline {{\bar {E}}^{T}F}}}$

Использование правил Шредера, AX ⊆ B эквивалентно X ⊆ A B . Таким образом, левые остаточное является наибольшим отношением , удовлетворяющее AX ⊆ B . Аналогичным образом , включение YC ⊆ D эквивалентно Y ⊆ D / C , а правая остаточный является самым большим отношением , удовлетворяющим YC ⊆ D . ^{[2] : 43–6}${\displaystyle \backslash }$

Присоединиться: другая форма композиции [ править ]

Оператор вилки (<) был введен , чтобы предохранитель два соотношения гр : H → A и D : H → B в C (<) d : H → × B . Конструкция зависит от проекций : × B → и б : × B → B , понимать , как отношения, а это означает , что есть обратные отношения ^Т и б ^Т . ТогдаВилка из C и D задается

${\displaystyle c(<)d\ :=\ c;a^{T}\cap \ d;b^{T}.}$^[17]

Другая форма композиции отношений, которая применяется к общим п -местных отношений для п ≥ 2, является присоединиться к операции реляционной алгебры . Обычная композиция двух бинарных отношений, как определено здесь, может быть получена путем их соединения, ведущего к тернарному отношению, за которым следует проекция, удаляющая средний компонент. Например, в языке запросов SQL есть операция Соединение (SQL) .

См. Также [ править ]

• Демоническая композиция
• Друг друга

Заметки [ править ]

Ссылки [ править ]

• М. Килп, У. Кнауэр, А.В. Михалев (2000) Моноиды, действия и категории с приложениями к сплетениям и графам , De Gruyter Expositions in Mathematics vol. 29, Вальтер де Грюйтер , ISBN 3-11-015248-7 .