Какие бинарные отношения обладают свойством эквивалентности

У этого термина существуют и другие значения, см. Отношение.

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

Связанные определения[править | править код]

Свойства отношений[править | править код]

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

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

Виды отношений[править | править код]

Виды бинарных отношений[править | править код]

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

Операции над отношениями[править | править код]

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

,
,
.

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

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

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

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

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

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

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

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

Примечания[править | править код]

↑ Цаленко М. Ш. Соответствие // Математическая энциклопедия. — 1985. — Т. 5 (Слу-Я). — С. 77.
↑ Соответствие. Большая российская энциклопедия.
↑ Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.
↑ 1 2 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)

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

Мальцев, А. И. Алгебраические системы. — М.: Наука, 1970. — 392 с. — 17 500 экз.

Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. — М.: Учебники Высшей школы экономики, 2006. — 300 с.

Пухначев Ю. В., Попов Ю. П. Кн. 1: Множества, отображения, отношения, последовательности, ряды, функции, свойства функций, дифференциальное и интегральное исчисление, функции многих переменных // Математика без формул. — Изд. 6-е, испр. — М.: URSS, 2017. — 231 с. — ISBN 978-5-9710-3871-9.

Источник

Классы эквивалентных элементов и их свойства

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%a%% — некоторый элемент из %%M%%. Рассмотрим множество всех элементов из %%M%%, находящихся в отношении %%R%% к элементу %%a%%.

Классом эквивалентности %%M_a%%

называется множество всех элементов %%M%%, находящихся в отношении %%R%% к элементу %%a%%, то есть множество

$$
M_a = {x in M : x~R~a}.
$$

Пример

Пусть %%M%% — множество всех жителей России и %%R%% — отношение эквивалентности «проживать в одном городе». Найти классы эквивалентных элементов %%M_a%% для %%a in M%%.

Класс элементов, эквивалентных элементу %%a%%, имеет вид:
$$
M_a = {x in M : x text{ проживает в одном городе с человеком } a}
$$

В зависимости от элемента %%a%% получаем несколько классов эквивалентности. Например, класс эквивалентности жителей Москвы или Санкт-Петербурга.

Свойства классов эквивалентности

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%M_a, M_b, dotsc, M_z, dotsc%% — все классы эквивалентности для отношения %%R%%. Тогда эти классы имеют следующие свойства.

Свойство 1

Для любого элемента %%a in M%% выполняется условие
$$
a in M_a
$$

Действительно, по определению, класс %%M_a = {x in M : x~R~a}%%. Тогда для элемента %%a%% должно выполняться условие %%a in M_a leftrightarrow a~R~a%%, которое выполняется в связи с тем, что отношение %%R%% рефлексивно по определению отношения эквивалентности. Следовательно, %%a in M_a%%.

Как следствие этого свойства можно сказать, что всякий класс %%M_a%% является непустым множеством.

Свойство 2

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Классы %%M_a%% и %%M_b%% равны тогда и только тогда, когда элемент %%a%% находится в отношении %%R%% к элементу %%b%%.
$$
M_a = M_b leftrightarrow a~R~b.
$$

Свойство 3

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Тогда классы %%M_a%% и %%M_b%% не имеют общих элементов.
$$
M_a neq M_b rightarrow M_a cap M_b = varnothing
$$

Свойство 4

Объединение всех классов эквивалентности множества %%M%% равно множеству %%M%%.
$$
bigcup_{ain M}{M_a} = M.
$$

Разбиение множества

Совокупностью подмножеств %%M_i%%, где %%i in I%% (множеству индексов), множества %%M%% называется разбиением множества %%M%% если выполняются следующие условия:

Каждое из подмножеств %%M_i%% непусто.
Объединение всех подмножеств %%M_i%% равно множеству %%M%%.
Два различных подмножества %%M_i%% и %%M_j%%, где %%i neq j%%, не имеют общих элементов.

Теорема. Пусть %%R%% — отношение эквивалентности на множестве %%M%%. Тогда совокупность классов эквивалентности множества %%M%% образует его разбиение.

