Однородное отношение

Бинарное отношение между множеством и самим собой

В математике однородное отношение ( также называемое эндоотношением ) на множестве X — это бинарное отношение между X и самим собой, т. е. это подмножество декартова произведения $X \times X.$ ^[1]^[2]^[3] Это обычно формулируется как «отношение на X » ^[4] или «(бинарное) отношение над X ». ^[5]^[6] Примером однородного отношения является отношение родства , где отношение существует между людьми.

Обычные типы эндореляций включают порядки , графы и эквивалентности . Специализированные исследования теории порядка и теории графов разработали понимание эндореляций. Терминология, специфичная для теории графов, используется для описания, при этом обычный (неориентированный) граф предположительно соответствует симметричному отношению , а общая эндореляция соответствует ориентированному графу . Эндореляция R соответствует логической матрице из нулей и единиц, где выражение xRy соответствует ребру между x и y в графе и 1 в квадратной матрице R. Она называется матрицей смежности в терминологии графов .

Частные однородные отношения

Некоторые частные однородные отношения над множеством X (с произвольными элементами $x 1$ , $x 2$ ) таковы:

Пустое отношение
$E = \emptyset$ ;
то есть $x 1 Ex 2$ никогда не выполняется;
Универсальное отношение
$U = X \times X$ ;
то есть $x 1 Ux 2$ выполняется всегда;
Отношение тождества (см. также Функция тождества )
$I = {(x, x) | x \in X$ };
то есть $x 1 Ix 2$ выполняется тогда и только тогда, когда $x 1 = x 2$ .

Пример

Пятнадцать крупных тектонических плит земной коры контактируют друг с другом в однородном отношении. Отношение можно выразить в виде логической матрицы , где 1 обозначает контакт, а 0 — отсутствие контакта. Этот пример выражает симметричное отношение.

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

Некоторые важные свойства, которыми может обладать однородное отношение $R$ над множеством $X$ :

Рефлексивный: для всех $x \in X$ , $xRx$ . Например, ≥ является рефлексивным отношением, а > — нет.
Иррефлексивный (или строгий ): для всех $x \in X$ , а не $xRx$ . Например, > является иррефлексивным отношением, а ≥ — нет.
Корефлексивный: для всех $x, y \in X$ , если $xRy$ , то $x = y$ . ^[7] Например, отношение над целыми числами, в котором каждое нечетное число связано с самим собой, является корефлексивным отношением. Отношение равенства является единственным примером как рефлексивного, так и корефлексивного отношения, и любое корефлексивное отношение является подмножеством отношения тождества.
Левый квазирефлексивный: для всех $x, y \in X$ , если $xRy$ , то $xRx$ .
Правый квазирефлексивный: для всех $x, y \in X$ , если $xRy$ , то $yRy$ .
Квазирефлексивный: для всех $x, y \in X$ , если $xRy$ , то $xRx$ и $yRy$ . Отношение является квазирефлексивным тогда и только тогда, когда оно является как левым, так и правым квазирефлексивным.

Предыдущие 6 альтернатив далеки от исчерпывающего рассмотрения; например, бинарное отношение $xRy,$ определяемое как $y = x 2,$ не является ни иррефлексивным, ни корефлексивным, ни рефлексивным, поскольку содержит пару $(0, 0)$ и $(2, 4)$ , но не $(2, 2)$ соответственно. Последние два факта также исключают (любой вид) квазирефлексивности.

Симметричный: для всех $x, y \in X$ , если $xRy$ , то $yRx$ . Например, «является кровным родственником» является симметричным отношением, поскольку $x$ является кровным родственником $y$ тогда и только тогда, когда $y$ является кровным родственником $x$ .
Антисимметричный: для всех $x, y \in X$ , если $xRy$ и $yRx$ , то $x = y$ . Например, ≥ является антисимметричным отношением; так же как и >, но бессодержательно (условие в определении всегда ложно). ^[8]
Асимметричный: для всех $x, y \in X$ , если $xRy$ , то не $yRx$ . Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно. ^[9] Например, > является асимметричным отношением, но ≥ — нет.

