Логические теории одноместных функций на натуральном ряде тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Семенов, А.Л.

• Семенов, А.Л.
• доктор физико-математических наук
• 1984

Оглавление диссертации доктор физико-математических наук Семенов, А.Л.

Оглавление

Введение

Глава I Некоторые общие определения и теоремы

Глава П Монадические теории

Глава Ш Элементарные теории.

Введение диссертации (часть автореферата) на тему «Логические теории одноместных функций на натуральном ряде»

Пусть задана функция , определенная на натуральном ряде Ж и принимающая значения токе в Д\/ • Во многих случаях при изучении свойств этой функции оказывается естественным описывать эти свойства на некотором логическом языке L . Так же как и в другах подобных ситуациях, например, при описании свойств группы, здесь возникает логическая теория некоторой структуры, т.е. множество всех истинных утверждений о рассматриваемой структуре, записываемых на языке L • Нас будут интересовать свойства функций, связанные с имеющимися на натуральном ряде отношением порядка ^ и операцией сложения + • Таким образом, будут изучаться теории структур ^ ^ > и /)/; +, / > . (В силу того, что порядок ^ можно определить через 4- , рассмотрение структуры ( /I-t, сводится к рассмотрению структуры К Л^у ). Логический язык при этом мы будем выбирать элементарным (языком первого порядка) или монадическим; в последнем, помимо средств элементарного языка, допускаются переменные по подмножествам натурального ряда (иначе говоря, по одноместным предикатам) и кванторы по этим переменным.

Центральным для нашего исследования будет вопрос о разрешимости возникающих теорий* Дальнейшее (по сравнению с монадической теорией) расширение логических средств языка, за счет введения кванторов по одноместным функциям из AV в AV и т.д., приводит к неразрешимым логическим теориям независимо от наличия какой-либо структуры на (Простое доказательство этого известного факта будет приведено в гл. I). Точно так же заведомо неразрешима монадичеекая теория любой структуры на /IV t в сигнатуру которой входит 4- (см., например, С Е R1 )• йтак, мы приходим к рассмотрению теорий следующих трех классов: монадические теории структур ^ f}9 обозначаемыеyUXf , элементарные теории структур <(^ , f )» обозначаемые 9 элементарные теории структур ч, | >, обозначаемые

Будем использовать аналогичные обозначения Jl Т , 7 и когда сигнатура вовсе не содержит f . Элементарную теорию произвольной структуры У будем обозначать Т У монадическую теорию

Конечно, необходимым условием разрешимости каждой из теорий Jl Т -f , f и 7~f служит вычислимость функции / . Легко показать, что это условие не является достаточным даже в случав, когда f - характеристическая. Пример вычислимой характеристической функции для которой теория 7"f неразрешима,построен в работе С TS J , аналогично пример для теории JA- Tf был приведен в fBL21 .

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

