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

В этой статье рассматриваются расширенные понятия. Основные темы см. в разделе Отношения (математика) .

показывать Транзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

В математике бинарное отношение связывает элементы одного набора, называемого доменом , с элементами другого набора, называемого кодоменом . Бинарное отношение над множествами $X$ и $Y$ представляет собой набор упорядоченных пар $(x,y)$ состоящий из элементов $x$ от $X$ и $y$ от $Y$. Он кодирует общую концепцию отношения: элемент $x$ относится к элементу $y$, тогда и только тогда, когда пара $(x,y)$ принадлежит множеству упорядоченных пар, которое определяет бинарное отношение.

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

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

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

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

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

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

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

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

Определение

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

Бинарное отношение $R$ больше сетов $X$ и $Y$ является подмножеством $X\times Y.$ Набор $X$ называется доменом или набор отправления $R$, и набор $Y$ или кодовый домен набор пунктов назначения $R$. Чтобы уточнить выбор наборов $X$ и $Y$некоторые авторы определяют бинарное отношение или соответствие как упорядоченную тройку $(X,Y,G)$, где $G$ является подмножеством $X\times Y$ называется графиком бинарного отношения. Заявление $(x,y)\in R$ читает " $x$ является $R$-относящийся к $y$" и обозначается $xRy$. Домен определения или активный домен из $R$ это совокупность всех $x$ такой, что $xRy$ хотя бы для одного $y$. Кодомен определения , активный кодомен , изображение или диапазон ​ $R$ это совокупность всех $y$ такой, что $xRy$ хотя бы для одного $x$. Область ​ ​ $R$ является объединением своей области определения и своей кодомена определения.

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

Неоднородное отношение называется прямоугольным отношением . предполагая, что оно не обладает квадратной симметрией однородного отношения на множестве , где $A=B.$ Комментируя развитие бинарных отношений за пределами однородных отношений, исследователи писали: «...развился вариант теории, который с самого начала трактует отношения как гетерогенные или прямоугольные , т.е. как отношения, где в нормальном случае они представляют собой отношения между разные наборы».

Условия переписки , диадическое отношение и двухместное отношение являются синонимами бинарного отношения, хотя некоторые авторы используют термин «бинарное отношение» для любого подмножества декартова произведения. $X\times Y$ без ссылки на $X$ и $Y$и зарезервируем термин «соответствие» для бинарного отношения со ссылкой на $X$ и $Y$.

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

Операции

Союз

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

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

Пересечение

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

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

Состав

Основная статья: Состав отношений

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

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

Конверсы

Основная статья: Обратное соотношение

Смотрите также: Двойственность (теория порядка)

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

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

Дополнить

Основная статья: Дополнительное отношение

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

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

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

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

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

Ограничение

Основная статья: Ограничение (математика)

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

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

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

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

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

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

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

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

Бинарные отношения над множествами $X$ и $Y$ могут быть представлены алгебраически логическими матрицами, индексированными $X$ и $Y$ с записями в булевом полукольце (сложение соответствует ИЛИ, а умножение И), где сложение матриц соответствует объединению отношений, умножение матриц соответствует композиции отношений (отношения над $X$ и $Y$ и отношение более $Y$ и $Z$), произведение Адамара соответствует пересечению отношений, нулевая матрица соответствует пустому отношению, а матрица единиц соответствует универсальному отношению. Однородные отношения (когда $X=Y$) образуют матричное полукольцо (фактически матричную полуалгебру над булевым полукольцом), где единичная матрица соответствует тождественному отношению.

Примеры

2-й пример отношения

$A$ $B$	мяч	машина	кукла	чашка
Джон	+	−	−	−
Мэри	−	−	+	−
Венера	−	+	−	−

1-й пример отношения

$A$ $B$	мяч	машина	кукла	чашка
Джон	+	−	−	−
Мэри	−	−	+	−
Ян	−	−	−	−
Венера	−	+	−	−

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

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

   

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

   Океан граничит с континентом

   	ЧТО	на	ИЗ	Евросоюз	КАК	В	АА
   Индийский	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

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

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

   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Гомогенное отношение

Однородное отношение над множеством $X$ является бинарным отношением над $X$ и сам по себе, т.е. это подмножество декартова произведения $X\times X.$ Его также называют просто (бинарным) отношением над $X$.

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

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

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

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

Все операции, определенные в разделе § Операции, также применимы к однородным отношениям.Кроме того, однородное отношение над множеством $X$ могут подвергаться операциям закрытия, таким как:

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

наименьшее рефлексивное отношение над $X$ содержащий $R$,

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

наименьшее транзитивное отношение над $X$ содержащий $R$,

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

наименьшее отношение эквивалентности над $X$ содержащий $R$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тип Феррера

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

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

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

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

Контакт

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

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

Установленное отношение принадлежности , $\epsilon =$ «является элементом», удовлетворяет этим свойствам, поэтому $\epsilon$ это контактное отношение. Понятие общего контактного отношения было введено Георгом Ауманном в 1970 году.

С точки зрения исчисления отношений, к достаточным условиям контактного отношения относятся: $$C^{\textsf {T}}{\bar {C}}\subseteq \ni {\bar {C}}\equiv C{\overline {\ni {\bar {C}}}}\subseteq C,$$ где $\ni$ является обратным членству в множестве ( $\in$).

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

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

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

Чтобы показать транзитивность , нужно, чтобы $(R\backslash R)(R\backslash R)\subseteq R\backslash R.$ Напомним, что $X=R\backslash R$ является наибольшим отношением таким, что $RX\subseteq R.$ Затем

$R(R\backslash R)\subseteq R$

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

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

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

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

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

$\Omega ={\overline {\ni {\bar {\in }}}}=\in \backslash \in .$

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

Учитывая отношение $R$, его граница — это подотношение, определяемое как $$\operatorname {fringe} (R)=R\cap {\overline {R{\bar {R}}^{\textsf {T}}R}}.$$

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

С другой стороны, $\operatorname {fringe} (R)=\emptyset$ когда $R$ представляет собой плотный , линейный, строгий порядок.

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

Основная статья: Куча (математика)

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

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

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

См. также

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

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

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

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

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