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

Связь между элементами двух множеств

В математике бинарное отношение связывает элементы одного множества , называемого доменом , с элементами другого множества, называемого кодоменом . ^[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] из — это множество всех таких, что по крайней мере для одного . Область определения , активная область определения , ^[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]} Префикс гетеро происходит от греческого ἕτερος ( heteros , «другой, другой, отличный»). ${\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}$

В бинарном отношении важен порядок элементов; если то может быть истинным или ложным независимо от . Например, делит , но не делит . ${\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».

Состав

Если — бинарное отношение над множествами и , а — бинарное отношение над множествами и , то (также обозначается как ) — отношение композиции множеств и над множествами и . ${\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] , также называемое обратным отношением [ ^18] для множеств и . ${\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 }$

Дополнение

Если — бинарное отношение над множествами , а тогда (также обозначается как ) — дополнительное отношение над и . ${\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\}}$отношение левого ограничения кболееи.^[необходимо ^{разъяснение ]} ${\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}$содержится в отношениинади, записанномеслиявляется подмножеством, то есть для всехиесли, то. Еслисодержится висодержится в, тоиназываютсяравнымизаписанными. Еслисодержится в ,ноне содержится в, тоговорят, что ${\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-й пример. Как набор, не включает Яна, и поэтому может рассматриваться как подмножество , то есть отношение по и см. 2-й пример. Но во втором примере не содержит информации о владении Яном. ${\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-го примера является сюръективным (см. ниже), отношение 1-го примера таковым не является.

   

   Океаны и континенты (острова не включены)

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] ): для всех и всех, если и тогда . Другими словами, каждый элемент кодомена имеет не более одного элемента -прообраза . Для такого отношения называется первичным ключом . ^[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] ): для всехи всех,еслиитогда. Другими словами, каждый элемент домена имеет не более одного элемента изображения . Такое бинарное отношение называется частичной функцией или частичным отображением . ^[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}$

• Total ^[23] (также называемый left-total ^[24] ): для всехсуществует такое, что. Другими словами, каждый элемент домена имеет по крайней мере один элемент изображения. Другими словами, область определенияравна. Это свойство отличается от определения связанного (также называемого total некоторыми авторами) ^{[ требуется ссылка ]} в Свойствах . Такое бинарное отношение называется многозначной функцией . Например, красные и зеленые бинарные отношения на диаграмме являются total, но синее не является (так как оно не относитсяни к какому действительному числу), как и черное (так как оно не относитсяни к какому действительному числу). В качестве другого примера,является total отношением над целыми числами . Но это не total отношение над положительными целыми числами, потому что нетсреди положительных целых чисел такого, что. ^[29] Однакоявляется total отношением над положительными целыми числами, рациональными числами и действительными числами. Каждое рефлексивное отношение является total: для данноговыберите. ${\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 =}$

В большинстве математических контекстов ссылки на отношения равенства, принадлежности и подмножества безвредны, поскольку их можно неявно понимать как ограниченные некоторым набором в контексте. Обычный обходной путь для этой проблемы — выбрать «достаточно большой» набор , содержащий все интересующие объекты, и работать с ограничением вместо . Аналогично, отношение «подмножество» должно быть ограничено, чтобы иметь домен и кодомен (множество мощности определенного набора ): результирующее отношение набора может быть обозначено как Кроме того, отношение «член» должно быть ограничено, чтобы иметь домен и кодомен, чтобы получить бинарное отношение , которое является набором. Бертран Рассел показал, что предположение о том, что оно определено по всем наборам, приводит к противоречию в наивной теории множеств , см. парадокс Рассела . ${\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 или теорию множеств Морса–Келли , и разрешить домену и кодомузелю (и, следовательно, графу) быть надлежащими классами : в такой теории равенство, членство и подмножество являются бинарными отношениями без особых комментариев. (Необходимо внести небольшое изменение в концепцию упорядоченной тройки , поскольку обычно надлежащий класс не может быть членом упорядоченного кортежа; или, конечно, можно отождествить бинарное отношение с его графом в этом контексте.) ^[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}$
• Антисимметрично : для всех,еслиитогдаНапример,является антисимметричным отношением. ^[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 }$
• Транзитивный : для всехеслиито. Транзитивное отношение является иррефлексивным тогда и только тогда, когда оно асимметрично. ^[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]

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

Алгебраическое утверждение, необходимое для отношения типа Феррерса R, имеет вид $${\displaystyle R{\bar {R}}^{\textsf {T}}R\subseteq R.}$$

Если хотя бы одно из отношений относится к типу Феррерса, то все они таковы. ^[48] ${\displaystyle R,{\bar {R}},R^{\textsf {T}}}$

Контакт

Предположим, что есть множество мощности , множество всех подмножеств . Тогда отношение является отношением контакта, если оно удовлетворяет трем свойствам: ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle g}$

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

