Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
"Connexity" перенаправляется сюда. Чтобы узнать о компании-покупателе, см. Connexity Inc.
Бинарные отношения 
Симметричный Антисимметричный Connex Обоснованный Присоединяется Встречается
Отношение эквивалентности ✓ ✗ ✗ ✗ ✗ ✗
Предзаказ (Квазипорядок) ✗ ✗ ✗ ✗ ✗ ✗
Частичный заказ ✗ ✓ ✗ ✗ ✗ ✗
Всего предзаказ ✗ ✗ ✓ ✗ ✗ ✗
Общий заказ ✗ ✓ ✓ ✗ ✗ ✗
Предварительный заказ ✗ ✗ ✓ ✓ ✗ ✗
Хорошо-квазиупорядоченный ✗ ✗ ✗ ✓ ✗ ✗
Хороший порядок ✗ ✓ ✓ ✓ ✗ ✗
Решетка ✗ ✓ ✗ ✗ ✓ ✓
Соединение-полурешетка ✗ ✓ ✗ ✗ ✓ ✗
Встреча-полурешетка ✗ ✓ ✗ ✗ ✗ ✓
« ✓ » указывает, что свойство столбца требуется в определении строки.
Например, определение отношения эквивалентности требует, чтобы оно было симметричным.
Все определения молчаливо требуют транзитивности и рефлексивности .

В математике, однородное отношение называется Connex отношение , [1] или отношение , обладающее свойством связанности , если она относится все пары элементов в некотором роде. Более формально, однородное отношение R на множестве X является связным, когда для всех x и y в X ,

Гомогенное соотношение называется semiconnex отношения , [1] или отношение , обладающее свойством semiconnexity , если же свойство имеет место для всех пар различных элементов х ≠ у , или, что то же самое, когда для всех х и у в X ,

Некоторые авторы определяют только свойство semiconnex и называют его Connex, а не semiconnex . [2] [3] [4]

Свойства коннекса возникли из теории порядка : если частичный порядок также является отношением коннекс, то это полный порядок . Поэтому в более старых источниках говорилось, что отношение коннекс обладает свойством тотальности ; [ необходима цитата ], однако, эта терминология невыгодна, поскольку может привести к путанице, например, с несвязанным понятием целостности права , также известным как сюръективность. Некоторые авторы называют Connex свойства отношения полноты . [5]

Характеристики [ править ]

Пусть R - однородное отношение.

где U представляет собой универсальное отношение и R Т представляет собой обратное соотношение из R . [1]
  • R полусложен ↔ I  ⊆ R ∪ R T ↔ R ⊆ R T ∪ I ↔ R антисимметричен,
где я  это дополнительное отношение по отношению идентичности Я и Р Т представляет собой обратное соотношение из R . [1]

Свойства [ править ]

  • Край соотношение [6] Е из турнира графа G всегда является semiconnex отношения на множестве G ' вершина с.
  • Отношение Connex не может быть симметричным , за исключением универсального отношения.
  • Отношение является связным тогда и только тогда, когда оно полусоединено и рефлексивно. [7]
  • Полусоединенное отношение на множестве X не может быть антитранзитивным , если X имеет не менее 4 элементов. [8] На трехэлементном множестве { a , b , c } , например, отношение {( a , b ), ( b , c ), ( c , a )} имеет оба свойства.
  • Если R является semiconnex отношение на X , то все, или все , кроме одного, элементов X находятся в диапазоне от R . [9] Кроме того , все или все , кроме одного, элементов X находятся в области R .

Ссылки [ править ]

  1. ^ а б в г Schmidt & Ströhlein 1993 , стр. 12.
  2. ^ Брэм ван Хеувельн. «Множества, отношения, функции» (PDF) . Трой, штат Нью-Йорк . Проверено 28 мая 2018 .[ постоянная мертвая ссылка ] Стр. 4.
  3. ^ Карл Поллард. «Отношения и функции» (PDF) . Государственный университет Огайо . Проверено 28 мая 2018 . Стр.7.
  4. ^ Феликс Брандт; Маркус Брилл; Пол Харренштейн (2016). «Турнирные решения» (PDF) . У Феликса Брандта; Винсент Конитцер; Улле Эндрисс; Жером Ланг; Ариэль Д. Прокачча (ред.). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN  978-1-107-06043-2. Архивировано 8 декабря 2017 года (PDF) . Дата обращения 22 января 2019 . Стр. 59, сноска 1.
  5. ^ Jehle, Джеффри; Рени, Филипп (2011). Продвинутая микроэкономическая теория . Эдинбургские ворота, Харлоу, Эссекс, CM20 2JE, Англия: Prentice Hall, Financial Times. п. 5. ISBN 978-0-273-73191-7.CS1 maint: location (link)
  6. ^ определяется формально vEw, если ребро графа ведет из вершины v в вершину w
  7. ^ Для единственного направления, оба свойства следуют тривиально. - Длянаправления if : когда x ≠ y , то xRy ∨ yRx следует из свойства полусоединения; когда x = y , даже xRy следует из рефлексивности.
  8. ↑ Йохен Бургхардт (июнь 2018 г.). Простые законы о невыразительных свойствах бинарных отношений (Технический отчет). arXiv : 1806.05036 . Bibcode : 2018arXiv180605036B . Лемма 8.2, стр.8.
  9. ^ Если x , y ∈ X \ ran ( R ), то xRy и yRx невозможны, поэтому x = y следует из свойства полусложности.
  • Шмидт, Гюнтер ; Стрёляйн, Томас (1993). Отношения и графы: дискретная математика для компьютерных ученых . Берлин: Springer-Verlag. ISBN 978-3-642-77970-1.