Теорема о разбиении множества отношением эквивалентности на классы

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

Пример. «∥» на множестве всех прямых в пространстве, «=» на множестве ℝ.

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

1) А₁ ... А_n=A;

2) A_i A _j = , i= , j= , j≠i.

Пример 1. Пусть А={1,2,3}. Тогда

1) A₁={1}, A₂={2}, A₃={3} – разбиение А;

2) B₁={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 на классы вида (*).