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

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

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

Слово дядя указывает на составное отношение: чтобы человек был дядей, он должен быть братом родителя. В алгебраической логике говорится, что отношение дядя ( ) является композицией отношений «является братом» ( ) и «является родителем» ( ). ${\displaystyle xUz}$ ${\displaystyle xBy}$ ${\displaystyle yPz}$ $${\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xUz{\text{ if and only if }}\exists y\ xByPz.}$$

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

Определение

Если и — два бинарных отношения, то их композиция — это отношение ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle S\subseteq Y\times Z}$ ${\displaystyle R\mathbin {;} S}$ $${\displaystyle R\mathbin {;} 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\mathbin {;} S\subseteq X\times Z}$ ${\displaystyle (x,z)\in R\mathbin {;} 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 являются ⨾ и ⨟. ^{[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\mathbin {;} (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin {;} T.}$
• Обратное отношение — это Это свойство делает множество всех бинарных отношений на множестве полугруппой с инволюцией . ${\displaystyle R\mathbin {;} S}$ ${\displaystyle (R\mathbin {;} S)^{\textsf {T}}=S^{\textsf {T}}\mathbin {;} R^{\textsf {T}}.}$
• Композиция (частичных) функций (то есть функциональных отношений) снова является (частичной) функцией.
• Если и инъективны , то инъективен, что, наоборот , подразумевает только инъективность ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\mathbin {;} S}$ ${\displaystyle R.}$
• Если и сюръективны , то сюръективно, что , наоборот, подразумевает только сюръективность ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\mathbin {;} S}$ ${\displaystyle S.}$
• Множество бинарных отношений на множестве (то есть отношений от до ) вместе с (левой или правой) композицией отношений образует моноид с нулем, где тождественное отображение на является нейтральным элементом , а пустое множество является нулевым элементом . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

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

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

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

Рассмотрим неоднородное отношение , то есть, где и — различные множества. Тогда, используя композицию отношения с его обратным, получим однородные отношения (на ) и (на ). ${\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 \mathrm {I} \subseteq RR^{\textsf {T}}}$ ${\displaystyle \{(x,x):x\in A\}.}$ ${\displaystyle R}$ $${\displaystyle R^{\textsf {T}}R\supseteq \mathrm {I} =\{(x,x):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 }.}$

Если — бинарное отношение, то представим обратное отношение , также называемое транспонированием . Тогда правила Шредера таковы : Устно одно отношение может быть получено из другого: выберите первый или второй множитель и транспонируйте его; затем дополните два других отношения и переставьте их. ^{[5] : 15–19} ${\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}}.}$$

Хотя это преобразование включения композиции отношений было подробно описано Эрнстом Шредером , на самом деле Август де Морган впервые сформулировал преобразование в виде теоремы К в 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\mathbin {;} a^{\textsf {T}}\cap \ d\mathbin {;} b^{\textsf {T}}.}$$

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

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

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

Примечания

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

Ссылки

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