Рекурсивная Теория Множеств

Раздел тео-рии рекурсивных функций, в к-ром рассматриваются и классифицируются подмножества натуральных чисел с алгоритмич. точки зрения, а также исследуются структуры, возникающие в результате такой классификации. Для каждого множества А, к-рое является подмножеством множества всех натуральных чисел N, можно сформулировать следующую п р о б л е м у р а з р еш и м о с т и: существует ли алгоритм, позволяющий для любого ответить на вопрос о принадлежности x к A? Математическая постановка проблем такого рода, как и развитие Р. т. м., стала возможна лишь в 40-х гг. 20 в. после успешной формализации интуитивного понятия (алгоритмически) вычислимой функции. Области значений таких функций образуют семейство р е к у рс и в н о п е р е ч и с л и м ы х м н о ж е с т в (р. п. м.). Множества, для к-рых сформулированная выше проблема разрешима, наз. р е к у р с и в н ы м и. Точнее, Арекурсивно тогда и только тогда, когда Аи оба являются р. п. м. Первыми примерами нерекурсивных р. п. м. оказались т. н. креативные (творческие) множества. Именно, р. п. м. Kназ. к р е а т и в н ы м, если существует вычислимая функция, к-рая по номеру любого р. п. м. А, не пересекающегося с K, выдает число, принадлежащее . Одновременно с креативными множествами были обнаружены и другие нерекурсивные р. п. м., в частности простые. Р. п. м. наз. п р о с т ы м, если оно имеет бесконечное дополнение, к-рое не содержит бесконечных р. п. м. Таким образом, уже для р. п. м. возникает тонкая проблема классификации их проблем разрешимости. Одним из инструментов для такой классификации служит понятие с в о д и м о с т и. На интуитивном уровне множество Ас в о д и м о к множеству В, если существует алгоритм, к-рый решал бы проблему вхождения элементов для множества А при условии, что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных натуральных чисел множеству В. В этом случае Аоказывается в определенном смысле "рекурсивным" относительно В, а обычные рекурсивные множества — "рекурсивными" относительно любого множества. Такая сводимость в самом общем виде (точная формулировка к-рой достаточно сложна) наз. т ь ю р и н г о в о и, или Т- сводимостью. Накладывая те или иные ограничения на алгоритм, участвующий в понятии сводимости, приходят к определению других сводимостей, напр. 1-, т-, btt- или tt -сводимости. В частности, А m -с в о д и м о к В, если существует всюду определенная вычислимая функция f такая, что для всех хиз N Если f можно выбрать разнозначной, то говорят, что А1-с в о д и м о к В. Обобщением m-сводимости является т а б л и ч н а я (tt-).сводимость. Множество А tt -сводимо к множеству В, если существует алгоритм, к-рый для каждого хдает набор чисел и булеву функцию , причем где c(t)=1, если , и c(t)=0 в противном случае. Если Аможно таблично свести к Втак, что n(х)будет ограничено нек-рой константой, то говорят, что Ао г р а н ич е н н о т а б л и ч н о (btt- )с в о д и т с я к В. Пусть r — нек-рая сводимость. Пишут , если множество А r -сводимо к В. Отношение должно быть предпорядком. Если положить то будет отношением эквивалентности, отдельный класс к-рой наз. r-с т е п е н ь ю (и рекурсивно перечислимой r-степенью, если этот класс содержит р. п. м.). Тьюринговы степени известны в литературе и как с т е п е н и н е р а з р е ш и м о с т и. Отношение порождает частичное упорядочение всех r-степеней. Сводимость r' слабее, чем r, если влечет Частично упорядоченные множества r-степеней для т- и более слабых сводимостей образуют верхние полурешетки (что неверно для 1-степеней), имеющие наименьший элемент 0-r-степень рекурсивных множеств. Если ограничиться изучением только рекурсивно перечислимых r-степеней, то они имеют также и наибольший элемент 1, к-рый наз. п о л н о й r-с т е п е н ь ю. Р. п. м., содержащиеся в полной r-степени, наз. r-п о л н ы м и. М и н и м а л ь н ы м и r-степенями наз. такие, к-рые имеют лишь единственную строго меньшую r-степепь, а именно 0. После определения той или иной сводимости ее изучение развивается в основном в двух направлениях. Первое связано с вопросами описания верхней полурешетки степеней относительно введенной сводимости. Известным примером проблемы такого типа явилась п р о б л е м а П о с т а [1]: верно ли, что все рекурсивно перечислимые нерекурсивные множества имеют одну и ту же степень неразрешимости? Или, другими словами, верно ли, что полурешетка рекурсивно перечислимых степеней неразрешимости состоит лишь из двух элементов? Получено отрицательное решение этой проблемы [2]. Решения этих вопросов о строении верхних полурешеток рекурсивно перечислимых т-, tt- и Т-степеней являются определенными вехами в изучении сводимостей. В нач. 1960-х гг. было доказано, что полурешетка Т-степеней (везде ниже подразумеваются полурешетки рекурсивно перечислимых степеней) не является решеткой и не имеет минимальных элементов; тогда же было отмечено существование минимальных m-степеней и показано, что полная m-степень не является точной верхней гранью двух несравнимых т- степеней. Позднее выяснилось, что этот факт не имеет места для btt- и более слабых сводимостей. Ю. Л. Ершов [4] доказал, что верхняя полурешетка m-степеней не является решеткой и что под нек-рыми ее элементами нет минимальных. Аналогичные результаты, а также существование минимальных элементов, были получены для полурешеток btt- и tt -степеней [5]. Установлено, что элементарные теории полурешеток т-, btt-, tt-, Т- и нек-рых других степеней попарно различны. Второе направление связано с вопросами о том, какие r -степени, сколько их и как они расположены в степенях относительно более слабой сводимости, чем r. В частности, полная Т (tt-, btt- )-степень содержит счетное число рекурсивно перечислимых tt (соответственно btt-, m -)-степеней. С другой стороны, существуют нерекурсивные Т(btt -)-степени, состоящие из одной tt(m-)-степени, но каждая нерекурсивная tt -степень содержит, по крайней мере, две btt -степени. К изучению р. п. м. имеются и другие подходы, не связанные с понятием сводимости. Один из них заключается в следующем. Все р. п. м. вместе с операциями объединения и пересечения образуют решетку Нек-рое свойство р. п. м. наз. теоретико-решеточным, если оно сохраняется при всех автоморфизмах . Такими, напр., являются свойства "быть рекурсивным", "быть простым" или "быть максимальным" множеством. Р. п. м. А наз. м а к с и м а л ьн ы м (r-м а к с и м а л ь н ы м), если его дополнение бесконечно и не может быть разбито р. п. м. (соответственно рекурсивным множеством) на две бесконечные части. Классич. результатами, связанными с изучением , могут служить теоремы о существовании максимальных множеств и о возможности разбиения любого нерекурсивного р. п. м. на два нерекурсивных р. п. м. (см. [2]) и теорема о существовании r-максимального множества без максимальных надмножеств (см. [3]). Понятие максимального множества возникло в связи с надеждой, что они окажутся не T-полными. Это было бы естественным решением проблемы Поста. Сам Э. Пост, накладывая все более жесткие ограничения на дополнения р. п. м., определил классы гиперпростых и гипергиперпростых множеств, показав, что гиперпростые множества не могут быть tt -полными. При этом р. п. м. Ас бесконечным дополнением наз. г и п е р п р о ст ы м (г и п е р г и п е р п р о с т ы м), если не существует вычислимой последовательности попарно непересекающихся конечных (соответственно рекурсивно перечислимых) множеств, каждое из к-рых имеет непустое пересечение с дополнением А. Определение этих классов множеств дается не в теоретико-решеточных терминах, и в действительности удалось показать, что "быть гиперпростым" не является теоретико-решеточным свойством. Однако доказано, что р. п. м. Асбесконечным дополнением является гипергиперпростым тогда и только тогда, когда для любого р. п. м. Всуществует рекурсивное множество Rтакое, что и , т. е. свойство "быть гипергиперпростым" оказалось теоретико-решеточным. Было построено гипергиперпростое множество без максимальных надмножеств, а также доказано, что для любого нерекурсивного р. п. м. Асуществует автоморфизм Ф решетки такой, что Ф(А)является T-полным множеством [6]. Таким образом, надежда найти теоретико-решеточное свойство, к-рым не обладали бы рекурсивные и T-полные множества, не оправдалась. Имеется также концепция (в духе [7]), согласно к-рой Р.