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

Отношение эквивалентности - бинарное отношение, являющееся рефлексивным, симметричным и транзитивным.

Примеры
  1. Рассмотренные выше отношения равенства, параллельности прямых.
  2. Отношение подобия треугольников.
  3. Отношение между элементами множества всех многоугольников: "иметь одинаковое число сторон".
  4. Бинарное отношение пропорциональности Р между парами чисел (X,Y) и (Z,T): (X,Y)P(Z,T),
    если X/У = Z/T.
  5. Упоминавшееся выше отношение между целыми числами -"иметь одинаковые остатки от деления на 7". Пусть на множестве М введено некоторое отношение эквивалентности R. Для каждого элемента αМ рассмотрим множество Мα = {β:αRβ } элементов βМ, эквивалентных α. В силу симметричности и транзитивности отношения R , если αRβ , то Мα = Мβ . Если же αRβ , то МαМβ = Ø; иначе, если бы существовал элемент γМαМβ, то выполнялось бы αRγ и βRγ и, в силу транзитивности R, αRβ.

    Таким образом, система различных множеств {Мα} - разбиение множества М (полнота разбиения обусловлена рефлексивностью R ), и тем самым, каждое отношение эквивалентности на множестве порождает разбиение этого множества на классы эквивалентности бинарного отношения R на множестве М - систему подмножеств множества М такую, что

    1. любые два элемента из одного класса эквивалентны;
    2. любые два элемента из разных классов не эквивалентны.

    Верно и обратное. Любое разбиение множества M можно рассматривать как отношение эквивалентности, в котором находятся пары элементов, отнесенные к одному и тому же классу разбиения, и не находятся элементы из разных классов.

    Группировку объектов, применяемую в статистике, законодательстве (например, разделение предприятий на малые, средние и крупные для установления нормативов, единых для всех элементов группы) и в других областях, можно рассматривать как установление эквивалентности. Классы эквивалентности для примеров 2-5.

      (2) - множества подобных друг другу треугольников; в разных классах - треугольники разной формы.
      (3) - счетное множество классов: в n-й класс входят все n -угольники.
      (4) - пары чисел (X,Y) , имеющих одинаковое значение частного X/Y .
      (5) - 7 классов чисел Ni (i = 0,1.....6), имеющих остаток i при делении на 7. Класс Ni содержит числа вида 7n + i (n = 0,+1,+2,...). Например, для i=4 класс N4 - это множество (...-10, -3, 4, 11, 18, 25,...).

    Рассмотрим еще один важный пример. Определим отношение Э между множествами следующим образом: Э(L, М), или короче - L Э М , если существует взаимно однозначное соответствие между множествами L и М . Можно показать, что Э является отношением эквивалентности. Действительно, если для трех множеств L,M,K выполнено L Э М и М Э К, то элементу lL соответствует некоторый элемент mM, а элементу m соответствует элемент kK, тогда LЭK, поскольку можно сопоставить элементу l элемент k. Классы эквивалентности состоят при этом из множеств, имеющих одинаковую мощность (для конечных множеств одинаковое число элементов).

 

Вопросы для самоконтроля

  1. Дайте определение отношения эквивалентности.
    Приведите примеры, свойства.
  2. Укажите свойства классов эквивалентности.
  3. Изучите самостоятельно такие понятия, как: фактормножества, ядро функции.

Практические задания

Tест для самоконтроля