Действительно, если в качестве подмножеств %%M_i%% взять классы эквивалентности %%M_a%%, то все три условия выполняются:

Каждый класс эквивалентности является непустым множеством, согласно свойству 1.
Объединение всех классов эквивалентности есть множество %%M%%, согласно свойству 4.
Два различных класса эквивалентности не имеют общих элементов, согласно свойству 3.

Все условия определения разбиения выполнены. Следовательно классы эквивалентности есть разбиение множества %%M%%.

Примеры

Пусть дано множество %%M = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }%%, тогда разбиением этого множества могут быть следующие совокупности множеств:

%%A_1 = {1, 2, 3}, A_2 = {4, 5, 6, 7}, A_3 = {8, 9, 0 }%%.
%%B_1 = {0, 7, 2}, B_2 = {1, 3, 5 }, B_3 = {4, 6, 8, 9}%%.

Но следующие совокупности не являются разбиением:

%%C_1 = {1, 2, 3}, C_2 = {4, 5, 6, 7}, C_3 = {8, 9, 0, 3}%%.
%%D_1 = {0, 7, 2}, D_2 = {1, 3, 5 }, D_3 = {4, 6, 8, 9}, D_4 = varnothing%%.
%%E_1 = {0, 1, 2}, E_2 = {3, 4, 5}, E_3 = {6, 7, 8}%%.

Совокупность множеств %%C_i%% не является разбиением, т.к. оно не удовлетворяет условию 3 разбиения множеств: множества %%C_1%% и %%C_3%% имеют общий элемент %%3%%.

Совокупность множеств %%D_i%% не является разбиением, т.к. оно не удовлетворяет условию 1 разбиения множеств: множество %%D_4%% пусто.

Совокупность множеств %%E_i%% не является разбиением, т.к. оно не удовлетворяет условию 2 разбиения множеств: объединение множеств %%E_1, E_2%% и %%E_3%% не образует множество %%M%%.

Источник

Разбиение множества

Пусть — произвольное множество. Семейство непустых и попарно не пересекающихся множеств называют разбиением множества , если объединение множеств семейства равно , то есть

Сами множества называют элементами (или членами) разбиения .

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

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

Теорема 1.4. Для любого отношения эквивалентности на множестве множество классов эквивалентности образует разбиение множества . Обратно, любое разбиение множества задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения.

Покажем, что отношение эквивалентности на множестве определяет некоторое разбиение этого множества. Убедимся вначале, что любые два класса эквивалентности по отношению либо не пересекаются, либо совпадают.

Пусть два класса эквивалентности и имеют общий элемент . Тогда и . В силу симметричности отношения имеем , и тогда и . В силу транзитивности отношения получим . Пусть , тогда . Так как , то и, следовательно, .

Обратно, если , то в силу симметричности получим и в силу транзитивности — , то есть . Таким образом, .

Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого справедливо (поскольку ), т.е. каждый элемент множества принадлежит некоторому классу эквивалентности по отношению , то множество всех классов эквивалентности по отношению образует разбиение исходного множества . Таким образом, любое отношение эквивалентности однозначно определяет некоторое разбиение.

Теперь пусть — некоторое разбиение множества . Рассмотрим отношение , такое, что имеет место тогда и только тогда, когда и принадлежат одному и тому же элементу данного разбиения:

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

Фактор-множество

Теорема 1.4 позволяет отождествлять отношения эквивалентности и разбиения: любая эквивалентность определяет единственное разбиение и наоборот.

Множество всех классов эквивалентности по данному отношению эквивалентности на множестве называют фактор-множеством множества по отношению и обозначают .

Пример 1.14. а. На множестве целых чисел определим отношение равенства по модулю , где . Положим , если и только если делится на .

Легко проверяется, что это отношение эквивалентности. Действительно, рефлексивность следует из того, что для любо и делится на ; симметричность — из того, что если делится на , то и делится на . Для доказательства транзитивности заметим, что если делится на и делится на , то и их сумма делится на . Другими словами, для любых целых из и следует , что доказывает транзитивность отношения .

