II р и м е р 4.1.
{А, В} — покрытие A U Z?, [А, А U В, В, С} — покрытие А U В U С. II
Используя понятие покрытия, можно обеспечить, чтобы пн одно из свойств пе было пропущено, так как каждый элемент включен по крайней мере в одно из подмножеств покрытия. Однако в общем случае могут встречаться случаи дублирования. Если в дальнейшем потребовать, чтобы элементы покрытия попарно не пересекались, то дублирования не будет. Отсюда возникает понятие разбиения.
Определение. Разбиением непустого множества А Называется совокупность подмножеств S^(A) таких, что объединение всех элементов У {А) совпадает с А и все элементы У (А) взаимно не пересекаются, т. е. А разбито таким образом, что каждый элемент А содержится только в одном подмножестве разбиения. II
II р и м е р 4.1.
{А, В} — покрытие A U Z?, [А, А U В, В, С} — покрытие А U В U С. II
Используя понятие покрытия, можно обеспечить, чтобы пн одно из свойств пе было пропущено, так как каждый элемент включен по крайней мере в одно из подмножеств покрытия. Однако в общем случае могут встречаться случаи дублирования. Если в дальнейшем потребовать, чтобы элементы покрытия попарно не пересекались, то дублирования не будет. Отсюда возникает понятие разбиения.
Определение. Разбиением непустого множества А Называется совокупность подмножеств S^(A) таких, что объединение всех элементов У {А) совпадает с А и все элементы У (А) взаимно не пересекаются, т. е. А разбито таким образом, что каждый элемент А содержится только в одном подмножестве разбиения. II
Пример 4.2.
{А, А'} — разбиение S,
{А П В, А П В', А' П В, А' П В'} - разбиение <У, {А\В, А П В, В\А} — разбиение А U В. II
Разбиение определяется однозначно, и части разбиения индуцируют особый род отношения, называемого отношением эквивалентности. Эти отношения ведут себя по-добпо отношению “=” между числами или множествами. Выделяя основные свойства равенства, мы приходим к следующему определению.
Определение. Бинарное отношение на множестве называют отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. II
Пример 4.3. На множестве всех треугольников отношение, определяемое как {(х, у): х и у имеют одинаковую площадь), является тривиальным отношением эквивалентности. Более интересно следующее отношение, определенное на множестве всех программ: ((а, b): а и b вычисляют одну и ту же функцию на определенной машине}. Это отношение является отио!испни;,1 анинва-лентности. II
Напомни?.!, что мы рассматриваем более простью способы создания больших мно/кести, разбивая их на мелкие части, чем если бы d качестве этих частей брали элементы множества. В настоящий момент у нас у?ке имеется математический аппарат, однако недостает подходящих простых обозначений. Сейчас это будет сделано, после чего приведем несколько известных примеров.
f Определение. Пусть р—отношение эквивалентности на множестве А. Определим класс эквивалентно-
, сти [х] для х <= А:
[х] = {у: хру}.
Таким образом,'1Та:] есть множество всех элементов А, которые р-эквивалентны х. В случаях, когда рассматривается только одно отношение эквивалентности, мы можем также использовать обозначение (эквивалентно), поэтому “ss”
[.с] = {у. х в” у}. *
В отдельных специальных случаях для обозначения эквивалентности иногда используют символ “~”. Теперь вместо проверки всего множества мы можем любым способом выбрать представителей (по одному от каждого из классов эквивалентности), что упрощает вычисления. Следующий пример иллюстрирует вышесказанное. Пример 4.4. Пусть s — фиксированный элемент N;
определим отношение р. на Z:
Р. = ^ {х. У}'- х— у = ns, где п <= Z}.
Рассмотрим случай s = 10. Тогда
[1]= {11, 21,-9, 10976631,...}, [1066] ={66, 226,-24,...}
и т. д.
В действительности существуют только десять различных классов эквивалентности. Целые О, 1, 2, 3, 4, 5, 6, 7, 8, 9 принадлежат различным классам. Поэтому мы можем использовать их в качестве представителей этих классов. II
В вычислениях отношения эквивалентности представляют особый интерес, поскольку они ассоциируются с различными алгоритмами, дающими один и тот же результат, или приводящими к одной и той же обработке данных, или же представляющими одну и ту же информацию о различных эквивалентных структурах данных. Примером таких очевидных ситуаций является борьба с трудностями, которые возникают при исследовании раз-
48
решимости. Такие факторы, однако, не вызывают проблем, если множества образуются путем хорошо сконструированных процессов с конечной базой. II все же типичным является случай, когда при описании даже “хорошего поведения” требуется большое число деталей, в связи с чем они должны быть здесь рассмотрены. Несмотря на это, мы будем возвращаться к подобным вопросам в § 6 и в гл. 8 и 9.
По-видимому, наиболее известное отношение эквивалентности знакомо читателю, хотя он мог и не знать, что оно — отношение эквивалентности. Это отношение связано с дробями. Рассмотрим множество Z Х N. Пару (а, Ь) мы можем рассматривать как дробь а/Ь. Эти два способа обозначения элементов Z Х N являются различными, но они “изоморфны”. Мы будем их рассматривать далее в § 1 гл. 5. Отметим, что можно переходить от одной формы обозначения к другой.
До сих пор все было хорошо, однако существуют различные элементы в Z X N, которые желательно рассматривать как одни и те же, хотя записываются они по-разному. Чтобы преодолеть эту трудность, определим отношение эквивалентности на ZXN следующим образом:
(д, Ь)—(с, d) тогда и только тогда, когда a“d=b”c.
Множество всех классов эквивалентности, определяемых этим отношением на Z X N, называют рациональными числами и обозначают символом Q. Обычно выбирают тех представителей классов, у которых самые малые а и Ь.
Следует упомянуть, что предполагается существование действительных чисел (множество действительных чисел обычно обозначают через R). Эти числа можно представить в форме
...О о” ... da di do 6i 62 ... 6m •••i
где каждое di и f>j принадлежат множеству
{О, 1, 2, 3, 4, 5, 6, 7, 8, 9) = Zio, d, ^ О,
исключая случай п == 0. В частности, допускается бесконечная непериодическая десятичная дробь, хотя нули перед ri„ обычно опускают. (Отрицательные числа представляют ненулевыми положительными числами со знаком минус.)
Заметим, что индекс отношения эквивалентности р на множестве А — это количество частей А, индуцируемых р (число р-эквивалентпых классов).
Упражнение 2.4.
1. Доказать, что любое отношение эквивалентности порождает такое разбиение, что для любых х, у <= А или [х] = [у], или [х] П [у] = 0.
2. Пусть ^4 — конечное множество. Какие отношения эквивалентности дают наибольшее и наименьшее число эквивалентных классов?
3. Если Ui, Аг, ..., An}—разбиение А ц А конечное, показать, что
i^i=ii^i.