Отношение эквивалентности
Свойства отношений
1. Рефлексивность: xr x ( например, x = x)
2. Антирефлексивность: ù x r x (например, x < x)
3. Симметричность: x r y Þ y r x (например, x = y Þ y = x)
4. Антисимметричность: x ¹ y , x r y Þù y r x (например, x ¹y ; y £ x Þù y ³ x)
4¢. Асимметричность: xry Þ ùy r x (например, x < y Þù y < x)
5. Связность( полнота ): x ¹ y Þ x r y или y r x (например, для любых двух различных натуральных чисел: либо x < y, либо y < x)
6. Транзитивность: x r y , y r z Þ x r z (например, x = y и у = z Þ y = z)
7.Антитранзитивность: x r y, y r z Þùx r z (например, отношение перпендикулярности прямых).
Отношение, обладающее одновременно свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности.
~ - символ отношения эквивалентности.
[x] - множество элементов, эквивалентных x (класс эквивалентности х).
Свойства отношения эквивалентности:
1. x ~ х
2. Если x ~ y Þ [x] = [y]
Доказательство 1-го свойства: Следует из свойства рефлексивности.
Доказательство 2-го свойства: 1. z Î [x] Þ z ~ x, x ~ y Þ z ~ y Þ z Î [y], т.е. [x] Í [y]
2. z Î [y] Þ z ~ y, x ~ y Þ z ~ x Þ z Î [x], т.е. [y] Í [x].
Следовательно [x] = [y]
P(M) - множество-степень множества М есть множество всех подмножеств множества М.
Пример:
М={1, 2, 3}
P(M)={Æ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
П(M) - покрытиеммножества М будем называть любое подмножество множества Р(М), такое, что объединение входящих в него элементов совпадает с М.
П(M) = {{1,2}, {2}, {2,3}}
так как {1,2} È {2} È {2,3} = {1, 2 ,3}
R(M) - разбиением множества М называется такое покрытие множества М, в котором элементы не пересекаются.
Пример разбиения: R = {{1,2}, {3}}
Свойства :
1. Каждый элемент исходного множества М принадлежит какому-либо из множеств, составляющих разбиение.
2. Каждый элемент исходного множества принадлежит строго одному из множеств, составляющих разбиение.
Теорема: Отношение эквивалентности разбивает множество, на котором оно определено на классы эквивалентности.
Доказательство: 1. Очевидно. х ~ [x]
2. Предположим, что z Î [x] и z Î [y]. Тогда из x ~ y и z ~ y следует x ~ y и по второму свойству отношения эквивалентности [x] = [y].
Четыре определения отношений порядка можно свести в таблицу.
| Свойства
| Рефлексивность
| Антирефлексивность
| Антисимметричность
| Полнота
| Транзитивность
|
Порядки
|
|
нестрогий
(частичный)
| +
|
| +
|
| +
|
совершенный
нестрогий
| +
|
| +
| +
| +
|
строгий
|
| +
| (+)
|
| +
|
совершенный
строгий
|
| +
| (+)
| +
| +
|
| | | | | | | |
То есть, например, нестрогий (частичный) порядок - отношение, обладающее свойствами , рефлексивности, антисимметричности и транзитивности.