Бинарное отношение

Relationship between elements of two sets

В математике бинарное отношение связывает элементы одного набора, называемого доменом , с элементами другого набора, называемого кодоменом . ^[1] Точнее, бинарное отношение над множествами и представляет собой множество упорядоченных пар , состоящих из элементов из и из . ^[2] Он кодирует общую концепцию отношения: элемент связан с элементом тогда и только тогда, когда пара принадлежит множеству упорядоченных пар, которое определяет бинарное отношение . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle y}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)}$

Примером бинарного отношения является отношение « делит » над набором простых чисел и набором целых чисел , в котором каждое простое число связано с каждым целым числом , кратным , но не с целым числом, не кратным . . В этом отношении, например, простое число связано с такими числами, как , , , , но не с или , точно так же, как простое число связано с , , и , но не с или . ${\displaystyle \mathbb {P} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle p}$ ${\displaystyle z}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle 2}$ ${\displaystyle -4}$ ${\displaystyle 0}$ ${\displaystyle 6}$ ${\displaystyle 10}$ ${\displaystyle 1}$ ${\displaystyle 9}$ ${\displaystyle 3}$ ${\displaystyle 0}$ ${\displaystyle 6}$ ${\displaystyle 9}$ ${\displaystyle 4}$ ${\displaystyle 13}$

Бинарные отношения используются во многих разделах математики для моделирования самых разных концепций. К ним относятся, среди прочего:

• отношения « больше », « равно » и «делит» в арифметике ;
• отношение « соответствует » в геометрии ;
• отношение «примыкает к» в теории графов ;
• отношение « ортогонален » в линейной алгебре .

Функция может быть определена как бинарное отношение, удовлетворяющее дополнительным ограничениям . ^[3] Бинарные отношения также широко используются в информатике .

Бинарное отношение над множествами и является элементом степенного множества Поскольку последнее множество упорядочено включением ( ), каждое отношение имеет место в решетке подмножеств Бинарное отношение называется однородным отношением, когда . Бинарное отношение также называется гетерогенным отношением, если в этом нет необходимости . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\times Y.}$ ${\displaystyle \subseteq }$ ${\displaystyle X\times Y.}$ ${\displaystyle X=Y}$ ${\displaystyle X=Y}$

Поскольку отношения представляют собой множества, ими можно манипулировать с помощью операций над множествами, включая объединение , пересечение и дополнение , и удовлетворяющих законам алгебры множеств . Помимо этого, доступны такие операции, как обращение отношения и композиция отношений , удовлетворяющие законам исчисления отношений , для которых существуют учебники Эрнста Шредера , ^[4] Кларенса Льюиса , ^[5] и Гюнтера Шмидта . ^[6] Более глубокий анализ отношений предполагает их разложение на подмножества, называемые понятиями , и размещение их в полной решетке .

В некоторых системах аксиоматической теории множеств отношения распространяются на классы , которые являются обобщениями множеств. Это расширение необходимо, среди прочего, для моделирования понятий «является элементом» или «является подмножеством» в теории множеств, не сталкиваясь с логическими несоответствиями, такими как парадокс Рассела .

Бинарное отношение — это наиболее изученный частный случай -арного отношения над множествами , которое является подмножеством декартова произведения ^[2] ${\displaystyle n=2}$ ${\displaystyle n}$ ${\displaystyle X_{1},\dots ,X_{n}}$ ${\displaystyle X_{1}\times \cdots \times X_{n}.}$

Определение

Учитывая наборы и , декартово произведение определяется как , а его элементы называются упорядоченными парами . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\times Y}$ ${\displaystyle \{(x,y)\mid x\in X{\text{ and }}y\in Y\},}$

Бинарное отношение над множествами и является подмножеством ^{[2] [7]} Набор называется областью ^[2] или набором отправления , а набор - кодоманом или набором назначения . Чтобы указать выбор наборов и , некоторые авторы определяют бинарное отношение или соответствие как упорядоченную тройку , где - подмножество, называемое графиком бинарного отношения. Заявление читается как « относится к » и обозначается . ^{[4] [5] [6] [примечание 1]} Область определения или активная область ^[2] of — это набор всех таких, что хотя бы для одного . Кодомен определения , активный кодомен , ^[2] изображение или диапазон — это набор всех таких, что хотя бы для одного . Поле — это объединение его области определения и его кодомена определения . ^{[9] [10] [11]} ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\times Y.}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle (X,Y,G)}$ ${\displaystyle G}$ ${\displaystyle X\times Y}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle xRy}$ ${\displaystyle y}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle x}$ ${\displaystyle R}$

Когда бинарное отношение называется однородным отношением (или эндореляцией ). Чтобы подчеркнуть тот факт, что и могут быть разными, бинарное отношение также называют гетерогенным отношением . ^{[12] [13] [14]} Приставка гетеро происходит от греческого ἕτερος ( гетерос , «другой, другой, другой»). ${\displaystyle X=Y,}$ ${\displaystyle X}$ ${\displaystyle Y}$

Неоднородное отношение было названо прямоугольным отношением ^[14] , предполагая, что оно не обладает квадратной симметрией однородного отношения на множестве, где, комментируя развитие бинарных отношений за пределами однородных отношений, исследователи писали: «... развился вариант теории, который с самого начала рассматривает отношения как гетерогенные или прямоугольные , то есть как отношения, в которых в обычном случае они являются отношениями между различными множествами». ^[15] ${\displaystyle A=B.}$

Термины соответствие , ^[16] диадическое отношение и двухместное отношение являются синонимами бинарного отношения, хотя некоторые авторы используют термин «бинарное отношение» для любого подмножества декартова произведения без ссылки на и и оставляют термин «соответствие» для бинарное отношение со ссылкой на и . ^{[ нужна цитата ]} ${\displaystyle X\times Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

В бинарном отношении важен порядок элементов; if then может быть истинным или ложным независимо от . Например, делит , но не делит . ${\displaystyle x\neq y}$ ${\displaystyle yRx}$ ${\displaystyle xRy}$ ${\displaystyle 3}$ ${\displaystyle 9}$ ${\displaystyle 9}$ ${\displaystyle 3}$

Операции

Союз

Если и являются бинарными отношениями над множествами , а затем является отношением объединения и над и . ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R\cup S=\{(x,y)\mid xRy{\text{ or }}xSy\}}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

Элемент идентификации — это пустое отношение. Например, это объединение < и = и объединение > и =. ${\displaystyle \leq }$ ${\displaystyle \geq }$

Пересечение

