Jump to content

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

(Перенаправлено из Сильно связанное отношение )
Транзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Total, Semiconnex Anti-
reflexive
Equivalence relation Green tickY Green tickY
Preorder (Quasiorder) Green tickY
Partial order Green tickY Green tickY
Total preorder Green tickY Green tickY
Total order Green tickY Green tickY Green tickY
Prewellordering Green tickY Green tickY Green tickY
Well-quasi-ordering Green tickY Green tickY
Well-ordering Green tickY Green tickY Green tickY Green tickY
Lattice Green tickY Green tickY Green tickY Green tickY
Join-semilattice Green tickY Green tickY Green tickY
Meet-semilattice Green tickY Green tickY Green tickY
Strict partial order Green tickY Green tickY Green tickY
Strict weak order Green tickY Green tickY Green tickY
Strict total order Green tickY Green tickY Green tickY Green tickY
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Definitions, for all and
Green tickY indicates that the column's property is always true the row's term (at the very left), while indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Green tickY in the "Symmetric" column and in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation be transitive: for all if and then
A term's definition may require additional properties that are not listed in this table.

В математике отношение на множестве называется связным , полным или тотальным, если оно связывает (или «сравнивает») все различные пары элементов множества в том или ином направлении, и сильно связным, если оно связывает все пары элементов множества. элементы. Как описано в разделе терминологии ниже , терминология для этих свойств не является единообразной. Это понятие «тотального» не следует путать с понятием тотального отношения в том смысле, что для всех есть так что (см. серийное отношение ).

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

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

[ редактировать ]

Отношение на съемочной площадке называется подключен, когда для всех или, что то же самое, когда для всех

Отношение к собственности, которое для всех называется сильно связан . [1] [2] [3]

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

[ редактировать ]

Понятие связанного отношения в основном используется в контексте порядков, где оно используется для определения полных или линейных порядков. В этом контексте свойство часто не упоминается конкретно. Скорее, общие заказы определяются как частичные заказы, в которых любые два элемента сопоставимы. [4] [5] Таким образом, Total используется в более общем смысле для отношений, которые связаны или сильно связаны. [6] Однако это понятие «тотального отношения» следует отличать от свойства серийности , которое также называют тотальным. Точно так же связанные отношения иногда называют полный , [7] хотя и это может привести к путанице: универсальное отношение еще называют полным, [8] а слово « полный » имеет несколько других значений в теории порядка .Связные отношения еще называют соединять [9] [10] или говорят, что удовлетворяет трихотомии [11] (хотя более распространенное определение трихотомии более сильное в том, что именно один из трех вариантов должен держаться).

Когда рассматриваемые отношения не являются порядками, связь и сильная связь являются важными разными свойствами. Источники, которые определяют оба, затем используют пары терминов, такие как слабо связан и связан , [12] полный и сильно полный , [13] тотальный и полный , [6] полуконнекс и связь , [14] или связь и строго связано , [15] соответственно, как альтернативные названия понятий связности и сильносвязности, определенных выше.

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

[ редактировать ]

Позволять быть однородным отношением . Следующие действия эквивалентны: [14]

  • сильно связан;
  • ;
  • ;
  • является асимметричным ,

где является универсальным отношением и является обратным отношением

Следующие действия эквивалентны: [14]

  • подключен;
  • ;
  • ;
  • является антисимметричным ,

где является дополнительным отношением тождественного отношения и является обратным отношением

Вводя прогрессии, Рассел ссылался на аксиому связи:

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

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

[ редактировать ]
  • Краевое отношение [примечание 1] турнира графика всегда является связным отношением на множестве ' s вершины.
  • Если сильно связное отношение симметрично , то это универсальное отношение .
  • Отношение является сильно связным тогда и только тогда, когда оно связно и рефлексивно. [доказательство 1]
  • Связное отношение на множестве не может быть антитранзитивным при условии, что имеет не менее 4 элементов. [16] На наборе из трех элементов например, отношение имеет оба свойства.
  • Если является связным отношением на тогда все или все, кроме одного, элементы в пределах находятся [доказательство 2] Аналогичным образом, все или все, кроме одного, элементы находятся в сфере

Примечания

[ редактировать ]
  1. ^ Формально определено если ребро графа выходит из вершины в вершину
Доказательства
  1. ^ Для единственного направления if оба свойства следуют тривиально. — Для направления if : когда затем следует из связности; когда следует из рефлексивности.
  2. ^ Если затем и невозможны, поэтому следует из связности.
  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: дата и год ( ссылка )
  9. ^ Уолл, Роберт Э. (1974). Введение в математическую лингвистику . Прентис-Холл. стр. 114.
  10. ^ Карл Поллард. «Отношения и функции» (PDF) . Университет штата Огайо . Проверено 28 мая 2018 г. Страница 7.
  11. ^ Кунен, Кеннет (2009). Основы математики . Публикации колледжа. ISBN  978-1-904987-14-7 . п. 24
  12. ^ Фишберн, Питер К. (8 марта 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.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: cf58ae2fc3369d5b6b2cc2638f332437__1720929300
URL1:https://arc.ask3.ru/arc/aa/cf/37/cf58ae2fc3369d5b6b2cc2638f332437.html
Заголовок, (Title) документа по адресу, URL1:
Connected relation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)