Равенство чисел и по модулю означает, что при делении на эти числа дают одинаковые остатки. Действительно, для каждого имеем , где — остаток от деления на . Следовательно, , то есть . Таким образом, каждое число попадает в тот же класс эквивалентности по отношению , что и остаток от деления его на . Поскольку всего различных остатков может быть ровно , получаем ровно попарно различных классов эквивалентности по данному отношению:

где класс состоит из всех целых чисел, дающих при делении на остаток .

Отметим, что мы установили взаимно однозначное соответствие между фактор-множеством и множеством , состоящим из чисел .

Второе множество дает нам как бы wнаглядный образ” построенного фактор-множества. Нельзя считать, что фактор-множество равно множеству . Нет, указанное фактор-множество состоит из элементов, каждый из которых есть не число, а множество всех целых чисел, при делении на дающих фиксированный остаток. Но каждому такому классу эквивалентности однозначно сопоставляется целое число от 0 до , и, наоборот, каждому целому числу от 0 до соответствует единственный класс эквивалентности по отношению . Заметим, что в математике часто используется прием сопоставления фактор-множеству такого находящегося с ним во взаимно однозначном соответствии множества, которое легко представить и описать.

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

Примечание. Под дробной частью числа понимается число из полуинтервала , такое, что для некоторого целого . Поэтому дробной частью отрицательного числа , где , будет число . Так, Дробной частью будет не , а .

Так как отношение определено через равенство, то легко понять, что все свойства отношения эквивалентности для него выполняются. Каждый класс эквивалентности будет содержать числа с равными дробными частями. Это значит, что каждый класс эквивалентности по данному отношению однозначно определяет некоторое число из полуинтервала и, наоборот, каждому числу однозначно сопоставляется класс эквивалентности, состоящий из всех действительных чисел, дробная часть которых равна . Таким образом, фактор-множество и полуинтервал на числовой прямой находятся во взаимно однозначном соответствии. Этот полуинтервал можно рассматривать как представление определенного выше фактор-множества.

Связь между понятиями эквивалентности и отображения

Установим теперь связь между понятиями эквивалентности и отображения. Заметим, что для любого отношения эквивалентности на множестве можно определить отображение , положив , т.е. сопоставив каждому содержащий его класс эквивалентности. Это отображение сюръективно, так как каждый элемент множества принадлежит некоторому классу эквивалентности, т.е. для каждого справедливо .

Отображение определенное таким образом, называют канонической сюръекцией множества .

Покажем, что любое отображение однозначно определяет некоторое отношение эквивалентности.

Теорема 1.5. Пусть — произвольное отображение. Отношение на множестве , для которого , если и только если , является отношением эквивалентности, причем существует биекция фактор-множества на множество .

Доказательство. Рефлексивность, симметричность и транзитивность отношения следуют непосредственно из его определения, т.е. — эквивалентность.

Зададим отображение фактор-множества в множество следующим образом: . Из способа задания отношения следует, что отображение определено корректно, т.е. каждому классу эквивалентности поставлен в соответствие единственный элемент .

Докажем, что — биекция, для чего убедимся в том, что это инъекция и сюръекция одновременно. Пусть классы эквивалентности и не совпадают. В силу теоремы 1.4 это означает, что они не пересекаются, т.е. не эквивалентно . Из определения отношения следует, что . Таким образом, — инъекция. Если элемент , то найдется такой элемент , что , то есть — сюръекция фактор-множества на множество . Итак, — биекция.

Следовательно, в силу доказанных теорем 1.4 и 1.5 существует связь между тремя понятиями — отображением множества, отношением эквивалентности на множестве и разбиением множества. Но неверно, что существует взаимно однозначное соответствие между отображениями и отношениями эквивалентности (заметим, что теорема 1.5 этого и не утверждает). Два разных отображения могут определять одно и то же разбиение отображаемого множества, тем самым задавая на нем одно и то же отношение эквивалентности. Так, например, любое биективное отображение задает на одно и то же разбиение — тривиальное разбиение на одноэлементные множества.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Источник