Отношение принадлежности множеству , "является элементом", удовлетворяет этим свойствам, поэтому является отношением контакта. Понятие общего отношения контакта было введено Георгом Ауманном в 1970 году. ^{[49] [50]} ${\displaystyle \epsilon =}$ ${\displaystyle \epsilon }$

В терминах исчисления отношений достаточные условия для контактного отношения включают, где есть обратное членство во множестве ( ). ^{[51] : 280} $${\displaystyle C^{\textsf {T}}{\bar {C}}\subseteq \ni {\bar {C}}\equiv C{\overline {\ni {\bar {C}}}}\subseteq C,}$$ ${\displaystyle \ni }$ ${\displaystyle \in }$

Предварительный заказ R\R

Каждое отношение порождает предпорядок , который является левым остатком . ^[52] В терминах обратного и дополнения, образуя диагональ , соответствующая строка и столбец будут иметь противоположные логические значения, поэтому диагональ состоит из одних нулей. Тогда ${\displaystyle R}$ ${\displaystyle R\backslash R}$ ${\displaystyle R\backslash R\equiv {\overline {R^{\textsf {T}}{\bar {R}}}}.}$ ${\displaystyle R^{\textsf {T}}{\bar {R}}}$ ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle {\bar {R}}}$

${\displaystyle R^{\textsf {T}}{\bar {R}}\subseteq {\bar {I}}\implies I\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}=R\backslash R}$, так что это рефлексивное отношение . ${\displaystyle R\backslash R}$

Чтобы показать транзитивность , требуется, чтобы Напомним, что — наибольшее отношение такое, что Тогда ${\displaystyle (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$ ${\displaystyle X=R\backslash R}$ ${\displaystyle RX\subseteq R.}$

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

${\displaystyle R(R\backslash R)(R\backslash R)\subseteq R}$(повторить)

${\displaystyle \equiv R^{\textsf {T}}{\bar {R}}\subseteq {\overline {(R\backslash R)(R\backslash R)}}}$(Правило Шредера)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq {\overline {R^{\textsf {T}}{\bar {R}}}}}$(дополнение)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$(определение)

Отношение включения Ω на множестве мощности может быть получено таким образом из отношения принадлежности на подмножествах : ${\displaystyle U}$ ${\displaystyle \in }$ ${\displaystyle U}$

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

Краешек отношения

Если задано отношение , его границей является подотношение, определяемое как ${\displaystyle R}$ $${\displaystyle \operatorname {fringe} (R)=R\cap {\overline {R{\bar {R}}^{\textsf {T}}R}}.}$$

Когда — частичное тождественное отношение, дифункциональное или блочно-диагональное отношение, то . В противном случае оператор выбирает граничное подотношение, описываемое в терминах его логической матрицы: — боковая диагональ, если — верхний правый треугольный линейный порядок или строгий порядок . — блочная бахрома, если — иррефлексивное ( ) или верхний правый блочно-треугольное. — последовательность граничных прямоугольников, когда — типа Феррерса. ${\displaystyle R}$ ${\displaystyle \operatorname {fringe} (R)=R}$ ${\displaystyle \operatorname {fringe} }$ ${\displaystyle \operatorname {fringe} (R)}$ ${\displaystyle R}$ ${\displaystyle \operatorname {fringe} (R)}$ ${\displaystyle R}$ ${\displaystyle R\subseteq {\bar {I}}}$ ${\displaystyle \operatorname {fringe} (R)}$ ${\displaystyle R}$

С другой стороны, когда — плотный , линейный, строгий порядок. ^[51] ${\displaystyle \operatorname {fringe} (R)=\emptyset }$ ${\displaystyle R}$

Математические кучи

При наличии двух множеств и множество бинарных отношений между ними может быть снабжено тернарной операцией , где обозначает обратное отношение . В 1953 году Виктор Вагнер использовал свойства этой тернарной операции для определения полукуч , куч и обобщенных куч. ^{[53] [54]} Контраст неоднородных и однородных отношений подчеркивается этими определениями: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {B}}(A,B)}$ ${\displaystyle [a,b,c]=ab^{\textsf {T}}c}$ ${\displaystyle b^{\mathsf {T}}}$ ${\displaystyle b}$

