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

Транзитивные  бинарные отношения
Симметричный Антисимметричный Связаны Обоснованный Присоединяется Встречается Рефлексивный Нерефлексивный Асимметричный Также известный как: Итого, Semiconnex Антирефлексивный Отношение эквивалентности ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Предзаказ (Квазипорядок) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Частичный заказ ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Всего предзаказ ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Общий заказ ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Предварительный заказ ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Хорошо-квазиупорядоченный ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ Хороший порядок ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Решетка ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ Соединение-полурешетка ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ Встреча-полурешетка ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ Строгий частичный заказ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Строгий слабый порядок ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Строгий общий порядок ✗ ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✓ Симметричный Антисимметричный Связаны Обоснованный Присоединяется Встречается Рефлексивный Нерефлексивный Асимметричный Определения: ${\displaystyle \scriptstyle {{\text{For all}}\,a,b\,{\text{and}}\,S\neq \varnothing :}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow bRa}}$ ${\displaystyle \scriptstyle {aRb\,{\text{and}}\,bRa\Rightarrow a=b}}$ ${\displaystyle \scriptstyle {a\neq b\Rightarrow aRb\,{\text{or}}\,bRa}}$ ${\displaystyle \scriptstyle {\min S\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {a\vee b\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {a\wedge b\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {aRa}}$ ${\displaystyle \scriptstyle {{\text{not}}\,aRa}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow {\text{not}}\,bRa}}$
Все определения неявно требуют, чтобы однородное отношение было транзитивным : « ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Упомянутые здесь дополнительные свойства , что однородное отношение может удовлетворять.${\displaystyle R}$${\displaystyle \scriptstyle {{\text{For all}}\,a,b,c,{\text{ if }}aRb{\text{ and }}bRc{\text{ then }}aRc}.}$

В математике , А бинарное отношение над множествами X и Y представляет собой подмножество в декартово произведение ; то есть, она представляет собой набор упорядоченных пар ( х , у ) , состоящих из элементов х в X и Y в Y . ^[1] Он кодирует общую концепцию соотношения: элемент х имеет связанный с элементом у , тогда и только тогда , когда пара ( х , у${\displaystyle X\times Y}$ ) принадлежит набору упорядоченных пар, определяющих бинарное отношение . Бинарное отношение является наиболее изученным частным случаем п = 2 из п -ичного соотношения над множествами Х ₁ , ..., Х _п , которое является подмножеством декартова произведения ^{[1] [2]}${\displaystyle X_{1}\times \cdots \times X_{n}.}$

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

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

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

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

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

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

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

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

Определение

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

Бинарное отношение R над множествами X и Y представляет собой подмножество ^{[1] [8]} Множество Х называется область ^[1] или набор вылета из R , а множество Y кообласть или набор назначения из R . Чтобы указать выбор множеств X и Y , некоторые авторы определяют бинарное отношение или соответствие как упорядоченную тройку ( X , Y , G${\displaystyle X\times Y.}$) , где G - подмножество, называемое графом бинарного отношения. Утверждение гласит: « x имеет отношение R к y » и обозначается xRy . ^{[4] [5] [6] [примечание 1]} область определения или активной области ^[1] из R представляет собой множество всех х таких , что хКу по крайней мере , одного у . Кообласть определения , активной области значений , ^[1] изображение или${\displaystyle X\times Y}$${\displaystyle (x,y)\in R}$ Диапазон из R представляет собой множество всех у таких , что хКа , по крайней мере , одного х . Поле из R является объединением своей области определения и его кообласти определения. ^{[10] [11] [12]}

Когда бинарное отношение называется гомогенным отношением (или эндорреляцией ). В противном случае это неоднородные отношения . ^{[13] [14] [15]}${\displaystyle X=Y,}$

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

Примеры

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

2) Пусть A = {Индийский, Арктический, Атлантический, Тихий}, океаны земного шара, и B = {NA, SA, AF, EU, AS, AU, AA}, континенты . Пусть ARB представляет этот океан на границах континент б . Тогда логическая матрица для этого отношения:

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

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

3) Визуализация отношений опирается на теорию графов : для отношений на множестве (однородные отношения) ориентированный граф иллюстрирует отношение, а граф - симметричное отношение. Для гетерогенных отношений гиперграф имеет ребра, возможно, с более чем двумя узлами, и может быть проиллюстрирован двудольным графом .

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

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

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

