Свойство отношения на множестве
В математике отношение на множестве называется связным , полным или тотальным , если оно связывает (или «сравнивает») все различные пары элементов множества в том или ином направлении, и сильно связным, если оно связывает все пары элементов множества. элементы. Как описано в разделе терминологии ниже, терминология для этих свойств неоднородна. Это понятие «тотального» не следует путать с понятием тотального отношения в том смысле, что для всех существует такое-то (см. серийное отношение ).![{\displaystyle x\in X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle y\in X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\mathrel {R} y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Связность занимает видное место в определении общего порядка : полный (или линейный) порядок — это частичный порядок , в котором любые два элемента сравнимы; то есть отношение порядка связно. Аналогично, строгий частичный порядок , который является связным, является строгим полным порядком. Отношение является полным порядком тогда и только тогда, когда оно одновременно является частичным порядком и сильно связным. Отношение является строгим тотальным порядком тогда и только тогда, когда оно является строгим частичным порядком и просто связно. Строгий общий порядок никогда не может быть сильно связан (за исключением пустой области).
Формальное определение
Отношение на множестве называется![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
подключен , когда для всех
![{\displaystyle {\text{if }}x\neq y{\text{ then }}x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x,y\in X,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\mathrel {R} y\quad {\text{or}} \quad y\mathrel {R} x\quad {\text{or}}\quad x=y.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Отношение к собственности, которое для всех
![{\displaystyle x\mathrel {R} y\quad {\text{or}} \quad y\mathrel {R} x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
сильно связан[1][2][3]Терминология
Понятие связанного отношения в основном используется в контексте порядков, где оно используется для определения полных или линейных порядков. В этом контексте свойство часто не упоминается конкретно. Скорее, общие заказы определяются как частичные заказы, в которых любые два элемента сопоставимы. [4] [5]
Таким образом,Total используется в более общем смысле для отношений, которые связаны или сильно связаны. [6]Однако это понятие «тотального отношения» следует отличать от свойства серийности,которое также называют тотальным. Точно так же связанные отношения иногда называютполное ,[7]хотя это тоже может привести к путанице:универсальное отношениетакже называется полным,[8]и «полный» имеет несколько других значений втеории порядка. Связные отношения еще называютconnex [9][10]или, как говорят, удовлетворяеттрихотомии[11](хотя более распространенное определениетрихотомииболее строгое, посколькуровно одиниз трех вариантов).![{\displaystyle x\mathrel {R} y,y\mathrel {R} x,x=y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Когда рассматриваемые отношения не являются порядками, связь и сильная связь являются важными разными свойствами. Источники, которые определяют оба, затем используют пары терминов, такие какслабо связный исвязный,[12] полныйисильно полный,[13] полныйиполный,[6] полуконнекс иконнекс ,[14]илисвязь истрого connex ,[15]соответственно, в качестве альтернативных названий понятий связности и сильно связности, определенных выше.
Характеристики
Пусть — однородное отношение . Следующие действия эквивалентны: [14]![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
сильно связан;
;
;
является асимметричным ,
где – универсальное отношение , а – обратное отношение![{\displaystyle U}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\top }}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Р.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Следующие действия эквивалентны: [14]
подключен;
;
;
является антисимметричным ,
где – дополнительное отношение тождественного отношения , а – обратное отношение тождественного отношения .
![{\displaystyle I}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle R^{\top }}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Р.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Вводя прогрессии, Рассел ссылался на аксиому связи:
Всякий раз, когда ряд первоначально задан транзитивным асимметричным отношением, мы можем выразить связь условием, что любые два члена нашего ряда должны иметь порождающее отношение .
Характеристики
- Отношение ребер [примечание 1] турнирного графа всегда является связным отношением на множестве вершин .
![{\displaystyle E}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle G}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle G}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если сильно связное отношение симметрично , то это универсальное отношение .
- Отношение сильно связно тогда и только тогда, когда оно связно и рефлексивно. [доказательство 1]
- Связное отношение на множестве не может быть антитранзитивным , если оно содержит не менее 4 элементов. [16] Например, в трехэлементном множестве отношение обладает обоими свойствами.
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle \ {a, b, c \},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle \ {(a, b), (b, c), (c, a) \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Если является связным отношением, то все элементы или все, кроме одного, находятся в области [доказательство 2]. Аналогично , все или все элементы, кроме одного, находятся в области
![{\displaystyle R}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Р.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Р.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Примечания
- ^ Формально определяется как если ребро графа ведет от вершины к вершине.
![{\displaystyle vEw}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle v}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle ш}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Доказательства
- ^ Для единственного направления if оба свойства следуют тривиально. — Для направления if : когда то следует из связности; когда следует из рефлексивности.
![{\displaystyle x\neq y,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\mathrel {R} y\lor y\mathrel {R} x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\mathrel {R} y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- ^ Если тогда и невозможны, то это следует из связности.
![{\displaystyle x,y\in X\setminus \operatorname {ran} (R),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x\mathrel {R} y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle y\mathrel {R} x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x=y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Рекомендации
- ^ Клэпхэм, Кристофер; Николсон, Джеймс (18 сентября 2014 г.). "связанный". Краткий Оксфордский математический словарь. Издательство Оксфордского университета. ISBN 978-0-19-967959-1. Проверено 12 апреля 2021 г.
- ^ Нивергельт, Ив (13 октября 2015 г.). Логика, математика и информатика: современные основы с практическим применением. Спрингер. п. 182. ИСБН 978-1-4939-3223-8.
- ^ Кози, Роберт Л. (1994). Логика, множества и рекурсия . Джонс и Бартлетт Обучение. ISBN 0-86720-463-Х., п. 135
- ^ Пол Р. Халмос (1968). Наивная теория множеств . Принстон: Ностранд.Здесь: Гл.14. Халмос называет рефлексивностью, антисимметрией и транзитивностью, но не связностью.
- ^ Патрик Кусо (1990). «Методы и логика доказательства программ». Ян ван Леувен (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Том. Б. Эльзевир. стр. 841–993. ISBN 0-444-88074-7.Здесь: п.6.3, стр.878
- ^ аб Алипрантис, Хараламбос Д.; Бордер, Ким К. (02 мая 2007 г.). Бесконечномерный анализ: Путеводитель для путешественника . Спрингер. ISBN 978-3-540-32696-0., п. 6
- ^ Макинсон, Дэвид (27 февраля 2012 г.). Множества, логика и математика для вычислений . Спрингер. ISBN 978-1-4471-2500-6., п. 50
- ^ Уайтхед, Альфред Норт ; Рассел, Бертран (1910). Принципы математики. Кембридж: Издательство Кембриджского университета.
{{cite book}}
: CS1 maint: date and year (link) - ^ Уолл, Роберт Э. (1974). Введение в математическую лингвистику . Прентис-Холл.стр. 114.
- ^ Карл Поллард. «Отношения и функции» (PDF) . Университет штата Огайо . Проверено 28 мая 2018 г.Страница 7.
- ^ Кунен, Кеннет (2009). Основы математики . Публикации колледжа. ISBN 978-1-904987-14-7.п. 24
- ^ Фишберн, Питер К. (08 марта 2015 г.). Теория социального выбора. Издательство Принстонского университета. п. 72. ИСБН 978-1-4008-6833-9.
- ^ Робертс, Фред С. (12 марта 2009 г.). Теория измерения: Том 7: С приложениями к принятию решений, коммунальным услугам и социальным наукам . Издательство Кембриджского университета. ISBN 978-0-521-10243-8.стр. 29
- ^ abc Шмидт, Гюнтер ; Стрёлейн, Томас (1993). Отношения и графики: дискретная математика для компьютерных специалистов. Берлин: Шпрингер. ISBN 978-3-642-77970-1.
- ^ Гантер, Бернхард; Вилле, Рудольф (6 декабря 2012 г.). Анализ формальных концепций: математические основы . Springer Science & Business Media. ISBN 978-3-642-59830-2.п. 86
- ^ Йохен Бургхардт (июнь 2018 г.). Простые законы о невыявленных свойствах бинарных отношений (технический отчет). arXiv : 1806.05036 . Бибкод : 2018arXiv180605036B.Лемма 8.2, п.8.