В работе Вагнера есть приятная симметрия между кучами, полукучами и обобщенными кучами с одной стороны, и группами, полугруппами и обобщенными группами с другой. По сути, различные типы полукуч появляются всякий раз, когда мы рассматриваем бинарные отношения (и частичные отображения один-один) между различными множествами и , тогда как различные типы полугрупп появляются в случае, когда . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A=B}$

—  Кристофер Холлингс, «Математика за железным занавесом: история алгебраической теории полугрупп» ^[55]

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

• Система переписывания аннотаций
• Аддитивное отношение , многозначный гомоморфизм между модулями
• Аллегория (теория категорий)
• Категория отношений , категория, имеющая множества в качестве объектов и бинарные отношения в качестве морфизмов.
• Слияние (переписывание терминов) , обсуждает несколько необычных, но фундаментальных свойств бинарных отношений.
• Соответствие (алгебраическая геометрия) — бинарное отношение, определяемое алгебраическими уравнениями.
• Диаграмма Хассе , графическое средство для отображения отношения порядка.
• Структура инцидентности , неоднородная связь между множеством точек и линий
• Логика родственников , теория отношений Чарльза Сандерса Пирса
• Теория порядка , исследует свойства отношений порядка.

Примечания

1. Авторы, которые рассматривают бинарные отношения только как частный случай -арных отношений для произвольных, обычно пишут как частный случай ( префиксная запись ). ^[8] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle Rxy}$ ${\displaystyle Rx_{1}\dots x_{n}}$

Ссылки

