§4. Область бинарного отношения. Операции над бинарными отношениями.

Пусть , то есть- бинарное отношение между элементами множеств А и В. Тогда элементами множестваявляются упорядоченные пары (a,b), где

Определение 1. Множество всех первых элементов пар из называетсяобластью определения бинарного отношения и обозначаетсяDom.

Определение 2. Множество всех вторых элементов пар из называетсяобластью значений бинарного отношения и обозначаетсяIm.

Определение 3. Множество DomImназывается областью бинарного отношения .

Из определений следует, что ,

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

Если , то\

Определим еще обратное или инверсное бинарное отношение для , обозначаемое.

Кроме свойств, приведенных в теореме 1 §2, справедливы также следующие:

Пусть то есть-бинарное отношение между А и В,-бинарное отношение между В и С.

Определение 4. Композицией или произведением бинарных отношений иназывается бинарное отношение между множествами А и С, обозначаемое∙или просто, состоящее из всех пар (a,c), таких что , то есть

Для бинарного отношения на множестве А справедливы следующие свойства

1.ассоциативность.

2.

3.

Обозначим через Это бинарное отношение называется также диагональю или отношением равенства. Тогда :

4.

5.На множестве А существует такое отношение, что

§ 5. Отношение эквивалентности. Теорема о разбиении множества отношением эквивалентности на классы.

Определение 1. Бинарное отношение на множестве А называетсяотношением эквивалентности, если - рефлексивно, симметрично и транзитивно.

Определение 2. Пусть -отношение эквивалентности на множестве А. Множествоназываетсяклассом эквивалентности с представителем а или смежным классом А по . И обозначается а\.

Множество всех классов эквивалентности называется фактор - множеством и обозначается А\.

Определение 3. Пусть Ø.Разбиением множества А на классы называется совокупность его непустых подмножеств множества А, объединение которых совпадает с самим множеством А, а пересечение любых двух различных из них пусто. Другими словами совокупность из S подмножеств множества А является разбиением множества А, если выполняются следующие условия:

1) каждое подмножество из S непусто;

2) объединение всех подмножеств из S совпадает с самим множеством А;

3) пересечение любых двух различных подмножеств из S равно пустому множеству.

Теорема 1. Если на непустом множестве А задано отношение эквивалентности , то А разбивается отношениемна непересекающиеся классы, причем эти классы имеют вид а\, где

Доказательство: Пусть а\=Необходимо показать, что:

1) Ø.

2)

3) из Ø следует, что

1) Действительно, так как - отношение эквивалентности, то- рефлексивно, а, значит,. Следовательно,, то естьØ.

2) Так как . С другой стороны,

Отсюда,

3) Предположим, что Ø. Пусть, например,, тогда, по определению класса эквивалентности,

Покажем, что ПустьТак как в силу симметричности,то в силу транзитивности,. Следовательно,. В силу произвольности выбора х, получаем:

Покажем, что . ПустьтогдаТак както в силу симметричности,. Следовательно, с учетом транзитивности,

Из и

Из (1) и (2) Получили противоречие с предположением, о том, что

Итак, множество А является объединением непустых непересекающихся классов, вида а\. Что и требовалось доказать.

Замечание. Пусть - отношение эквивалентности на непустом множестве А. Тогда по теореме 1 множество А разлагается на непересекающиеся классы эквивалентности по отношениюс представителем а.

Пример: Дано множество: A={1,2,3,4}, на котором задано отношение эквивалентности ={(1,1);(2,2);(3,3);(4,4);(2,4);(4,2)}. Построить разбиение множества А на непересекающиеся классы, соответствующее оношению эквивалентности.

Решение: A₁={1}; A₂={2,4}; A₃={4}. A/={A₁, A₂, A₃}.

Теорема 2. Пусть Если- разбиение непустого множества А на непересекающиеся классы, тоS соответствует отношение эквивалентности на множестве А, причем

Доказательство. Пусть разбиение непустого множества А на непересекающиеся классы. Тогда, 1)Ø,2)Ø

Определим на множестве А бинарное отношение по правилу:Другими словами, элементыa и b находятся в отношении тогда и только тогда, когда они принадлежат одному и тому же классу

1. Так как S - разбиение А, то и так как элементa принадлежит одному классу , то по определению, пара, то есть- рефлексивно на А.

2. Пусть .Тогда, по определению ,a и b принадлежат одному и тому же классу . Следовательно, и элементыb и a принадлежат одному и тому же классу . По определениюимеем:, то есть-симметрично на А.

3. Пусть и . Значит, по определению, а иb принадлежат одному и тому же классу А_t и b и с принадлежат одному и тому же классу А_k. Так как b  А_t и b  А_k, то А_t= А_k, следовательно, а и с принадлежат одному и тому же классу и, значит, (а, с) . Итак,- -транзитивно на А.

Следовательно, - отношение эквивалентности на А.

Так как каждый класс эквивалентности по отношению эквивалентности состоит из тех и только тех элементов из А, которые находятся в отношении, то классы эквивалентности совпадают с классами изS. Но множество всех классов эквивалентности есть Что и требовалось доказать.

Замечание. В силу теорем 1 и 2, между множеством всех отношений эквивалентности на множестве А и множеством всех разбиений множества А на непересекающиеся классы существует взаимно однозначное соответствие. Следовательно, эквиваленций на конечном множестве А существует столько, сколько существует разбиений множества А.

Пример. Подсчитать, сколько отношений эквивалентности существует на множестве А={1,2,3}. Выписать отношения эквивалентности на А и соответствующие им разбиения.

Решение.

1. S₁={{1},{2},{3}}

2. S₂={{1,2},{3}

3. S₃={{1,3},{2}}.

4. S₄={{1},{2,3}}.

5. S₅={{1,2,3}}

Итак, существует лишь 5 разбиений множества А, следовательно, на А существует лишь 5 отношений эквивалентности.