Как известно (см. [В> 1]) монадическая, (а, значит, и элементарная) теория структуры разрешима. В силу этого разрешима всякая теория ^JlTf , где функция ^ определима в ji^T . Например, теория JlTf разрешима, если J есть прибавление единицы. Однако семейство определимых ъ JlT функций небогато. Все функции этого семейства имеют вид ос (ее) ас. -+ fb (ос) ,где оС, (Ъ - периодические (как и всюду в дальнейшем, мы считаем, что периодическая функция может иметь предпериод), оС ; Д^ —* { 0,1J, см. [SlJ). С другой стороны, как следует из результатов если для некоторой строго монотонной функции f теория Jl J~f разрешима, то эта функция определима в Jl Т .

Таким образом, для строго монотонных не определимых в JA Т функций (а основные естественно возникающие функции с бесконечным множеством значений таковы) теория оказывается неразрешимой.

Иной оказывается ситуация, когда множество значений функции / конечно, например, когда f - характеристическая функция. Здесь уже не существенно, являются ли значения 4 натуральными числами или элементами заданного конечного множества ^ (в одном из примеров ниже этим множеством будет j О, ). Такие функции часто называют также сверхсловами в алфавите ^7 . Атомарными формулами теории, использующими символ ^ , являются |(х+с) = ос , где с € 2 , (подробнее, см. гл. П). Элгот и Рабин в [E"R.] доказали разрешимость jllTj в случаях, когда f - характеристическая функция множества значений экспоненты d*, d € Л^/ t множества значений данного многочлена, множества всех факториалов. Зифквс в [S2] нашел некоторые общие условия на характеристическую функцию f (фактически, на функцию с произвольным конечным числом значений), при которых методом Эл-гота - Рабина может быть доказана разрешимость Jl T'f . В работе [ S2 ] Зифкес поставил проблему: существуют ли функции f ,для которых ^JA. Tf разрешима и которые не удовлетворяют найденным им условиям. В работе Г S 3 ] он сформулировал проблему построения метода, который позволил бы выяснить, разрешима ли JlTit^n ^Ги ос. Автор в [с±] нашел общий критерий разрешимости; применимый для монадических теорий произвольных функций с конечным числом значений. Этот критерий, формулируемый ниже в теореме 1 главы П диссертации, показывает, что класс функций / , для которых ,/lTf разрешима, существенно шире, чем класс, описываемый условием Элгота - Рабина - Зифкеса. В частности, к этому классу относятся все вычислимые эффективно почти периодические функции; среди таких функций только периодические удовлетворяют уеловиям Элгота - Рабина - Зифкеса. Функция liqn- 4 «и- ос вычислима .и эффективно почти периодична, значит ьАСТJig*- ^ разрешима. Конечно, эта функция (натурального аргумента) не периодична. Мы сейчас сформулируем не критерий разрешимости, даваемый теоремой!, а его следствие, имеющее более простую формулировку (следствие 3 гл. П). В нем функция f представлена как бесконечная последовательность - сверхслово в алфавите своих значений.

Для всякого вычислимого сверхслова </ следующие две проблемы алгоритмически сводятся одна к другой: -I) проблема разрешения для М ;

2) проблема: по всякому регулярному множеству А выяснить, существует ли конец сверхслова / , не содержащий элементов из А, и, если существует, то указать какой-нибудь такой конец.

Наряду с монадической теорией данной структуры естественно рассматривать также слабую монадическую, в которой множественные переменные пробегают только конечные подмножества. Бюхи и Ландвебер поставили вопрос: вытекает ли для произвольного сверхслова / разрешимость f из разрешимости слабой монадической теории такой же структуры? ( [BL. Z J , проблема 3). Положительный ответ на этот вопрос был получен в [С Ъ~](полное доказательство опубликовано в fCl]) и, затем, в ГТ2], в диссертации этот ответ дается следствием 1 из главы П.

Перейдем теперь к элементарным теориям. Конечно, как и для монадических теорий, можно утверждать разрешимость теории следовательно,

Tf ) для , определимых в теория г: как известно, см. [62]. разрешима). И в этом случае запас таких функций jf- не велик. Легко показать, что все они имеют вид <х(эс)a: -f /2>(эО ,где и (Ъ - периодические функции Первый пример не опредлимой в «7~+функции для которой теория T"t / разрешима, был построен Бюхи в С&2] . Именно, Бюхи показал, что в качестве f можно взять характеристическую функцию множества значений экспоненты d*, d € ^ . Подход Бюхи основан на его результатах о монадических теориях и на кодировке чисел конечными множествами. Этот подход не позволял выяснить вопрос о разрешимости теорий ту ■ гу, где f - скажем характеристическая функция множества факториалов, или функция а: •-» 2 х, В той же работе Бюхи, обобщая результат Патнэма из [ Р], установил неразрешимость если f - характеристическая функция множества значений произвольного полинома (от одной переменной) степени выше первой. Там же Бюхи поставил проблему существования характеристической функции f , для которой теория г у неразрешима, но в ней определимы не все рекурсивные отношения (или, что эквивалентно, не все арифметические отношения). В работе автора Lei проблема Бюхи получила положительное решение (теорема б гл. I диссертации), что было приложением общего метода доказательства разрешимости теорий вида У/ и ту • Зтот метод позволил также установить разрешимость , для характеристических функций множества факториалов, множества чисел Фибоначчи и др.

Перечисленные результаты о разрешимости элементарных теорий J*+J!}Tf касались функций / с конечным числом значений. Напомним, что в случав монадических теорий естественно возникающие функции с бесконечным числом значений приводят к неразрешимым теориям. Развитие методов работы Гс2] показало, что для элементарных теорий ситуация иная. В докладе автора на Пятой Всесоюзной конференции по математической логике были приведены первые результаты в этом направлении, касающиеся теорий с монотонными функциями / • В дальнейшем удалось упростить используемую технику и расширить область ее применения. Оказалось, что для широкого класса монотонных функций ^ , содержащего основные естественно возникающие примеры, теории 7"*~f и !Tf разрешимы. Мы приведем теперь, в несколько ослабленном,для упрощения формулировки, виде, соответствующие результаты из работы Сс^3«