Введение понятия «отношение эквивалентности»

Бинарное отношение называется отношением эквивалентности, если отвечает условиям:

Рефлексивность: [latex]a sim a[/latex], [latex]forall a in A[/latex];
Симметричность: [latex]a sim b[/latex], то [latex]b sim a[/latex], [latex]forall a,b in A[/latex];
Транзитивность: [latex]a sim b[/latex] и [latex]b sim c[/latex], то [latex]a sim c[/latex], [latex]forall a,b,c in A[/latex].

Если [latex]a[/latex] связан с [latex]b[/latex], будем писать [latex]a sim b[/latex] и говорить, что [latex]a[/latex] эквивалентен [latex]b[/latex].

Определение

Пусть [latex]rho[/latex] — отношение эквивалентности, тогда подмножество [latex]overline{X}={yin Avert ysim_{rho}x}[/latex] называется классом эквивалентности.

Теорема

Любое отношения эквивалентности на множестве [latex]A[/latex] образует разбиение множества [latex]A[/latex] на классы эквивалентности. Обратно, любое разбиение множества [latex]A[/latex] задает на нем отношение эквивалентности.

Доказательство

Действительно, пусть [latex]K_a[/latex] — группа элементов из [latex]A[/latex] эквивалентных фиксированному элементу [latex]a[/latex]. В силу рефлексивности [latex]a in K_a[/latex].
Покажем, что для любых [latex]K_a[/latex] и [latex]K_b[/latex]: [latex]K_a = K_b[/latex] или не имеют общих элементов.
Докажем методом «от противного».
Пусть [latex]exists c: cin K_a[/latex] и [latex]cin K_b[/latex], т.е. [latex]c sim a[/latex] и [latex]c sim b[/latex], а в силу транзитивности [latex]a sim b[/latex], и [latex]b sim a[/latex]. Тогда [latex]forall x in K_a[/latex], то [latex]x sim a[/latex][latex]Rightarrow[/latex][latex]x sim b[/latex], т.е. [latex]x in K_b[/latex]. Таким образом, две группы, имеющие хотя бы [latex]1[/latex] общий элемент, полностью совпадают.
Мы получили разбиение на классы.
Докажем обратное.
Теперь пусть [latex](B_i)_{iin I}[/latex] — некоторое разбиение множества [latex]A[/latex]. Рассмотрим отношение [latex]rho[/latex], такое, что [latex]x sim_{rho} y[/latex] имеет место тогда и только тогда, когда [latex]x[/latex] и [latex]y[/latex] принадлежат одному и тому же элементу [latex]B_i[/latex] данного разбиения:

[latex]x sim_{rho} y Leftrightarrow (exists i in I)(x in B_i) land (y in B_i).[/latex]

Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых [latex]x[/latex],[latex]y[/latex] и [latex]z[/latex] имеет место [latex]x sim_{rho} y[/latex] и [latex]y sim_{rho} z[/latex], то [latex]x[/latex], [latex]y[/latex] и [latex]z[/latex] в силу определения отношения [latex]rho[/latex] принадлежат одному и тому же элементу [latex]B_i[/latex] разбиения. Следовательно, [latex]x sim_{rho} z[/latex] и отношение [latex]rho[/latex] транзитивно. Таким образом, [latex]rho[/latex] — эквивалентность на [latex]A[/latex].

Пример

Отношение равенства [latex] =_rho [/latex] на множестве действительных чисел является отношением эквивалентности.
[latex]forall a in R[/latex]: [latex]a=a[/latex] [latex]Rightarrow[/latex] [latex] =_rho [/latex] рефлексивно на множестве [latex]R[/latex];
[latex]forall a,b in A[/latex]: [latex]a=b[/latex] и [latex]b=a[/latex] [latex]Rightarrow[/latex] [latex] =_rho [/latex] симметрично на множестве [latex]R[/latex];
[latex]forall a,b,c in A[/latex]: [latex]a=b[/latex] и [latex]b=c[/latex], то [latex]a=c[/latex] [latex]Rightarrow[/latex] [latex] =_rho [/latex] транзитивно на множестве [latex]R[/latex].

