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

Приведем таблицу классификации отношений по их свойствам:

П р и м е р ы: Отношение на множестве R ― нестрогого порядка, ― строгого порядка, х = у ― отношение эквивалентности.

Систему S непустых подмножеств заданного множества A будем называть разбиением множества А, если каждый элемент множества А принадлежит одному и только одному подмножеству из системы S. Подмножество из S называются смежными классами разбиения S.

С каждым разбиением S мы свяжем бинарное отношение φ на множестве А, полагая, по определению, тогда и только тогда, когда x и y принадлежат одному и тому же смежному классу множества А.

Изобразим множество А в виде квадрата, а смежные классы ― в виде прямоугольников, на которые разбивается квадрат. Имеем, что тогда и только тогда, когда x и y принадлежат одному и тому же прямоугольнику. Ясно, что отношение является отношением эквивалентности. Оно называется отношением эквивалентности, отвечающим разбиению S.

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

Однозначное отображение , при котором каждый элемент переходит в содержащий его смежный класс , называется каноническим отображением А на .

Упражнения

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

2. Построить отношение эквивалентности на множестве Z.

3. Доказать, что отношение на множестве Z есть отношение эквивалентности. Построить фактор-множество по этому отношению.

4. Найти фактор-множество , если:

а) , ;

б) «x и y имеют одинаковые остатки при делении на 7», .

5. Доказать, что любые два смежных класса из фактор-множества общих элементов не имеют.