double arrow

Разбиение и эквивалентность

Def. Система (конечная или бесконечная) непустых подмножеств А1, A2,..., Аn... множества А называется разбиением, если:

1) объединение множеств Аi образуют все A (т.е. ÈАi=А);

2) множества Аi попарно не пересекаются (т.е. для любых i¹j справедливо Аi Ç Aj = Æ ).

Теорема о разбиении. Отношение I ÌА´А, будет отношением эквивалентности тогда и только тогда, когда существует разбиение А1, А2,..., Аn,... множества А, что из xIy следует существование такого Аi, что x, yÎАi.

Другими словами, отношение I является отношением эквивалентности в том и только в том случае, когда множество А можно разбить на пересекающиеся классы, в каждом из которых все элементы эквивалентны между собой. Такие классы называют классами эквивалентности или фактор-множествами.

Доказательство. Предположим, что I – отношение эквивалентности, т.е. оно является рефлексивным, симметричным, транзитивным. Наша задача – построить такое разбиение, чтобы между элементами каждого класса выполнялось отношение I. Введем для каждого xÎА множество Вx, состоящее из элементов эквивалентных х, т.е. Вx = {zÎA | xIz }.

Покажем, что два любых множества Bx и By либо совпадают, либо не пересекаются. Пусть zÎBx Ç By. Это означает, что одновременно zIx и zIy. Тогда, в силу симметричности и транзитивности, получаем xIy. Пусть теперь v – произвольный элемент из Bx, т.е. выполнено отношение vIx. Тогда, вследствие транзитивности отношения I и соотношения xIy, получим vIy, т.е. vÎBy. Точно также можно доказать, что если vÎBy, то vÎBx. Это означает, что всякий элемент v из Bx одновременно принадлежит и By и наоборот. Следовательно, два множества Bx и By, имеющие хотя бы один общий элемент, совпадают между собой.

Наконец, в силу того, что множества Bx построены для всех элементов х из A, и, в силу рефлексивности I, элемент х принадлежит своему множеству Bx, объединение Bx включает в себя все множество A. Это означает, что система {Bx} образует разбиение A, т.е. в одну сторону теорема доказана.

Докажем обратное. Пусть имеем разбиение множества А на непересекающиеся классы. Определим отношение I следующим образом: элемент x находится с элементом y в отношении I тогда и только тогда, когда они оба принадлежат одному классу. Тогда это отношение обладает свойством рефлексивности, т.к. сам элемент х принадлежит классу, элементом которого является.

Обладает отношение I и свойством симметричности, т.к. если x и y принадлежат какому-то классу, то это же можно сказать и про y и x.

Наконец, если имеют место отношения xIy и yIz, то это значит, что x, yÎB и y, zÎB, где B – какой-то класс. Таким образом, x, zÎB, т.е. между x и z установлено отношение I. Следовательно, I обладает транзитивностью. Значит, I – отношение эквивалентности. Теорема полностью доказана.


Сейчас читают про: