Бинарное отношение
Бина́рное (двуме́стное) отноше́ние (соответствие[1][2]) — отношение между двумя множествами и , то есть всякое подмножество декартова произведения этих множеств: [3]. Бинарное отношение на множестве — любое подмножество , такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.
Связанные определения
[править | править код]- Множество всех первых компонент пар из называется областью определения отношения и обозначается как .[4]
- Множество всех вторых компонент пар из называется областью значений отношения и обозначается как .
- Инверсия (обратное отношение) — это множество и обозначается, как .
- Композиция[англ.] (суперпозиция) бинарных отношений и — это множество и обозначается, как .[5][6]
Свойства отношений
[править | править код]Бинарное отношение на некотором множестве может обладать различными свойствами, например:
- рефлексивность: ,
- антирефлексивность (иррефлексивность): ,
- корефлексивность: ,
- симметричность: ,
- антисимметричность: ,
- асимметричность: ,
- транзитивность: ,
- евклидовость: ,
- полнота (или связность[7]): ,
- связность[англ.] (или слабая связность[7]): ,
- трихотомия[англ.]: верно ровно одно из трех утверждений: , или .
Виды отношений
[править | править код]- Рефлексивное транзитивное отношение называется отношением квазипорядка.
- Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.
- Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.
- Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.
- Полное антисимметричное (для любых выполняется или ) транзитивное отношение называется отношением линейного порядка.
- Антирефлексивное антисимметричное отношение называется отношением доминирования.
Виды бинарных отношений
[править | править код]- Обратное отношение[уточнить] (отношение, обратное к ) — это двуместное отношение, состоящее из пар элементов , полученных перестановкой пар элементов данного отношения . Обозначается: . Для данного отношения и обратного ему верно равенство: .
- Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
- Рефлексивное отношение — двуместное отношение , определённое на некотором множестве и отличающееся тем, что для любого этого множества элемент находится в отношении к самому себе, то есть для любого элемента этого множества имеет место . Примеры рефлексивных отношений: равенство, одновременность, сходство.
- Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любого элемента этого множества неверно, что оно находится в отношении к самому себе (неверно, что ).
- Транзитивное отношение — двуместное отношение , определённое на некотором множестве и отличающееся тем, что для любых из и следует (). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
- Нетранзитивное отношение[уточнить] — двуместное отношение , определённое на некотором множестве и отличающееся тем, что для любых этого множества из и не следует (). Пример нетранзитивного отношения: «x отец y»
- Симметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых элементов и этого множества из того, что находится к в отношении , следует, что и находится в том же отношении к — . Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
- Антисимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из и следует (то есть и выполняются одновременно лишь для равных между собой членов).
- Асимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из следует . Пример: отношения «больше» (>) и «меньше» (<).
- Отношение эквивалентности — бинарное отношение между объектами и , являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
- Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
- Отношение толерантности — бинарное отношение, удовлетворяющее свойствам рефлексивности и симметричности, но не обязательно являющееся транзитивным. Таким образом, отношение эквивалентности является частным случаем толерантности.
- Функция одного переменного — бинарное отношение , определённое на некотором множестве, отличающееся тем, что каждому значению отношения соответствует лишь единственное значение . Свойство функциональности отношения записывается в виде аксиомы: .
- Биекция (взаимно-однозначное отношение) — бинарное отношение , определённое на некотором множестве, отличающееся тем, что в нём каждому значению соответствует единственное значение , и каждому значению соответствует единственное значение .
Операции над отношениями
[править | править код]Так как отношения, заданные на фиксированной паре множеств и суть подмножества множества , то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных , :
- ,
- ,
- .
Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.
Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.
Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .
Пусть , . Композицией (или произведением) отношений и называется отношение такое, что:
- .
Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: .
Бинарные отношения и называются перестановочными, если . Для любого бинарного отношения , определённого на , имеет место , где символом обозначено равенство, определённое на . Однако равенство не всегда справедливо.
Имеют место следующие тождества:
- ,
- ,
- ,
- ,
- ,
- ,
- .
Аналоги последних двух тождеств для пересечения отношений не имеют места.
Примечания
[править | править код]- ↑ Цаленко М. Ш. Соответствие // Математическая энциклопедия. — 1985. — Т. 5 (Слу-Я). — С. 77.
- ↑ Соответствие . Большая российская энциклопедия. Дата обращения: 1 мая 2023. Архивировано 4 февраля 2023 года.
- ↑ Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.
- ↑ 1 2 Куликов Л.Я. Глава вторая. Множества и отношения // Алгебра и теория чисел: Учеб. пособие для педагогических институтов. — М.: Высшая школа, 1979. — С. 50. — 559 с.
- ↑ Ерусалимский Я.М. 4. Композиция бинарных отношений. Булево произведение матриц // Дискретная математика: теория, задачи, приложения. — 3-е издание. — М.: Вузовская книга, 2000. — С. 112. — 280 с. — ISBN 5-89522-034-7.
- ↑ Новиков Ф.А. 1.5.4. Композиция отношений // Дискретная математика для программистов. — СПб.: Питер, 2000. — С. 34. — 304 с. — ISBN 5-272-00183-4.
- ↑ 1 2 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)
Литература
[править | править код]- Мальцев, А. И. Алгебраические системы. — М.: Наука, 1970. — 392 с. — 17 500 экз.
- Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. — М.: Учебники Высшей школы экономики, 2006. — 300 с.
- Пухначев Ю. В., Попов Ю. П. Кн. 1: Множества, отображения, отношения, последовательности, ряды, функции, свойства функций, дифференциальное и интегральное исчисление, функции многих переменных // Математика без формул. — Изд. 6-е, испр. — М.: URSS, 2017. — 231 с. — ISBN 978-5-9710-3871-9.