Если и являются бинарными отношениями над множествами , а затем является отношением пересечения и над и . ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R\cap S=\{(x,y)\mid xRy{\text{ and }}xSy\}}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

Элементом идентичности является универсальное отношение. Например, отношение «делится на 6» является пересечением отношений «делится на 3» и «делится на 2».

Состав

If – бинарное отношение над множествами и , и – бинарное отношение над множествами , а затем (также обозначается ) – отношение композиции и над и . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle S\circ R=\{(x,z)\mid {\text{ there exists }}y\in Y{\text{ such that }}xRy{\text{ and }}ySz\}}$ ${\displaystyle R;S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Z}$

Элементом идентичности является отношение идентичности. Порядок и в используемых здесь обозначениях соответствует стандартному порядку обозначений композиции функций . Например, композиция (является родителем) (является матерью) дает (является бабушкой и дедушкой по материнской линии), а композиция (является матерью) (является родителем) дает (является бабушкой). В первом случае, если является родителем и матерью , то он является дедушкой и бабушкой по материнской линии . ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S\circ R,}$ ${\displaystyle \circ }$ ${\displaystyle \circ }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$

Конверсы

Если является бинарным отношением над множествами , а затем является обратным отношением ^[17] также называемым обратным отношением [ ¹⁸ ] над и . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R^{\textsf {T}}=\{(y,x)\mid xRy\}}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle X}$

Например, является обратным самому себе, как и и являются обратными друг другу, как и . Бинарное отношение равно обратному тогда и только тогда, когда оно симметрично . ${\displaystyle =}$ ${\displaystyle \neq }$ ${\displaystyle <}$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle \geq }$

Дополнение

If – бинарное отношение над множествами , а затем (также обозначается ) – дополнительное отношение над и . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\bar {R}}=\{(x,y)\mid \neg xRy\}}$ ${\displaystyle \neg R}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$

Например, и дополняют друг друга, как и и , и , и , а для полных порядков также и , и и . ${\displaystyle =}$ ${\displaystyle \neq }$ ${\displaystyle \subseteq }$ ${\displaystyle \not \subseteq }$ ${\displaystyle \supseteq }$ ${\displaystyle \not \supseteq }$ ${\displaystyle \in }$ ${\displaystyle \not \in }$ ${\displaystyle <}$ ${\displaystyle \geq }$ ${\displaystyle >}$ ${\displaystyle \leq }$

Дополнение обратного отношения является обратным дополнению: ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.}$

Если дополнение обладает следующими свойствами: ${\displaystyle X=Y,}$

• Если отношение симметрично, то и дополнение тоже.
• Дополнение рефлексивного отношения иррефлексивно — и наоборот.
• Дополнением строгого слабого порядка является полный предварительный порядок — и наоборот.

Ограничение

Если это бинарное однородное отношение над множеством и является его подмножеством, то ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S{\text{ and }}y\in S\}}$ограничение отношение кболее. ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$

Если — бинарное отношение над множествами , и если — подмножество, то — это ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S\}}$левое ограничение отношениякoverи.^{[ нужны разъяснения ]} ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

Если — бинарное отношение над множествами , и если — подмножество, то — это ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle Y}$ ${\displaystyle R^{\vert S}=\{(x,y)\mid xRy{\text{ and }}y\in S\}}$право-ограничение отношения кoverи. ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

Если отношение является рефлексивным , иррефлексивным, симметричным , антисимметричным , асимметричным , транзитивным , полным , трихотомическим , частичным порядком , полным порядком , строгим слабым порядком , полным предпорядком (слабый порядок) или отношением эквивалентности , то такими же являются и его ограничения.

Однако транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания, т. е. вообще говоря, не равно. Например, ограничение отношения « является родителем » женщинами дает отношение « является матерью женщины »; его транзитивное замыкание не связывает женщину с ее бабушкой по отцовской линии. С другой стороны, транзитивное замыкание «является родителем» есть «является предком»; его ограничение на женщин действительно связывает женщину с ее бабушкой по отцовской линии. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Кроме того, различные концепции полноты (не путать с «тотальностью») не переносятся на ограничения. Например, над действительными числами свойство отношения состоит в том, что каждое непустое подмножество с верхней границей имеет наименьшую верхнюю границу (также называемую супремумом) в. Однако для рациональных чисел эта верхняя граница не обязательно является рациональной, поэтому то же свойство не сохраняется и при ограничении отношения к рациональным числам. ${\displaystyle \leq }$ ${\displaystyle S\subseteq \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} .}$ ${\displaystyle \leq }$

Бинарное отношение над множествами называется ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$содержится в отношениинади, записанномifявляется подмножеством, то есть для всехиесли, то. Еслисодержится висодержится в, тоиназываютсяравныминаписанными. Еслисодержится в ,ноне содержится в, тоговорят, что ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle R\subseteq S,}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y,}$ ${\displaystyle xRy}$ ${\displaystyle xSy}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R=S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle R}$меньше , записаноНапример, длярациональных чиселотношениеменьше, и равно композиции. ${\displaystyle S}$ ${\displaystyle R\subsetneq S.}$ ${\displaystyle >}$ ${\displaystyle \geq }$ ${\displaystyle >\circ >}$

Матричное представление

Бинарные отношения над множествами могут быть алгебраически представлены логическими матрицами, индексированными и с элементами в булевом полукольце (сложение соответствует ИЛИ, а умножение — И), где сложение матриц соответствует объединению отношений, умножение матриц соответствует композиции отношений (из отношение над и и отношение над и ), ^[19] произведение Адамара соответствует пересечению отношений, нулевая матрица соответствует пустому отношению, а матрица единиц соответствует универсальному отношению. Однородные отношения (когда ) образуют матричное полукольцо (действительно, матричную полуалгебру над булевым полукольцом), где единичная матрица соответствует тождественному отношению. ^[20] ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle X=Y}$

Примеры

1. Следующий пример показывает, насколько важен выбор кодомена. Предположим, есть четыре объекта и четыре человека. Возможным отношением является отношение «принадлежит», заданное формулой То есть Джон владеет мячом, Мэри владеет куклой, а Венера владеет машиной. Чашка никому не принадлежит, и Йену ничего не принадлежит; см. 1-й пример. Как набор, он не включает в себя Ян, и поэтому его можно рассматривать как подмножество, т. е. отношения , см. второй пример. Но во втором примере не содержится никакой информации о собственности Яна. ${\displaystyle A=\{{\text{ball, car, doll, cup}}\}}$ ${\displaystyle B=\{{\text{John, Mary, Ian, Venus}}\}.}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R=\{({\text{ball, John}}),({\text{doll, Mary}}),({\text{car, Venus}})\}.}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle A\times \{{\text{John, Mary, Venus}}\},}$ ${\displaystyle A}$ ${\displaystyle \{{\text{John, Mary, Venus}}\};}$ ${\displaystyle R}$

   Хотя второй пример отношения является сюръективным (см. ниже), первый — нет.

   

   Океаны и континенты (острова опущены)