Опять же, предыдущие 3 альтернативы далеки от исчерпывающих; в качестве примера для натуральных чисел можно привести отношение $xRy$ , определяемое соотношением $x > 2,$ которое не является ни симметричным, ни антисимметричным, не говоря уже о том, что оно асимметрично.

Переходный: для всех $x, y, z \in X$ , если $xRy$ и $yRz$ , то $xRz$ . Транзитивное отношение является иррефлексивным тогда и только тогда, когда оно асимметрично. ^[10] Например, «является предком» является транзитивным отношением, тогда как «является родителем» — нет.
Антитранзитивный: для всех $x, y, z \in X$ , если $xRy$ и $yRz$ , то никогда $xRz$ .
Ко-транзитивный: если дополнение R транзитивно. То есть, для всех $x, y, z \in X$ , если $xRz$ , то $xRy$ или $yRz$ . Это используется в псевдопорядках в конструктивной математике.
Квазитранзитивный: для всех $x, y, z \in X$ , если $xRy$ и $yRz$ , но ни $yRx$ , ни $zRy$ , то $xRz$ , но не $zRx$ .
Транзитивность несравнимости: для всех $x, y, z \in X$ , если $x$ и $y$ несравнимы относительно $R$ и если то же самое верно для $y$ и $z$ , то $x$ и $z$ также несравнимы относительно $R.$ Это используется в слабых порядках .

Опять же, предыдущие 5 альтернатив не являются исчерпывающими. Например, отношение $xRy$ if ( $y = 0$ or $y = x +1$ ) не удовлетворяет ни одному из этих свойств. С другой стороны, пустое отношение тривиально удовлетворяет всем из них.

Плотный: для всех $x, y \in X$ таких , что $xRy$ , существует некоторый $z \in X$ такой , что $xRz$ и $zRy$ . Это используется в плотных порядках .
Подключен: для всех $x, y \in X$ , если $x \neq y ,$ то $xRy$ или $yRx$ . Это свойство иногда ^{[ требуется ссылка ]} называют «общим», что отличается от определений «левого/правого общего», приведенных ниже.
Сильно связаны: для всех $x, y \in X$ , $xRy$ или $yRx$ . Это свойство также иногда ^{[ требуется ссылка ]} называют «общим», что отличается от определений «левого/правого общего», приведенных ниже.
трихотомический: для всех $x, y \in X$ выполняется ровно одно из $xRy$ , $yRx$ или $x = y$ . Например, > является трихотомическим отношением на действительных числах, тогда как отношение «делит» на натуральных числах таковым не является. ^[11]
Правое евклидово (или просто евклидово ): для всех $x, y, z \in X$ , если $xRy$ и $xRz$ , то $yRz$ . Например, = является евклидовым отношением , потому что если $x = y$ и $x = z$ , то $y = z$ .
Левый Евклид: для всех $x, y, z \in X$ , если $yRx$ и $zRx,$ то $yRz$ .
Обоснованный: каждое непустое подмножество $S$ из $X$ содержит минимальный элемент относительно $R.$ Обоснованность подразумевает условие нисходящей цепи (то есть не может существовать бесконечной цепи ... $x n R ... Rx 3 Rx 2 Rx 1$ ). Если предполагается аксиома зависимого выбора , оба условия эквивалентны. ^[12]^[13]

Более того, все свойства бинарных отношений в целом также могут быть применимы к однородным отношениям:

Набор-подобный: для всех $x \in X$ — класс всех $y$ , таких что $yRx$ является множеством. (Это имеет смысл только в том случае, если допускаются отношения над собственными классами.)
Левый уникальный: для всех $x, z \in X$ и всех $y \in Y$ , если $xRy$ и $zRy$ , то $x = z$ .
Унивалентный: для всех $x \in X$ и всех $y, z \in Y$ , если $xRy$ и $xRz ,$ то $y = z$ . ^[14]
Всего (также называется лево-всего): для всех $x \in X$ существует $y \in Y$ такой, что $xRy$ . Это свойство отличается от определения связности (также называемой тотальной некоторыми авторами). ^{[ необходима цитата ]}
Сюръективный (также называется право-тотальным): для всех $y \in Y$ существует $x \in X$ такой, что xRy .