Как отношение между некоторыми временными событиями и некоторыми пространственными событиями, гиперболическая ортогональность (как обнаруживается в расщепленных комплексных числах ) является неоднородным отношением. ^[16]

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

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

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

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

Как набор^{[ необходима цитата ]} (или местный )

для всех в классе всех у таких , что угх представляет собой набор. (Это имеет смысл только в том случае, если разрешены отношения над соответствующими классами.) Например, обычное упорядочение <над классом порядковых чисел является отношением, подобным множеству, а его обратное> - нет.${\displaystyle x\in X,}$

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

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

Свойства целостности (можно определить, только если указаны домен X и домен Y ):

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

Свойства уникальности и полноты (можно определить, только если заданы домен X и домен Y ):

• Функции : бинарное отношение , что является функциональным и серийным. Например, красные и зеленые бинарные отношения на диаграмме являются функциями, а синие и черные - нет.
• Инъекции : функция , которая инъективна. Например, зеленое двоичное отношение на диаграмме является инъекцией, а красный, синий и черный - нет.
• Сюръекция : функция , которая сюръективна. Например, зеленое бинарное отношение на диаграмме является сюрпризом, а красный, синий и черный - нет.
• Биекция : функция, инъективно и сюръективно. Например, зеленое бинарное отношение на диаграмме является взаимно однозначным, а красный, синий и черный - нет.

Операции над бинарными отношениями

Союз

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

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

Пересечение

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

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

Состав

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

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

Converse

Если R представляет собой бинарное отношение над множествами X и Y , то есть обратное соотношение из R над Y и X .${\displaystyle R^{\text{T}}=\{(y,x):xRy\}}$

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

Дополнение

Если R представляет собой бинарное отношение над множествами X и Y затем (также обозначается через R или ¬ R ) является комплементарной отношение из R над X и Y .${\displaystyle {\overline {R}}=\{(x,y):{\text{ not }}xRy\}}$

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

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

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

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

Ограничение

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

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

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

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

Однако транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания, т. Е. В общем случае не равнозначно. Например, ограничение отношения « x является родителем y » женщинами дает отношение « x - мать женщины y »; его переходное закрытие не связывает женщину с бабушкой по отцовской линии. С другой стороны, транзитивное закрытие "является предком" является "является предком"; его ограничение женщинами действительно связывает женщину с ее бабушкой по отцовской линии.

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

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

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

Бинарные отношения над множествами X и Y могут быть представлены алгебраически логическими матрицами, проиндексированными X и Y с элементами в булевом полукольце (сложение соответствует OR, а умножение - AND), где сложение матриц соответствует объединению отношений, умножение матриц соответствует составу отношения (отношения над X и Y и отношения над Y и Z ), ^[21] произведение Адамара соответствует пересечению отношений, нулевая матрицасоответствует пустому отношению, а матрица единиц соответствует универсальному отношению. Однородные отношения (когда X = Y ) образуют матричное полукольцо (действительно, матричную полуалгебру над булевым полукольцом), где единичная матрица соответствует единичному отношению. ^[22]

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

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

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

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

Однородное отношение

Однородное отношение над множеством X представляет собой бинарное отношение над X и само по себе, т.е. является подмножеством декартова произведения ^{[15] [24] [25]} Она также называется просто (двоичный) отношение над X .${\displaystyle X\times X.}$

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

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

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

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

Все операции, определенные в разделе Операции с бинарными отношениями, также применимы к однородным отношениям. Помимо этого, однородное отношение над множеством X может подвергаться закрывающим операциям, например:

