Книги и конспекты / Шпоры / 8
.pdf
8.Разбиение и отношение эквивалентности. Теорема о классах эквивалентности. Классы эквивалентности. Факторизация множества.
Определение эквивалентности. -бинарное отношение называется отношением эквивалентности, если оно обладает свойствами:
1) |
рефлексивности: |
x x , |
x Si x S j |
|
|
|
2) |
симметричности: |
x y y x , |
x Si , y Si |
y Si , x Si |
||
3) |
транзитивности: x y, y z x z |
|
|
|
||
x S |
P (x) {z S : x z} |
(1) – (задание эквивалентности) x P(x) , |
P (x) S |
|||
|
|
|
|
|
|
x |
P (x) P ( y) = ø
Разбиение множества. Рассмотрим множество S, разобьѐм его на части:
Sk : Si S j |
ø, для i j ; : Si |
S |
|
i |
|
-разбиение множества S
{Sk }
Классом эквивалентности C(a) элемента a называется подмножество элементов, эквивалентных a. Из вышеприведѐнного определения немедленно следует, что, если b C(a) , то C(a)=C(b).
Теорема о классах эквивалентности: P (x) и P ( y) вида (1) для различных точек либо не пересекаются, либо совпадают.
Доказательство.
Существует t P(x), t P( y)
x t, y t,t y x y
Для любого t S,t x,t P(x)
t x, x y t y t P( y)
P(x) P( y)
t y,t P( y) t y, y x t x,t P(x)
P( y) P(x) P( y) P(x) .
Определение факторизации множества. Разбиение множества S на классы
эквивалентности называется факторизацией S
Пример:
x, y S, |
x y, |
x y mk |
|
1) x x |
x x m 0 |
|
|
2) x y mk, |
y x mk |
x y y x |
|
3) x y mk |
x z ml |
x z m(k r) ml |
|
y z mr |
|
|
|
Рассмотрим :
P (0) : 0 y km y km
P (1) :1 y r m y 1 r m
…………………………….
P (m 1) y (m 1) lm