Содержание к диссертации
Введение
Глава I Некоторые общие определения и теоремы 13
Глава II Монадические теории 25
Глава III Элементарные теории 69
Литература 83
Введение к работе
Пусть задана функция ^ , определенная на натуральном ряде Л> и принимающая значения токе в /w Во многих случаях при изучении свойств этой функции оказывается естественным описывать эти свойства на некотором логическом языке L . Так же как и в других подобных ситуациях, например, при описании свойств группы, здесь возникает логическая теория некоторой структуры, т.е* множество всех истинных утверждений о рассматриваемой структуре, записываемых на языке L Нас будут интересовать свойства функций, связанные с имеющимися на натуральном ряде отношением порядка ^ и операцией сложения + Таким образом, будут изучаться теории структур <^ /V; ^ f. > и ( /)/; +, / > . (В силу того, что порядок ^ можно определить через 4- , рассмотрение структуры ( /і/; -t, ) сводится к рассмотрению структуры
Центральным для нашего исследования будет вопрос о разрешимости возникающих теорий* Дальнейшее (по сравнению с монадической теорией) расширение логических средств языка, за счет введения кванторов по одноместным функциям из AV в AV и т.д., приводит к неразрешимым логическим теориям независимо от наличия какой--либо структуры на Л" (Простое доказательство этого известного факта будет приведено в гл. I). Точно так же заведомо неразрешима монадическая теория любой структуры на AV, в сигнатуру которой входит 4- (см., например, С Е R1 ) йтак, мы приходим к рассмотрению теорий следующих трех классов: монадические теории структур (/і/; ^ f}t обозначаемыеyUTf , элементарные теории структур (/V', ^ , f >i обозначаемые Т$ % элементарные теории структур ^y\V; -+, | >, обозначаемые 7*^? Будем использовать аналогичные обозначения JiT, 7* и J, когда сигнатура вовсе не содержит f . Элементарную теорию произвольной структуры У будем обозначать Т У монадическую теорию -
Конечно, необходимым условием разрешимости каждой из теорий Jk Т -f , Т+f и T*f служит вычислимость функции f . Легко показать, что это условие не является достаточным даже в случав, когда f - характеристическая. Пример вычислимой характеристической функции /, для которой теория Tf неразрешима,построен в работе [ ТЗ ] , аналогично пример для теории U/CC Tf был приведен в fBL2] .
Мы начнем с исторического обзора результатов (включая результаты диссертации), относящихся именно к проблеме разрешимости рассматриваемых теорий. Сначала речь будет идти о ионадических теориях, потом - об элементарных.
Как известно (см. в1]) монадическая, (а, значит, и элементарная) теория структуры - периодические (как и всюду в дальнейшем, мы считаем, что периодическая функция может иметь предпериод), оС ; Л/ —* { О, 4 J, |Ь : /ІК-» ^. (см. L^O)« с другой стороны, как следует из результатов {ji]t если для некоторой строго монотонной функции f теория И Tf разрешима, то эта функция определима в Jtt,T . - 5~-
Таким образом, для строго монотонных не определимых в Ji Т функций (а основные естественно возникающие функции с бесконечным множеством значений таковы) теория J J~f оказывается неразрешимой.
Иной оказывается ситуация, когда множество значений функции f конечно, например, когда f - характеристическая функция. Здесь уже не существенно, являются ли значения т натуральными числами или элементами заданного конечного множества ^ (в одном из примеров ниже этим множеством будет | О, d,-l] ). Такие функции часто называют также сверхсловами в алфавите 2? . Атомарными формулами теории, использующими символ
Для всякого вычислимого сверхслова >f следующие две проблемы алгоритмически сводятся одна к другой: -Ї) проблема разрешения для М (Tf \
2) проблема: по всякому регулярному множеству А выяснить, существует ли конец сверхслова / , не содержащий элементов из А, и, если существует, то указать какой-нибудь такой конец.
Наряду с монаднческой теорией данной структуры естественно рассматривать также слабую монадическую, в которой множественные переменные пробегают только конечные подмножества. Бюхи и Ландвебер поставили вопрос: вытекает ли для произвольного сверхслова
Перейдем теперь к элементарным теориям. Конечно, как и для мояадических теорий, можно утверждать разрешимость теории У"*У (и, следовательно, 7f ) для 1' / разрешима, был построен Бюхи в С&2] Именно, Бюхи показал, что в качестве f можно взять характеристическую функцию мно- жества значений экспоненты d , cL G AV # Подход Бюхи ос нован на его результатах о монадических теориях и на кодировке чи сел конечными множествами. Этот подход не позволял выяснить вопрос о разрешимости теорий Тf и ^ f , где f - скажем характерис тическая функция множества факториалов, или функция я: *—» 2 . В той же работе Бюхи, обобщая результат Патнэма из [ PJ, установил неразрешимость 7~*/, если / - характеристическая функция мно жества значений произвольного полинома (от одной переменной) сте пени выше первой. Там же Бюхи поставил проблему существования ха рактеристической функции f , для которой теория нераз решима, но в ней определимы не все рекурсивные отношения (или, что эквивалентно, не все арифметические отношения). В работе автора Гс2. проблема Бюхи получила положительное решение (георема б гл. I дис сертации), что было приложением общего метода доказательства разре шимости теорий вида Этот метод позволил также установить разрешимость У+/ , для характеристических функций множества факториалов, множества чисел Фибоначчи и др.
Перечисленные результаты о разрешимости элементарных теорий T+
Пусть f - вычислимая функция, эффективно удовлетворяющая условию #«. (U* + D- /( = )) = + <~- л: —* о
Тогда теория J 4 разрешима. (Следствие і гл. Ш). В случав теории Т f предыдущего условия на скорость роста функции f явно не достаточно, ведь этому условию удовлетворяют, например*, полиномы, а для них теория J f неразрешима. Также ясно, что помимо'условия на скорость роста необходимы и некоторые условия, касающиеся делимости значений f .
Пусть f вычислимая функция, эффективно удовлетворяющая следующим двум условиям одновременно; hJf(""/((*>)-+*.
2) для произвольного пгі остатки от деления на пп. чисел f(o) fd) f(2.) ... образуют периодическую последовательность.
Тогда теория разрешима. (Следствие 2 гл. Ш).
Таковы основные результаты, относящиеся к разрешимости теорий jf и j /. Разработанные для доказательства разрешимости методы позволили, как это часто бывает, решить ряд вопросов, относящихся к определимости в этих теориях. Об этом будет говориться далее, в изложении содержания диссертации, к которому мы сейчас переходим.
В первой главе диссертации вводятся основные объекты изучения - элементарные и монадические теории рассматриваемых структур, приводятся некоторые известные результаты о них. Даются также определения, касающиеся сверхелов. Кроме того, в гл. Ї содержатся некоторые результаты общего характера, относящиеся не только к основным структурам, изучаемым в диссертации, но и к другим структурам. Во-первых, здесь вводится и исследуется понятие разделенной структуры, во-вторых, излагается обобщенный метод элиминации кванторов. Разделенные структуры применяются далее при изучении определимости; обобщенный метод элиминации кванторов - при доказательстве разрешимости.
Вторая глава посвящена изучению монадических теорий» Основным результатом ее является построение системы понятий и конструкций, связанных с наличием повторяемости "по модулю заданной конгруэтнос-ти" в произвольной бесконечной последовательности символов (сверх-слове). Центральным здесь является понятие индекса, идейно связанное с понятием ранга, используемом в классификации периодических слов (см. L^J ) Технические результаты, связанные с этим понятием, составляют содержание лемм Ї-8. Из этих лемм непосредственно вытекает теорема Ї - критерий разрешимости монадической теории Jt JW для произвольного сверхслова \J ; упрощенная форма этого критерия (Следствие 3) приводилась выше во введении. Затем отдельно рассматривается случай почти периодических сверхслов, т.е. таких сверхслов \Дл , что всякое слово содержитсяштолько в начальном или в каждом отрезке Vv подходящей длины. Для таких сверхслов "\л/ разрешимость yU, 7 W оказывается эквивалентной их эффективной почти периодичности (следствие 2). Почти периодические сверхслова образуют класс, представляющий интерес с точки зрения символической динамики (раздела теории динамических систем, см. [АЯ] СП] [IA]). Отметим, что в символической динамике обычно рассматриваются не сверхслова, а двойные сверхслова -- отображения множества всех целых чисел 12. в конечный алфавит
Г . Приведем результаты, которые дает метод главы П в применении к этим объектам. Следуя Н ] назовем двойное сверхслово рекуррентным, если никакое слово не имеет ни самого левого ни самого правого вхождения в него, и транзитивным, если в него входит любое слово в алфавите 21 В следствии 4 теоремы і доказы- --/0- вается, что теория y4l JW *^ ;U J (Ж'^^^т рекуррентного двойного сверхслова \jj полностью определяется тем, какие сло ва входят в \s/ . В силу этого все рекуррентные транзитивные \Jимеют одну и ту же теорию J/i J W,;3Ta теория разрешима. Весьма частным случаем этого утверждения оказывается следующая теорема символической динамики (см. [HJ , п.И): все рекуррентные тран зитивные \л/" имеют одно и то же число прообразов при всяком заданном эндоморфизме символического потока. Метод главы "Й применим также для изучения определимых в теории Jb J отображений. В теореме 2 строится класс преобразователей, позволяющих решать проблему униформизации; построенный по формуле Я"5 (-Х, у)языка лт преобразователь перерабатывает всякое сверхслово Л длякоторого найдется j , обращающее ^(К^Оъ истину, в некото рое Y с таким свойством. Затем в главе П вводится понятие (бес конечного) произведения, обобщающее понятие блочного произведе ния символической динамики, см. и применимое для по строения сверхслов с заданными свойствами. В такое произведение оказывается разложимым любое сверхслово. Если процесс построения бесконечного произведения эффективен, то монадическая теория получаемого сверхслова разрешима (теорема 3), это дает еще один критерий разрешимости теорий вида jU, J W~ . Конструкция бес конечного произведения используется для построения (при всяком 'И ) предикатов R t Р± > #.ч, Н^ таких, что теория М, J (Л*> ^, R>,...j Ри)неразрешима, а удаление из сигнатуры любого предиката из числа ft Н^ дает разрешимую тео рию (теорема 4). Из этого утверждения легко получается положи тельный ответ на следующий вопрос Зифкеса из [S2J : существуют ли такие Рв^ Р , что Ji J ( /!/; Рв Р± ) разрешима и преди кат Pt при і =г о,і не определим в Jl7 ( fi/; ^5 P^_lX
Перечисленные в начале введения результаты, устанавливающие разрешимость теорий JA,J f для различных ^ с конечным числом значений и неразрешимость для некоторых f с бесконечным множеством значений, порождают вопрос: Бывают ли вообще функции f с бесконечным множеством значений, для которых теория разрешима? Конечно, в такой постановке вопрос имеет очевидный положительный ответ, достаточно взять, например, f (<*-) = ос -f і . Поэтому представляет интерес поиск такой функции f , для которой JA Jf разрешима, но / не определима ни в какой разре-шимой теории yCi J Q Для й , принимающей конечное число значений. Такие функции строятся в теореме 5 главы П, причем, каждая из этих функций не определима ни в какой (даже неразрешимой) теории JA, J а , где а принимает конечное число значений. Построение можно грубо описать так: натуральный ряд разбивается на отрезки растущей длины, функция і япервкладывает половины" каждого из отрезков.
В третьей главе исследуются вопросы разрешимости и определимости для элементарных теорий вида J f и J fn их расширений. В теореме 1 устанавливается связь элиминируемости кванторов в теории Ур/CW- сверхслово) с почти периодичностью Далее рассматривается следующая ситуация. Пусть в натуральном ряде выделено подмножество k , на котором задана произвольная сигнатура g Если кроме того на самом натуральном ряде задана структура ( AV; 4 У (как в теореме 2) или ^ /У) -+), (как в теореме 4), то можно свести проблему разрешения возникающей теории (включающей и эту структуру и ( К >?>) к проблеме разрешения некоторого просто устроенного расширения теории структуры. Наконец, мы получаем условия разрешимос-ти теорий 7^f (в теореме 3) и J~+ f (в теореме 5), где f принадлежит определяемым в гл.J классам монотонных функций; следствия этих теорем уже формулирова- -да- лись во введении. Добавим к этому, что из теоремы 5 вытекает также разрешимость теории
Двоичная система счисления устанавливает взаимнооднозначное соответствие между конечными подмножествами натурального ряда и натуральными числами. Это соответствие распространяется на теории: слабой монадической теории структуры <С $ ; 4 ) (как и любой структуры ^ИИ) o)t где О - произвольная сигнатура) соответствует некоторая элементарная теория. Бюхи утверждал ( Lb2j, теорема 4), что в смысле определимости эха теория эквивалентна СГ+ Pw , где rw одноместный предикат, выделяющий степени двойки. Маквотон в указал ошибку в рассуждении Бюхи и предположил, что его утверждение неверно. Эта гипотеза Макнотона доказывается в следствии 3 главы I.
Выше уже говорилось, что в работе LC2J был получен ответ на вопрос Бюхи о существовании неразрешимых теорий вида ^7"+^> в которых определимы не все разрешимые отношения. В этой работе доказательство опиралось на теоремы, которые ыы приводим в третьей главе. Однако возможен и несколько иной ход рассуждений, использующий теоремы второй главы. Именно так получается этот результат в завершающей диссертацию теореме 6 клавы I.
Результаты диссертации опубликованы в работах Они докладывались на Всесоюзных конференциях по математической логике (см. [СЪ\ [С4]), на научно-исследовательском семинаре по математической логике и других семинарах кафедры математической логики МГУ, на Ленинградском семинаре по конструктивной математике и математической логике.
Некоторые общие определения и теоремы
В настоящей главе будут даны общие определения, касающиеся математических объектов, которые мы будем изучать в дальнейшем, и изложены два общих подхода. Один опирается на понятие разделенной структуры и будет использован при харантеризации определимости. Другой - обобщенная элиминация кванторов - будет использован при доказательстве разрешимости интересующих нас теорий. Хотя в диссертации оба подхода будут применяться только к структурам вида ( AV; } f ) и ( fw , + , f / , но они никак не используют специфику этих структур. Поэтому соответствующие определения и теоремы вынесены в отдельную главу.
Наборы объектов и переменных будем обозначать через U., А, X и т.д. Структурой мы будем называть множество с заданными на нем отношениями и операциями, обозначенными символами. Это множество - носитель структуры -у нас всегда будет множеством всех натуральных или всех целых чисел. Список обозначений для отношений (предикатных символов) и операций (функциональных символов) называется сигнатурой. Если сигнатура содержит только предикатные символы, она называется предикатной, если только функциональные символы - функциональной.
Для заданной сигнатуры элементарный язык этой сигнатуры определяется обычным образом. Отметим лишь, что равенство считается логическим символом, всегда имеющимся в языке и не включаемым в сигнатуру.
Что же касается монадического языка, то существует несколько различных способов его введения, удобных с той или иной точки зрения. Все эти способы эквивалентны между собой в довольно сильном смысле. Мы не будем формально учтонять в чем состоит эквивалентность этих языков. Ограничимся лишь замечанием, что разрешимость мояадической теории данной структуры не зависит от того, в каком из перечисленных ниже смыслов мы понимаем монадическии язык. Переходим к описаниям. Для фиксированной структуры опишем 4- монадических языка.
1) Помимо предметных переменных элементарного языка имеются множественные переменные. Помимо атомарных формул элементарного языка есть еще формулы X є X , где Л - множественная переменная, X - терм (элементарного языка). В индуктивном определении формулы разрешается навешивать кванторы по множественным переменным, Семантика - очевидна.
2) То же, что иі), но вместо множественных добавляются одноместные предикатные переменные, новые атомарные формулы имеют вид X (г).
3) Пусть 2 { о, ± -- J - конечное или счетное множество символов. Помимо предметных переменных есть одноместные функциональные переменные, интерпретируемые как функции, область определения которых - множество о , а области значений включены в 21 Помимо атомарных формул элементарного языка допускаются еще формулы вида A (w = c , где Х- функциональная переменная, Т - терм элементарного языка, є S .
Монадические теории
Основное содержание этой главы состоит в выработке системы алгебраических понятий, предназначенных для изучения монадических теорий вида jU J W9 изучению некоторых свойств этих понятий (основные свойства сформулированы в виде лемм 1-8), и их использованию в доказательстве результатов, относящихся к разрешимости и определенности в рассматриваемых теориях.
Начнем с определения используемых в данной главе понятий.
Для всякого множества А слов в некотором алфавите S , обозначим через А итерацию А - множество всех слов, являющихся произведениями элементов А , включая пустое слово. Конгруэнтностью будем называть любое отношение эквивалентности конечного индекса на t , инвариантное относительно умножения на слово справа и слева. Пусть X - некоторая конгруэнтность. Класс, содержащий слово Г , получает естественное обозначение ?ае; при (u,v-) с мы будем писать ц, і? и говорить, что Ц, и лг - f-конгру-энтяы; классы конгруэнтности 2? мы будем иногда называть классами, число таких классов будем обозначать Y Важнейшим из элементарных свойств конгруэнтностей для нас будет то, что пересечение двух конгруэтностей - снова конгруэнтность. Ясно, что всякая конгруэнтность имеет естественное конструктивное задание; в качестве такого задания можно взять, например, какой-нибудь список имен для всех классов конгруэнтности, с указанием, какой класс содержит пустое слово и для всякого класса К и всякого символа CL є 2, в каком классе содержится множество t Я, Регулярным множеством будем называть всякое объединение каких-либо классов какой-либо конгруэнтности. Регулярные множества образуют булевую алгебру, замкнутую относительно умножения (множеств слов в свободной полугруппе) и итерации. Для произвольного сверхслова О через LtW О обозначим множество всех символов, встречающихся в Су бесконечное число раз.
Первый пример связи между конгруэнтностями и логическими теориями дает лемма Ї. Прежде чем ее сформулировать, приведем одно техническое определение.
Элементарные теории
В настоящей главе будет доказана разрешимость ряда теорий вида Tf « ту и их расширений. Попутно будут найдены условия, при которых в этих теориях элиминируются кванторы. Основным методом доказательства является метод обобщенной элиминации кванторов. Мы начнем с простейшего случая J f , где f принимает конечное число значений (теорема Ї). Затем мы рассмотрим ситуации, когда в натуральном ряде выделяется некоторое подмножество R , на котором задается произвольная сигнатура J . Оказывается, вели кроме того на самом натуральном ряде задана структура ( /V; ) (как в теореме 2), или ( А , +), (как в теореме 4), то можно свести проблему разрешимости возникающей теории к проблеме разрешимости подходящих расширений теории «/(К ,?). Наконец, мы получаем условия разрешимости теорий Jf (в теореме 3) и J f (в теореме 5), где f принадлежит определяемым ниже классам монотонных функций. В качестве следствия из теорем настоящей главы получается доказательство гипотезы Макнотояа (следствие теоремы 5). Отметим сразу же, что как правило мы, в целях технического удобства будем использовать структуры с носителем 2 , а резул ьтаты для структур на натуральном ряде тривиально из них получаются.
В работе [CZl был получен ответ на один вопрос Бюхи, касавшийся элементарных теорий вида j / . Там этот ответ получался как следствие из приводимых ниже теорем. Однако он может быть получен и как следствие результатов главы ТГ о монадических теориях, что и проделывается в завершении настоящей главы (теорема б).
Пусть \J сверхслово в алфавите 21 Определим некоторую элементарную теорию, которую мы будем использовать для описания свойств W Термами будем считать с 9 Х4с t х-с[ где с є где t, б - термы, хє 2» ЭТУ теорию обозначим Ана логично, если W - двойное сверхслово, определим термы как с, х + с Сс Ж) , атомарные формулы определим как для сверхслова и полученную теорию также обозначим 7 W .
Как видно из определений, то, что мы обозначаем j W не является в точности элементарной теорией структуры №, 4 } W), Например, мы добавили в сигнатуру +1 . Однако для вопросов разрешимости и определимости это неважно. Аналогичная ситуация будет иметь место и в дальнейшем.
