Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

Определение 2.10. Бинарное отношение в на множестве А называется отношением, эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Если 0 - отношение эквивалентности на множестве А, то классом эквивалентности, порожденным элементом а, называется подмножество множества А, состоящее из тех элементов 6е А, для которых а О Ь.

Класс эквивалентности, порожденный элементом а, обозначается через [а] или Са• По определению имеем: [а] = {ЬЬеА и а 0 6}.

Приведем примеры отношения эквивалентности.

  • 1. Отношение равенства на множестве целых чисел. При этом каждый класс эквивалентности состоит из одного элемента, т. е. для любого целого числа х класс [х] — {х}.
  • 2. Отношение подобия па множестве всех треугольников. Каждый класс эквивалентности представляет собой множество подобных между собой треугольников.
  • 3. Отношение принадлежности одной учебной группе па множестве всех студентов. Классом эквивалентности в этом случае является множество студентов одной группы.
  • 4. Бинарное отношение 0, определенное на множестве целых чисел Z следующим образом: хОу тогда и только тогда, когда разность х — у делится па п ? Лг, называется отношением сравнения по модулю натурального числа п и обозначается х = у (mod п).

П р и м е р 2.5. Показать, что отношение сравнения по модулю натурального числа п есть отношение эквивалентности и определить к л ассы эквив ал ентн ости.

Это отношение рефлексивно на Z, так как для любого целого числа х верно х—х = 0 = 0п. Очевидно, что если х—у делится на п, то и у—х делится на п. Это означает симметричность отношения. Покажем транзитивность отношения сравнимости по модулю п. Если х = у (mod п), то для некоторого целого числа г имеем х — у — гп. А если y = z (mod n), то для некоторого целого г/ имеем y — z — qn. Складывая эти два равенства, получаем: х — z = (r + q)n, т. е. разность x — z делится па п, так как (r + g) - целое число. Следовательно, x = z (mod п).

Данное отношение порождает следующие классы эквивалентности: вместе с любым целым числом а в этом же классе эквивалентности содержатся все числа вида а + кп, где к - целое число. Очевидно, что числа О, 1, 2, .... п - 1 порождают различные классы эквивалентности: [0], [1], и, ..., [п— 1]. Они называются классами вычетов по модулю п. Поскольку любое целое число а можно представить в виде a = qn+r, где О^г^п, то все остальные классы эквивалентности совпадают с указанными выше.

Для любого отношения эквивалентности в па множестве Л справедливы следующие утверждения:

  • 1. Если а ? А, то а?[а] (т. е. каждый элемент множества А принадлежит порожденному им классу эквивалентности).
  • 2. Если а, 6? А и авЪ, то [а] = [6] (т. е. класс эквивалентности порождается любым своим элементом).
  • 3. Если а,б?Д, то [а] = [6] или [а]П[6] = 0 (т. е. различные классы эквивалентности попарно не пересекаются).

Справедливость первого утверждения следует из того, что отношение эквивалентности рефлексивно, а 0 а и, следовательно, аЕ[а].

Докажем второе утверждение. Пусть с ? ]. Тогда свЬ и в силу транзитивности отношения, с в а, т. е. с Е [а]. Отсюда [b] С [а]. Аналогично в силу симметричности 0 можно показать, что [а] С [6], а значит, [а] = [Ь].

Для доказательства третьего утверждения предположим, что два различных класса эквивалентности пересекаются, т. е. существует такой элемент с, что се[а]П[6]. Это означает, что а# с, и b 0 с, следовательно [о] = [с], [6] = [с]. Откуда, [о] = [6].

Из приведенных выше утверждений следует, что любое отношение эквивалентности 0 па множестве А позволяет представить это множество в виде объединения попарно непересекающихся подмножеств - классов эквивалентности. Такое представление множества А имеет специальное название.

Определение 2.11. Разбиением, множества А называется совокупность попарно непересекающихся подмножеств А& таких, что каждый элемент множества А принадлежит одному и только одному из этих подмножеств, т. е. А = и/Ц, ?:? К и AiPAj = tf) при

Используя понятие разбиения, сформулируем приведенные выше рассуждения в виде теоремы.

Теорема 2.1. Всякое отношение эквивалентности определяет разбиение множества на классы эквивалентности относительно этого отношения.

С другой стороны, справедлива обратная теорема.

Теорема 2.2. Всякое разбиение множества А определяет на нем отношение эквивалентности в: аОЪ тогда и только тогда, когда а и Ь принадлежат одному подмножеству разбиения.

Действительно, отношение в, очевидно, рефлексивно и симметрично. Докажем транзитивность. Пусть а()Ь и ЬОс, тогда а, Ье_Ау, 6, cG/В, где А] и Ао - подмножества разбиения множества А. Тогда bG Aj П /В, следовательно, А = Ао и а 0 с.

Если отношение эквивалентности задано матрицей, то с помощью перестановки строк (столбцов) матрицу отношения можно привести к такому виду, что около главной диагонали расположены подматрицы (клетки), состоящие из единиц, остальные элементы матрицы равны нулю. Каждая такая подматрица (клетка) соответствует классу эквивалентности.

П р pi м е р 2.6. Показать, что бинарное отношение т, определенное на множестве А = {ai, аз, аз, аз, аз}, есть отношение эквивалентности, указать соответствующее ему разбиение множества А, если отношение т задано матрицей

Матрица Ст имеет клеточную структуру. Рассмотрим соответствующие ей подмножества А = {щ, а<), аз}, А2 = {а.4, а$}. Тогда А = A] UA‘> - разбиение множества А. Согласно теореме 2.2 данное разбиение задает отношение эквивалентности, которое, как легко видеть, совпадает с отношением т.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>