Отношение эквивалентности и фактор-множество

1.

Отношение эквивалентности
и фактор-множество

2.

Определение.
Бинарное отношение на множестве A
называется отношением эквивалентности
(или просто эквивалентностью), если оно
рефлексивно, симметрично и транзитивно.
Для
обозначения
эквивалентности
используется инфиксная запись с помощью
символа :
вместо
( a, b)
пишут
a b( )
или просто
a b.

3.

(a)
Cрезы
называются
классами
эквивалентности по отношению
и
сокращенно обозначаются символом [a] .
Множество
всех
таких
классов
{[a] : a A}
эквивалентности
называется
фактор-множеством множества A по
эквивалентности и обозначается символом
A/ .

4.

Определение. Ядром отображения : A B
называется бинарное отношение ker
на
множестве A, которое определяется по формуле
ker {(a, b) A2 : (a) (b)} .
Определение. Каноническим отображением
эквивалентности называется отображение nat
множества A на фактор множество A/ , которое
каждому элементу a A ставит в соответствие
содержащий его класс эквивалентности [a] .
Легко видеть, что ker nat = .

5.

Определение. Подмножество T A называется
полной системой представителей классов
эквивалентности на множестве A, если:
1) (T ) A ,
2) из условия t1 t 2 ( ) следует t1 t 2 .
Классы эквивалентности [t ] A / могут быть
отождествлены со своими представителями t и
фактор-множество A/ может быть отождествлено
с множеством T.

6.

Примеры.
1. Пусть A – множество шаров в коробке, состоящее из 7
красных, 5 синих и 8 зеленых шаров. Определим на множестве A
отношение по формуле: для любых шаров a,b A условие a b( )
означает, что шары a,b одного цвета.
Отношение рефлексивно, симметрично и транзитивно, т.е.
является эквивалентностью на множестве A. Любой красный шар
aк A определяет класс эквивалентности [ a к ] , состоящий из 7
красных шаров, любой синий шар aс A определяет класс
эквивалентности [aс ] , состоящий из 5 синих шаров и любой
зеленый шар a з A определяет класс эквивалентности [a з ] ,
состоящий из 8 зеленых шаров. Значит, фактор-множество A/
состоит из трех элементов [aк ] , [aс ] , [a з ] и может быть
отождествлено с полной системой представителей классов
эквивалентности на множестве A, состоящей из трех
разноцветных шаров {aк , aс , a з } , или просто с множеством трех
цветов {красный, синий, зеленый}.

7.

2. Пусть A=Z – множество целых чисел. Определим на
множестве Z отношение по формуле: для любых a,b Z
условие a b( ) означает, что числа a,b имеют одинаковые
остатки при делении на число 3, т.е. разность a b кратна
числу 3.
Отношение рефлексивно, симметрично и транзитивно,
т.е. является эквивалентностью на множестве Z. Ясно, что
число 0 определяет класс эквивалентности [0] {0, 3, 6,...},
число
1
–
класс
эквивалентности
число
2
–
класс
[1] {1,1 3,1 6,...} {..., 5, 2,1,4,7,...},
эквивалентности [2] {2,2 3,2 6,...} {..., 4, 1,2,5,8,...}. Так как
этими множествами исчерпываются все классы данной
эквивалентности , то фактор-множество Z/ состоит из трех
элементов [0] , [1] , [2] и может быть отождествлено с полной
системой представителей классов эквивалентности на
множестве Z - трехэлементным множеством {0,1,2} .

8.

Задача
представления данных

9.

Постановка задачи:
Имеется множество объектов A , на котором
задано отношение эквивалентности .
Требуется
1) найти полную систему представителей
классов T A эквивалентности на
множестве A , т.е. в каждом классе
эквивалентных
объектов
выбрать
единственного представителя этого класса,
2) найти
алгоритм,
по
которому
для
элементов множества A вычисляются их
представители.

10.

Примеры задач представления данных:
1) Представление рациональных чисел
2) Представление векторов.
3) Представление целых чисел.
4) Представление многочленов с одной
переменной и с несколькими переменными.
5) Представление
формул
исчисления
высказываний.
6) Представление формул булевой алгебры.
7) Криптографическая схема на основе задачи
представления данных

11.

Домашнее задание
Задание 1. Доказать, что каждое из следующих отношений
является отношением эквивалентности, найти классы
эквивалентности и указать полную систему представителей.
1. На множестве N N задано бинарное отношение так, что
условие ( a, b , (c, d )) равносильно условию a d b c.
2. На множестве R задано бинарное отношение так, что
условие (a, b) равносильно условию a b Z .
3. На множестве Q задано бинарное отношение так, что
условие (a, b) равносильно равенству a 2 k b для некоторого k Z .
4. На множестве N задано бинарное отношение по формуле:
условие (a, b) означает, что последняя цифра в десятичной записи
числа a совпадает с последней цифрой в десятичной записи числа b .
5. На множестве R задано бинарное отношение по формуле:
условие (a, b) означает, что a a b b .
2
2