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

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

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

$$U=BP\quad {\text{ is equivalent to: }}\quad xByPz{\text{ if and only if }}xUz.$$

Начиная с Огастеса Де Моргана , традиционная форма рассуждения с помощью силлогизма была подчинена реляционным логическим выражениям и их композиции.

Определение

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

$$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\}.$$

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

Варианты обозначений

Точка с запятой как инфиксное обозначение состава отношений восходит к учебнику Эрнста Шредера 1895 года. Гюнтер Шмидт возобновил использование точки с запятой, особенно в «Реляционной математике» (2011). Использование точки с запятой совпадает с обозначением композиции функций, используемым (в основном учеными-компьютерщиками) в теории категорий . а также обозначение динамического союза в лингвистической динамической семантике .

Маленький круг $(R\circ S)$ использовался для инфиксной записи композиции отношений Джоном М. Хоуи в его книгах, посвященных полугруппам отношений. Однако маленький круг широко используется для обозначения композиции функций. $g(f(x))=(g\circ f)(x)$ который меняет текстовую последовательность на противоположную последовательность операций. Маленький кружок использовался на вводных страницах книги « Графики и отношения». пока от него не отказались в пользу сопоставления (без инфиксной записи). Сопоставление $(RS)$ обычно используется в алгебре для обозначения умножения, а также может означать относительное умножение.

Кроме того, при обозначении круга можно использовать индексы. Некоторые авторы предпочитаю писать $\circ _{l}$ и $\circ _{r}$ явно, когда это необходимо, в зависимости от того, какое отношение применяется первым: левое или правое. Еще одним вариантом, встречающимся в информатике, является обозначение Z : $\circ$ используется для обозначения традиционной (правой) композиции, а левая композиция обозначается жирной точкой с запятой. Символы Юникода: ⨾ и ⨟.

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

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

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

Свойства

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

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

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

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

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

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

$$R^{\textsf {T}}R\supseteq I=\{(x,x):x\in B\}.$$

В этом случае $R\subseteq RR^{\textsf {T}}R.$ Противоположное включение происходит для дифункционального отношения.

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

Пример

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

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

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

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

Эта матрица симметрична и представляет собой однородное отношение на $A.$

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

Шредер

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

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

$$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}}.$$

Устно одну эквивалентность можно получить из другой: выберите первый или второй фактор и транспонируйте его; затем дополните два других отношения и переставьте их местами.

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

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

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

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

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

Частные

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

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

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

Используя правила Шредера, $AX\subseteq B$ эквивалентно $X\subseteq A\backslash B.$ Таким образом, левый остаток — это наибольшее отношение, удовлетворяющее $AX\subseteq B.$ Аналогично, включение $YC\subseteq D$ эквивалентно $Y\subseteq D/C,$ а правый остаток — это наибольшее отношение, удовлетворяющее $YC\subseteq D.$

Логику остатков можно практиковать с помощью судоку .

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

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

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

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

См. также

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

Ссылки

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