Предпорядок — это отношение, которое является рефлексивным и транзитивным. Полный предпорядок , также называемый линейным предпорядком или слабым порядком , — это отношение, которое является рефлексивным, транзитивным и связанным.

Частичный порядок , также называемый порядком , ^{[ нужна ссылка ]} — это отношение, которое является рефлексивным, антисимметричным и транзитивным. Строгий частичный порядок , также называемый строгим порядком , ^{[ нужна ссылка ]} — это отношение, которое является иррефлексивным, антисимметричным и транзитивным. Полный порядок , также называемый линейным порядком , простым порядком или цепью , — это отношение, которое является рефлексивным, антисимметричным, транзитивным и связанным. ^[15] Строгий полный порядок , также называемый строгим линейным порядком , строгим простым порядком или строгой цепью , — это отношение, которое является иррефлексивным, антисимметричным, транзитивным и связанным.

Отношение частичной эквивалентности — это отношение, которое является симметричным и транзитивным. Отношение эквивалентности — это отношение, которое является рефлексивным, симметричным и транзитивным. Это также отношение, которое является симметричным, транзитивным и полным, поскольку эти свойства подразумевают рефлексивность.

Последствия и конфликты между свойствами однородных бинарных отношений
Импликации (синие) и конфликты (красные) между свойствами (желтые) однородных бинарных отношений. Например, каждое асимметричное отношение является иррефлексивным ( " ASym ⇒ Irrefl " ), и никакое отношение на непустом множестве не может быть одновременно иррефлексивным и рефлексивным ( " Irrefl # Refl " ). Исключение красных ребер приводит к диаграмме Хассе .

Операции

Если R — однородное отношение над множеством X , то каждое из следующих отношений является однородным отношением над X :

Рефлексивное закрытие , R ⁼: Определяется как $R = = {(x, x) | x \in X} \cup R$ или наименьшее рефлексивное отношение над X , содержащее R. Можно доказать, что оно равно пересечению всех рефлексивных отношений, содержащих R.
Рефлексивная редукция , R ^≠: Определяется как $R ≠ = R \ {( x , x ) | x ∈ X$ } или наибольшее иррефлексивное отношение над X , содержащееся в R .
Транзитивное замыкание , R ⁺: Определяется как наименьшее транзитивное отношение над X, содержащее R. Можно видеть, что оно равно пересечению всех транзитивных отношений, содержащих R.
Рефлексивное транзитивное замыкание , R *: Определяется как $R * = (R +) =$ , наименьший предварительный порядок, содержащий R .
Рефлексивное транзитивное симметричное замыкание , R ^≡: Определяется как наименьшее отношение эквивалентности над X , содержащее R.

Все операции, определенные в разделе Бинарные отношения § Операции, также применяются к однородным отношениям.

Однородные отношения по свойству
	Рефлексивность	Симметрия	Транзитивность	Связанность	Символ	Пример
Направленный граф					→
Неориентированный граф		Симметричный
Зависимость	Рефлексивный	Симметричный
Турнир	Нерефлексивный	Асимметричный				Порядок иерархии
Предварительный заказ	Рефлексивный		Переходный		≤	Предпочтение
Всего предзаказов	Рефлексивный		Переходный	Подключен	≤
Частичный заказ	Рефлексивный	Антисимметричный	Переходный		≤	Подмножество
Строгий частичный порядок	Нерефлексивный	Асимметричный	Переходный		<	Строгое подмножество
Общий заказ	Рефлексивный	Антисимметричный	Переходный	Подключен	≤	В алфавитном порядке
Строгий общий порядок	Нерефлексивный	Асимметричный	Переходный	Подключен	<	Строгий алфавитный порядок
Отношение частичной эквивалентности		Симметричный	Переходный
Отношение эквивалентности	Рефлексивный	Симметричный	Переходный		~, ≡	Равенство

Перечисление