• Рефлексивное замыкание : (единственное) рефлексивное отношение над X, содержащее R ,
• Транзитивное замыкание : наименьшее транзитивное отношение над X, содержащее R ,
• Эквивалентность замыкание : наименьшее отношение эквивалентности над X , содержащей R .

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

В математике , А гетерогенное отношение является бинарным отношением , A подмножеством из декартово произведения , где и B различны множества. ^[30] Приставка гетеро происходит от греческого ἕτερος ( гетерос , «другой, другой, другой»).${\displaystyle A\times B,}$

Гетерогенный отношение было названо прямоугольное отношение , ^[31] предполагая , что он не имеет квадратную-симметрию однородного отношения на множестве , где Комментируя развитие бинарных отношений за пределами однородных отношений, пишут исследователи,»... эволюционировал вариант теории, который рассматривает отношения с самого начала как гетерогенные или прямоугольные , то есть как отношения, в которых нормальным случаем является то, что они являются отношениями между различными наборами ». ^[32]${\displaystyle A=B.}$

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

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

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

Решетка индуцированных концепций

Бинарные отношения были описаны через их индуцированные решетки понятий : понятие C ⊂ R удовлетворяет двум свойствам: (1) логическая матрица C - это внешнее произведение логических векторов

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

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

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

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

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

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

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

• Утверждение : если R - последовательное отношение, а R ^T - его транспонирование, то где - тождественное отношение m × m .${\displaystyle I\subseteq R^{T}R}$${\displaystyle I}$
• Утверждение : если R - сюръективное отношение , то где - тождественное отношение.${\displaystyle I\subseteq RR^{T}}$${\displaystyle I}$${\displaystyle n\times n}$

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

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

Логическая матрица такого отношения R может быть повторно выполнена в виде блока матрицы с блоками единиц по диагонали. В терминах исчисления отношений Жак Риге в 1950 году показал, что такие отношения удовлетворяют включению

${\displaystyle R\ R^{T}\ R\ \subseteq \ R.}$^[36]

Он назвал эти отношения дифункциональными, поскольку композиция FG ^T включает однолистные отношения, обычно называемые функциями .

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

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

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

В теории автоматов термин прямоугольное отношение также использовался для обозначения дифункционального отношения. Эта терминология напоминает тот факт, что, когда они представлены в виде логической матрицы, столбцы и строки дифункционального отношения могут быть расположены в виде блочно-диагональной матрицы с прямоугольными блоками истинности на (асимметричной) главной диагонали. ^[40]

Тип Феррера

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

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

Алгебраическое утверждение, необходимое для отношения R типа Феррерса, имеет следующий вид:

$${\displaystyle R{\bar {R}}^{T}R\subseteq R.}$$

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

Контакт

Предположим , что В представляет собой силовой агрегат из А , множество всех подмножеств из А . Тогда отношение 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 году. ^{[42] [43]}

С точки зрения исчисления отношений, достаточные условия для отношения контакта включают:

$${\displaystyle C^{T}{\bar {C}}\ \subseteq \ \ni {\bar {C}}\ \ \equiv \ C\ {\overline {\ni {\bar {C}}}}\ \subseteq \ C,}$$

${\displaystyle \ni }$

Предзаказ R \ R

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

${\displaystyle R^{T}{\bar {R}}\subseteq {\bar {I}}\ \implies \ I\subseteq {\overline {R^{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^{T}{\bar {R}}\subseteq {\overline {(R\backslash R)(R\backslash R)}}}$ (Правило Шредера)

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

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

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

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

Граница отношения

Для отношения R подотношение, называемое его бахромой , определяется как

$${\displaystyle \operatorname {fringe} (R)=R\cap {\overline {R{\bar {R}}^{T}R}}.}$$

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

С другой стороны, Fringe ( R ) =, когда R - плотный , линейный, строгий порядок. ^[44]

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

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

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

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

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

Примечания

использованная литература

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

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

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

• СМИ, связанные с бинарными отношениями на Викискладе?
• "Бинарные отношения" , Энциклопедия математики , EMS Press , 2001 [1994]