Теорема о разбиении множества отношением эквивалентности на классы
Лекции.Орг

Поиск:


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




Определение 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 на классы вида (*).

 





Дата добавления: 2015-05-06; просмотров: 456 | Нарушение авторских прав | Изречения для студентов


Читайте также:

Рекомендуемый контект:


Поиск на сайте:



© 2015-2020 lektsii.org - Контакты - Последнее добавление

Ген: 0.004 с.