imported>Leganto Esploristo в 19:30, 8 ноября 2025

2025-11-08T19:30:22Z

Новая страница

{{Значения|Отношение}}
'''Бина́рное''' ('''двуме́стное''') '''отноше́ние''' (соответствие<ref>{{Статья|ссылка=|автор=Цаленко М. Ш.|заглавие=Соответствие|год=1985|язык=|издание=Математическая энциклопедия|тип=|месяц=|число=|том=5 (Слу-Я)|номер=|страницы=77|issn=}}</ref><ref>{{Cite web|url=https://old.bigenc.ru/mathematics/text/3637175|title=Соответствие|author=|website=Большая российская энциклопедия|date=|publisher=|access-date=2023-05-01|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204183325/https://old.bigenc.ru/mathematics/text/3637175|url-status=live}}</ref>) — [[отношение (теория множеств)|отношение]] между двумя множествами <math>A</math> и <math>B</math>, то есть всякое подмножество [[декартово произведение|декартова произведения]] этих множеств: <math>R \subseteq A \times B</math><ref>{{книга
|автор = [[Кострикин, Алексей Иванович|Кострикин А. И.]]
|заглавие = Введение в алгебру. Основы алгебры.
|ссылка = https://archive.org/details/isbn_5020146447|место = {{М}}
|издательство = [[Физматлит]]
|год = 1994
|страницы = [https://archive.org/details/isbn_5020146447/page/n46 47]-48
|страниц = 320
|isbn = 5-02-014644-7
}}</ref>. Бинарное отношение на множестве <math>A</math> — любое подмножество <math>R \subseteq A^2 = A \times A</math>, такие бинарные отношения наиболее часто используются в математике, в частности, таковы [[равенство (математика)|равенство]], [[неравенство]], [[Отношение эквивалентности|эквивалентность]], [[отношение порядка]].

== Связанные определения ==
* Множество всех первых компонент пар из <math>R \subseteq A \times B</math> называется ''областью определения отношения'' <math>R</math> и обозначается как <math>\mathrm{Dom}\,R</math>.<ref name="Куликов">{{книга
|автор = [[Куликов Леонид Яковлевич|Куликов Л. Я.]]
|часть = Глава вторая. Множества и отношения
|заглавие = Алгебра и теория чисел: Учеб. пособие для педагогических институтов
|издание =
|ссылка =
|место = М.
|издательство = [[Высшая школа (издательство)|Высшая школа]]
|год = 1979
|страницы = 50
|страниц = 559
|isbn =
}}</ref>
: <math>\mathrm{Dom}\,R=\{x\mid\exists y((x,\;y)\in R)\}.</math>
* Множество всех вторых компонент пар из <math>R</math> называется ''областью значений отношения'' <math>R</math> и обозначается как <math>\mathrm{Im}\,R</math>.
: <math>\mathrm{Im}\,R=\{y\mid\exists x((x,\;y)\in R)\}.</math><ref name="Куликов"></ref>
* Инверсия ([[обратное отношение]]) <math>R</math> — это множество <math>\{(x,\;y)\mid(y,\;x)\in R\}</math> и обозначается, как <math>R^{-1}</math>.
* {{нп3|Композиция отношений|Композиция||Composition of relations}} (суперпозиция) бинарных отношений <math>R</math> и <math>S</math> — это множество <math>\{(x,\;y)\mid\exists z(xRz\land zSy)\}</math> и обозначается, как <math>R\circ S</math>.<ref>{{книга
|автор = [[Ерусалимский, Яков Михайлович|Ерусалимский Я. М.]]
|часть = 4. Композиция бинарных отношений. Булево произведение матриц
|заглавие = Дискретная математика: теория, задачи, приложения
|издание = 3-е издание
|ссылка =
|место = М.
|издательство = Вузовская книга
|год = 2000
|страницы = 112
|страниц = 280
|isbn = 5-89522-034-7
}}</ref><ref>{{книга
|автор = Новиков Ф. А.
|часть = 1.5.4. Композиция отношений
|заглавие = Дискретная математика для программистов
|издание =
|ссылка =
|место = СПб
|издательство = [[Питер (издательство)|Питер]]
|год = 2000
|страницы = 34
|страниц = 304
|isbn = 5-272-00183-4
}}</ref>

== Свойства отношений ==
Бинарное отношение <math>R</math> на некотором множестве <math>M</math> может обладать различными свойствами, например:
* [[Рефлексивное отношение|рефлексивность]]: <math>\forall x\in M\colon(xRx)</math>,
* [[Антирефлексивное отношение|антирефлексивность]] (иррефлексивность): <math>\forall x\in M\colon \neg(xRx)</math>,
* [[Корефлексивное отношение|корефлексивность]]: <math>\forall x,y\in M\colon (xRy \Rightarrow x=y)</math>,
* [[Симметричное отношение|симметричность]]: <math>\forall x,\;y\in M\colon(xRy\Rightarrow yRx)</math>,
* [[Антисимметричное отношение|антисимметричность]]: <math>\forall x,\;y\in M\colon(xRy\wedge yRx\Rightarrow x=y)</math>,
* [[Асимметричное отношение|асимметричность]]: <math>\forall x,\;y\in M\colon(xRy\Rightarrow\neg(yRx))</math>,
* [[свойство Мура — Смита]]<ref name=Пономарёв/> ([[Отношение иерархичности|иерархичность]]<ref name=Султанбеков7/>): <math>\forall x,\, y \in M\, \exists z \in M\colon (xRz \wedge yRz)</math>,
* [[транзитивность]]: <math>\forall x,\;y,\;z\in M\colon(xRy\wedge yRz\Rightarrow xRz)</math>,
* [[Евклидово отношение|евклидовость]]: <math>\forall x,y,z\in M\colon (xRy \wedge xRz\Rightarrow yRz)</math>,
* [[Полное отношение|полнота]] (или связность<ref name=autogenerated1>Дубов Ю. А., Травкин С. И., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. С. 48.</ref>): <math>\forall x,y\in M\colon (xRy \lor yRx)</math>,
* {{нп3|Связное отношение|связность||Connected relation}} (или слабая связность<ref name=autogenerated1 />): <math>\forall x,y\in M\colon (x\neq y\Rightarrow xRy \lor yRx)</math>,
* {{нп3|Трихотомия (математика)|трихотомия||Trichotomy (mathematics)}}: <math>\forall x,y\in M</math> верно ровно одно из трёх утверждений: <math>xRy</math>, <math>yRx</math> или <math>x=y</math>.

== Виды отношений ==
* Рефлексивное транзитивное отношение называется [[Предпорядок|предпорядком]].
* Рефлексивное транзитивное отношение со свойством Мура — Смита называется [[Направление (отношение порядка)|направлением]].
* Рефлексивное транзитивное симметричное отношение называется [[отношение эквивалентности|отношением эквивалентности]].
* Рефлексивное транзитивное антисимметричное отношение называется [[отношение порядка|отношением (частичного) порядка]].
* Антирефлексивное транзитивное антисимметричное, то есть асимметричное и транзитивное, отношение называется [[отношение порядка|отношением строгого порядка]].
* Полное антисимметричное (для любых <math>x, y</math> выполняется <math>xRy</math> или <math>yRx</math>) транзитивное отношение называется [[отношение линейного порядка|отношением линейного порядка]].
* Антирефлексивное антисимметричное отношение называется [[отношение доминирования|отношением доминирования]].

=== Виды бинарных отношений ===
* '''Обратное отношение'''{{уточнить}} (отношение, обратное к <math>R</math>) — это двуместное отношение, состоящее из пар элементов <math>(y, x)</math>, полученных перестановкой пар элементов <math>(x, y)</math> данного отношения <math>R</math>. Обозначается: <math>R^{-1}</math>. Для данного отношения и обратного ему верно равенство: <math>(R^{-1})^{-1} = R</math>.
* '''Взаимо-обратные отношения''' (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
* [[Рефлексивность|Рефлексивное отношение]] — двуместное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любого <math>x</math> этого множества элемент <math>x</math> находится в отношении <math>R</math> к самому себе, то есть для любого элемента <math>x</math> этого множества имеет место <math>xRx</math>. Примеры рефлексивных отношений: [[равенство (математика)|равенство]], [[одновременность]], [[сходство]].
* [[Антирефлексивное отношение]] (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любого элемента <math>x</math> этого множества неверно, что оно находится в отношении <math>R</math> к самому себе (неверно, что <math>xRx</math>).
* [[Транзитивность|Транзитивное отношение]] — двуместное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x, y, z</math> из <math>xRy</math> и <math>yRz</math> следует <math>xRz</math> (<math>xRy \wedge yRz \to xRz</math>). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
* '''Нетранзитивное отношение'''{{уточнить}} — двуместное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x, y, z</math> этого множества из <math>xRy</math> и <math>yRz</math> не следует <math>xRz</math> (<math>\neg (xRy \wedge yRz \to xRz)</math>). Пример нетранзитивного отношения: «x отец y»
* [[Симметричное отношение]] — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых элементов <math>x</math> и <math>y</math> этого множества из того, что <math>x</math> находится к <math>y</math> в отношении <math>R</math>, следует, что и <math>y</math> находится в том же отношении к <math>x</math> — <math>xRy \to yRx</math>. Примером симметричных отношений могут быть равенство, [[отношение эквивалентности]], [[подобие]], одновременность.
* [[Антисимметричное отношение]] — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x</math> и <math>y</math> из <math>xRy</math> и <math>yRx</math> следует <math>x = y</math> (то есть <math>R</math> и <math>R^{-1}</math> выполняются одновременно лишь для равных между собой членов).
* [[Асимметричное отношение]] — бинарное отношение <math>R</math>, определённое на некотором множестве и отличающееся тем, что для любых <math>x</math> и <math>y</math> из <math>xRy</math> следует <math>\neg yRx</math>. Пример: отношения «больше» (>) и «меньше» (<).
* [[Отношение эквивалентности]] — бинарное отношение <math>R</math> между объектами <math>x</math> и <math>y</math>, являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, [[равномощность]] двух множеств, [[подобие]], [[одновременность]].
* [[Отношение порядка]] — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
* [[Отношение толерантности]] — бинарное отношение, удовлетворяющее свойствам рефлексивности и симметричности, но не обязательно являющееся транзитивным. Таким образом, отношение эквивалентности является частным случаем толерантности.
* [[Функция (математика)|Функция одного переменного]] — бинарное отношение <math>R</math>, определённое на некотором множестве, отличающееся тем, что каждому значению <math>x</math> отношения <math>xRy</math> соответствует лишь единственное значение <math>y</math>. Свойство функциональности отношения <math>R</math> записывается в виде аксиомы: <math>(xRy \wedge xRz) \to (y \equiv z)</math>.
* [[Биекция]] (взаимно-однозначное отношение) — бинарное отношение <math>R</math>, определённое на некотором множестве, отличающееся тем, что в нём каждому значению <math>x</math> соответствует единственное значение <math>y</math>, и каждому значению <math>y</math> соответствует единственное значение <math>x</math>.

== Операции над отношениями ==
Так как отношения, заданные на фиксированной паре множеств <math>A</math> и <math>B</math> суть подмножества множества <math>A \times B</math>, то совокупность всех этих отношений образует [[Булева алгебра|булеву алгебру]] относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных <math>a \in A</math>, <math>b \in B</math>:
: <math>a \,(R \cup S) \, b \Leftrightarrow a \, R \, b \vee a\, S \, b</math>,
: <math>a \,(R \cap S) \, b \Leftrightarrow a \, R \, b \wedge a\, S \, b</math>,
: <math>a \,\overline{R} \, b \Leftrightarrow \neg a \, R \, b</math>.

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

Например, <math>({=}) \cup ({<}) = ({\leqslant})</math>, <math>({=}) \cap ({<}) = \varnothing</math>, то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если <math>R \subseteq A \times B</math>, то обратным отношением называется отношение <math>R^{-1}</math>, определённое на паре <math>B</math>, <math>A</math> и состоящее из тех пар <math>(b, a)</math>, для которых <math>a \, R \, b</math>. Например, <math>({<})^{-1} = ({>})</math>.

Пусть <math>R \subseteq A \times B</math>, <math>S \subseteq B \times C</math>. Композицией (или произведением) отношений <math>R</math> и <math>S</math> называется отношение <math>R \circ S \subseteq A \times C</math> такое, что:
: <math>a \, (R \circ S) \, c \Leftrightarrow \exists b \in B: \, a \, (R) \, b \wedge b \, (S) \, c</math>.

Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: <math>a({<})({<})b \Leftrightarrow a + 1 < b</math>.

Бинарные отношения <math>R</math> и <math>S</math> называются перестановочными, если <math>RS = SR</math>. Для любого бинарного отношения <math>R</math>, определённого на <math>A</math>, имеет место <math>R\mathsf{Id}_A = \mathsf{Id}_AR</math>, где символом <math>\mathsf{Id}_A</math> обозначено равенство, определённое на <math>A</math>. Однако равенство <math>RR^{-1} = \mathsf{Id}</math> не всегда справедливо.

Имеют место следующие тождества:
* <math>R(ST) = (RS)T</math>,
* <math>(RS)^{-1} = S^{-1}R^{-1}</math>,
* <math>\overline{R^{-1}} = {\overline{R}}^{-1}</math>,
* <math>(R \cup S)^{-1} = R^{-1} \cup S^{-1}</math>,
* <math>(R \cap S)^{-1} = R^{-1} \cap S^{-1}</math>,
* <math>R(S \cup T) = RS \cup RT</math>,
* <math>(R \cup S)T = RT \cup ST</math>.

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

== Примечания ==
<references>
{{sfn|''Пономарёв В. И.'' Направление|1982|name=Пономарёв}}
{{sfn|''Султанбеков Ф. Ф.'' От решёток к булевым алгебрам|2012|loc=§ 1. Отношения. Упорядоченные множества. 1.3|с=7|name=Султанбеков7}}
</references>
{{примечания}}

== Литература ==
* {{книга
|автор = [[Мальцев, Анатолий Иванович|Мальцев А. И.]]
|заглавие = Алгебраические системы
|место = {{М.}}
|издательство = [[Наука (издательство)|Наука]]
|год = 1970
|страниц = 392
|тираж = 17500
|ref = Мальцев
}}

* {{книга
|автор = [[Алескеров, Фуад Тагиевич|Алескеров Ф. Т.]], Хабина Э. Л., Шварц Д. А
|заглавие = Бинарные отношения, графы и коллективные решения
|место = {{М.}}
|издательство = Учебники Высшей школы экономики
|год = 2006
|страниц = 300
|тираж =
|ref = Алескеров
}}
* {{МатЭнц|3|автор=Пономарёв В. И|статья=Направление|столбцы=889|ref = ''Пономарёв В. И.'' Направление}}
* {{книга |автор= Пухначев Ю. В., Попов Ю. П.|заглавие= Математика без формул|часть= Кн. 1: Множества, отображения, отношения, последовательности, ряды, функции, свойства функций, дифференциальное и интегральное исчисление, функции многих переменных|издание= Изд. 6-е, испр |место= {{М}}|издательство= URSS|год= 2017|страниц= 231|isbn= 978-5-9710-3871-9}}
* {{книга |автор = {{автор||Султанбеков Ф. Ф}} |заглавие = От решёток к булевым алгебрам: Учебное пособие |язык = ru |место = Казань |издательство = [[Казанский (Приволжский) федеральный университет]] |год = 2012 |страниц как есть = 74 с., ил |ref = ''Султанбеков Ф. Ф.'' От решёток к булевым алгебрам}}

{{ВС}}

[[Категория:Математические отношения]]

Бинарное отношение - История изменений

imported>Leganto Esploristo в 19:30, 8 ноября 2025