Тест поможет определить как хорошо вы усвоили материал.

Источники:

Конспект лекций С.В.Федоровского
Воеводин В.В. Линейная алгебра. М.: Наука, 1994,стр 15-17
Отношения эквивалентности на множестве

Пусть $A$ и $B$ два конечных множества. Декартовым произведением множеств $A$ и $B$ называют множество $Atimes B,$состоящее из всех упорядоченных пар, где $ ain A, bin B. $

Бинарным отношением между элементами множества $A$ и $B$ называется любое подмножество $R$ множества $Atimes B$, то есть $ Rsubset Atimes B.$

По определению, бинарным отношением называется множество пар. Если R — бинарное отношение (т.е. множество пар), то говорят, что параметры $x$ и $y$ связаны бинарным отношением $R$, если пара $langle x,y rangle $ является элементом R, т.е. $langle x,y ranglein R. $

Высказывание: «предметы $x$ и $y$ связаны бинарным отношением $R$» записывают в виде $xRy.$Таким образом, $ xRyleftrightarrowlangle x,yranglein R.$

Если $Rsubset Atimes A $, то говорят, что бинарное отношение определено на множестве $A$.

Примеры бинарных отношений:

на множестве целых чисел $Z$ отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;
на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;
на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».

Областью определения бинарного отношения $R$ называется множество, состоящее из таких $x$, для которых $langle x,y ranglein R $ хотя бы для одного $y$.
Область определения бинарного отношения будем обозначать $ Re R$.
$Re R={ x|exists y(langle x,yranglein R)}$
Областью значений бинарного отношения $R$ называется множество, состоящее из таких $y$, для которых $langle x,y ranglein R $ хотя бы для одного $x$.
Область значений бинарного отношения будем обозначать $Im R$
$Im R={ y|exists x(langle x,yranglein R)}$

Инверсия (обратное отношение) $R$ — это множество ${langle x,yrangle |langle y,xranglein R}$ и обозначается, как ${R}^{-1}.$

Композиция (суперпозиция) бинарных отношений $R$ и $S$ — это множество ${langle x,yrangle |exists zlangle xSzwedge zRyrangle}$ и обозначается, как $Rcirc S$.

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

Рефлексивность: $forall xin M(xRx)$
Антирефлексивность (иррефлексивность): $forall xin Mneg (xRx)$
Корефлексивность: $forall x,yin M(xRyRightarrow x=y)$
Симметричность: $forall x,yin M(xRyRightarrow yRx)$
Антисимметричность: $forall x,yin M(xRywedge yRxRightarrow x=y)$
Асимметричность: $forall x,yin M(xRyRightarrowneg (yRx))$. Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
Транзитивность: $forall x,y,zin M(xRywedge yRzRightarrow xRz)$
Связность: $forall x,yin M(xneq yRightarrow xRylor yRx)$

Рефлексивное транзитивное отношение называется отношением квазипорядка
Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка
Полное антисимметричное (для любых $x, y$ выполняется $xRy$ или $yRx$) транзитивное отношение называется отношением линейного порядка

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

Пересечение. Пересечением двух бинарных отношений ($A$и $B$) является отношение, которое определяется пересечением соответствующих подмножеств. Очевидно, что отношение $Acap B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны как первым, так и вторым отношением ($xAy$ и $xBy$).
Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».
$ xAyLeftrightarrow xgeq y, xByLeftrightarrow xneq y$, тогда $Acap BLeftrightarrow x>y $
Объединение. Объединением двух бинарных отношений ($A$ и $B$) является отношение, которое определяется объединением соответствующих подмножеств. Отношение $Acup B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны хотя бы одним из двух отношений хотя бы одно из отношений ($xAy$ или $xBy$).
Например, объединением отношения «больше» и отношения «равно» является отношение «больше, либо равно».
Включение. Обозначается $Asubseteq B$. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если $Asubseteq B$, то $Aneq B$. Если $Asubseteq B$, то, когда любые два элемента из множества, на котором выполняется отношение $A$, связаны этим отношением, они связаны отношением $B$.

