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

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

В математике отношение на множестве называется связным , полным или тотальным , если оно связывает (или «сравнивает») все различные пары элементов множества в том или ином направлении, и сильно связным, если оно связывает все пары элементов множества. элементы. Как описано в разделе терминологии ниже, терминология для этих свойств неоднородна. Это понятие «тотального» не следует путать с понятием тотального отношения в том смысле, что для всех существует такое-то (см. серийное отношение ). ${\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]Однако это понятие «тотального отношения» следует отличать от свойства серийности,которое также называют тотальным. Точно так же связанные отношения иногда называютполное ,^[7]хотя это тоже может привести к путанице:универсальное отношениетакже называется полным,^[8]и «полный» имеет несколько других значений втеории порядка. Связные отношения еще называютconnex ^[9][10]или, как говорят, удовлетворяеттрихотомии^[11](хотя более распространенное определениетрихотомииболее строгое, посколькуровно одиниз трех вариантов). ${\displaystyle x\mathrel {R} y,y\mathrel {R} x,x=y}$

Когда рассматриваемые отношения не являются порядками, связь и сильная связь являются важными разными свойствами. Источники, которые определяют оба, затем используют пары терминов, такие какслабо связный исвязный,^[12] полныйисильно полный,^[13] полныйиполный,^[6] полуконнекс иконнекс ,^[14]илисвязь истрого connex ,^[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] Например, в трехэлементном множестве отношение обладает обоими свойствами. ${\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. Для единственного направления if оба свойства следуют тривиально. — Для направления if : когда то следует из связности; когда следует из рефлексивности. ${\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. Клэпхэм, Кристофер; Николсон, Джеймс (18 сентября 2014 г.). "связанный". Краткий Оксфордский математический словарь. Издательство Оксфордского университета. ISBN 978-0-19-967959-1. Проверено 12 апреля 2021 г.
2. Нивергельт, Ив (13 октября 2015 г.). Логика, математика и информатика: современные основы с практическим применением. Спрингер. п. 182. ИСБН 978-1-4939-3223-8.
3. Кози, Роберт Л. (1994). Логика, множества и рекурсия . Джонс и Бартлетт Обучение. ISBN 0-86720-463-Х., п. 135
4. Пол Р. Халмос (1968). Наивная теория множеств . Принстон: Ностранд.Здесь: Гл.14. Халмос называет рефлексивностью, антисимметрией и транзитивностью, но не связностью.
5. Патрик Кусо (1990). «Методы и логика доказательства программ». Ян ван Леувен (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Том. Б. Эльзевир. стр. 841–993. ISBN 0-444-88074-7.Здесь: п.6.3, стр.878
6. Алипрантис, Хараламбос Д.; Бордер, Ким К. (02 мая 2007 г.). Бесконечномерный анализ: Путеводитель для путешественника . Спрингер. ISBN 978-3-540-32696-0., п. 6
7. Макинсон, Дэвид (27 февраля 2012 г.). Множества, логика и математика для вычислений . Спрингер. ISBN 978-1-4471-2500-6., п. 50
8. Уайтхед, Альфред Норт ; Рассел, Бертран (1910). Принципы математики. Кембридж: Издательство Кембриджского университета.{{cite book}}: CS1 maint: date and year (link)
9. Уолл, Роберт Э. (1974). Введение в математическую лингвистику . Прентис-Холл.стр. 114.
10. Карл Поллард. «Отношения и функции» (PDF) . Университет штата Огайо . Проверено 28 мая 2018 г.Страница 7.
11. Кунен, Кеннет (2009). Основы математики . Публикации колледжа. ISBN 978-1-904987-14-7.п. 24
12. Фишберн, Питер К. (08 марта 2015 г.). Теория социального выбора. Издательство Принстонского университета. п. 72. ИСБН 978-1-4008-6833-9.
13. Робертс, Фред С. (12 марта 2009 г.). Теория измерения: Том 7: С приложениями к принятию решений, коммунальным услугам и социальным наукам . Издательство Кембриджского университета. ISBN 978-0-521-10243-8.стр. 29
14. Шмидт, Гюнтер ; Стрёлейн, Томас (1993). Отношения и графики: дискретная математика для компьютерных специалистов. Берлин: Шпрингер. ISBN 978-3-642-77970-1.
15. Гантер, Бернхард; Вилле, Рудольф (6 декабря 2012 г.). Анализ формальных концепций: математические основы . Springer Science & Business Media. ISBN 978-3-642-59830-2.п. 86
16. Йохен Бургхардт (июнь 2018 г.). Простые законы о невыявленных свойствах бинарных отношений (технический отчет). arXiv : 1806.05036 . Бибкод : 2018arXiv180605036B.Лемма 8.2, п.8.