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

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

Определение 28. Пусть А - непустое множество. Совокупность А₁,...,А_n,... непустых подмножеств множества А называется разбиением множества А на классы (при этом сами множества называют классами), если каждый элемент множества А принадлежит одному и только одному из подмножеств А₁,...,А_n,...,

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

Доказательство. Пусть R отношение эквивалентности на А. Пусть аА, ={xA| (a,x)R} Отметим, что A, аА. Покажем что подмножество образует разбиение множества А на непересекающиеся классы.

1) Покажем что =А.

а) Покажем что А. Действительно, т.к. аА A , то А.

б) Покажем что А. Пусть bA. Покажем, что b. Действительно, т.к. R - отношение эквивалентности, то R-рефлексивно. Значит, (b,b)R и b. Следовательно, А.

Из а) и б) следует, что =А.

2) Покажем, что любые два класса в рассматриваемом покрытии либо не пересекаются, либо совпадают. Пусть . Покажем =.

а) Покажем, что . Т.к. , то существует с. Пусть x. Тогда (a,x)R, (a,c)R и (b,c)R. Так как R симметрично, то (c,a)R и, значит, в силу транзитивности R, получим (c,x)R. Из (b,c)R и (c,x)R следует, что (b,x)R. Следовательно, xи .

б) Аналогично, нетрудно показать, что .

Таким образом, =.

Теорема доказана.

Определение 29. Пусть R - отношение эквивалентности на непустом множестве А. Множество всех классов эквивалентности называется фактормножеством множества А по отношению к R и обозначается , то есть .

Теорема 3. Каждому разбиению непустого множества на непересекающиеся классы соответствует некоторое отношение эквивалентности на этом множестве.