Множество всех однородных отношений над множеством X — это множество $2$ $X$ $\times$ $X$ , которое является булевой алгеброй , дополненной инволюцией отображения отношения в его обратное отношение . Рассматривая композицию отношений как бинарную операцию над , она образует моноид с инволюцией , где единичным элементом является единичное отношение. ^[16] ${\mathcal {B}}(X)$ ${\mathcal {B}}(X)$

Число различных однородных отношений на множестве из n элементов равно $2 n 2$ (последовательность A002416 в OEIS ):

Число n -элементных бинарных отношений разных типов
Элементы	Любой	Переходный	Рефлексивный	Симметричный	Предварительный заказ	Частичный заказ	Всего предзаказов	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
н	2 ^{н ²}		2 ^{n ( n −1)}	2 ^{н ( н +1)/2}			∑^н _{к =0} к ! С ( н , к )	н !	∑^н _{к =0} С ( н , к )
ОЭИС	А002416	А006905	А053763	А006125	А000798	А001035	А000670	А000142	А000110

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

Примечания:

Число нерефлексивных отношений такое же, как и число рефлексивных отношений.
Число строгих частичных порядков (иррефлексивных транзитивных отношений) такое же, как и число частичных порядков.
Количество строго слабых заказов равно общему количеству предварительных заказов.
Общее количество заказов — это частичные заказы, которые также являются общими предварительными заказами. Количество предварительных заказов, которые не являются ни частичным заказом, ни общим предварительным заказом, равно, таким образом, количеству предварительных заказов, минус количество частичных заказов, минус количество общих предварительных заказов, плюс количество общих заказов: 0, 0, 0, 3 и 85 соответственно.
Число отношений эквивалентности равно числу разбиений , которое является числом Белла .

Однородные отношения можно сгруппировать в пары (отношение, дополнение ), за исключением того, что при $n = 0$ отношение является своим собственным дополнением. Несимметричные отношения можно сгруппировать в четверки (отношение, дополнение, обратное, обратное дополнение).

Примеры

Отношения порядка , включая строгие приказы :
- Больше чем
- Больше или равно
- Меньше, чем
- Меньше или равно
- Делит (поровну)
- Подмножество
Отношения эквивалентности :
- Равенство
- Параллельно (для аффинных пространств )
- Равнозначность или «находится в биекции с»
- Изоморфный
- Равнополные отрезки линии
Отношение толерантности , рефлексивное и симметричное отношение:
- Отношение зависимости , отношение конечной толерантности
- Отношение независимости , дополнение некоторого отношения зависимости
Родственные отношения

Обобщения

Бинарное отношение в общем случае не обязательно должно быть однородным, оно определяется как подмножество R ⊆ X × Y для произвольных множеств X и Y.
Финитное отношение — это подмножество R ⊆ X ₁ × ... × X _n для некоторого натурального числа n и произвольных множеств X ₁ , ..., X _n , его также называют n -арным отношением.

Ссылки

