Введение к работе
Результаты диссертации относятся к теории конструктивных моделей - области математики, возникшей на стыке теории алгоритмов и теории моделей почти одновременно в работах как западных математиков, где такие модели называются рекурсивными, так и в трудах А.И.Мальцева.
Особенно стоит отметить основополагающую статью А.И. Мальцева [13] , где обобщены методы изучения конструктивных алгебраических объектов и заложены основы теории, а также намечены пути дальнейшего исследования.
При этом именно использование понятия нумерации позволяет с единой точки зрения взглянуть на природу вычислимости алгебраических и теоретико-модельных конструкций и объединить методы теории алгоритмов с методами алгебры и теории моделей.
В монографии Ю.Л.Ершова [ 12 J подведены итоги первого этапа развития теории конструктивных моделей и сформулированы две основные проблемы: проблема существования конструктивиза-ции модели (возможно, со специальными свойствами) и проблема числа неэквивалентных конструктивизаций.
Со второй проблемой тесно связаны проблемы существования и характеризации моделей конечной и бесконечной алгоритмической размерности, а также автоустойчивых моделей, которые по существу уже рассматривались в [19 ] , а также в [21 7
Поскольку понятие автоустойчивости является очень естест-
венным - речь идет о единственности с точностью до автоэквивалентности конструктивизации у конструктивной модели - оно исследовалось в работах очень многих авторов, но особенно стоит отметить работы С.С.Гончарова Г 5-9] . Так, в [9J построен пример і -однородной неавтоустойчивой модели конечной алгоритмической размерности, а в [ 5, 6] показана связь автоустойчивости с теоретико-модельным понятием і-полноты, дан критерий автоустойчивости для 2-конструктивных моделей в терминах вычислимого плотного семейства атомных 3 --формул с параметрами (семейства 3 -формул Скотта) и аналогичный критерий для понятия рекурсивной устойчивости в классе 1 -конструктивных моделей.
Настоящая диссертация связана с попыткой описания автоустойчивых моделей в теоретико-модельных терминах. Эту задачу удалось полностью решить в классе ±-конструктивных моделей и в некоторых других классах моделей, близких к полям алгебраических чисел.
В общем случае проблема существования такого описания остается открытой, поскольку работа [3~] , отрицательно отвечавшая на этот вопрос, содержит ошибку, что отмечается в главе 3 диссертации.
Автору удалось найти некоторое достаточное условие авто-устойчивости, формулируемое в терминах орбит элементов модели, которое оказалось также и необходимым для тех классов моделей, которые рассматриваются в диссертации.
Кроме того, предложен критерий рекурсивной устойчивости моделей (что соответствует автоустойчивости жестких моделей) в терминах некоторой новой сводимости конструктивизации, а
также введены и изучены понятия равномерной автоустойчивости по классам и по индексам конструктивизаций.
В диссертации используются методы теории алгоритмов и рекурсивных функций, в частности, метод приоритета с нарушениями, конечность которых устанавливается в ходе доказательства , метод элиминации кванторов в модифицированном виде для установления разрешимости 3-теории, а также широко применяются идея моделирования, аппарат теории категорий, а также аппарат и результаты из статей [7, 8] .
Все результаты диссертации являются новыми и обоснованы доказательствами.
Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты и методы могут найти применение как в теории конструктивных моделей, так и в теории алгоритмов и рекурсивных функций. Полученные результаты дают решение ряда проблем из теории конструктивных моделей, и могут быть использованы при чтении спецкурсов для студентов и аспирантов университетов.
Апробация. Результаты диссертации докладывались и анонсировались в разное время на семинарах ИМ СО РАН, НГУ ,
на логическом коллоквиуме Клини-90 (Варна, 1990), межреспубликанской конференции по математической логике (Казань, 1992), и международной конференции по математической логике памяти А.И.Мальцева (Новосибирск, 1994).
Основные результаты диссертации опубликованы в работах автора [23 - 27]
Структура диссертации. Диссертация состоит из введения, трех глав и списка литературы. Названия глав следующие: "Критерии автоустойчивости некоторых классов моделей", "Автоустойчивость 1 -разрешимых моделей", "Проблемаи описания автоустойчивых моделей". Объем диссертации - 89 страниц, список литературы включает 27 наименований.