Очевидно, для любого отношения $A varnothingsubseteq Asubseteq U$, где $varnothing$ — пустое, а $U$- полное отношение.

Приведём в пример два графических представления бинарных отношений на множстве $X = {a, b, c, d, e}.$
Первый способ тесно связан с аналитической геометрией. Пусть дана пара взаимно перпендикулярных осей ($Ox$ и $Oy$). На каждой оси нужно отметить точки которые являются элементами множества $X$.
Будем считать, что $a, b, c, d, e$ — координаты точек на горизонтальной и вертикальной осях. Теперь отметим на плоскости точки с координатами $(x, y)$. На рисунке изображена совокупность точек, соответствующих следующему отношению: $R={(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}.$

Следующий способ, который мы рассмотрим, заключается в использовании ориентированных графов. Элементы множества $X$ становятся вершинами графа, а элементы $langle x,yrangle $ отношения $R$ ребрами, которые соединяют первый член $x$ отношения со вторым членом $y$. Граф, соответствующий бинарному отношению $R$, изображен на рисунке.

Задача

Бинарное отношение $R$ задано на множестве $A={1,2,3,4}$, определить его свойства.
$R={(1,1),(1,2),(2,3),(2,2),(2,4)}$

Спойлер

Проверим все свойства отношения:

Рефлексивность
$(forall xin A)langle x,xranglein R$ – это ложное высказывание.
Можно привести контрпример: $x=3$, пара $langle 3,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является рефлексивным.
Антирефлексивность
$(forall xin A)langle x,xranglenotin R$ – это ложное высказывание.
Можно привести контрпример: $x=1$, пара $langle 1,1rangle$ принадлежит множеству $R$. Бинарное отношение не является антирефлексивным.
Корефлексивность
$(forall x,yin A)langle x,yranglenotin R$ – это ложное высказывание.
Можно привести контрпример: $x=1,y=2$, пара $langle 1,2rangle$ принадлежит множеству $R$, но $xneq y$. Бинарное отношение не является антирефлексивным.
Симметричность
$ forall x,yin A (langle x,yranglein R): langle y,xranglein R$ – это ложное высказывание.
Можно привести контрпример, $x=1,y=2$ пара $langle 1,2rangle$ принадлежит множеству $R$, а пара $langle 2,1rangle$ не принадлежит множеству $R$. Бинарное отношение не является симметричным.
Антисимметричность
$forall x,yin A(xRywedge yRxRightarrow x=y)$ – это истинное высказывание
Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.
Асимметричность
Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.
Транзитивность
$forall x,y,zin A(xRywedge yRzRightarrow xRz)$– это ложное высказывание.
Можно привести контр пример, $x=1,y=2,z=3$ пара $langle 1,2rangle$ принадлежит множеству R и пара $langle 2,3rangle$ принадлежит множеству $R$, а пара $langle 1,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является транзитивным.
Связность
$forall x,yin A(xneq yRightarrow xRylor yRx)$ – это ложное высказывание.
Можно привести контрпример, $x=3,y=4$, $3neq 4$ пара $langle 3,4rangle$ не принадлежит множеству $R$ и пара $langle 4,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является связанным.

Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

[свернуть]

Источники:

Галушкина, Марьямов, «Задачи и упражнения по дискретной математике», 2007 г., стр.51
С.В.Федоровский.Конспект лекций по математической логике
Кострикин А.В. , «Введение в алгебру», 1977, стр.134
А.И. Мальцев, «Алгебраические системы», 1970, стр.16-19

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

Вопросы для закрепления пройденного материала

Таблица лучших: Бинарные отношения

максимум из 15 баллов

Место	Имя	Записано	Баллы	Результат
Таблица загружается

Источник