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

Свойство отношения на множестве

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

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

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

Отношение на множестве называется ${\displaystyle R}$ ${\displaystyle X}$связано , когда для всех или, что то же самое, когда для всех ${\displaystyle x,y\in X,}$ $${\displaystyle {\text{ if }}x\neq y{\text{ then }}x\mathrel {R} y\quad {\text{or}}\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]

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

Основное применение понятия связанного отношения — в контексте порядков, где оно используется для определения полных или линейных порядков. В этом контексте свойство часто не называется конкретно. Скорее, полные порядки определяются как частичные порядки, в которых любые два элемента сопоставимы. ^{[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] полуконнект иконнекс ,^[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.}$

Примечания

1. Формально определяется как если ребро графа ведет от вершины к вершине. ${\displaystyle vEw}$ ${\displaystyle v}$ ${\displaystyle w}$

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

1. Для направления « только если » оба свойства следуют тривиально. — Для направления «если» : когда то следует из связности; когда следует из рефлексивности. ${\displaystyle x\neq y,}$ ${\displaystyle x\mathrel {R} y\lor y\mathrel {R} x}$ ${\displaystyle x=y,}$ ${\displaystyle x\mathrel {R} y}$
2. Если и невозможны, то это следует из связности. ${\displaystyle x,y\in X\setminus \operatorname {ran} (R),}$ ${\displaystyle x\mathrel {R} y}$ ${\displaystyle y\mathrel {R} x}$ ${\displaystyle x=y}$

Ссылки

1. Клэпхэм, Кристофер; Николсон, Джеймс (2014-09-18). "connected". Краткий Оксфордский словарь математики. Oxford University Press. ISBN 978-0-19-967959-1. Получено 2021-04-12 .
2. Нивергельт, Ив (2015-10-13). Логика, математика и информатика: современные основы с практическими приложениями. Springer. стр. 182. ISBN 978-1-4939-3223-8.
3. Коуси, Роберт Л. (1994). Логика, множества и рекурсия . Jones & Bartlett Learning. ISBN 0-86720-463-X., стр. 135
4. Пол Р. Халмош (1968). Наивная теория множеств . Принстон: Nostrand.Здесь: Гл. 14. Халмош приводит названия рефлексивности, антисимметрии и транзитивности, но не связности.
5. Патрик Кусо (1990). «Методы и логика для доказательства программ». В Jan van Leeuwen (ред.). Formal Models and Semantics . Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 841–993. ISBN 0-444-88074-7.Здесь: Раздел 6.3, стр.878
6. Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Анализ бесконечных измерений: Путеводитель для путешествующих автостопом . Springer. ISBN 978-3-540-32696-0., стр. 6
7. Макинсон, Дэвид (2012-02-27). Множества, логика и математика для вычислений . Springer. ISBN 978-1-4471-2500-6., стр. 50
8. Уайтхед, Альфред Норт ; Рассел, Бертран (1910). Principia Mathematica. Кембридж: Издательство Кембриджского университета.{{cite book}}: CS1 maint: date and year (link)
9. Уолл, Роберт Э. (1974). Введение в математическую лингвистику . Prentice-Hall.страница 114.
10. Карл Поллард. «Отношения и функции» (PDF) . Университет штата Огайо . Получено 28.05.2018 .Страница 7.
11. Кунен, Кеннет (2009). Основы математики . College Publications. ISBN 978-1-904987-14-7.стр. 24
12. Фишберн, Питер С. (2015-03-08). Теория социального выбора. Princeton University Press. стр. 72. ISBN 978-1-4008-6833-9.
13. Робертс, Фред С. (2009-03-12). Теория измерений: Том 7: с приложениями к принятию решений, полезности и социальным наукам . Cambridge University Press. ISBN 978-0-521-10243-8.страница 29
14. Шмидт, Гюнтер ; Штрёляйн, Томас (1993). Отношения и графы: Дискретная математика для компьютерных ученых. Берлин: Springer. ISBN 978-3-642-77970-1.
15. Гантер, Бернхард; Вилле, Рудольф (2012-12-06). Формальный концептуальный анализ: математические основы . Springer Science & Business Media. ISBN 978-3-642-59830-2.стр. 86
16. Йохен Бургхардт (июнь 2018 г.). Простые законы о невыдающихся свойствах бинарных отношений (технический отчет). arXiv : 1806.05036 . Bibcode :2018arXiv180605036B.Лемма 8.2, п.8.