Связанное отношение - Connected relation

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

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

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

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

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

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

называется сильно связан .

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

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

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

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

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

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

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

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

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

где это дополнительное отношение по отношению идентичности и это обратное соотношение из${\ displaystyle {\ overline {I}}}$ ${\ displaystyle I}$${\ displaystyle R ^ {\ top}}$${\ displaystyle R.}$

Рассматривая прогрессии, Рассел воспользовался аксиомой связи:

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

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

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

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

Примечания

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

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