2. Пусть , океаны земного шара, и , континенты . Давайте представим, что океан граничит с континентом . Тогда логическая матрица для этого отношения: ${\displaystyle A=\{{\text{Indian}},{\text{Arctic}},{\text{Atlantic}},{\text{Pacific}}\}}$ ${\displaystyle B=\{{\text{NA}},{\text{SA}},{\text{AF}},{\text{EU}},{\text{AS}},{\text{AU}},{\text{AA}}\}}$ ${\displaystyle aRb}$ ${\displaystyle a}$ ${\displaystyle b}$

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

   Связность планеты Земля можно рассматривать через и , первое из которых представляет собой отношение на , которое является универсальным отношением ( или логической матрицей всех). Это универсальное соотношение отражает тот факт, что каждый океан отделен от других не более чем одним континентом. С другой стороны, это соотношение не может быть универсальным, поскольку для путешествия из Европы в Австралию необходимо пересечь как минимум два океана . ${\displaystyle RR^{\mathsf {T}}}$ ${\displaystyle R^{\mathsf {T}}R}$ ${\displaystyle 4\times 4}$ ${\displaystyle A}$ ${\displaystyle A\times A}$ ${\displaystyle R^{\mathsf {T}}R}$ ${\displaystyle B\times B}$
3. Визуализация отношений опирается на теорию графов : для отношений на множестве (однородных отношений) ориентированный граф иллюстрирует отношение, а граф — симметричное отношение . Для гетерогенных отношений гиперграф имеет ребра, возможно, с более чем двумя узлами, и его можно проиллюстрировать двудольным графом . Подобно тому, как клика является неотъемлемой частью отношений на множестве, биклики используются для описания гетерогенных отношений; на самом деле, это «концепции», которые создают решетку, связанную с отношением.

   

   Различные оси представляют время для движущихся наблюдателей, соответствующие оси — их линии одновременности. ${\displaystyle t}$ ${\displaystyle x}$

4. Гиперболическая ортогональность : время и пространство — это разные категории, а временные свойства отделены от пространственных свойств. Идея одновременных событий проста в абсолютном времени и пространстве, поскольку каждое время определяет одновременную гиперплоскость в этой космологии. Герман Минковский изменил это, когда сформулировал понятие относительной одновременности , которая существует, когда пространственные события «нормальны» ко времени, характеризуемому скоростью. Он использовал неопределенное внутреннее произведение и указал, что вектор времени нормален к вектору пространства, когда это произведение равно нулю. Неопределенный скалярный продукт в композиционной алгебре определяется выражением ${\displaystyle t}$

   ${\displaystyle \langle x,z\rangle =x{\bar {z}}+{\bar {x}}z\;}$где черта означает сопряжение.

   Как отношение между некоторыми временными событиями и некоторыми пространственными событиями, гиперболическая ортогональность (как обнаруживается в расщепленных комплексных числах ) является гетерогенным отношением. ^[21]
5. Геометрическую конфигурацию можно рассматривать как связь между ее точками и линиями. Отношение выражается как инцидентность . Включены конечные и бесконечные проективные и аффинные плоскости. Якоб Штайнер был пионером в каталогизации конфигураций с помощью систем Штайнера , которые имеют набор из n элементов и набор подмножеств из k-элементов, называемых блоками , так что подмножество с элементами лежит только в одном блоке. Эти структуры заболеваемости были обобщены с помощью блочных планов . Матрица инцидентности , используемая в этих геометрических контекстах, соответствует логической матрице, обычно используемой с бинарными отношениями. ${\displaystyle \operatorname {S} (t,k,n)}$ ${\displaystyle \operatorname {S} }$ ${\displaystyle t}$

   Структура инцидентности представляет собой тройку, где и — любые два непересекающихся множества, и представляет собой бинарное отношение между и , т. е. элементы будут называться точками , элементами блоков и элементами флагов . ^[22] ${\displaystyle \mathbf {D} =(V,\mathbf {B} ,I)}$ ${\displaystyle V}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle I}$ ${\displaystyle V}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle I\subseteq V\times \mathbf {B} .}$ ${\displaystyle V}$ ${\displaystyle \mathbf {B} }$ ${\displaystyle I}$

Типы бинарных отношений

Примеры четырех типов бинарных отношений над действительными числами : один-к-одному (зеленый), один-ко-многим (синий), многие-к-одному (красный), многие-ко-многим (черный). ).

Некоторые важные типы бинарных отношений над множествами перечислены ниже. ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$

Свойства уникальности:

• Инъективный ^[23] (также называемый уникальным слева ^[24] ): для всех и всех if и then . Другими словами, каждый элемент кодомена имеет не более одного элемента -прообраза . Для такого отношения называется первичным ключом . ^[2] Например, зеленое и синее бинарные отношения на диаграмме являются инъективными, а красное — нет (поскольку оно относится как к ) , так и черное (поскольку оно относится как к , так и к ). ${\displaystyle x,y\in X}$ ${\displaystyle z\in Y,}$ ${\displaystyle xRz}$ ${\displaystyle yRz}$ ${\displaystyle x=y}$ ${\displaystyle Y}$ ${\displaystyle R}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 0}$
• Функционал ^{[23] [25] [26]} (также называемый единственным справа ^[24] или однолистным ^[27] ): для всех и всех if и then . Другими словами, каждый элемент домена имеет не более одного элемента изображения . Такое бинарное отношение называется частичной функцией или частичным отображением . ^[28] Для такого отношения называется первичным ключом . ^[2] Например, красные и зеленые бинарные отношения на диаграмме являются функциональными, а синие — нет (поскольку они относятся к обоим и ), а также черные (поскольку они относятся к обоим и ). ${\displaystyle x\in X}$ ${\displaystyle y,z\in Y,}$ ${\displaystyle xRy}$ ${\displaystyle xRz}$ ${\displaystyle y=z}$ ${\displaystyle \{X\}}$ ${\displaystyle R}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle 0}$ ${\displaystyle -1}$ ${\displaystyle 1}$
• Один к одному : инъективный и функциональный. Например, зеленое бинарное отношение на диаграмме взаимно однозначное, а красное, синее и черное — нет.
• Один-ко-многим : инъективный и нефункциональный. Например, синее бинарное отношение на диаграмме является отношением «один ко многим», а красное, зеленое и черное — нет.
• Многие-к-одному : функционально, а не инъективно. Например, красное двоичное отношение на диаграмме является отношением многие-к-одному, а зеленое, синее и черное — нет.
• Многие-ко-многим : не инъективны и не функциональны. Например, черное бинарное отношение на диаграмме является отношением многие-ко-многим, а красное, зеленое и синее — нет.

