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

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

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

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

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

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

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

Если , то \

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

Кроме свойств, приведенных в теореме 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 отношений эквивалентности.