Пусть f - вычислимая функция, эффективно удовлетворяющая условию

X —* о°

Тогда теория разрешима. (Следствие i гл. Ш).

В случав теории Т'*/ предыдущего условия на скорость роста функции ^ явно не достаточно, ведь этому условию удовлетворяют, например*, полиномы, а для них теория неразрешима. Также ясно, что помимо'условия на скорость роста необходимы и некоторые условия, касающиеся делимости значений f .

Пусть £ вычислимая функция, эффективно удовлетворяющая следующим двум условиям одновременно; ii

2) для произвольного та, остатки от деления на пп. чисел fd), f(2) . образуют периодическую последовательность.

Тогда теория г v разрешима. (Следствие 2 гл. Пятаковы основные результаты, относящиеся к разрешимости теорий 7~У и T^f * Разработанные для доказательства разрешимости методы позволили, как это часто бывает, решить ряд вопросов, относящихся к определимости в этих теориях. Об этом будет говориться далее, в изложении содержания диссертации, к которому мы сейчас переходим.

В первой главе диссертации вводятся основные объекты изучения - элементарные и монадические теории рассматриваемых структур, приводятся некоторые известные результаты о них. Даются также определения, касающиеся сверхелов. Кроме того, в гл. I содержатся некоторые результаты общего характера, относящиеся не только к основным структурам, изучаемым в диссертации, но и к другим структурам. Во-первых, здесь вводится и исследуется понятие разделенной структуры, во-вторых, излагается обобщенный метод элиминации кванторов. Разделенные структуры применяются далее при изучении определимости; обобщенный метод элиминации кванторов - при доказательстве разрешимости.

Вторая глава посвящена изучению монадических теорий. Основным результатом ее является построение системы понятий и конструкций, связанных с наличием повторяемости "по модулю заданной конгруэтнос-ти" в произвольной бесконечной последовательности символов (сверхслове). Центральным здесь является понятие индекса, идейно связанное с понятием ранга, используемом в классификации периодических слов (см. СД] ). Технические результаты, связанные с этим понятием, составляют содержание лемм 1-8. Из этих лемм непосредственно вытекает теорема 1 - критерий разрешимости монадической теории Jt 7W* для произвольного сверхслова "W* ; упрощенная форма этого критерия (Следствие 3) приводилась выше во введении. Затем отдельно рассматривается случай почти периодических сверхслов, т.е. таких сверхслов "W* , что всякое слово содержится ъттолько в начальном или в каждом отрезке W" подходящей длины. Для таких сверхслов V7 разрешимость JA, 7"W оказывается эквивалентной их эффективной почти периодичности (следствие 2). Почти периодические сверхслова образуют класс, представляющий интерес с точки зрения символической динамики (раздела теории динамических систем, см. ГАЯ] ^ [Л] [ 1АЗ )• Отметим, что в символической динамике обычно рассматриваются не сверхслова, а двойные сверхслова -- отображения множества всех целых чисел 12. в конечный алфавит Т . Приведем результаты, которые дает метод главы П в применении к этим объектам. Следуя £ И ] назовем двойное сверхслово рекуррентным, если никакое слово не имеет ни самого левого ни самого правого вхождения в него, и транзитивным, если в него входит любое слово в алфавите 21 • В следствии 4 теоремы i доказывается, что теория рекуррентного двойного сверхслова полностью определяется тем, какие слова входят в \J . В силу этого все рекуррентные транзитивные имеют одну и ту же теориюJ/i J W,;3Ta теория разрешима. Весьма частным случаем этого утверждения оказывается следующая теорема символической динамики (см. [Н] , п.И): все рекуррентные транзитивные W имеют одно и то же число прообразов при всяком заданном эндоморфизме символического потока. Метод главы "П применим также для изучения определимых в теории Jb J отображений. В теореме 2 строится класс преобразователей, позволяющих решать проблему униформизации: построенный по формуле ^f5 (X, У)языка лт преобразователь перерабатывает всякое сверхслово Л для которого найдется Y , обращающее Ф(Х,У)в истину, в некоторое Y с таким свойством. Затем в главе П вводится понятие (бесконечного) произведения, обобщающее понятие блочного произведения символической динамики, см. [К], LJ] и применимое для построения сверхслов с заданными свойствами. В такое произведение оказывается разложимым любое сверхслово. Если процесс построения бесконечного произведения эффективен, то монадическая теория получаемого сверхслова разрешима (теорема 3), это дает еще один критерий разрешимости теорий вида jU, J W~ . Конструкция бесконечного произведения используется для построения (при всяком У\< ) предикатов R} F^ > ^ , Р^ таких, что теория Л, ^ Р0у.} Ри)неразрешима, а удаление из сигнатуры любого предиката из числа ft . . , R^ дает разрешимую теорию (теорема 4). Из этого утверждения легко получается положительный ответ на следующий вопрос Зифкеса из [S2] : существуют ли такие Р^ Р4 , что yWTt /\V; Рв Р± ) разрешима и предикат Rt при i =г oi не определим в JlT ( AV-, P^L^.

