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

Математическая операция

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

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

$${\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xByPz{\text{ if and only if }}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:{\text{ there exists }}y\in Y{\text{ such that }}(x,y)\in R{\text{ and }}(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] Однако маленький кружок широко используется для обозначения композиции функций , которая меняет последовательность текста на последовательность операций. Маленький кружок использовался на вводных страницах книги «Графики и отношения» ^{[5] : 18} , пока от него не отказались в пользу сопоставления (без инфиксной записи). Сопоставление обычно используется в алгебре для обозначения умножения, поэтому оно также может означать относительное умножение. ${\displaystyle (R\circ S)}$ ${\displaystyle g(f(x))=(g\circ f)(x)}$ ${\displaystyle (RS)}$

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

Математические обобщения

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

Учитывая регулярную категорию , ее категория внутренних отношений имеет те же объекты, что и , но теперь морфизмы задаются подобъектами в . ^[14] Формально это совместные монические промежутки между и . Категории внутренних отношений являются аллегориями . В частности . Учитывая поле (или, в более общем смысле, область главных идеалов ), категория отношений, внутренних по отношению к матрицам над , имеет морфизмы, линейные подпространства . Категория линейных отношений над конечным полем изоморфна бесфазному кубиту ZX-исчисления по модулю скаляров. ${\displaystyle \mathbb {X} }$ ${\displaystyle {\mathsf {Rel}}(\mathbb {X} )}$ ${\displaystyle \mathbb {X} }$ ${\displaystyle X\to Y}$ ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle \mathbb {X} }$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\mathsf {Rel}}({\mathsf {Set}})\cong {\mathsf {Rel}}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k))}$ ${\displaystyle n\to m}$ ${\displaystyle R\subseteq k^{n}\oplus k^{m}}$ ${\displaystyle \mathbb {F} _{2}}$

Характеристики

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

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

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

Гетерогенные отношения

Рассмотрим гетерогенное отношение , где и — различные множества. Тогда, используя композицию отношения с его обратным, возникают однородные отношения (on ) и (on ). ${\displaystyle R\subseteq A\times B;}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R}$ ${\displaystyle R^{\textsf {T}},}$ ${\displaystyle RR^{\textsf {T}}}$ ${\displaystyle A}$ ${\displaystyle R^{\textsf {T}}R}$ ${\displaystyle B}$

Если для всех существует такое, что (то есть является (лево-)тотальным отношением ), то для всех так, что это рефлексивное отношение или где I — тождественное отношение . Аналогично, если — сюръективное отношение , то ${\displaystyle x\in A}$ ${\displaystyle y\in B,}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle x,xRR^{\textsf {T}}x}$ ${\displaystyle RR^{\textsf {T}}}$ ${\displaystyle I\subseteq RR^{\textsf {T}}}$ ${\displaystyle \{xIx:x\in A\}.}$ ${\displaystyle R}$

$${\displaystyle R^{\textsf {T}}R\supseteq I=\{xIx:x\in B\}.}$$

дифункционального ${\displaystyle R\subseteq RR^{\textsf {T}}R.}$

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

Пример

Пусть { Франция, Германия, Италия, Швейцария } и { французский, немецкий, итальянский } с отношением, заданным условием, когда является национальным языком Поскольку оба и конечны, могут быть представлены логической матрицей , предполагая строки (сверху вниз) и столбцы (слева направо) расположены в алфавитном порядке: ${\displaystyle A=}$ ${\displaystyle B=}$ ${\displaystyle R}$ ${\displaystyle aRb}$ ${\displaystyle b}$ ${\displaystyle a.}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R}$

$${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}$$

Обратное отношение соответствует транспонированной матрице , а композиция отношения соответствует произведению матрицы , когда суммирование осуществляется посредством логической дизъюнкции . Оказывается, матрица содержит 1 в каждой позиции, а произведение обратной матрицы вычисляется как: ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle R^{\textsf {T}};R}$ ${\displaystyle R^{\textsf {T}}R}$ ${\displaystyle 3\times 3}$ ${\displaystyle R^{\textsf {T}}R}$

$${\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}$$

${\displaystyle A.}$

Соответственно, это универсальное отношение, следовательно , любые два языка принадлежат одной нации, в которой на обоих говорят (фактически: Швейцарии). И наоборот, на вопрос, имеют ли две данные нации общий язык, можно ответить, используя ${\displaystyle R^{\textsf {T}}\,;R}$ ${\displaystyle B,}$ ${\displaystyle R\,;R^{\textsf {T}}.}$

