Отношение эквивалентности

Определение. Отношение P называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно (обозначается ~, E, ≡).

Примеры отношений эквивалентности:

а) отношение равенства на любом множестве:

1)x=x;

2) x=y→y=x;

3) x=y; y=z → x=z;

б) отношение подобия на множестве треугольников.

Определение. Пусть Е – отношение эквивалентности на множестве А и х А. Подмножество элементов множества А, эквивалентных x, называется классом эквивалентности элемента х. Обозначается: [x]_E, E(x). Таким образом, E(x)={y | yEx}.

Определение. Множество классов эквивалентности называется фактор -множеством множества А относительно эквивалентности Е, обозначается А/Е: А/Е={E(x)|x A}. Фактор –множество является подмножеством булеана.

Пример 1.2.8 - А – множество студентов в институте. Е – отношение принадлежности к одной группе. [x]_E-студенты одной группы. А/Е– множество студенческих групп института.

Из определений ясно, что

1) любой элемент класса эквивалентности порождает класс эквивалентности, т.е. b [a] → [a]=[b];

2) каждый класс эквивалентности содержит хотя бы один элемент, т.е. а А [a]≠Ø;

3) никакой элемент множества А не может принадлежать двум различным классам: aEb → [a] = [b].

Теорема. Фактор – множество А/Е является разбиением множества А. Обратно, еслиА={A_i} какое-то разбиение множества А, то ему соответствует некоторое отношение эквивалентности Е: xEy x,y A_i для некоторого i.

Таким образом, существует взаимно однозначное соответствие между множеством всех разбиений А и множеством всех отношений эквивалентности на множестве А.

Пример 1.2.9 - А={1,2,3,4}. А={{1},{2,3,4}}={A₁,A₂}- разбиение А.

E={(x;y)|x,y A_i,i=1,2}={(1,1),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,2),(4,3),(4,4)}- отношение эквивалентности, соответствующее данному разбиению.

Пример 1.2.10 - A={1,2,3,4,5,6}, P A²,

P={(1;1);(2;2);(3;3);(4;4);(5;5);(6;6);(1;2);(1;4);(2;1);(2;4);(3;5);(5;3);(4;1);(4;2)}.

Покажем, что данное отношение является отношением

эквивалентности. По его матрице

[P] =

определяем, что P рефлексивно, симметрично, транзитивно (см. выше), следовательно Р есть отношение эквивалентности на множестве А. Построим классы эквивалентности и фактор – множество:

[1]_P={x|(x;1) P}={1,2,4};

[2]_P={x|(x;2) P}={1,2,4};

[3]_P={x|(x;3) P}={3,5};

[4]_P={x|(x;4) P}={1,2,4};

[5]_P={x|(x;5) P}={3,5};

[6]_P={x|(x;6) P}={6}.

Таким образом, имеется только три различных класса эквивалентности [1]=[2]=[4]={1,2,4}, [3]=[5]={3,5}, [6]={6}. Фактор – множество A/Р= ={[1],[3],[6]}={{1,2,4},{3,5},{6}} является разбиением множества А, которое соответствует данному отношению эквивалентности.

Дата добавления: 2014-12-27