Отношение эквивалентности. Разбиения множества

Бинарное отношение α, опре­деленное на множестве А, называется отношением экви­валентности на множест­ве А, если α:

- рефлексивно,

- симметрично,

- транзитивно.

Определение 2. Пусть σ — отношение эквивалентности на множест­ве А, и пусть .

Множество всех таких элемен­тов , что х σ а истинно, называют смежным классом множества А по эквивалентности σ, или классом эквива­лентности, и обозначают [ а ] _σ.

Теорема:

Свойство I: .

Свойство II: если a σ b, то [ а ] = [ b ].

Лемма. Любые два смежных класса множества А по эквивалентности σ либо не пересекаются, либо совпа­дают.

Определение 3. Совокупность всех различных смежных классов множества А по эквивалентности σ на­зывается фактор-множеством множества А по эквива­лентности σ и обозначается А /σ.

Определение 4. Разбиением (или расслое­нием) множества А называется система S непустых под­множеств множества А таких, что каждый элемент из А принадлежит одному и только одному подмножеству из системы S.

Теорема. Если σ — отношение эквивалентности на множестве А, то совокупность всех различных смежных классов множества А по эквивалентности σ является раз­биением множества А.

Обратная теорема. Пусть S — разбиение множества А, а σ — бинарное отношение на множестве А такое, что, х σ у истинно тогда и только тогда, когда в S есть подмножество М, для которого , . Тогда σ — отношение эквивалентности на мно­жестве А. Эта эквивалентность σ называется эквивалент­ностью, отвечающей разбиению S.