6.4. Изоморфизм т-полных множеств

В этом разделе мы докажем, что все т-полные множе­ства «устроены одинаково» и отличаются друг от друга только вычислимой перестановкой.

Теорема 41. Пусть А и В — m-полные перечислимые множества. Тогда существует вычислимая перестановка (вычислимое взаимно однозначное соответствие) /: N —>■ —5- N, при которой А переходит в В, то есть х £ А -<=> *<=> f(x) £ В при всех х.

<] Мы будем использовать тот же приём, что и в приведённом выше доказательстве теоремы Роджерса об изоморфизме главных нумераций (см. с. 39). Именно, мы для начала докажем такую лемму:

Лемма. Пусть А — т-полное перечислимое множест­во. Тогда существует способ по любому натуральному числу п алгоритмически указать сколько угодно других натуральных чисел, которые принадлежат или не при­надлежат А одновременно с п.

Доказательство леммы. Как и раньше, у нас будут два способа получать новые числа, которые ведут себя по от­ношению к А так же, как и исходное. Один из них будет гарантированно давать новое число, если х £ А, дру­гой — если х £ А. При этом мы можем применять оба, не зная, какой из случаев имеет место на самом деле (и можем так этого и не узнать).

Первый способ состоит в следующем. Пусть Р — пе­речислимое неразрешимое множество. Рассмотрим пере­числимое множество пар А х Р. Оно сводится к А, так как А является m-полным. (Вообще-то в определении сво­димости шла речь о множествах натуральных чисел, а не пар, но, как всегда, это не играет роли — пары можно вычислимо нумеровать.) Другими словами, существует вычислимая всюду определённая функция / двух пату-

Изоморфизм т-полных множеств

ральных аргументов с таким свойством:

f(n, т) £ Л •О (п £ А) и (т £ Р).

В частности, при т £ Р числа п и f(n, т) одновременно принадлежат или не принадлежат А. Поэтому, располо­жив Р в вычислимую последовательность р(0),р(1),..., мы можем вычислять числа f(n,p(Q)), f(n,p(l)),... и по­лучать новые числа, которые принадлежат или не при­надлежат А одновременно с п.

Пусть п £ А. Покажем, что множество X получаемых таким образом чисел (все они в этом случае тоже принад­лежат А) будет бесконечно. В самом деле, f(n, т) £ X при т £ Р (по построению X) и f(n, т) f X при т f (f Р (поскольку в этом случае f(n,m) (f А, а X С А). Таким образом, функция т н->- f(n, т) сводит неразре­шимое множество Р к множеству X, так что X неразре­шимо и потому бесконечно.

Теперь опишем другой способ, который гарантирует успех, если п £ А. Возьмём два перечислимых неотдели­мых множества Р и Q. Рассмотрим перечислимое мно­жество пар (А х Р) U (N х Q). Пусть функция / сводит его к А. Это означает, что f(n, т) £ А тогда и только тогда, когда (п £ А и т £ Р) или т £ Q. Как и прежде, при т £ Р числа п и f(n, т) одновременно принадлежат или не принадлежат А, так что мы можем снова рассмо­треть последовательность f(m,p(Q)), f(n,p(l)),...; оста­лось лишь показать, что (если п (Ё А) в этой последова­тельности бесконечно много различных членов.

Пусть это не так и множество X всех членов этой последовательности конечно. По нашему предположе­нию X не пересекается с А. Заметим, что f(n, т) £ X при т £ Р (по построению) и f(n, т) (Ё X при т £ Q (так как в этом случае (п, т) принадлежит нашему пе­речислимому множеству пар и f(n,m) принадлежит А). Таким образом, прообраз множества X при отображе­нии т и-)- f(n, т) отделяет Р от Q. Но этот прообраз разрешим (X разрешимо, ибо конечно, а указанное ото­бражение всюду определено и вычислимо). А по нашемупредположению множества Р ж нельзя отделить раз­решимым множеством.

Итак, мы привели два способа получать новые эле­менты, которые принадлежат или не принадлежат А од­новременно с исходным. Применяя их параллельно, мы наверняка добьёмся результата. Лемма доказана.

Пусть теперь А ж В — два т-полных перечислимых множества. Докажем, что они отличаются лишь вычи­слимой перестановкой натурального ряда. Будем стро­ить эту перестановку по шагам. На к-ош шаге мы имеем взаимно однозначное соответствие

си     Ь\,а2     Ь2,.. .,аи «->• Ьк,

при котором щ £ .4 О 6,- £ В при всех г. На чётных шагах мы берём минимальное число, не входящее в ле­вую часть этого соответствия. Используя факт т-сво-димости А к В, мы находим ему компаньона. При этом доказанная нами лемма позволяет выбрать компаньона, не встречающегося среди уже имеющихся справа элемен­тов. На нечётных шагах мы делаем то же самое, только справа налево.

В пределе этот процесс даёт искомую вычислимую пе­рестановку, связывающую А ж В. >

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