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

В математике отношение в наборе называется связным или полным, если оно связывает все различные пары элементов набора в одном или другом направлении, т. Е. Если можно сравнить любые два элемента. Более формально, отношение R на множестве X является связным, когда для всех где , ${\ displaystyle x, y \ in X,}$${\ Displaystyle х \ neq y}$

${\ Displaystyle х \ mathrel {R} y \ quad {\ text {или}} \ quad y \ mathrel {R} x,}$

или, что то же самое, когда для всех ,${\ displaystyle x, y \ in X}$

${\ displaystyle x \ mathrel {R} y \ quad {\ text {or}} \ quad y \ mathrel {R} x \ quad {\ text {or}} \ quad x = y.}$

Отношение к собственности, которая для всех , ${\ displaystyle x, y \ in X}$

${\displaystyle x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x}$

называется сильно связным . ^{[1] [2] [3]}

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

Связность и общее количество заказов [ править ]

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

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

Терминология [ править ]

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

Когда рассматриваемые отношения не являются порядками, связь и сильная связь - важные разные свойства. Источники, которые определяют оба, затем используют пары терминов, такие как слабо связанный и связанный , ^[12] полный и строго полный , ^[13] тотальный и полный , ^[6] полусоединение и коннекс , ^[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}$

Свойства [ править ]

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

Ссылки [ править ]