§ 4. Разбиения и отношения эквивалентности

Во многих вычислительных задачах берутся большие множества и разбиваются таким образом, чтобы все интересующие нас ситуации можно было исследовать на нескольких правильно выбранных примерах. Например, один из путей получения качественной оценки характе­ристик языка программирования — это посмотреть кон­кретные программы, написанные на этом языке. Однако каждый интересный язык, включая такие языки высоко­го уровня, как Паскаль и Фортран, порождает бесконеч­но много программ, и, следовательно, мы должны выби­рать программы так, чтобы они правильно отражали до­стоинства и недостатки языка. Чтобы быть более кон­кретными, давайте в дальнейшем предполагать, что язык имеет три основные управляющие структуры и четыре метода доступа и более у него нет никаких особые свойств. Мы могли бы в качестве примера взять семь программ, каждая из которых включает только одну ха­рактеристику языка (хотя, вообще говоря, каждая про­грамма может использовать более чем одну характеристи­ку языка). Исследование этих программ тогда могло бы покрыть большую часть свойств языка. Математически это можно определить следующим образом.

Определение. Пусть A — непустое множество и {A_i}— совокупность подмножеств (i=l,…, n, n N) таких, что

Совокупность этих подмножеств называется покры­тием А.//

Пример 4.1.

{А, В} — покрытие A В,

{A, A В, В, С} - покрытие A В С. //

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

Определение. Разбиением непустого множества А называется совокупность подмножеств (А) таких, что объединение всех элементов (А) совпадает с А и все элементы (А) взаимно не пересекаются, т. е. А разбито таким образом, что каждый элемент А содер­жится только в одном подмножестве разбиения. //

Пример 4.2.

{А, А'} — разбиение ξ,

{А В, А В', А' В, А' В'} - разбиение ξ,

{A\B, A B,B\A} — разбиение A В. //

Разбиение определяется однозначно, и части разбиения индуцируют особый род отношения, называемого отно­шением эквивалентности. Эти отношения ведут себя по­добно отношению «=» между числами или множествами. Выделяя основные свойства равенства, мы приходим к следующему определению.

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

Пример 4.3. На множестве всех треугольников от­ношение, определяемое как {(х, у): х и y имеют одина­ковую площадь}, является тривиальным отношением эк­вивалентности. Более интересно следующее отношение, определенное на множестве всех программ: {(а, b): а и b вычисляют одну и ту же функцию на определенной машине}. Это отношение является отношением эквива­лентности. //

Напомним, что мы рассматриваем более простые спо­собы создания больших множеств, разбивая их на мел­кие части, чем если бы в качестве этих частей брали элементы множества. В настоящий момент у нас уже имеется математический аппарат, однако недостает под­ходящих простых обозначений. Сейчас это будет сделано, после чего приведем несколько известных примеров.

Определение. Пусть — отношение эквивалент­ности на множестве А. Определим класс эквивалентно­сти [х] для х А:

[х] = {у: х у}.

Таким образом, [х] есть множество всех элементов A, которые -эквивалентны x. В случаях, когда рассматри­вается только одно отношение эквивалентности, мы мо­жем также использовать обозначение « » (эквивалент­но), поэтому

[x] = {y: x y}.

В отдельных специальных случаях для обозначения эквивалентности иногда используют символ «~». Теперь вместо проверки всего множества мы можем любым спо­собом выбрать представителей (по одному от каждого из классов эквивалентности), что упрощает вычисления.

Следующий пример иллюстрирует вышесказанное.

Пример 4.4. Пусть s — фиксированный элемент N; определим отношение _S на Z:

^{S = {(x, y): х — y = ns, где п Z).}

Рассмотрим случай s = 10. Тогда

[1] = {11, 21, -9, 10 976 631,…},

[1066] = {66, 226, -24,…}

и т. д.

В действительности существуют только десять раз­личных классов эквивалентности. Целые 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 принадлежат различным классам. Поэтому мы можем использовать их в качестве представителей этих классов. //

В вычислениях отношения эквивалентности представ­ляют особый интерес, поскольку они ассоциируются с различными алгоритмами, дающими один и тот же ре­зультат, или приводящими к одной и той же обработке данных, или же представляющими одну и ту же инфор­мацию о различных эквивалентных структурах данных. Примером таких очевидных ситуаций является борьба с трудностями, которые возникают при исследовании разрешимости. Такие факторы, однако, не вызывают проблем, если множества образуются путем хорошо сконст­руированных процессов с конечной базой. И все же ти­пичным является случай, когда при описании даже «хо­рошего поведения» требуется большое число деталей, в связи с чем они должны быть здесь рассмотрены. Не­смотря на это, мы будем возвращаться к подобным во­просам в § 6 и в гл. 8 и 9.

По-видимому, наиболее известное отношение эквива­лентности знакомо читателю, хотя он мог и не знать, что оно — отношение эквивалентности. Это отношение связано с дробями. Рассмотрим множество . Пару (a, b) мы можем рассматривать как дробь a/b. Эти два способа обозначения элементов являются различ­ными, но они «изоморфны». Мы будем их рассматривать далее в § 1 гл. 5. Отметим, что можно переходить от од­ной формы обозначения к другой.

До сих пор все было хорошо, однако существуют раз­личные элементы в , которые желательно рассмат­ривать как одни и те же, хотя записываются они по-разному. Чтобы преодолеть эту трудность, определим от­ношение эквивалентности на следующим образом:

^{(a, b) ≡ (c, d) тогда и только тогда, когда a*d=b*c.}

Множество всех классов эквивалентности, определяемых этим отношением на , называют рациональными чис­лами и обозначают символом Q. Обычно выбирают тех представителей классов, у которых самые малые а и о.

Следует упомянуть, что предполагается существова­ние действительных чисел (множество действительных чисел обычно обозначают через R). Эти числа можно представить в форме

… 0 d_n … d₂ d₁ d_{0 1 2} … _m …,

где каждое d_i и _j принадлежат множеству

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} = Z₁₀, d_n ≠ 0,

исключая случай n = 0. В частности, допускается беско­нечная непериодическая десятичная дробь, хотя нули перед d_n обычно опускают. (Отрицательные числа пред­ставляют ненулевыми положительными числами со зна­ком минус.)

Заметим, что индекс отношения эквивалентности на множестве А — это количество частей А, индуцируе­мых (число -эквивалентных классов).

Упражнение 2.4.

1. Доказать, что любое отношение эквивалентности порождает такое разбиение, что для любых х, у А или [х] = [y], или [х] [у] = ø.

2. Пусть А — конечное множество. Какие отношения эквивалентности дают наибольшее и наименьшее число эквивалентных классов?

3. Если {А₁, А₂,…, A_n} — разбиение A и A конеч­ное, показать, что