- •2. Элементы комбинаторики
- •2.1. Основные понятия
- •2.2. Виды комбинаторных задач
- •2.3. Основные правила комбинаторики
- •Базис индукции
- •Решение
- •Решение
- •2.4. Размещения и сочетания
- •Определение
- •Рассмотрим примеры сочетаний
- •2.5. Разбиения множеств на части
- •2.6. Формула включений-исключений
- •Рассмотрим пример
- •Упражнение
- •3. Отношения
- •3.1. Определение и примеры отношений
- •3.2. Представление отношений
- •Табличное задание отношений
- •3.3. Операции над отношениями
- •Определение
- •3.4. Бинарные отношения на множестве
- •3.5. Отношения эквивалентности определение
- •Определение
- •Доказательство
- •Построение разбиения, порождаемого отношением .
- •3.6. Отношения порядка
- •Определение
- •Определение
3.5. Отношения эквивалентности определение
Всякое рефлексивное, симметричное и транзитивное отношение А А, называется отношением эквивалентности.
Если отношение эквивалентности и a b, то элементы a и b называются эквивалентными в этом отношении или просто эквивалентными.
Рассмотренное ранее отношение "быть родственником" является отношением эквивалентности. Аналогично, отношением эквивалентности на множестве всех людей является отношение "быть однофамильцем". Это отношение связывает между собой людей с одинаковыми фамилиями, распределяя их по классам людей, каждый из которых состоит из всех людей, имеющих одну и ту же фамилию.
Для представления фундаментального свойства отношений эквивалентности введем понятие разбиения множества.
Определение
Разбиением множества A называется конечное или бесконечное семейство множеств Ai, i I таких, что:
1) iI(Ai );
2) i,jI(i j Ai Aj = );
3) Ai = A .
Здесь I это множество значений нижнего индекса множеств разбиения. В разбиениях счетных множеств в качестве множества индексов I обычно применяется все или часть множества натуральных чисел.
Пусть A1, ... , Ak, . . . разбиение множества A. Нетрудно проверить, что отношение на множестве A, определяемое соотношением: a b , является отношением эквивалентности.
Следующая теорема показывает, что справедливо и обратное свойство.
ТЕОРЕМА 3.2
Всякое отношение эквивалентности на множестве A разбивает это множество на классы эквивалентных элементов.
Доказательство
Разобьем доказательство теоремы на несколько этапов.
Построение разбиения, порождаемого отношением .
Пусть отношение эквивалентности на множестве A.
Для каждого x A обозначим как [x] множество {yxy}. Поскольку отношение рефлексивно, то x [x], а, значит, каждое множество [x] является непустым и система множеств [x], где x A, содержит все элементы A. Из семейства множеств {[x] x A } удалим кратные вхождения одинаковых множеств. В результате получим семейство непустых несовпадающих множеств R, в которых содержатся все элементы A.
Обоснование того, что R образует разбиение.
Пусть [x] и [y] произвольные классы из семейства R. Покажем, что они либо не пересекаются, либо совпадают, т.е. возможны только два случая:
1) [x] [y] = ;
2) [x] [y] .
Предположим, что это свойство является неверным. То есть для некоторых двух элементов x и y множества [x] и [y] пересекаются, но не совпадают (рис 3.1).
[x] [y]
x z y
a b
Рис.3.1
Здесь z это элемент, общий для классов [x] и [y], а a и b произвольные элементы в [x] и [y] соответственно.
1. Докажем, что [x] [y]. Пусть x a. Покажем, что справедливо отношение y a:
a) поскольку x z, то из симметричности следует, что z x;
b) поскольку z x и x a, то из транзитивности вытекает, что z a;
c) из y z и z a и транзитивности имеем y a. Поэтому a [y], а, значит, [x] [y].
2. Обратное включение [y] [x] может быть доказано, если повторить проведенные рассуждения, поменяв в них местами x и y, а также a и b.
Следовательно, справедливо равенство множеств [x] и [y]. Последнее противоречит предположению о том, что эти множества являются разными.
Это означает, система множеств R образует разбиение множества разбиение A.
3. Обоснование того, что R разбивает A на классы эквивалентных элементов.
3.1. Покажем, что в каждом классе из R любые два элемента находятся между собой в отношении .
Пусть выбраны произвольное множество [x] R и элементы a, b A. Покажем, что a b. Действительно, по определению множества [x] справедливы соотношения: xa и xb. Из соотношения xa и симметричности следует, что ax. Из ax и xb, а также транзитивности следует, что ab.
3.2. Покажем, что элементы из разных классов в R не находятся в отношении . Пусть [x], [y] R и a[x], b[y] произвольные элементы этих множеств. Покажем, что (a, b) . Предположим противное. Пусть ab. Тогда из симметричности отношения следует, что ba. Поскольку yb и ba, то из транзитивности следует, что ya. Поэтому a[y]. Последнее противоречит тому, что множества [x] и [y] не пересекаются.
Следовательно, (a, b) .
Доказательство окончено.
Упражнение. Проверить, является ли отношением эквивалентности отношение синонимии на множестве слов русского языка.