Бинарные и унарные отношения. Решение задач по отношениям между множествами

Определение. Отношение S на множестве А называется отношением эквивалентности, если оно удовлетворяет следующим условиям:
1) аSа для аА (рефлексивность);
2) если аSв, то вSа (симметричность);
3) если аSв и вSс, то аSс (транзитивность).
В дальнейшем отношение эквивалентности будем обозначать значком .
Определение. Пусть задано отношение эквивалентности на А. Множество ХА называется классом эквивалентности для этого отношения, если оно удовлетворяет следующим условиям:
1) для любых хХ и уХ выполняется х  у;
2) если хХ , уА и х  у, то уХ.
Пусть на А задано отношение эквивалентности. Введем следующее обозначение:
[x] = {yA: x  y}.
Нетрудно видеть из определений, что [x] является классом эквивалентности. Его называют классом эквивалентности, порожденным элементом х.
Лемма 1. Для классов эквивалентности [x] и [y] возможны только следующие два случая:
1) [x] = [y];
2) [x][y] = .
Доказательство. Предположим, что [x][y] и а[x][y]. Тогда x  a и y  a. Покажем, что в этом случае один класс эквивалентности содержится в другом, а так как они равнозначны, то будет доказано равенство этих классов.
Пусть в[x]. Тогда х  в, а  х, следовательно в  а. Но а  y, значит в  y и в[y], т.е. [x][y].
Пусть некоторое множество А представимо в виде:
А = _ А , где А_А_ =  , если .
В этом случае говорят, что {A_} задает разбиение А. Из доказанной леммы вытекает, что классы эквивалентности задают разбиение на А. Оказывается, верно и обратное.
Лемма 2. Если {A_} - некоторое разбиение множества А, то отношение S, определяемое следующим условием: аSв: аА_ и вА_, является отношением эквивалентности.
Доказательство. По существу, в доказательстве нуждается лишь третье свойство эквивалентности. Пусть аSв и вSс. Тогда из задания отношения S вытекает следующее: : аА_ и вА_ , а также : вА_ и сА_ . Тогда вА_А_ и из свойств разбиения следует, что А_ = А_ или  = , следовательно, аА_ и сА_ . Это доказывает, что аSс и отношение S является отношением эквивалентности.
Теорема. Пусть S - некоторое отношение эквивалентности на А. Пусть {А_} - разбиение множества А, порожденное этим отношением (лемма 1). Пусть Т - отношение эквивалентности, порожденное разбиением {А_} (лемма 2). Тогда S=T.
Доказательство. Для доказательства напомним, что S и T являются подмножеством АА и их равенство понимается как равенство множеств. Пусть (а,в)S, т.е. аSв. Тогда а и в из одного класса эквивалентности, т.е. : аА_ и вА_. Это означает, что (а,в)T и ST. Аналогично показывается обратное включение.