Отношение Connex - Connex relation

«Связь» перенаправляется сюда. Для сравнения торговых компаний см. Connexity Inc.

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

В математике однородное отношение называется отношение Connex,^[1] или отношение, имеющее свойство связь, если он каким-то образом связывает все пары элементов. Более формально однородное отношение р на съемочной площадке Икс это Connex, когда для всех Икс и у в Икс,

${\displaystyle x\ R\ y\quad {\text{or}}\quad y\ R\ x.}$

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

${\displaystyle x\ R\ y\quad {\text{or}}\quad y\ R\ x\quad {\text{or}}\quad x=y.}$

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

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

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

Позволять р - однородное отношение.

• р Connex ↔ U ⊆ р ∪ р^Т ↔ р ⊆ р^Т ↔ р асимметричный,

куда U это универсальное отношение и р^Т это обратное отношение из р.^[1]

• р это полусоединение ↔ я  ⊆ р ∪ р^Т ↔ р ⊆ р^Т ∪ я ↔ р антисимметричен,

куда я  это дополнительные отношения из отношение идентичности я и р^Т это обратное отношение из р.^[1]

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

• В край связь^[5] E из турнир график грамм всегда является полусоединенным отношением на множестве грамм's вершин.
• Связь коннекс не может быть симметричный, за исключением универсального отношения.
• Отношение является связным тогда и только тогда, когда оно полусоединено и рефлексивно.^[6]
• Полусоединенное отношение на множестве Икс не может быть антитранзитивный, при условии Икс имеет как минимум 4 элемента.^[7] На трехэлементном наборе {а, б, c}, например Соотношение {(а, б), (б, c), (c, а)} имеет оба свойства.
• Если р является полусоединенным отношением на Икс, то все или все, кроме одного, элементы Икс находятся в классифицировать из р.^[8] Точно так же все или все, кроме одного, элементы Икс находятся в сфере р.

Рекомендации

1. Шмидт и Стрёляйн 1993, п. 12.
2. Брэм ван Хёвельн. «Наборы, отношения, функции» (PDF). Трой, штат Нью-Йорк. Получено 2018-05-28.^{[постоянная мертвая ссылка ]} Стр. 4.
3. Карл Поллард. «Отношения и функции» (PDF). Государственный университет Огайо. Получено 2018-05-28. Стр.7.
4. Феликс Брандт; Маркус Брилл; Пол Харренштейн (2016). «Турнирные решения» (PDF). У Феликса Брандта; Винсент Конитцер; Улле Эндрисс; Жером Ланг; Ариэль Д. Прокачча (ред.). Справочник по вычислительному социальному выбору. Издательство Кембриджского университета. ISBN  978-1-107-06043-2. В архиве (PDF) из оригинала 8 декабря 2017 г.. Получено 22 января 2019. Стр. 59, сноска 1.
5. формально определен vEw если ребро графа ведет из вершины v вершить ш
6. Для только если направление, оба свойства следуют тривиально. - Для если направление: когда Икс≠у, тогда xRy ∨ yRx следует из свойства полусоединения; когда Икс=у, четное xRy следует из рефлексивности.
7. Йохен Бургхардт (июнь 2018 г.). Простые законы о невыразительных свойствах бинарных отношений (Технический отчет). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Лемма 8.2, стр.8.
8. Если Икс, у∈Икс побежал (р), тогда xRy и yRx невозможно, поэтому Икс=у следует из свойства полусоединения.

• Шмидт, Гюнтер; Стрёляйн, Томас (1993). Отношения и графы: дискретная математика для компьютерных ученых. Берлин: Springer-Verlag. ISBN  978-3-642-77970-1.