^ Майкл Винтер (2007). Категории Гогена: Категориальный подход к L-нечетким отношениям . Springer. стр. x– xi. ISBN 978-1-4020-6164-6.
^ ME Müller (2012). Relational Knowledge Discovery . Cambridge University Press. стр. 22. ISBN 978-0-521-19021-3.
^ Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. стр. 496. ISBN 978-3-540-67995-0.
^ Мордесон, Джон Н.; Наир, Премчанд С. (8 ноября 2012 г.). Нечеткая математика: введение для инженеров и ученых. Physica. стр. 2. ISBN 978-3-7908-1808-6.
^ Танаев, В.; Гордон, В.; Шафранский, Яков М. (6 декабря 2012 г.). Теория расписания. Одноступенчатые системы. Springer Science & Business Media. стр. 41. ISBN 978-94-011-1190-4.
^ Мейер, Бертран (29 июня 2009 г.). Touch of Class: Learning to Program Good with Objects and Contracts. Springer Science & Business Media. стр. 509. ISBN 978-3-540-92145-5.
^ Фонсека де Оливейра, JN, и Перейра Кунья Родригес, CDJ (2004). Транспонирование отношений: от функций Maybe к хэш-таблицам. В «Математике построения программ» (с. 337).
^ Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2006), Переход к высшей математике (6-е изд.), Brooks/Cole, стр. 160, ISBN 0-534-39900-2
^ Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, стр. 158.
^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF) . Прага: School of Mathematics – Physics Karlov University. стр. 1. Архивировано из оригинала (PDF) 2013-11-02.Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
^ Поскольку ни 5 не делит 3, ни 3 не делит 5, ни 3=5.
^ "Условие обоснованности". ProofWiki . Архивировано из оригинала 20 февраля 2019 . Получено 20 февраля 2019 .
^ Фрейсс, Р. (15 декабря 2000 г.). Теория отношений, том 145 - 1-е издание (1-е изд.). Elsevier. стр. 46. ISBN 9780444505422. Получено 20 февраля 2019 г. .
^ Гюнтер Шмидт и Томас Штролейн (2012)[1987] Отношения и графики , стр. 54, в Google Books
^ Джозеф Г. Розенштейн, Линейные упорядочения , Academic Press, 1982, ISBN 0-12-597680-1 , стр. 4
^ Шмидт, Гюнтер; Штрёляйн, Томас (1993). "Однородные отношения". Отношения и графы: Дискретная математика для компьютерных ученых . Берлин, Гейдельберг: Springer. стр. 14. doi :10.1007/978-3-642-77968-8_2. ISBN 978-3-642-77968-8.

[Winter2007-1] Майкл Винтер (2007). Категории Гогена: Категориальный подход к L-нечетким отношениям . Springer. стр. x– xi. ISBN 978-1-4020-6164-6.

[Müller2012-2] ME Müller (2012). Relational Knowledge Discovery . Cambridge University Press. стр. 22. ISBN 978-0-521-19021-3.

[PahlDamrath2001-p496-3] Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. стр. 496. ISBN 978-3-540-67995-0.

[4] Мордесон, Джон Н.; Наир, Премчанд С. (8 ноября 2012 г.). Нечеткая математика: введение для инженеров и ученых. Physica. стр. 2. ISBN 978-3-7908-1808-6.

[5] Танаев, В.; Гордон, В.; Шафранский, Яков М. (6 декабря 2012 г.). Теория расписания. Одноступенчатые системы. Springer Science & Business Media. стр. 41. ISBN 978-94-011-1190-4.

[6] Мейер, Бертран (29 июня 2009 г.). Touch of Class: Learning to Program Good with Objects and Contracts. Springer Science & Business Media. стр. 509. ISBN 978-3-540-92145-5.

[7] Фонсека де Оливейра, JN, и Перейра Кунья Родригес, CDJ (2004). Транспонирование отношений: от функций Maybe к хэш-таблицам. В «Математике построения программ» (с. 337).

[8] Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2006), Переход к высшей математике (6-е изд.), Brooks/Cole, стр. 160, ISBN 0-534-39900-2

[9] Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, стр. 158.

[10] Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF) . Прага: School of Mathematics – Physics Karlov University. стр. 1. Архивировано из оригинала (PDF) 2013-11-02.Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».

[11] Поскольку ни 5 не делит 3, ни 3 не делит 5, ни 3=5.

[12] "Условие обоснованности". ProofWiki . Архивировано из оригинала 20 февраля 2019 . Получено 20 февраля 2019 .

[13] Фрейсс, Р. (15 декабря 2000 г.). Теория отношений, том 145 - 1-е издание (1-е изд.). Elsevier. стр. 46. ISBN 9780444505422. Получено 20 февраля 2019 г. .

[14] Гюнтер Шмидт и Томас Штролейн (2012)[1987] Отношения и графики , стр. 54, в Google Books

[15] Джозеф Г. Розенштейн, Линейные упорядочения , Academic Press, 1982, ISBN 0-12-597680-1 , стр. 4

[16] Шмидт, Гюнтер; Штрёляйн, Томас (1993). "Однородные отношения". Отношения и графы: Дискретная математика для компьютерных ученых . Берлин, Гейдельберг: Springer. стр. 14. doi :10.1007/978-3-642-77968-8_2. ISBN 978-3-642-77968-8.