На правах рукописи

Зубков Максим Витальевич

Вычислимые линейные порядки и

-представимость

01.01.06 – Математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание ученой степени

кандидата физико-математических наук

Казань – 2009

Работа выполнена на кафедре алгебры и математической логики государственного образовательного учреждения высшего профессионального образования ”Казанский государственный университет им. В. И. Ульянова-Ленина“.

Научный руководитель: доктор физико-математических наук, профессор Арсланов Марат Мирзаевич,

Официальные оппоненты: доктор физико-математических наук, профессор Добрица Вячеслав Порфирьевич, доктор физико-математических наук, ведущий научный сотрудник Алаев Павел Евгеньевич.

Ведущая организация : государственное образовательное учреждение высшего профессионального образования ”Новосибирский государственный университет“.

Защита состоится 8 октября 2009 г. в 17.00 на заседании диссертационного совета Д 212.081.24 при ГОУВПО ”Казанский государственный университет им. В. И. Ульянова-Ленина“ по адресу: 420008, г. Казань, ул. Кремлевская, д. 35., конференц-зал библиотеки им. Н. И. Лобачевского.

С диссертацией можно ознакомиться в библиотеке Казанского государственного университета.

Автореферат разослан 2009 г.

Ученый секретарь диссертационного совета Д 212.081. к.ф.-м.н., доц. Еникеев А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. В представленной работе изучаются конструктивные или, другими словами, алгоритмические свойства линейных порядков и их типов. Исследование конструктивных свойств алгебраических структур началось в 50-ых годах XX века с работ А. И. Мальцева, М. Рабина и других математиков и с тех пор активно развивается.

Одно из направлений исследований конструктивных свойств линейных порядков было начато К. Джокушем. Он ввел степени типа изоморфизма структуры A, как наименьшую из степеней, содержащих представление структуры A. Применительно к линейным порядкам это определние оказалось не очень полезным. Л. Рихтер1 установила, что если A порядковый тип, имеющий степень, то эта степень вычислима, и если A подпорядок Q, то существует такой подпорядок B A, что нижняя грань степеней A и B есть = 0. Техника доказательства этих утверждений может быть расширена на широкий класс структур. Л. Рихтер получила теоретико-структурный результат, который включает, как частный случай, результат о линейных порядках.

Некоторые структуры могут иметь отличную от 0 степень, например, группы или решетки. Естественным является вопрос о существовании вычислимой структуры изоморфной данной. Эта проблема получила наибольшее развитие в исследованиях отечественных и зарубежных математиков, например, Л. Фейнера, С. С. Гончарова, К. Джокуша, Дж. Найт. Диссертационная работа лежит в русле этих исследований. Так как существует континуум попарно неизоморфных друг другу счетных линейных порядков, сложно надеяться на получение простого описания порядковых типов, имеющих вычислимые представRichter L. J. Degrees of Unsolvability of Models. – Ph. D. Thesis. – Urbana: University of Illinois at UrbanaChampaing. – 1997.

Там же.

ления. Поэтому, как правило, рассматриваются типы линейных порядков с какими-либо дополнительными ограничениями. Так, характеризация вычислимо представимых вполне упорядоченных типов не представляет большой сложности. В самом деле, если A какое-либо вполне упорядоченное арифметическое подмножество Q, тогда порядковый тип A есть вычислимый ординал, следовательно, вычислимо представим. Для другого естественного типа линейных порядков дискретного линейного порядка, Р. Ватником4 было показано, что имеет вычислимое представление тогда и только тогда, когда имеет 0 представление (ясно, что любой дискретный линейный порядок представим в виде, где тип естественного упорядочения целых чисел).

Доказательство этой теоремы предоставляет важный метод построения вычислимых представлений различных порядковых типов. Так М. Лерман5, используя конструкцию, похожую на конструкцию в доказательстве теоремы Ватника, методом приоритета с бесконечными нарушениями на деревьях получил, что если A бесконечное 0 множество, то существует вычислимый линейный порядок, имеющий порядковый тип:

+ n0 + + n1 +...