1. Мейер, Альберт (17 ноября 2021 г.). "MIT 6.042J Math for Computer Science, Lecture 3T, Slide 2" (PDF) . Архивировано (PDF) из оригинала 17.11.2021.
2. Кодд, Эдгар Франк (июнь 1970 г.). «Реляционная модель данных для больших общих банков данных» (PDF) . Сообщения ACM . 13 (6): 377–387. doi :10.1145/362384.362685. S2CID  207549016. Архивировано (PDF) из оригинала 2004-09-08 . Получено 2020-04-29 .
3. "Определение отношения – Math Insight". mathinsight.org . Получено 11.12.2019 .
4. Эрнст Шредер (1895) Алгебра и логика относительной, через Интернет-архив
5. CI Lewis (1918) Обзор символической логики, страницы 269–279, через интернет-архив
6. Gunther Schmidt , 2010. Реляционная математика . Cambridge University Press, ISBN 978-0-521-76268-7 , Глава 5 
7. Эндертон 1977, Гл. 3. стр. 40
8. Ганс Гермес (1973). Введение в математическую логику . Hochschultext (Springer-Verlag). Лондон: Springer. ISBN 3540058192. ISSN  1431-4657.Раздел II.§1.1.4
9. Suppes, Patrick (1972) [первоначально опубликовано D. van Nostrand Company в 1960]. Аксиоматическая теория множеств . Дувр. ISBN 0-486-61630-4.
10. Smullyan, Raymond M. ; Fitting, Melvin (2010) [исправленное и переиздание работы, первоначально опубликованной в 1996 году Oxford University Press, Нью-Йорк]. Теория множеств и проблема континуума . Довер. ISBN 978-0-486-47484-7.
11. Леви, Азриэль (2002) [переиздание работы, опубликованной Springer-Verlag, Берлин, Гейдельберг и Нью-Йорк в 1979 году]. Базовая теория множеств . Дувр. ISBN 0-486-42079-5.
12. Шмидт, Гюнтер ; Штрёляйн, Томас (2012). Отношения и графы: Дискретная математика для компьютерных ученых. Springer Science & Business Media. Определение 4.1.1. ISBN 978-3-642-77968-8.
13. Христодулос А. Флудас ; Панос М. Пардалос (2008). Энциклопедия оптимизации (2-е изд.). Springer Science & Business Media. стр. 299–300. ISBN 978-0-387-74758-3.
14. Michael Winter (2007). Категории Гогена: Категориальный подход к L-нечетким отношениям . Springer. стр. x–xi. ISBN 978-1-4020-6164-6.
15. Г. Шмидт, Клаудия Хальтеншпергер и Майкл Винтер (1997) «Гетерогенная реляционная алгебра», глава 3 (страницы 37–53) в книге «Реляционные методы в информатике» , «Достижения в информатике», книги Springer ISBN 3-211-82971-7 
16. Якобсон, Натан (2009), Основы алгебры II (2-е изд.) § 2.1.
17. Гаррет Биркгофф и Томас Барти (1970) Современная прикладная алгебра , стр. 35, McGraw-Hill
18. Мэри П. Долчиани (1962) Современная алгебра: структура и метод , книга 2, стр. 339, Houghton Mifflin
19. Джон К. Баез (6 ноября 2001 г.). "квантовая механика над коммутативной установкой". Группа новостей : sci.physics.research. Usenet:  [email protected] . Получено 25 ноября 2018 г.
20. Droste, M., & Kuich, W. (2009). Полукольца и формальные степенные ряды. Справочник по взвешенным автоматам , 3–28. doi :10.1007/978-3-642-01492-5_1, стр. 7-10
21. Относительная одновременность в Wikibooks
22. Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1986). Теория дизайна . Издательство Кембриджского университета . С. 15.. 2-е изд. (1999) ISBN 978-0-521-44432-3 
23. Ван Гастерен 1990, с. 45.
24. Kilp, Кнауэр, Михалев 2000, с. 3.
25. "Функциональное отношение - Энциклопедия математики". encyclopediaofmath.org . Получено 2024-06-13 .
26. "функциональное отношение в nLab". ncatlab.org . Получено 2024-06-13 .
27. Шмидт 2010, стр. 49.
28. Килп, Кнауэр, Михалев 2000, с. 4.
29. Яо, YY; Вонг, SKM (1995). "Обобщение грубых множеств с использованием отношений между значениями атрибутов" (PDF) . Труды 2-й ежегодной совместной конференции по информационным наукам : 30–33..
30. Кунен, Кеннет (1980). Теория множеств: введение в доказательства независимости . Северная Голландия. стр. 102. ISBN 0-444-85401-0. Збл  0443.03021.
31. Тарский, Альфред ; Дживант, Стивен (1987). Формализация теории множеств без переменных. Американское математическое общество. стр. 3. ISBN 0-8218-1041-3.
32. ME Müller (2012). Relational Knowledge Discovery . Cambridge University Press. стр. 22. ISBN 978-0-521-19021-3.
33. Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. стр. 496. ISBN 978-3-540-67995-0.
34. Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2006), Переход к высшей математике (6-е изд.), Brooks/Cole, стр. 160, ISBN 0-534-39900-2
35. Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, стр. 158.
36. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF) . Прага: School of Mathematics – Physics Karlov University. стр. 1. Архивировано из оригинала (PDF) 2013-11-02.Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
37. Джозеф Г. Розенштейн, Линейные упорядочения , Academic Press, 1982, ISBN 0-12-597680-1 , стр. 4 
38. Р. Бергхаммер и М. Винтер (2013) «Декомпозиция отношений на решетках понятий», Fundamenta Informaticae 126(1): 37–82 doi :10.3233/FI-2013-871
39. Ки-Ханг Ким (1982) Теория булевых матриц и ее применение , стр. 37, Марсель Деккер ISBN 0-8247-1788-0 
40. Али Джауа, Рехаб Дувайри, Самир Эллуми и Садок Бен Яхья (2009) «Интеллектуальный анализ данных, рассуждения и инкрементальный поиск информации с помощью нерасширяемого прямоугольного покрытия отношений», страницы 199–210 в книге « Отношения и алгебры Клини в информатике» , Lecture Notes in Computer Science 5827, Springer MR 2781235
41. Риге, Жак (январь 1950 г.). «Quelques proprietes deslations difonctionelles». Comptes Rendus (на французском языке). 230 : 1999–2000.
42. Юлиус Рихард Бюхи (1989). Конечные автоматы, их алгебры и грамматики: к теории формальных выражений . Springer Science & Business Media. стр. 35–37. ISBN 978-1-4613-8853-1.
43. East, James; Vernitski, Alexei (февраль 2018). «Ранги идеалов в обратных полугруппах дифункциональных бинарных отношений». Semigroup Forum . 96 (1): 21–30. arXiv : 1612.04935 . doi : 10.1007/s00233-017-9846-9. S2CID  54527913.
44. Крис Бринк; Вольфрам Каль; Гюнтер Шмидт (1997). Реляционные методы в информатике . Springer Science & Business Media. п. 200. ИСБН 978-3-211-82971-4.
45. Али Джауа, Надин Белкхитер, Хабиб Уналли и Теодор Мукам (1997) «Базы данных», страницы 197–210 в Relational Methods in Computer Science , под редакцией Криса Бринка, Вольфрама Каля и Гюнтера Шмидта , Springer Science & Business Media ISBN 978-3-211-82971-4 
46. Гамм, HP; Заррад, M. (2014). "Коалгебраические симуляции и сравнения". Коалгебраические методы в информатике . Конспект лекций по информатике . Том 8446. стр. 118. doi :10.1007/978-3-662-44124-4_7. ISBN 978-3-662-44123-7.
47. Ж. Риге (1951) «Отношения Феррера», Comptes Rendus 232: 1729,30
48. Шмидт, Гюнтер ; Штрёляйн, Томас (2012). Отношения и графы: Дискретная математика для компьютерных ученых. Springer Science & Business Media. стр. 77. ISBN 978-3-642-77968-8.
49. Георг Ауманн (1971). «Контакт-Relationen». Sitzungsberichte der mathematish-physicalischen Klasse der Bayerischen Akademie der Wissenschaften München . 1970 (II): 67–77.
50. Энн К. Штайнер (1970) Обзор: Kontakt-Relationen из Mathematical Reviews
51. Гюнтер Шмидт (2011) Реляционная математика , страницы 211−15, Cambridge University Press ISBN 978-0-521-76268-7 
52. В данном контексте символ не означает « установленную разницу ». ${\displaystyle \backslash }$
53. Виктор Вагнер (1953) «Теория обобщенных груд и обобщенных групп», Математический сборник 32(74): 545-632 MR 0059267
54. CD Hollings & MV Lawson (2017) Теория обобщенных куч Вагнера , Springer books ISBN 978-3-319-63620-7 MR 3729305 
55. Кристофер Холлингс (2014) Математика через железный занавес: история алгебраической теории полугрупп , стр. 265, История математики 41, Американское математическое общество ISBN 978-1-4704-1493-1 