Свойства совокупности (определяются только в том случае, если указаны домен и кодомен ): ${\displaystyle X}$ ${\displaystyle Y}$

• Тотал ^[23] (также называемый левым тоталом ^[24] ): для всех существует такое, что . Другими словами, каждый элемент домена имеет хотя бы один элемент изображения. Другими словами, область определения равна . Это свойство отличается от определения связного (также называемого некоторыми авторами общим ) ^{[ нужна ссылка ]} в разделе «Свойства» . Такое бинарное отношение называется многозначной функцией . Например, красные и зеленые бинарные отношения на диаграмме являются полными, а синие — нет (поскольку не относятся ни к какому действительному числу), ни черные (поскольку не относятся ни к какому действительному числу). Другой пример — общее отношение над целыми числами. Но это не тотальное отношение над целыми положительными числами, потому что среди положительных целых чисел нет таких, что . ^[29] Однако это полное отношение к положительным целым числам, рациональным числам и действительным числам. Каждое рефлексивное отношение тотально: для данного выберите . ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle -1}$ ${\displaystyle 2}$ ${\displaystyle >}$ ${\displaystyle y}$ ${\displaystyle 1>y}$ ${\displaystyle <}$ ${\displaystyle x}$ ${\displaystyle y=x}$
• Сюръективный ^[23] (также называемый правом тоталом ^[24] ): для всех существует такое, что . Другими словами, каждый элемент кодомена имеет хотя бы один элемент прообраза. Другими словами, область определения равна . Например, зеленое и синее бинарные отношения на диаграмме являются сюръективными, а красное — нет (поскольку оно не связывает ни одно действительное число с ), ни черное (поскольку оно не связывает ни одно действительное число с ). ${\displaystyle y\in Y}$ ${\displaystyle x\in X}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle -1}$ ${\displaystyle 2}$

Свойства уникальности и совокупности (определяются только в том случае, если указаны домен и кодомен ): ${\displaystyle X}$ ${\displaystyle Y}$

• Функция (также называемая отображением ^[24] ): бинарное отношение, которое является функциональным и тотальным . Другими словами, каждый элемент домена имеет ровно один элемент изображения. Например, красные и зеленые бинарные отношения на диаграмме являются функциями, а синие и черные — нет.
• Инъекция : функция, которая является инъективной . Например, зеленое бинарное отношение на диаграмме является инъекцией, а красное, синее и черное — нет.
• Сюръекция : функция, которая является сюръективной . Например, зеленое бинарное отношение на диаграмме является сюръекцией, а красное, синее и черное — нет.
• Биекция : функция, которая является инъективной и сюръективной . Другими словами, каждый элемент домена имеет ровно один элемент изображения, а каждый элемент кодомена имеет ровно один элемент прообраза. Например, зеленое бинарное отношение на диаграмме является биекцией, а красное, синее и черное — нет.

Если отношения над соответствующими классами разрешены:

• Набор-подобный (также называемый локальным ): для всех класс всех таких , что , т. е . является набором. Например, отношение является множественным, и каждое отношение на двух множествах является множественным. ^[30] Обычное упорядочение < по классу порядковых чисел является отношением, подобным множеству, а обратное ему > - нет. ^{[ нужна цитата ]} ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle yRx}$ ${\displaystyle \{y\in Y,yRx\}}$ ${\displaystyle \in }$

Наборы против классов

Определенные математические «отношения», такие как «равно», «подмножество» и «член», нельзя понимать как бинарные отношения, определенные выше, поскольку их области определения и кодомены не могут рассматриваться как множества в обычных системах. аксиоматической теории множеств . Например, чтобы смоделировать общую концепцию «равенства» как бинарного отношения , возьмем домен и кодомен как «класс всех множеств», который не является множеством в обычной теории множеств. ${\displaystyle =}$

В большинстве математических контекстов ссылки на отношения равенства, членства и подмножества безвредны, поскольку их можно неявно понимать как ограниченные некоторым множеством в контексте. Обычный способ решения этой проблемы — выбрать «достаточно большой» набор , содержащий все интересующие объекты, и работать с ограничением вместо . Аналогичным образом, отношение «подмножество» должно быть ограничено наличием домена и кодомена (степенного набора определенного набора ): результирующее отношение множества может быть обозначено как Кроме того, отношение «член» должно быть ограничено наличием домена и codomain для получения бинарного отношения, которое представляет собой множество. Бертран Рассел показал, что предположение о том , что оно определено для всех множеств, приводит к противоречию в наивной теории множеств , см. Парадокс Рассела . ${\displaystyle A}$ ${\displaystyle =_{A}}$ ${\displaystyle =}$ ${\displaystyle \subseteq }$ ${\displaystyle P(A)}$ ${\displaystyle A}$ ${\displaystyle \subseteq _{A}.}$ ${\displaystyle A}$ ${\displaystyle P(A)}$ ${\displaystyle \in _{A}}$ ${\displaystyle \in }$

Другое решение этой проблемы — использовать теорию множеств с соответствующими классами, такую ​​как NBG или теория множеств Морса-Келли , и позволить домену и кодомену (и, следовательно, графу) быть правильными классами : в такой теории равенство, членство , и subset — это бинарные отношения без специальных комментариев. (Необходимо внести небольшую модификацию в концепцию упорядоченной тройки , поскольку обычно правильный класс не может быть членом упорядоченного кортежа; или, конечно, в этом контексте можно идентифицировать бинарное отношение с его графиком.) ^[31] С помощью этого определения можно, например, определить бинарное отношение для каждого множества и его набора степеней. ${\displaystyle (X,Y,G)}$

Гомогенное отношение

Однородное отношение над множеством является бинарным отношением над самим собой, т.е. оно является подмножеством декартова произведения ^{[14] [32] [33]} Его также просто называют (бинарным) отношением над . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X\times X.}$ ${\displaystyle X}$