Перечисленные в начале введения результаты, устанавливающие разрешимость теорий J^J / для различных ^ с конечным числом значений и неразрешимость для некоторых f с бесконечным множеством значений, порождают вопрос: Бывают ли вообще функции f с бесконечным множеством значений, для которых теория JiTf разрешима? Конечно, в такой постановке вопрос имеет очевидный положительный ответ, достаточно взять, например, ^ = ос -f £ . Поэтому представляет интерес поиск такой функции f , для которой ^ii разрешима, но £ не определима ни в какой разрешимой теории yCi J § Для Q , принимающей конечное число значений. Такие функции строятся в теореме 5 главы Д, причем, каждая из этих функций не определима ни в какой (даже неразрешимой) теории , где ^ принимает конечное число значений.

Построение можно грубо описать так: натуральный ряд разбивается на отрезки растущей длины, функция ^ япервкладывает половины" каждого из отрезков.

В третьей главе исследуются вопросы разрешимости и определимости для элементарных теорий вида f и 7и их расширений. В теореме 1 устанавливается связь элиминируемости кванторов в теории

Tvcw- сверхслово) с почти периодичностью W.

Далее рассматривается следующая ситуация. Пусть в натуральном ряде выделено подмножество R , на котором задана произвольная сигнатура g . Если кроме того на самом натуральном ряде задана структура ( AV; 4 У (как в теореме 2) или ^ /\У) (как в теореме 4), то можно свести проблему разрешения возникающей теории (включающей и эту структуру и ( R к проблеме разрешения некоторого просто устроенного расширения теории структуры. Наконец, мы получаем условия разрешимости теорий (в теореме 3) и f (в теореме 5), где f принадлежит определяемым в гл. J классам монотонных функций; следствия этих теорем уже формулировались во введении. Добавим к этому, что из теоремы 5 вытекает также разрешимость теории

Двоичная система счисления устанавливает взаимнооднозначное соответствие между конечными подмножествами натурального ряда и натуральными числами. Это соответствие распространяется на теории: слабой монадической теории структуры К Л^4 ) (как и любой структуры ^/V) Cf)t где О - произвольная сигнатура) соответствует некоторая элементарная теория. Бюхи утверждал ( Г&2], теорема 4), что в смысле определимости эта теория эквивалентна Т+ , где PWz одноместный предикат, выделяющий степени двойки. Макнотон в [ Мс М2] указал ошибку в рассуждении Бюхи и предположил, что его утверждение неверно. Эта гипотеза Макното-на доказывается в следствии 3 главы I.

Выше уже говорилось, что в работе [с2] был получен ответ на вопрос Бюхи о существовании неразрешимых теорий вида в которых определимы не все разрешимые отношения. В этой работе доказательство опиралось на теоремы, которые мы приводим в третьей главе. Однако возможен и несколько иной ход рассуждений, использующий теоремы второй главы. Именно так получается этот результат в завершающей диссертацию теореме 6 клавы Ш.

Результаты диссертации опубликрваны в работах

С1], Ссг].

Они докладывались на Всесоюзных конференциях по математической логике (см. [СЬ\ на научно-исследовательском семинаре по математической логике и других семинарах кафедры математической логики МГУ, на Ленинградском семинаре по конструктивной математике и математической логике.