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

Материал из Викиконспекты
Версия от 23:53, 16 ноября 2011; Nook (обсуждение | вклад) (Новая страница: «== Определение == {{Определение |definition = Бинарное отношение <tex>R</tex> на множестве <tex>X</tex> наз...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение

Определение:
Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется отношением эквивалентности, если оно обладает следующими свойствами:

Отношение эквивалентности обозначают символом [math]\thicksim[/math]. Запись вида [math]a \thicksim b[/math] читают как "[math]a[/math] эквивалентно [math]b[/math]"

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

  • Отношение равенства([math]=[/math]) является тривиальным примером отношения эквивалентности на любом множестве.
  • Отношение равенства по модулю [math]k[/math]: [math]a \equiv b (mod~k)[/math].
  • Отношение параллельности прямых на плоскости.
  • Отношение подобия фигур на плоскости.
  • Отношение равносильности на множестве уравнений.
  • Отношение связности вершин в графе.
  • Отношение быть одного роста на множестве людей.

Следующие отношения не являются отношениями эквивалентности:

  • Отношения порядка, т.к. они не являются симметричными.
  • Отношение быть знакомым на множестве людей, т.к. оно не транзитивное.

Классы эквивалентности

Определение:
Система непустых подмножеств [math]\{M_1, M_2, ..., M_n\}[/math] множества [math]M[/math] называется разбиением данного множества, если:
  • [math]M = M_1 \cup M_2 \cup ... \cup M_n[/math].
  • [math]M_i \cap M_j = \varnothing[/math] при [math]i \neq j[/math].
Множества [math]M_1, M_2, ..., M_n[/math] называются классами данного разбиения.

Примерами разбиений являются:

  • Разбиение многоугольников на группы по числу вершин.
  • Разбиение треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные).
  • Разбиение учащихся школы по классам.
Теорема:
Если на множестве M задано отношение эквивалентности [math]\thicksim[/math], то оно порождает разбиение этого множества на классы эквивалентности такое, что:
  • любые два элемента одного класса находятся в отношении [math]\thicksim[/math]
  • любые два элементы разных классов не находятся в отношении [math]\thicksim[/math]

Семейство всех классов эквивалентности множества образует множество, называемое фактор-множеством, или факторизацией множества [math]M[/math] по отношению [math]\thicksim[/math], и обозначаемое [math]M/^{\thicksim}[/math].

Ссылки