Связанное отношение

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

В математике отношение на множестве называется связным , полным или тотальным, если оно связывает (или «сравнивает») все различные пары элементов множества в одном или другом направлении, в то время как оно называется сильно связным, если оно связывает все пары элементов. Как описано в разделе терминологии ниже, терминология для этих свойств не является единообразной. Это понятие «тотального» не следует путать с понятием тотального отношения в том смысле, что для всех существует так что (см. последовательное отношение ).${\displaystyle x\in X}$${\displaystyle y\in X}$${\displaystyle x\mathrel {R} y}$

Связность играет важную роль в определении полных порядков : полный (или линейный) порядок — это частичный порядок , в котором любые два элемента сравнимы; то есть отношение порядка связано. Аналогично, строгий частичный порядок , который связан, является строгим полным порядком. Отношение является полным порядком тогда и только тогда, когда оно является как частичным порядком, так и сильно связанным. Отношение является строгим полным порядком тогда и только тогда, когда оно является строгим частичным порядком и просто связанным. Строгий полный порядок никогда не может быть сильно связанным (кроме как в пустом домене).

Отношение на множестве называется${\displaystyle R}$${\displaystyle X}$связано , когда для всех или, что то же самое, когда для всех${\displaystyle x,y\in X,}$ $${\displaystyle {\text{ если }}x\neq y{\text{ тогда }}x\mathrel {R} y\quad {\text{или}}\quad y\mathrel {R} x,}$$${\displaystyle x,y\in X,}$$${\displaystyle x\mathrel {R} y\quad {\text{или}}\quad y\mathrel {R} x\quad {\text{или}}\quad x=y.}$$

Отношение со свойством, которое для всех называется${\displaystyle x,y\in X,}$ $${\displaystyle x\mathrel {R} y\quad {\text{или}}\quad y\mathrel {R} x}$$сильно связан .^[1][2][3]

Основное применение понятия связанного отношения — в контексте порядков, где оно используется для определения полных или линейных порядков. В этом контексте свойство часто не называется конкретно. Скорее, полные порядки определяются как частичные порядки, в которых любые два элемента сопоставимы. ^{[4] [5]} Таким образом,total используется в более общем смысле для отношений, которые связаны или сильно связаны.^[6]Однако это понятие «общего отношения» следует отличать от свойства бытьпоследовательным, которое также называется total. Аналогично, связанные отношения иногда называютполное ,^[7]хотя это тоже может привести к путанице:Универсальное отношениетакже называется полным,^[8]и «полное» имеет несколько других значений втеории порядка. Связанные отношения также называютсяconnex ^[9][10]или, как говорят, удовлетворяеттрихотомии^[11](хотя более общее определениетрихотомииявляется более строгим, посколькутолько одноиз трех условий).${\displaystyle x\mathrel {R} y,y\mathrel {R} x,x=y}$

Когда рассматриваемые отношения не являются порядками, быть связанным и быть сильно связанным являются существенно разными свойствами. Источники, которые определяют оба, затем используют пары терминов, такие какслабо связанный исвязанный,^[12] полныйисильно полный,^[13] полныйиполный,^[6] полуконнект иconnex ,^[14]илисвязь истрого коннекс [^15]соответственно, как альтернативные названия для понятий связанного и сильно связанного, определенных выше.

Пусть будет однородным отношением . Следующие соотношения эквивалентны: ^[14]${\displaystyle R}$

• ${\displaystyle R}$тесно связан;
• ${\displaystyle U\subseteq R\cup R^{\top }}$;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }}$;
• ${\displaystyle {\overline {R}}}$асимметричный ,​

где - универсальное отношение , а - обратное отношение${\displaystyle U}$${\displaystyle R^{\top }}$${\displaystyle R.}$

Следующие утверждения эквивалентны: ^[14]

• ${\displaystyle R}$подключен;
• ${\displaystyle {\overline {I}}\subseteq R\cup R^{\top }}$;
• ${\displaystyle {\overline {R}}\subseteq R^{\top }\cup I}$;
• ${\displaystyle {\overline {R}}}$является антисимметричным ,

где - дополнительное отношение отношения тождества , а - обратное отношение${\displaystyle {\overline {I}}}$ ${\displaystyle I}$${\displaystyle R^{\top }}$${\displaystyle R.}$

Вводя прогрессии, Рассел прибегнул к аксиоме связи:

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

—  Бертран Рассел , «Принципы математики» , стр. 239

• Отношение ребер [ ^{примечание 1]} турнирного графа всегда является связным отношением на множестве вершин .${\displaystyle E}$${\displaystyle G}$${\displaystyle G}$
• Если сильно связанное отношение симметрично , то оно является универсальным отношением .
• Отношение является сильно связанным тогда и только тогда, когда оно связано и рефлексивно. ^{[доказательство 1]}
• Связное отношение на множестве не может быть антитранзитивным , если оно содержит не менее 4 элементов. ^[16] Например, на множестве из 3 элементов отношение обладает обоими свойствами.${\displaystyle X}$${\displaystyle X}$${\displaystyle \{a,b,c\},}$${\displaystyle \{(a,b),(b,c),(c,a)\}}$
• Если — связное отношение на , то все или все, кроме одного, элементы из находятся в области значений [ ^{доказательство 2]} Аналогично, все или все, кроме одного, элементы из находятся в области значений${\displaystyle R}$${\displaystyle X,}$${\displaystyle X}$${\displaystyle R.}$${\displaystyle X}$${\displaystyle R.}$

Доказательства