Однородное отношение над множеством можно отождествить с ориентированным простым графом, допускающим петли , где – множество вершин и – множество ребер (ребро из вершины в вершину существует тогда и только тогда, когда ). Множество всех однородных отношений над множеством — это степенное множество , которое представляет собой булеву алгебру, дополненную инволюцией отображения отношения в обратное ему отношение . Рассматривая композицию отношений как бинарную операцию над , она образует полугруппу с инволюцией . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle {\mathcal {B}}(X)}$ ${\displaystyle X}$ ${\displaystyle 2^{X\times X}}$ ${\displaystyle {\mathcal {B}}(X)}$

Некоторые важные свойства, которыми может обладать однородное отношение над множеством : ${\displaystyle R}$ ${\displaystyle X}$

• Рефлексивный : для всех. Например,является рефлексивным отношением, а > нет. ${\displaystyle x\in X,}$ ${\displaystyle xRx}$ ${\displaystyle \geq }$
• Иррефлексивно : для всехнет. Например,является иррефлексивным отношением, нотаковым не является. ${\displaystyle x\in X,}$ ${\displaystyle xRx}$ ${\displaystyle >}$ ${\displaystyle \geq }$
• Симметричный : для всех, если,то. Например, «кровный родственник» является симметричным отношением. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$
• Антисимметричное : для всехifиthenНапример,это антисимметричное отношение. ^[34] ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle x=y.}$ ${\displaystyle \geq }$
• Асимметричный : для всех, еслито нет. Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно. ^[35] Например, > является асимметричным отношением, ноэто не так. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle \geq }$
• Транзитив : для всехifиthen. Транзитивное отношение иррефлексивно тогда и только тогда, когда оно асимметрично. ^[36] Например, «является предком» является транзитивным отношением, а «является родителем» — нет. ${\displaystyle x,y,z\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRz}$ ${\displaystyle xRz}$
• Подключено : для всех, еслитогдаили. ${\displaystyle x,y\in X,}$ ${\displaystyle x\neq y}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$
• Сильно связаны : для всехили. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$
• Плотный : для всех, еслитогдасуществует такой, чтои. ${\displaystyle x,y\in X,}$ ${\displaystyle xRy,}$ ${\displaystyle z\in X}$ ${\displaystyle xRz}$ ${\displaystyle zRy}$

Частичный порядок — это отношение, которое является рефлексивным, антисимметричным и транзитивным. Строгий частичный порядок — это отношение, которое является иррефлексивным, асимметричным и транзитивным. Тотальный порядок — это отношение, которое является рефлексивным, антисимметричным, транзитивным и связным. ^[37] Строгий тотальный порядок — это отношение, которое является иррефлексивным, асимметричным, транзитивным и связным. Отношение эквивалентности — это отношение, которое является рефлексивным, симметричным и транзитивным. Например, « делит » — частичный, но не полный порядок натуральных чисел, « » — строгий полный порядок, а « параллельно » — отношение эквивалентности на множестве всех прямых на евклидовой плоскости . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \mathbb {N} ,}$ ${\displaystyle x<y}$ ${\displaystyle \mathbb {N} ,}$ ${\displaystyle x}$ ${\displaystyle y}$

Все операции, определенные в разделе § Операции, также применимы к однородным отношениям. Помимо этого, однородное отношение над множеством может подвергаться операциям замыкания, например: ${\displaystyle X}$

Рефлексивное закрытие

наименьшее рефлексивное отношение к содержанию , ${\displaystyle X}$ ${\displaystyle R}$

Транзитивное замыкание

наименьшее транзитивное отношение к содержащему , ${\displaystyle X}$ ${\displaystyle R}$

Замыкание эквивалентности

наименьшее отношение эквивалентности , содержащее . ${\displaystyle X}$ ${\displaystyle R}$

Исчисление отношений

Развитие алгебраической логики облегчило использование бинарных отношений. Исчисление отношений включает алгебру множеств , расширенную за счет композиции отношений и использования обратных отношений . Значение включения , которое подразумевает , устанавливает сцену в решетке отношений. Но так как символ включения лишний. Тем не менее, композиция отношений и манипулирование операторами в соответствии с правилами Шредера обеспечивают исчисление для работы в степенном наборе ${\displaystyle R\subseteq S,}$ ${\displaystyle aRb}$ ${\displaystyle aSb}$ ${\displaystyle P\subseteq Q\equiv (P\cap {\bar {Q}}=\varnothing )\equiv (P\cap Q=P),}$ ${\displaystyle A\times B.}$

В отличие от однородных отношений, операция композиции отношений представляет собой лишь частичную функцию . Необходимость сопоставления цели и источника составных отношений привела к предположению, что изучение гетерогенных отношений представляет собой главу теории категорий , как и категория множеств , за исключением того, что морфизмы этой категории являются отношениями. Объекты категории Rel являются множествами, а морфизмы отношений составляются по мере необходимости в категории . ^{[ нужна цитата ]}

Индуцированная решетка понятий

Бинарные отношения описывались через индуцированные ими решетки понятий : понятие удовлетворяет двум свойствам: ${\displaystyle C\subset R}$

• Логическая матрица является внешним произведением логических векторов логических векторов . ^{[ нужны разъяснения ]} ${\displaystyle C}$ ${\displaystyle C_{ij}=u_{i}v_{j},\quad u,v}$
• ${\displaystyle C}$является максимальным и не содержится ни в каком другом внешнем произведении. Таким образом, описывается как нерасширяемый прямоугольник . ${\displaystyle C}$

Для данного отношения набор понятий, расширенный за счет их соединений и встреч, образует «индуцированную решетку понятий», причем включение образует предварительный порядок . ${\displaystyle R\subseteq X\times Y,}$ ${\displaystyle \sqsubseteq }$

Теорема МакНила о пополнении (1937) (о том, что любой частичный порядок может быть вложен в полную решетку ) цитируется в обзорной статье 2013 года «Декомпозиция отношений на решетках понятий». ^[38] Разложение

${\displaystyle R=fEg^{\textsf {T}}}$, где и являются функциями , называемыми в этом контексте отображениями или левыми функциональными отношениями. «Индуцированная решетка понятий изоморфна разрезному пополнению частичного порядка, который принадлежит минимальному разложению отношения ». ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle E}$ ${\displaystyle (f,g,E)}$ ${\displaystyle R}$

Ниже рассматриваются частные случаи: полный порядок соответствует типу Феррера, а тождество соответствует дифункционалу — обобщению отношения эквивалентности на множестве. ${\displaystyle E}$ ${\displaystyle E}$

Отношения могут быть ранжированы по рангу Шейна , который подсчитывает количество понятий, необходимых для покрытия отношения. ^[39] Структурный анализ отношений с понятиями обеспечивает подход к интеллектуальному анализу данных . ^[40]

Особые отношения

