Вычислимые линейные порядки и η-представимость

• Автор: Зубков, Максим Витальевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Казань
• Количество страниц: 83 с.

Содержание
Введение
Глава 1. Предельно монотонные функции и 77-схожие линейные порядки
§1.1. Некоторые свойства предельно монотонных функций
§1.2. ц-схожие линейные порядки
Глава 2. Сильно 77-прєдставимьіе множества и степени
§2.1. Объединение Е§— и П—множеств
§2.2. Множества и степени сильно 77-представимые и 77-представимые
по неубыванию
§2.3. Сильно 77-представимые степени в разностной иерархии
Глава 3. Начальные сегменты вычислимых линейных порядков с дополнительными вычислимыми предикатами
§3.1. начальные сегменты
§3.2. Щ начальные сегменты
Литература

Список условных обозначений
ш множество неотрицательных целых чисел, порядковый
тип натуральных чисел Г] порядковый тип счетного плотного линейного порядка
без наибольшего и наименьшего элементов С порядковый тип целых чисел
fog суперпозиция двух функций fug
<р(х) I функция <р в точке х определена
ip(x) |= у р(х) определена и равна у
р(х) I функция <р в точке х неопределена
dom( rang(ip) область значений функции <р
graph(f) {(х, у) у = /(ж)}, график функции
epigr(f) {{ж, у) I у > f(x)}, надграфик функции
/ функция, определяемая по функции / двух аргумен-
тов равенством /(ж) = lim inf f{x, s)
s—»oo
A кардинальное число (мощность) множества А
Ха характеристическая функция множества А
А дополнение множества А
А — В АП В, теоретико-множественная разность А и В
(ж, у) значение стандартной функции пары на аргументах х

3 существует
V для любого
3°°ж существует бесконечно много х таких, что
3!ж существует единственный х такой, что
Введение
В представленной работе изучаются конструктивные или, другими словами, алгоритмические свойства линейных порядков и их типов. Исследование конструктивных свойств алгебраических структур началось в 50-ых годах XX века с работ А. И. Мальцева, М. Рабина и других математиков и с тех пор активно развивается.
Одно из направлений исследований конструктивных свойств линейных порядков было начато К. Джокушем. Он ввел понятие степени типа изоморфизма структуры А, как наименьшую из степеней, содержащих представление структуры А. Применительно к линейным порядкам это определение оказалось не очень полезным. Л. Рихтер [30] установила, что если А — порядковый тип имеющий степень, то эта степень вычислима, и если А — подпоря-док <5, то существует такой подпорядок В = А, что нижняя грань степеней А и В есть 0. Техника доказательства этих утверждний может быть расширена на широкий класс структур. Л. Рихтер получила теоретико-структурный результат, который включает, как частный случай, результат о линейных порядках. Некоторые структуры могут иметь отличную от 0 степень, например, группы или решетки [30].
Естественным вопросом является проблема существования вычислимой структуры, изоморфной дайной. Эта проблема получила наибольшее развитие в исследованиях отечественных и зарубежных математиков, например, Л. Фейнера, С. С. Гончарова, К. Джокуша, Дж. Найт. Диссертационная работа лежит в русле этих исследований. Так как существует континуум попарно неизоморфных друг другу счетных линейных порядков, сложно надеяться на получение простого описания порядковых типов, имеющих вычислимые представления. Поэтому, как правило, рассматриваются типы линейных порядков с какими-либо дополнительными ограничениями. Так, характериза-

Глава
Сильно ?7~представимые множества и степени
Вторая глава посвящена изучению сильно -представимых и -представимых по неубыванию множеств. В первом параграфе обобщаются приведенные во введении результаты Дж. Розенштейна и С. Феллнера о сильной 77-представимости 2" и П-множеств, что является продвилсением описания сильно 77-представимых множеств и, следовательно, степеней в арифметической иерархии.
Во втором параграфе получено полное описание всех 77-представимых по неубыванию степеней. А именно, доказано что каждая Д§ степень 77-представима по неубыванию. Учитывая результат Харриса получаем, что существует 77-представимое по неубыванию множество не имеющее вычислимого сильного 77-представления. Более того, это множество не является Т-эквивалентным ни какому сильно 77-представимому множеству.
Кроме того, показано, что каждая сильно 77-представимая степень содержит множество, являющееся рангом некоторой О'-предельно монотонной псевдовозрастающей на функции. Таким образом, получено описание сильно 77-представимых степеней в терминах О'-нределыю монотонных функции.
В третьем параграфе продолжается изучение вопроса, частично затронутого в параграфе 1 данной главы, а именно, уровней в разностной иерархии степеней (релятивизованной относительно 0'), содержащих сильно 77-предста-вимые мнолсества. В первом параграфе установлено, что каждая степень, содержащая множество уровня 2, содержит сильно 77-представимое множество. Это построение не удается продолжить естественным образом на более высокие уровни. В третьем параграфе предложена другая конструкция, которая позволяет доказать, в частности, что каждое таблично сводящееся к 0" множество т-эквивалентно некоторому сильно 77-представимому множеству.