где n0, n1,... перечисление A в порядке возрастания. (Здесь предполагается, что 0 A).

/ Линейный порядок такого типа называется сильным -представлением множества A. Если перечисление множества A берется не обязательно в порядке возрастания и, возможно, с повторениями, то такой порядок называетRice H. G. Recursive and recursively enumerable orders // Trans. AMS. –1956. – V.83. – P.713–746.

Rosenstein J. Linear orderings. – New York: Academic Press, 1982. – 487 P.

Watnik R. A generalization of Tennenbaum’s Theorem on eectively nite recursive linear orderings // J. Symbolic Logic. – 1966. – V.31. – P.159–168.

Lerman M. On recursive linear orderings // Lecture Notes in Mathematics. – Berlin: Springer-Verlag. – 1981. – V.859. – P.132–142.

ся просто -представимым. С помощью алгоритма Тарского-Куратовского и результата М. Лермана легко проверить, что множество A имеет вычислимое -представление тогда и только тогда, когда оно имеет вычислимое сильное -представление, тогда и только тогда, когда A 0.

Дж. Розенштейном6 были рассмотрены -схожие линейные порядки. Линейный порядок называется -схожим, если он не содержит бесконечных блоков (по определению, элементы лежат в одном блоке, если между ними не более конечного числа различных элементов). Дж. Розенштейн доказал, что если L вычислимый -схожий линейный порядок, то существует такая функция F : Q N, что L F (q). Используя технику, аналогичную доказательству теоремы Ватника, в частности, представление 0 множеств на деревьях, C. Феллнер7 показал, что если F является 0 -функцией, то линейный порядок F (q) имеет вычислимое представление. Аналогичный результат имеет место и для 0 -функций. Возникает естественный вопрос, можно ли эти результаты распространить на 0 -уровень арифметической иерархии? М. Лерман и Дж. Розенштейн8 построили такую 0 -функцию, что порядок что при этом функция F может иметь конечное число значений.

F : Q N, что L F (q)? Этот вопрос ставился в нескольких работах. Аналогично определению -представимых и сильно -представимых мноRosenstein J. Linear orderings. – New York: Academic Press, 1982. – 487 P.

Fellner S. Recursive and Finite Axiomatizability of Linear Orderings // Ph.D. Thesis. – Rutgers Univsity.

– 1976.

Lerman M., Rosenstein J. G. Recursive linear orderings // Stud. Logic Found. Math. – 1982. – V.109. – P.132-142.

Downey R. G. Computability theory and linear orderings // Handbook of computable algebra. – Amsterdam:

Elsevier, 1998. – V.2. – P.823–976.

Rosenstein J. Linear orderings. – New York: Academic Press, 1982. – 487 P.

жеств, можно определить -представимые и сильно -представимые множества, соответственно заменив в исходных определениях на тип упорядочения рациональных чисел. Как видно из определения, -представления являются -схожими линейными порядками. Нетрудно доказать, что -представимые множества (то есть множества, имеющие вычислимые -представления) принадлежат 0 -уровню арифметической иерархии.11 Дж. Розенштейн и С. Феллнер13, соответственно, показали, что любое 0 - или 0 -множество является сильно -представимым. С другой стороны, М. Лерман14 построил 0 -множество, не имеющее вычислимого -представления. Также М. Лерман дал полное описание -представимых степеней. А именно, он доказал, что каждая 0 -степень -представима. Дж. Розенштейн15 показал, что любое сильно -представимое множество лежит в классе 0. Он, фактически, доказал, что каждое -представимое по неубыванию множество лежит в классе 0 (множество -представимо по неубыванию, если оно имеет вычислимое -представление, для некоторого неубывающего перечисления данного множества).

В связи с этими результатами Р. Доуни16 поставил вопрос об описании сильно -представимых степеней и, в частности, спросил, верно ли, что кажLerman M., Rosenstein J. G. Recursive linear orderings // Stud. Logic Found. Math. – 1982. – V.109. – P.132– 142.

Downey R. G. Computability theory and linear orderings // Handbook of computable algebra. – Amsterdam:

Elsevier, 1998. – V.2. – P.823–976.