• Предложение : если — серийное отношение и — его транспонирование, то где находится тождественное отношение. ${\displaystyle R}$ ${\displaystyle R^{\mathsf {T}}}$ ${\displaystyle I\subseteq R^{\textsf {T}}R}$ ${\displaystyle I}$ ${\displaystyle m\times m}$
• Предложение : Если – сюръективное отношение , то где – тождественное отношение. ${\displaystyle R}$ ${\displaystyle I\subseteq RR^{\textsf {T}}}$ ${\displaystyle I}$ ${\displaystyle n\times n}$

Дифункциональный

Идея дифункционального отношения заключается в разделении объектов путем различения атрибутов, что является обобщением концепции отношения эквивалентности . Один из способов сделать это – использовать промежуточный набор индикаторов . Отношение разделения — это композиция отношений с использованием функциональных отношений. Жак Риге назвал эти отношения дифункциональными, поскольку композиция включает в себя функциональные отношения, обычно называемые частичными функциями . ${\displaystyle Z=\{x,y,z,\ldots \}}$ ${\displaystyle R=FG^{\textsf {T}}}$ ${\displaystyle F\subseteq A\times Z{\text{ and }}G\subseteq B\times Z.}$ ${\displaystyle FG^{\mathsf {T}}}$

В 1950 г. Риге показал, что такие соотношения удовлетворяют включению: ^[41]

$${\displaystyle RR^{\textsf {T}}R\subseteq R}$$

В теории автоматов термин « прямоугольное отношение» также использовался для обозначения дифункционального отношения. Эта терминология напоминает тот факт, что при представлении в виде логической матрицы столбцы и строки дифункционального отношения могут быть организованы как блочная матрица с прямоугольными блоками единиц на (асимметричной) главной диагонали. ^[42] Более формально, отношение на является дифункциональным тогда и только тогда, когда оно может быть записано как объединение декартовых произведений , где являются разбиением подмножества и, аналогично, разбиением подмножества . ^[43] ${\displaystyle R}$ ${\displaystyle X\times Y}$ ${\displaystyle A_{i}\times B_{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle X}$ ${\displaystyle B_{i}}$ ${\displaystyle Y}$

Используя обозначения , дифункциональное отношение можно также охарактеризовать как такое отношение, что везде, где и имеют непустое пересечение, то эти два множества совпадают; формально подразумевает ^[44] ${\displaystyle \{y\mid xRy\}=xR}$ ${\displaystyle R}$ ${\displaystyle x_{1}R}$ ${\displaystyle x_{2}R}$ ${\displaystyle x_{1}\cap x_{2}\neq \varnothing }$ ${\displaystyle x_{1}R=x_{2}R.}$

В 1997 году исследователи обнаружили «полезность двоичной декомпозиции, основанной на дифункциональных зависимостях, при управлении базами данных ». ^[45] Кроме того, дифункциональные отношения имеют основополагающее значение в изучении бисимуляций . ^[46]

В контексте однородных отношений отношение частичной эквивалентности является дифункциональным.

Тип Феррера

Строгий порядок на множестве — однородное отношение, возникающее в теории порядка . В 1951 году Жак Риге принял упорядочение целочисленного разбиения , названное диаграммой Феррера , чтобы распространить упорядочение на бинарные отношения в целом. ^[47]

Соответствующая логическая матрица общего бинарного отношения имеет строки, заканчивающиеся последовательностью единиц. Таким образом, точки диаграммы Феррера заменяются единицами и выравниваются справа в матрице.

An algebraic statement required for a Ferrers type relation R is $${\displaystyle R{\bar {R}}^{\textsf {T}}R\subseteq R.}$$

If any one of the relations ${\displaystyle R,{\bar {R}},R^{\textsf {T}}}$ is of Ferrers type, then all of them are.^[48]

Contact

Suppose ${\displaystyle B}$ is the power set of ${\displaystyle A}$, the set of all subsets of ${\displaystyle A}$. Then a relation ${\displaystyle g}$ is a contact relation if it satisfies three properties:

1. ${\displaystyle {\text{for all }}x\in A,Y=\{x\}{\text{ implies }}xgY.}$
2. ${\displaystyle Y\subseteq Z{\text{ and }}xgY{\text{ implies }}xgZ.}$
3. ${\displaystyle {\text{for all }}y\in Y,ygZ{\text{ and }}xgY{\text{ implies }}xgZ.}$

The set membership relation, ${\displaystyle \epsilon =}$ "is an element of", satisfies these properties so ${\displaystyle \epsilon }$ is a contact relation. The notion of a general contact relation was introduced by Georg Aumann in 1970.^[49][50]

In terms of the calculus of relations, sufficient conditions for a contact relation include $${\displaystyle C^{\textsf {T}}{\bar {C}}\subseteq \ni {\bar {C}}\equiv C{\overline {\ni {\bar {C}}}}\subseteq C,}$$ where ${\displaystyle \ni }$ is the converse of set membership ( ${\displaystyle \in }$).^[51]: 280

Preorder R\R

Every relation ${\displaystyle R}$ generates a preorder ${\displaystyle R\backslash R}$ which is the left residual.^[52] In terms of converse and complements, ${\displaystyle R\backslash R\equiv {\overline {R^{\textsf {T}}{\bar {R}}}}.}$ Forming the diagonal of ${\displaystyle R^{\textsf {T}}{\bar {R}}}$, the corresponding row of ${\displaystyle R^{\textsf {T}}}$ and column of ${\displaystyle {\bar {R}}}$ will be of opposite logical values, so the diagonal is all zeros. Then

${\displaystyle R^{\textsf {T}}{\bar {R}}\subseteq {\bar {I}}\implies I\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}=R\backslash R}$, so that ${\displaystyle R\backslash R}$ is a reflexive relation.

