Связанное отношение
В математике отношение на множестве называется связным , полным или тотальным, если оно связывает (или «сравнивает») все различные пары элементов множества в том или ином направлении, и сильно связным, если оно связывает все пары элементов множества. элементы. Как описано в разделе терминологии ниже , терминология для этих свойств не является единообразной. Это понятие «тотального» не следует путать с понятием тотального отношения в том смысле, что для всех есть так что (см. серийное отношение ).
Связность занимает видное место в определении общего порядка : полный (или линейный) порядок — это частичный порядок , в котором любые два элемента сравнимы; то есть отношение порядка связно. Аналогично, строгий частичный порядок , который является связным, является строгим полным порядком.Отношение является полным порядком тогда и только тогда, когда оно одновременно является частичным порядком и сильно связным. Отношение является строгим тотальным порядком тогда и только тогда, когда оно является строгим частичным порядком и просто связно. Строгий общий порядок никогда не может быть сильно связан (за исключением пустой области).
Формальное определение
[ редактировать ]Отношение на съемочной площадке называется подключен, когда для всех или, что то же самое, когда для всех
Отношение к собственности, которое для всех называется сильно связан . [1] [2] [3]
Терминология
[ редактировать ]Понятие связанного отношения в основном используется в контексте порядков, где оно используется для определения полных или линейных порядков. В этом контексте свойство часто не упоминается конкретно. Скорее, общие заказы определяются как частичные заказы, в которых любые два элемента сопоставимы. [4] [5] Таким образом, Total используется в более общем смысле для отношений, которые связаны или сильно связаны. [6] Однако это понятие «тотального отношения» следует отличать от свойства серийности , которое также называют тотальным. Точно так же связанные отношения иногда называют полный , [7] хотя и это может привести к путанице: универсальное отношение еще называют полным, [8] а слово « полный » имеет несколько других значений в теории порядка .Связные отношения еще называют соединять [9] [10] или говорят, что удовлетворяет трихотомии [11] (хотя более распространенное определение трихотомии более сильное в том, что именно один из трех вариантов должен держаться).
Когда рассматриваемые отношения не являются порядками, связь и сильная связь являются важными разными свойствами. Источники, которые определяют оба, затем используют пары терминов, такие как слабо связан и связан , [12] полный и сильно полный , [13] тотальный и полный , [6] полуконнекс и связь , [14] или связь и строго связано , [15] соответственно, как альтернативные названия понятий связности и сильносвязности, определенных выше.
Характеристики
[ редактировать ]Позволять быть однородным отношением . Следующие действия эквивалентны: [14]
- сильно связан;
- ;
- ;
- является асимметричным ,
где является универсальным отношением и является обратным отношением
Следующие действия эквивалентны: [14]
- подключен;
- ;
- ;
- является антисимметричным ,
где является дополнительным отношением тождественного отношения и является обратным отношением
Вводя прогрессии, Рассел ссылался на аксиому связи:
Всякий раз, когда ряд первоначально задан транзитивным асимметричным отношением, мы можем выразить связь условием, что любые два члена нашего ряда должны иметь порождающее отношение .
- Бертран Рассел , «Основы математики» , стр. 239.
Характеристики
[ редактировать ]- Краевое отношение [примечание 1] турнира графика всегда является связным отношением на множестве ' s вершины.
- Если сильно связное отношение симметрично , то это универсальное отношение .
- Отношение является сильно связным тогда и только тогда, когда оно связно и рефлексивно. [доказательство 1]
- Связное отношение на множестве не может быть антитранзитивным при условии, что имеет не менее 4 элементов. [16] На наборе из трех элементов например, отношение имеет оба свойства.
- Если является связным отношением на тогда все или все, кроме одного, элементы в пределах находятся [доказательство 2] Аналогичным образом, все или все, кроме одного, элементы находятся в сфере
Примечания
[ редактировать ]- ^ Формально определено если ребро графа выходит из вершины в вершину
- Доказательства
Ссылки
[ редактировать ]- ^ Клэпхэм, Кристофер; Николсон, Джеймс (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: дата и год ( ссылка ) - ^ Уолл, Роберт Э. (1974). Введение в математическую лингвистику . Прентис-Холл. стр. 114.
- ^ Карл Поллард. «Отношения и функции» (PDF) . Университет штата Огайо . Проверено 28 мая 2018 г. Страница 7.
- ^ Кунен, Кеннет (2009). Основы математики . Публикации колледжа. ISBN 978-1-904987-14-7 . п. 24
- ^ Фишберн, Питер К. (8 марта 2015 г.). Теория социального выбора . Издательство Принстонского университета. п. 72. ИСБН 978-1-4008-6833-9 .
- ^ Робертс, Фред С. (12 марта 2009 г.). Теория измерения: Том 7: С приложениями к принятию решений, коммунальным услугам и социальным наукам . Издательство Кембриджского университета. ISBN 978-0-521-10243-8 . стр. 29
- ^ Перейти обратно: а б с Шмидт, Гюнтер ; Стрёлейн, Томас (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.