Шредер рулит

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

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

$${\displaystyle QR\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}$$

^{[5] : 15–19}

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

$${\displaystyle LM\subseteq N{\text{ implies }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}$$

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

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

левым остатком от ${\displaystyle RX\subseteq S{\text{ implies }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}$ ${\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}$ ${\displaystyle S}$ ${\displaystyle R}$

Коэффициенты

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

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

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

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

Логику остатков можно практиковать с помощью судоку . ^{[ нужны дальнейшие объяснения ]}

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

Был введен оператор вилки для объединения двух отношений и в . Конструкция зависит от проекций и понимается как отношения, что означает, что существуют обратные отношения и Тогда ${\displaystyle (<)}$ ${\displaystyle c:H\to A}$ ${\displaystyle d:H\to B}$ ${\displaystyle c\,(<)\,d:H\to A\times B.}$ ${\displaystyle a:A\times B\to A}$ ${\displaystyle b:A\times B\to B,}$ ${\displaystyle a^{\textsf {T}}}$ ${\displaystyle b^{\textsf {T}}.}$развилка иопределяется выражением^[18] ${\displaystyle c}$ ${\displaystyle d}$

$${\displaystyle c\,(<)\,d~\mathrel {:=} ~c;a^{\textsf {T}}\cap \ d;b^{\textsf {T}}.}$$

Другой формой композиции отношений, которая применяется к отношениям общего места, является операция соединения реляционной алгебры . Обычную композицию двух бинарных отношений, определенную здесь, можно получить, взяв их соединение, ведущее к троичному отношению, за которым следует проекция, удаляющая средний компонент. Например, в языке запросов SQL есть операция Join (SQL) . ${\displaystyle n}$ ${\displaystyle n\geq 2,}$

Смотрите также

• Демоническая композиция
• Друг друга  - Человеческий контакт, возникающий благодаря общему другу.

Примечания

1. Бьярни Йонссен (1984) «Максимальные алгебры бинарных отношений», в «Вкладах в теорию групп» , редактор К.И. Аппеля ISBN Американского математического общества 978-0-8218-5035-0 
2. Гюнтер Шмидт (2011) Реляционная математика , Энциклопедия математики и ее приложений, том. 132, ISBN издательства Кембриджского университета 978-0-521-76268-7 
3. А. Де Морган (1860) «О силлогизме: IV и логике отношений»
4. Дэниел Д. Меррилл (1990) Огастес Де Морган и логика отношений , страница 121, Kluwer Academic ISBN 9789400920477 
5. Гюнтер Шмидт и Томас Стрёлейн (1993) Отношения и графики , книги Springer
6. Эрнст Шредер (1895) Алгебра и логика относительности
7. Пол Тейлор (1999). Практические основы математики. Издательство Кембриджского университета. п. 24. ISBN 978-0-521-63107-5.Бесплатная HTML-версия книги доступна по адресу http://www.cs.man.ac.uk/~pt/Practical_Foundations/.
8. Майкл Барр и Чарльз Уэллс (1998) Теория категорий для ученых-компьютерщиков. Архивировано 4 марта 2016 г. в Wayback Machine , стр. 6, из Университета Макгилла.
9. Рик Нувен и другие (2016) Динамическая семантика §2.2, из Стэнфордской энциклопедии философии
10. Джон М. Хоуи (1995) Основы теории полугрупп , страница 16, монография LMS № 12, Clarendon Press ISBN 0-19-851194-9 
11. Килп, Кнауэр и Михалев, с. 7
12. ISO/IEC 13568:2002(E), стр. 23
13. Символ Юникода: реляционная композиция Z Notation из FileFormat.info
14. «Внутренние отношения». нлаб . Проверено 26 сентября 2023 г.
15. Ирвинг Копиловиш (декабрь 1948 г.) «Матричное развитие исчисления отношений», Журнал символической логики 13 (4): 193–203 Ссылка на Jstor, цитата со страницы 203
16. Вон Пратт. Истоки исчисления отношений, из Стэнфордского университета.
17. Де Морган указал противоположное строчными буквами, преобразование как M ⁻¹ и включение с помощью )), поэтому его обозначения были ${\displaystyle nM^{-1}))\ l.}$
18. Гюнтер Шмидт и Майкл Винтер (2018): Реляционная топология , стр. 26, Конспекты лекций по математике, том. 2208, книги Springer , ISBN 978-3-319-74451-3 

Рекомендации

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