Feiner L. J. Hierarchies of Boolean algebras // J. Symbolic Logic. – 1970. – V.35. – P.365–374.

Rosenstein J. Linear orderings. – New York: Academic Press, 1982. – 487 P.

Fellner S, Recursive and Finite Axiomatizability of Linear Orderings // Ph.D. Thesis. – Rutgers Univsity.

– 1976.

Lerman M. On recursive linear orderings // Lecture Notes in Mathematics. – Berlin: Springer-Verlag. – 1981. – V.859. – P.132–142.

Rosenstein J. Linear orderings. – New York: Academic Press, 1982. – 487 P.

Downey R. G. Computability theory and linear orderings // Handbook of computable algebra. – Amsterdam:

Elsevier, 1998. – V.2. – P.823–976.

дая 0 -степень содержит сильно -представимые множества? К. Харрис построил такую 0 -степень, что она не содержит сильно -представимых множеств, получив, таким образом, отрицательный ответ на второй вопрос.

Н. Хисамиевым18, при исследовании конструктивизируемости абелевых групп специального вида, были введены предельно монотонные функции. В настоящее время они играют важную роль в изучении (с точки зрения теории вычислимости) различных структур, в том числе, линейных порядков. К. Харрисом20, была получена характеризация -представимых с использованием предельно монотонных функций. Он доказал, что множество является -представимым тогда и только тогда, когда оно является множеством значений некоторой 0 -предельно монотонной функции. Однако, пока не удалось получить подобного критерия для сильно -представимых множеств.

Так К. Харрис21 построил пример сильно -представимого множества, которое не является областью значений никакой возрастающей 0 -предельно монотонной функции определeнной на. В работе А. Каца и Д. Турецкого было предложено рассматривать функции, определенные на множестве рациональных чисел и возрастающие не на всей области определения, a на своем Harris K. -Represetation of Sets and Degrees // J. Symbolic Logic – 2008. – V.73. – P.1097–1121.

Хисамиев Н. Г. Критерий конструктивизируемости прямой суммы циклических p-групп // Изв. АН Каз. ССР., сер. физ.-мат. – 1981. – Т.98. – №1. – С.51–55.

Csima B. F., Hirshfeldt D. R., Knight J. F., Soare R. I. Bounding prime models // J. Symbolic Logic. – 2004. – V.69. – № 4. – P.1117–1142.

Hirshfeldt D., Miller R., Podzorov S. Order-computable sets // Notre Dam J.Formal Logic.– 2007. – V.48. – №3. – P.317–347.

Khisamiev N. G. Constructive abelian groups // Handbook of computable algebra. – Amsterdam: Elsevier, 1998.

– V.2. – P.1177–1231.

Khoussainov B., Nies A., Shore R. Computable models of theories with few models // Notre Dam J. Formal Logic. – 1997. – V.38. – №2. – P.165–178.

Harris K. -Represetation of Sets and Degrees // J. Symbolic Logic – 2008. – V.73. – P. 1097–1121.

Kach A. M. and Turetsky D. Limitwise Monotonic Functions, Sets and Degrees on Computable Domaine // J. Symbolic Logic, принято к печати.

носителе. В нашей работе предложенные ими функции нашли применение при описании сильно -представимых степеней.

Цель диссертационной работы. Исследование сильных -представлений множеств и их связи с предельно монотонными функциями, а также описание уровней в релятивизованной иерархии Ершова, содержащих сильно -представимые множества.

Научная новизна. Все основные результаты диссертации являются новыми.

Практическая ценность. Диссертация носит теоретический характер, её результаты могут использоваться в дальнейших исследованиях по теории конструктивных моделей. Материалы диссертации могут быть использованы при чтении спецкурсов для студентов и аспирантов в университетах.

Основные результаты диссертации.

1. Получено описание сильно -представимых тьюринговых степеней в терминах 0 -предельно монотонных функций.

2. Доказано, что каждое таблично сводящееся к 0 множество (в частности, каждое множество из конечного уровня релятивизованной относительно 0 иерархии Ершова) m-эквивалентно некоторому сильно -представимому множеству.