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

«Связь» перенаправляется сюда. Для сравнения торговых компаний см. Connexity Inc.

showТранзитивные   бинарные отношения
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\in X$ есть $y\in X$ так что $x\mathrel {R} y$ (см. серийное отношение ).

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

Формальное определение

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

Отношение к собственности, которое для всех $x,y\in X,$$$x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x$$называется сильно связан .

Терминология

Понятие связанного отношения в основном используется в контексте порядков, где оно используется для определения полных или линейных порядков. В этом контексте свойство часто не упоминается конкретно. Скорее, общие заказы определяются как частичные заказы, в которых любые два элемента сопоставимы. Таким образом, Total используется в более общем смысле для отношений, которые связаны или сильно связаны. Однако это понятие «тотального отношения» следует отличать от свойства серийности , которое также называют тотальным. Точно так же связанные отношения иногда называют полный , хотя и это может привести к путанице: универсальное отношение еще называют полным, а слово « полный » имеет несколько других значений в теории порядка .Связные отношения еще называют соединять или говорят, что удовлетворяет трихотомии (хотя более распространенное определение трихотомии более сильное в том, что именно один из трех вариантов $x\mathrel {R} y,y\mathrel {R} x,x=y$ должен держаться).

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

Характеристики

Позволять $R$ быть однородным отношением . Следующие действия эквивалентны:

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

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

Следующие действия эквивалентны:

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

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

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

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

- Бертран Рассел , «Основы математики» , стр. 239.

Характеристики

• Краевое ​ отношение $E$ турнира ​ графика $G$ всегда является связным отношением на множестве $G$' s вершины.
• Если сильно связное отношение симметрично , то это универсальное отношение .
• Отношение является сильно связным тогда и только тогда, когда оно связно и рефлексивно.
• Связное отношение на множестве $X$ не может быть антитранзитивным при условии, что $X$ имеет не менее 4 элементов. На наборе из трех элементов $\{a,b,c\},$ например, отношение $\{(a,b),(b,c),(c,a)\}$ имеет оба свойства.
• Если $R$ является связным отношением на $X,$ тогда все или все, кроме одного, элементы $X$ в пределах находятся $R.$ Аналогично, все или все, кроме одного, элементы $X$ находятся в сфере $R.$

Примечания

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