Теорема о разбиении множества отношением эквивалентности на классы
Определение 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 на классы вида (*).