Теорема о разбиении множества отношением эквивалентности на классы
Определение 27. Бинарное отношение R на множестве А называется отношением эквивалентности, если оно рефлексивно, симметрично, транзитивно.
Пример. «∥» на множестве всех прямых в пространстве, «=» на множестве ℝ.
Определение 28. Пусть А - непустое множество. Совокупность А1,...,Аn непустых подмножеств множества А называется разбиением множества А на классы (при этом сами множества А1,...,Аn называют классами), если каждый элемент множества А принадлежит одному и только одному из подмножеств А1,...,Аn, т.е.
1) А1 
... Аn=A;
2) Ai 
A j = 
, i= 
, j= , j≠i.
Пример 1. Пусть А={1,2,3}. Тогда
1) A1={1}, A2={2}, A3={3} – разбиение А;
2) B1={123} – разбиение А.
Теорема 2. Пусть R - отношение эквивалентности на множестве А.Тогда множество А разбивается отношением R на классы, которые называются классами эквивалентности, а множество этих классов обозначается A/R (A по R) и называется фактормножеством множества А по отношению эквивалентности R.
Доказательство. Пусть R отношение эквивалентности на А.
Пусть а 
А, aR={x A| (a,x) R}(*)
Отметим, что aR 
A, 
а А.
Покажем что подмножества вида (*) образуют разбиение множества А. Для этого достаточно показать, что они удовлетворяют усл.1 и усл.2 из определения 28.
Усл.1) Покажем что 
=А
а) Покажем что А
Действительно, т.к. а А: аR А 
А
б) Покажем что А
Пусть b A. Покажем, что b . Действительно, т.к. R- отношение эквивалентности R-рефлексивно (b,b) R x=b bR А
Из а) и б) =А
Усл. 2) Пусть aR bR 
. Покажем, что вв этом случае aR=bR.
а) Покажем, что aR bR . Для этого ∀xÎaR покажем, что xÎbR.
Т.к. aR bR 
с аR bR. Тогда выполняются условия(1) c aR
и (2) c bR
Согласно (*), из x aR (a,x) R
Аналогично, из (1) (a,c) R, и поскольку R симметрично, то (c,a) R. Ввиду транзит ивности R, из (c,a) R и (a,x) R (c,x) R
Далее, из (2) (b,c) R. Ввиду транзитивности R, из (b,c) R и (c,x) R (b,x) R x bR
Значит, aR bR.
б) Покажем bR aR
T.к. aR bR= 
c bR aR
(1)c bR и (2) с аR
Пусть x bR (b,x) R
Из (1) (b,c) R (c,x) R (b,x) R
Из (2) (a,c) R (a,x) R x aR
Значит, bR aR
Из а) и б) заключаем, что aR=bR.
Вывод: из Усл.1) и Усл.2) следует, что множество А разбивается отношением R на классы вида (*).