Бинарное отношение

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Соответствие»)
Перейти к навигации Перейти к поиску

Бина́рное (двуме́стное) отноше́ние (соответствие[1][2]) — отношение между двумя множествами и , то есть всякое подмножество декартова произведения этих множеств: [3]. Бинарное отношение на множестве  — любое подмножество , такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.

Связанные определения

[править | править код]
  • Множество всех первых компонент пар из называется областью определения отношения и обозначается как .[4]
  • Множество всех вторых компонент пар из называется областью значения отношения и обозначается как .
[4]
  • Инверсия (обратное отношение)  — это множество и обозначается, как .
  • Композиция[англ.] (суперпозиция) бинарных отношений и  — это множество и обозначается, как .[5][6]

Свойства отношений

[править | править код]

Бинарное отношение на некотором множестве может обладать различными свойствами, например:

  • рефлексивность: ,
  • антирефлексивность (иррефлексивность): ,
  • корефлексивность: ,
  • симметричность: ,
  • антисимметричность: ,
  • асимметричность: ,
  • транзитивность: ,
  • евклидовость: ,
  • полнота (или связность[7]): ,
  • связность[англ.] (или слабая связность[7]): ,
  • трихотомия[англ.]: верно ровно одно из трех утверждений: , или .

Виды отношений

[править | править код]

Виды бинарных отношений

[править | править код]
  • Обратное отношение[уточнить] (отношение, обратное к ) — это двуместное отношение, состоящее из пар элементов , полученных перестановкой пар элементов данного отношения . Обозначается: . Для данного отношения и обратного ему верно равенство: .
  • Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
  • Рефлексивное отношение — двуместное отношение , определённое на некотором множестве и отличающееся тем, что для любого этого множества элемент находится в отношении к самому себе, то есть для любого элемента этого множества имеет место . Примеры рефлексивных отношений: равенство, одновременность, сходство.
  • Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любого элемента этого множества неверно, что оно находится в отношении к самому себе (неверно, что ).
  • Транзитивное отношение — двуместное отношение , определённое на некотором множестве и отличающееся тем, что для любых из и следует (). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
  • Нетранзитивное отношение[уточнить] — двуместное отношение , определённое на некотором множестве и отличающееся тем, что для любых этого множества из и не следует (). Пример нетранзитивного отношения: «x отец y»
  • Симметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых элементов и этого множества из того, что находится к в отношении , следует, что и находится в том же отношении к  — . Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
  • Антисимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из и следует (то есть и выполняются одновременно лишь для равных между собой членов).
  • Асимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из следует . Пример: отношения «больше» (>) и «меньше» (<).
  • Отношение эквивалентности — бинарное отношение между объектами и , являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
  • Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
  • Отношение толерантности — бинарное отношение, удовлетворяющее свойствам рефлексивности и симметричности, но не обязательно являющееся транзитивным. Таким образом, отношение эквивалентности является частным случаем толерантности.
  • Функция одного переменного — бинарное отношение , определённое на некотором множестве, отличающееся тем, что каждому значению отношения соответствует лишь единственное значение . Свойство функциональности отношения записывается в виде аксиомы: .
  • Биекция (взаимно-однозначное отношение) — бинарное отношение , определённое на некотором множестве, отличающееся тем, что в нём каждому значению соответствует единственное значение , и каждому значению соответствует единственное значение .

Операции над отношениями

[править | править код]

Так как отношения, заданные на фиксированной паре множеств и суть подмножества множества , то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных , :

,
,
.

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .

Пусть , . Композицией (или произведением) отношений и называется отношение такое, что:

.

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

Бинарные отношения и называются перестановочными, если . Для любого бинарного отношения , определённого на , имеет место , где символом обозначено равенство, определённое на . Однако равенство не всегда справедливо.

Имеют место следующие тождества:

  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • .

Аналоги последних двух тождеств для пересечения отношений не имеют места.

Примечания

[править | править код]
  1. Цаленко М. Ш. Соответствие // Математическая энциклопедия. — 1985. — Т. 5 (Слу-Я). — С. 77.
  2. Соответствие. Большая российская энциклопедия. Дата обращения: 1 мая 2023. Архивировано 4 февраля 2023 года.
  3. Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.
  4. 1 2 Куликов Л.Я. Глава вторая. Множества и отношения // Алгебра и теория чисел: Учеб. пособие для педагогических институтов. — М.: Высшая школа, 1979. — С. 50. — 559 с.
  5. Ерусалимский Я.М. 4. Композиция бинарных отношений. Булево произведение матриц // Дискретная математика: теория, задачи, приложения. — 3-е издание. — М.: Вузовская книга, 2000. — С. 112. — 280 с. — ISBN 5-89522-034-7.
  6. Новиков Ф.А. 1.5.4. Композиция отношений // Дискретная математика для программистов. — СПб.: Питер, 2000. — С. 34. — 304 с. — ISBN 5-272-00183-4.
  7. 1 2 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)

Литература

[править | править код]
  • Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. — М.: Учебники Высшей школы экономики, 2006. — 300 с.
  • Пухначев Ю. В., Попов Ю. П. Кн. 1: Множества, отображения, отношения, последовательности, ряды, функции, свойства функций, дифференциальное и интегральное исчисление, функции многих переменных // Математика без формул. — Изд. 6-е, испр. — М.: URSS, 2017. — 231 с. — ISBN 978-5-9710-3871-9.