To show transitivity, one requires that ${\displaystyle (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$ Recall that ${\displaystyle X=R\backslash R}$ is the largest relation such that ${\displaystyle RX\subseteq R.}$ Then

${\displaystyle R(R\backslash R)\subseteq R}$

${\displaystyle R(R\backslash R)(R\backslash R)\subseteq R}$ (repeat)

${\displaystyle \equiv R^{\textsf {T}}{\bar {R}}\subseteq {\overline {(R\backslash R)(R\backslash R)}}}$ (Schröder's rule)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}}$ (complementation)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$ (definition)

The inclusion relation Ω on the power set of ${\displaystyle U}$ can be obtained in this way from the membership relation ${\displaystyle \in }$ on subsets of ${\displaystyle U}$:

${\displaystyle \Omega ={\overline {\ni {\bar {\in }}}}=\in \backslash \in .}$^[51]: 283

Fringe of a relation

Given a relation ${\displaystyle R}$, its fringe is the sub-relation defined as $${\displaystyle \operatorname {fringe} (R)=R\cap {\overline {R{\bar {R}}^{\textsf {T}}R}}.}$$

When ${\displaystyle R}$ is a partial identity relation, difunctional, or a block diagonal relation, then ${\displaystyle \operatorname {fringe} (R)=R}$. Otherwise the ${\displaystyle \operatorname {fringe} }$ operator selects a boundary sub-relation described in terms of its logical matrix: ${\displaystyle \operatorname {fringe} (R)}$ is the side diagonal if ${\displaystyle R}$ is an upper right triangular linear order or strict order. ${\displaystyle \operatorname {fringe} (R)}$ is the block fringe if ${\displaystyle R}$ is irreflexive ( ${\displaystyle R\subseteq {\bar {I}}}$) or upper right block triangular. ${\displaystyle \operatorname {fringe} (R)}$ is a sequence of boundary rectangles when ${\displaystyle R}$ is of Ferrers type.

On the other hand, ${\displaystyle \operatorname {fringe} (R)=\emptyset }$ when ${\displaystyle R}$ is a dense, linear, strict order.^[51]

Mathematical heaps

Given two sets ${\displaystyle A}$ and ${\displaystyle B}$, the set of binary relations between them ${\displaystyle {\mathcal {B}}(A,B)}$ can be equipped with a ternary operation ${\displaystyle [a,b,c]=ab^{\textsf {T}}c}$ where ${\displaystyle b^{\mathsf {T}}}$ denotes the converse relation of ${\displaystyle b}$. In 1953 Viktor Wagner used properties of this ternary operation to define semiheaps, heaps, and generalized heaps.^[53][54] The contrast of heterogeneous and homogeneous relations is highlighted by these definitions:

There is a pleasant symmetry in Wagner's work between heaps, semiheaps, and generalised heaps on the one hand, and groups, semigroups, and generalised groups on the other. Essentially, the various types of semiheaps appear whenever we consider binary relations (and partial one-one mappings) between different sets ${\displaystyle A}$ and ${\displaystyle B}$, while the various types of semigroups appear in the case where ${\displaystyle A=B}$.

— Christopher Hollings, "Mathematics across the Iron Curtain: a history of the algebraic theory of semigroups"^[55]

See also

• Abstract rewriting system
• Additive relation, a many-valued homomorphism between modules
• Allegory (category theory)
• Category of relations, a category having sets as objects and binary relations as morphisms
• Confluence (term rewriting), discusses several unusual but fundamental properties of binary relations
• Correspondence (algebraic geometry), a binary relation defined by algebraic equations
• Hasse diagram, a graphic means to display an order relation
• Incidence structure, a heterogeneous relation between set of points and lines
• Logic of relatives, a theory of relations by Charles Sanders Peirce
• Order theory, investigates properties of order relations

Notes

1. Authors who deal with binary relations only as a special case of ${\displaystyle n}$-ary relations for arbitrary ${\displaystyle n}$ usually write ${\displaystyle Rxy}$ as a special case of ${\displaystyle Rx_{1}\dots x_{n}}$ (prefix notation).^[8]

References

1. Meyer, Albert (17 November 2021). "MIT 6.042J Math for Computer Science, Lecture 3T, Slide 2" (PDF). Archived (PDF) from the original on 2021-11-17.
2. Codd, Edgar Frank (June 1970). "A Relational Model of Data for Large Shared Data Banks" (PDF). Communications of the ACM. 13 (6): 377–387. doi:10.1145/362384.362685. S2CID 207549016. Archived (PDF) from the original on 2004-09-08. Retrieved 2020-04-29.
3. "Relation definition – Math Insight". mathinsight.org. Retrieved 2019-12-11.
4. Ernst Schröder (1895) Algebra und Logic der Relative, via Internet Archive
5. C. I. Lewis (1918) A Survey of Symbolic Logic, pages 269–279, via internet Archive
6. Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7, Chapt. 5
7. Enderton 1977, Ch 3. pg. 40
8. Hans Hermes (1973). Introduction to Mathematical Logic. Hochschultext (Springer-Verlag). London: Springer. ISBN 3540058192. ISSN 1431-4657. Sect.II.§1.1.4
9. Suppes, Patrick (1972) [originally published by D. van Nostrand Company in 1960]. Axiomatic Set Theory. Dover. ISBN 0-486-61630-4.
10. Smullyan, Raymond M.; Fitting, Melvin (2010) [revised and corrected republication of the work originally published in 1996 by Oxford University Press, New York]. Set Theory and the Continuum Problem. Dover. ISBN 978-0-486-47484-7.
11. Levy, Azriel (2002) [republication of the work published by Springer-Verlag, Berlin, Heidelberg and New York in 1979]. Basic Set Theory. Dover. ISBN 0-486-42079-5.
12. Schmidt, Gunther; Ströhlein, Thomas (2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. Definition 4.1.1. ISBN 978-3-642-77968-8.
13. Christodoulos A. Floudas; Panos M. Pardalos (2008). Encyclopedia of Optimization (2nd ed.). Springer Science & Business Media. pp. 299–300. ISBN 978-0-387-74758-3.
14. Michael Winter (2007). Goguen Categories: A Categorical Approach to L-fuzzy Relations. Springer. pp. x–xi. ISBN 978-1-4020-6164-6.
15. G. Schmidt, Claudia Haltensperger, and Michael Winter (1997) "Heterogeneous relation algebra", chapter 3 (pages 37 to 53) in Relational Methods in Computer Science, Advances in Computer Science, Springer books ISBN 3-211-82971-7
16. Jacobson, Nathan (2009), Basic Algebra II (2nd ed.) § 2.1.
17. Garrett Birkhoff & Thomas Bartee (1970) Modern Applied Algebra, page 35, McGraw-Hill
18. Mary P. Dolciani (1962) Modern Algebra: Structure and Method, Book 2, page 339, Houghton Mifflin
19. John C. Baez (6 Nov 2001). "quantum mechanics over a commutative rig". Newsgroup: sci.physics.research. Usenet: [email protected]. Retrieved November 25, 2018.
20. Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. Handbook of Weighted Automata, 3–28. doi:10.1007/978-3-642-01492-5_1, pp. 7-10
21. Relative simultaneity at Wikibooks
22. Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986). Design Theory. Cambridge University Press. p. 15.. 2nd ed. (1999) ISBN 978-0-521-44432-3
23. Van Gasteren 1990, p. 45.
24. Kilp, Knauer, Mikhalev 2000, p. 3.
25. "Functional relation - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2024-06-13.
26. "functional relation in nLab". ncatlab.org. Retrieved 2024-06-13.
27. Schmidt 2010, p. 49.
28. Kilp, Knauer, Mikhalev 2000, p. 4.
29. Yao, Y.Y.; Wong, S.K.M. (1995). "Generalization of rough sets using relationships between attribute values" (PDF). Proceedings of the 2nd Annual Joint Conference on Information Sciences: 30–33..
30. Kunen, Kenneth (1980). Set theory: an introduction to independence proofs. North-Holland. p. 102. ISBN 0-444-85401-0. Zbl 0443.03021.
31. Tarski, Alfred; Givant, Steven (1987). A formalization of set theory without variables. American Mathematical Society. p. 3. ISBN 0-8218-1041-3.
32. M. E. Müller (2012). Relational Knowledge Discovery. Cambridge University Press. p. 22. ISBN 978-0-521-19021-3.
33. Peter J. Pahl; Rudolf Damrath (2001). Mathematical Foundations of Computational Engineering: A Handbook. Springer Science & Business Media. p. 496. ISBN 978-3-540-67995-0.
34. Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), A Transition to Advanced Mathematics (6th ed.), Brooks/Cole, p. 160, ISBN 0-534-39900-2
35. Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, p. 158.
36. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF). Prague: School of Mathematics – Physics Charles University. p. 1. Archived from the original (PDF) on 2013-11-02. Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".
37. Joseph G. Rosenstein, Linear orderings, Academic Press, 1982, ISBN 0-12-597680-1, p. 4
38. R. Berghammer & M. Winter (2013) "Decomposition of relations on concept lattices", Fundamenta Informaticae 126(1): 37–82 doi:10.3233/FI-2013-871
39. Ki-Hang Kim (1982) Boolean Matrix Theory and Applications, page 37, Marcel Dekker ISBN 0-8247-1788-0
40. Ali Jaoua, Rehab Duwairi, Samir Elloumi, and Sadok Ben Yahia (2009) "Data mining, reasoning and incremental information retrieval through non enlargeable rectangular relation coverage", pages 199 to 210 in Relations and Kleene algebras in computer science, Lecture Notes in Computer Science 5827, Springer MR2781235
41. Riguet, Jacques (January 1950). "Quelques proprietes des relations difonctionelles". Comptes rendus (in French). 230: 1999–2000.
42. Julius Richard Büchi (1989). Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions. Springer Science & Business Media. pp. 35–37. ISBN 978-1-4613-8853-1.
43. East, James; Vernitski, Alexei (February 2018). "Ranks of ideals in inverse semigroups of difunctional binary relations". Semigroup Forum. 96 (1): 21–30. arXiv:1612.04935. doi:10.1007/s00233-017-9846-9. S2CID 54527913.
44. Chris Brink; Wolfram Kahl; Gunther Schmidt (1997). Relational Methods in Computer Science. Springer Science & Business Media. p. 200. ISBN 978-3-211-82971-4.
45. Ali Jaoua, Nadin Belkhiter, Habib Ounalli, and Theodore Moukam (1997) "Databases", pages 197–210 in Relational Methods in Computer Science, edited by Chris Brink, Wolfram Kahl, and Gunther Schmidt, Springer Science & Business Media ISBN 978-3-211-82971-4
46. Gumm, H. P.; Zarrad, M. (2014). "Coalgebraic Simulations and Congruences". Coalgebraic Methods in Computer Science. Lecture Notes in Computer Science. Vol. 8446. p. 118. doi:10.1007/978-3-662-44124-4_7. ISBN 978-3-662-44123-7.
47. J. Riguet (1951) "Les relations de Ferrers", Comptes Rendus 232: 1729,30
48. Schmidt, Gunther; Ströhlein, Thomas (2012). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. p. 77. ISBN 978-3-642-77968-8.
49. Georg Aumann (1971). "Kontakt-Relationen". Sitzungsberichte der mathematisch-physikalischen Klasse der Bayerischen Akademie der Wissenschaften München. 1970 (II): 67–77.
50. Anne K. Steiner (1970) Review:Kontakt-Relationen from Mathematical Reviews
51. Gunther Schmidt (2011) Relational Mathematics, pages 211−15, Cambridge University Press ISBN 978-0-521-76268-7
52. In this context, the symbol ${\displaystyle \backslash }$ does not mean "set difference".
53. Viktor Wagner (1953) "The theory of generalised heaps and generalised groups", Matematicheskii Sbornik 32(74): 545 to 632 MR0059267
54. C.D. Hollings & M.V. Lawson (2017) Wagner's Theory of Generalised Heaps, Springer books ISBN 978-3-319-63620-7 MR3729305
55. Christopher Hollings (2014) Mathematics across the Iron Curtain: a history of the algebraic theory of semigroups, page 265, History of Mathematics 41, American Mathematical Society ISBN 978-1-4704-1493-1

Bibliography

• Schmidt, Gunther (2010). Relational Mathematics. Berlin: Cambridge University Press. ISBN 9780511778810.
• Schmidt, Gunther; Ströhlein, Thomas (2012). "Chapter 3: Heterogeneous relations". Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Science & Business Media. ISBN 978-3-642-77968-8.
• Ernst Schröder (1895) Algebra der Logik, Band III, via Internet Archive
• Codd, Edgar Frank (1990). The Relational Model for Database Management: Version 2 (PDF). Boston: Addison-Wesley. ISBN 978-0201141924. Archived (PDF) from the original on 2022-10-09.
• Enderton, Herbert (1977). Elements of Set Theory. Boston: Academic Press. ISBN 978-0-12-238440-0.
• Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander (2000). Monoids, Acts and Categories: with Applications to Wreath Products and Graphs. Berlin: De Gruyter. ISBN 978-3-11-015248-7.
• Van Gasteren, Antonetta (1990). On the Shape of Mathematical Arguments. Berlin: Springer. ISBN 9783540528494.
• Peirce, Charles Sanders (1873). "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic". Memoirs of the American Academy of Arts and Sciences. 9 (2): 317–178. Bibcode:1873MAAAS...9..317P. doi:10.2307/25058006. hdl:2027/hvd.32044019561034. JSTOR 25058006. Retrieved 2020-05-05.
• Schmidt, Gunther (2010). Relational Mathematics. Cambridge: Cambridge University Press. ISBN 978-0-521-76268-7.

External links

• Media related to Binary relations at Wikimedia Commons
• "Binary relation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]