Библиография

• Шмидт, Гюнтер (2010). Реляционная математика . Берлин: Cambridge University Press. ISBN 9780511778810.
• Шмидт, Гюнтер ; Штрёляйн, Томас (2012). "Глава 3: Гетерогенные отношения". Отношения и графы: Дискретная математика для компьютерных ученых . Springer Science & Business Media. ISBN 978-3-642-77968-8.
• Эрнст Шредер (1895) Algebra der Logik, Band III, через Интернет-архив
• Кодд, Эдгар Франк (1990). Реляционная модель управления базами данных: Версия 2 (PDF) . Бостон: Addison-Wesley . ISBN 978-0201141924. Архивировано (PDF) из оригинала 2022-10-09.
• Эндертон, Герберт (1977). Элементы теории множеств . Бостон: Academic Press . ISBN 978-0-12-238440-0.
• Килп, Мати; Кнауэр, Ульрих; Михалев, Александр (2000). Моноиды, акты и категории: с приложениями к произведениям сплетений и графам . Берлин: De Gruyter . ISBN 978-3-11-015248-7.
• Ван Гастерен, Антонетта (1990). О форме математических аргументов . Берлин: Шпрингер. ISBN 9783540528494.
• Пирс, Чарльз Сандерс (1873). «Описание нотации для логики отношений, полученное в результате амплификации концепций логического исчисления Буля». Мемуары Американской академии искусств и наук . 9 (2): 317–178. Bibcode :1873MAAAS...9..317P. doi :10.2307/25058006. hdl : 2027/hvd.32044019561034 . JSTOR  25058006 . Получено 05.05.2020 .
• Шмидт, Гюнтер (2010). Реляционная математика. Кембридж: Cambridge University Press . ISBN 978-0-521-76268-7.

Внешние ссылки

• «Двоичное отношение», Энциклопедия математики , EMS Press , 2001 [1994]