Содержание
Введение 4
Глава 1. Предельно монотонные функции и ту-схожие линейные порядки 19
§1.1. Некоторые свойства предельно монотонных функций...........19
§1.2. ту-схожие линейные порядки ................................29
Глава 2. Сильно ту-представимые множества и степени 35
§2.1. Объединение Г*]— и П®—множеств.............................36
§2.2. Множества и степени сильно ту-представимые и ту-представимые
по неубыванию...............................................41
§2.3. Сильно ту-представимые степени в разностной иерархии .... 53
Глава 3. Начальные сегменты вычислимых линейных порядков с дополнительными вычислимыми предикатами 03
§3.1. начальные сегменты.........................................63
§3.2. 11§ начальные сегменты.....................................72
Литература 80
2
Список условных обозначений
uj множество неотрицательных целых чисел, порядковый
тип натуральных чисел т? порядковый тип счетного плотного линейного порядка
без наибольшего и наименьшего элементов £ порядковый тип целых чисел
fog суперпозиция двух функций / и д
<р(х) | функция (р в точке х определена
<р(х) |= у <р(х) определена и равна у
vK-T) Т функция <р в точке х неопределена
dom((p) область определения функции у?
гапд(ф) область значений функции ip
graph(f) {(х, у) \ у = /(ж)}, график функции /
epigr(f) {{х, у) \ у> f(x)}, надграфик функции /
/ функция, определяемая по функции / двух аргумен-
тов равенством f(x) = lim inf /(гг, s)
s—’СО
|Л| кардинальное число (мощность) множества А
Хл характеристическая функция множества А
А дополнение множества А
А — 13 АП В, теоретико-множественная разность А и В
(х, у) значение стандартной функции пары на аргументах х
и у
3 существует
V для любого
3°°:г существует бесконечно много х таких, что ...
3\х существует единственный х такой, что ...
\
3
Введение
В представленной работе изучаются конструктивные или, другими словами, алгоритмические свойства линейных порядков и их типов. Исследование конструктивных свойств алгебраических структур началось в 50-ых годах XX века с работ А. И. Мальцева, М. Рабииа и других математиков и с тех пор активно развивается.
Одно из направлений исследований конструктивных свойств линейных порядков было начато К. Джокушем. Он ввел понятие степени типа изоморфизма структуры А, как наименьшую из степеней, содержащих представление структуры А. Применительно к линейным порядкам это определение оказалось не очень полезным. Л. Рихтер [30| установила, что если А — порядковый тип имеющий степень, то эта степень вычислима, и если А — подпоря-док то существует такой подпорядок Б = А, что нижняя грань степеней А и Б есть 0. Техника доказательства этих утверждний может быть расширена на широкий класс структур. Л. Рихтер получила теоретико-структурный результат, который включает, как частный случай, результат о линейных порядках. Некоторые структуры могут иметь отличную от 0 степень, например, группы или решетки [30].
Естественным вопросом является проблема существования вычислимой структуры, изоморфной данной. Эта проблема получила наибольшее развитие в исследованиях отечественных и зарубежных математиков, например. Л. Фейнера, С. С. Гончарова, К. Джокуша, Дж. Найт. Диссертационная работа лежит в русле этих исследований. Так как существует континуум попарно пеизоморфных друг другу счетных линейных порядков, сложно надеяться на получение простого описания порядковых типов, имеющих вычислимые представления. Поэтому, как правило, рассматриваются типы линейных порядков с какими-либо дополнительными ограничениями. Так, характериза-
ция вычислимо представимых вполне упорядоченных типов не представляет большой сложности. В самом деле, если А какое-либо вполне упорядоченное арифметическое подмножество тогда порядковый тип А есть вычислимый ординал, следовательно, вычислимо представим [29], [31].
Для другого естественного типа линейных порядков — дискретного линейного порядка, Р. Ватником [32] было показано, что СР имеет вычислимое представление тогда и только тогда, когда р имеет П® представление (ясно, что любой дискретный линейный порядок представим в виде Сд, где С — тип естественного упорядочения целых чисел).
Доказательство этой теоремы предоставляет важный метод построения вычислимых представлений различных порядковых типов. М. Лерман [25], используя конструкцию, похожую на конструкцию в доказательстве теоремы Ватника, методом приоритета с бесконечными нарушениями на деревьях получил, что если А бесконечное Е^-множество, то существует вычислимый линейный порядок, имеющий порядковый тип:
С 4- 7го 4- £ 4- 711 4-...
где по, П1, ... — перечисление А в порядке возрастания. (Здесь предполагается, что 0 £ А).
Линейный порядок такого типа называется сильным С-представлением множества А. Если перечисление множества А берется не обязательно в порядке возрастания и, возможно, с повторениями, то такой порядок называется просто ^-представимым. С помощью алгоритма Тарского-Куратовского и результата М. Лермана легко проверить, что множество А имеет вычислимое ^-представление тогда и только тогда, когда имеет вычислимое сильное С-предс тавление, тогда и только тогда, когда А £ Ед.
Дж. Розенштейном [31] были рассмотрены р-схоэ/сие линейные порядки. Линейный порядок называется т/-схожим, если он не содержит бесконечных
5
блоков (по определению, что элементы лежат в одном блоке, если между ними не более конечного числа различных элементов). Дж. Розенштейн доказал, что если С вычислимый 77-схожий линейный порядок, то существует такая Дд-фуикция Р : ф —> №, что £ = ^ Используя технику, аналогичную
<7Є<3
доказательству теоремы Ватника, в частности, представление П^-множеств на деревьях, С. Феллиер [16] показал, что если Г является П^-функцией, то линейный порядок X] ^(я) имеет вычислимое представление. Аналогичный
результат имеет место и для Х^-функций. Возникает естественный вопрос, можно ли эти результаты распространить на Ад-уровень арифметической иерархии? М. Лерман и Дж. Розенштейн [26] построили такую Ад-функцию, что порядок X] Р(д) не имеет вычислимой копии. Болсс того, Р. Доуни [14] показал, что при этом функция / может иметь конечное число значений.
Эти результаты оставляют открытым следующий вопрос: если £ — вычислимый 77-схожий линейный порядок, то существует ли такая П^-фуикция Р : (ф —^ 1ГС, что £ = ^2 .Р(д)? Этот вопрос ставился в нескольких работах [31], [26], [14]. В работе [8], фактически, было показано, что если £ некоторый 77-схожий линейный порядок, мощность блоков которого ограничена некоторым числом, 'го С имеет вычислимую копию тогда и только тогда, когда существует такая функция F : (3 —> Е\т, что £ = ^ Р(д) и ергдг(Р) €
Аналогично определению С-представимых и сильно С-представимьтх множеств, можно определить 77-представимые и сильно //-представимые множества, соответственно заменив в исходных определениях С на 7/ — тип упорядочения рациональных чисел. Как видно из определения, 77-представления являются //-схожими линейными порядками. Нетрудно доказать, что 77-предета-вимые множества (то есть множества, имеющие вычислимые 77-представле-ния) принадлежат £д уровню арифметической иерархии [15]. Дж. Розеп-штейн (31) и С. Феллиер [16], соответственно, показали, что любое или
- Київ+380960830922