Вычислимые линейные порядки и η-представимость тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Зубков, Максим Витальевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Казань
МЕСТО ЗАЩИТЫ
|
||||
|
2009
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Зубков Максим Витальевич
Вычислимые линейные порядки и //-представимость
01.01.06 - Математическая логика, алгебра и теория чисел
Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
7 с^'*
Казань - 2009
003476623
Работа выполнена на кафедре алгебры и математической логики государственного образовательного учреждения высшего профессионального образования "Казанский государственный университет им. В. И. Улъянова-Ле-нина".
Научный руководитель: доктор физико-математических наук,
профессор Арсланов Марат Мирзаевич,
Официальные оппоненты: доктор физико-математических наук,
профессор Добрица Вячеслав Порфирьевич, доктор физико-математических наук, ведущий научный сотрудник Алаев Павел Евгеньевич.
Ведущая организация : государственное образовательное учреждение
высшего профессионального образования "Новосибирский государственный университет". Защита состоится «8» октября 2009 г. в 17.00 на заседании диссертационного совета Д 212.081.24 при ГОУВПО "Казанский государственный университет им. В. И. Ульянова-Ленина" по адресу: 420008, г. Казань, ул. Кремлевская, д. 35., конференц-зал библиотеки им. Н. И. Лобачевского.
С диссертацией можно ознакомиться в библиотеке Казанского государственного университета.
Автореферат разослан «_ У селг*}^ 9.000 г Ученый секретарь
диссертационного совета Д 212.081.24
к.ф.-м.н., доц. Еникеев А.И.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. В представленной работе изучаются конструктивные или, другими словами, алгоритмические свойства линейных порядков и их типов. Исследование конструктивных свойств алгебраических структур началось в 50-ых годах XX века с работ А. И. Мальцева, М. Раблна и других математиков и с тех пор активно развивается.
Одно из направлений исследований конструктивных свойств линейных порядков было начато К. Джокушем. Он ввел степени типа изоморфизма структуры Л, как наименьшую из степеней, содержащих представление структуры А. Применительно к линейным порядкам это онределние оказалось не очень полезным. Л. Рихтер1 установила, что если А — порядковый тип, имеющий степень, то эта степень вычислима, и если Л — подпорядок Q, то существует такой подпорядок В = А, что нижняя грань степеней А и В есть 0. Техника доказательства этих утверждений может быть расширена на широкий класс структур. Л. Рихтер получила теоретико-структурный результат, который включает, как частный случай, результат о линейных порядках. Некоторые структуры могут иметь отличную от 0 степень, например, группы или решетки.2
Естественным является вопрос о существовании вычислимой структуры изоморфной данной. Эта проблема получила наибольшее развитие в исследованиях отечественных и зарубежных математиков, например, Л. Фейнера, С. С. Гончарова, К. Джокуша, Дж. Найт. Диссертационная работа лежит в русле этих исследований. Так как существует континуум попарно неизоморфных друг другу счетных линейных порядков, сложно надеяться на получение простого описания порядковых типов, имеющих вычислимые представ-
1 Richter L. J. Degrees о/ Unsolvability of Models - Ph.D. Thesis - Urbana: University of Illinois at Urbana-Champaing,. - 1997
2Там же.
ления. Поэтому, как правило, рассматриваются типы линейных порядков с какими-либо дополнительными ограничениями. Так, характеризация вычислимо представимых вполне упорядоченных типов не представляет большой сложности. В самом деле, если Л какое-либо вполне упорядоченное арифметическое подмножество Q, тогда порядковый тип Л есть вычислимый ординал, следовательно, вычислимо представим.3
Для другого естественного типа линейных порядков — дискретного линейного порядка, Р. Ватником4 было показано, что имеет вычислимое представление тогда и только тогда, когда р имеет ni> представление (ясно, что любой дискретный линейный порядок представим в виде (р, где ( "■; естественного упорядочения целых чисел).
Доказательство этой теоремы предоставляет важный метод построения вычислимых представлений различных порядковых типов. Так М. Лерман0, используя конструкцию, похожую на конструкцию в доказательстве теоремы Ватника, методом приоритета с бесконечными нарушениями на деревьях получил, что если А бесконечное £3 множество, то существует вычислимый линейный порядок, имеющий порядковый тип:
С + Щ + С + + • - •
где по, «1, ... — перечисление А в порядке возрастания. (Здесь предполагается, что 0 ^ .4).
Линейный порядок такого типа называется сильным ^-представлением множества А. Если перечисление множества А берется не обязательно в порядке возрастания и, возможно, с повторениями, то такой порядок называет-
JRice н. С,. Rmir.nnc and recursively enumerable orders /,/ Ttans. AMS. -1956. - V.83. - P.713-746. Rosenstein J. [Amur ordciiugs. - New Yovk". Academic Pros:;. 1982. - 487 P.
4Walnik R. A generalization of Tennenbaum's Theorem on effectively finite recursive, linear ordehngs ''
J. Symbolic Uigic. - 19GC. - V.3I. - P.159-I68.
'Lerman \i. Ov. recursive linear orderings jj Lecture Notes in Mathematics. - Berlin: Springer-Verlag. -
1981.-V.85!). - P.132-142.
ся просто £-представнмым. С помощью алгоритма Тарского-Куратовского и результата М. Лермана легко проверить, что множество А имеет вычислимое (^-представление тогда и только тогда, когда оно имеет вычислимое сильное ^-представление, тогда и только тогда, когда А 6 £3-
Дж. Розенштейпом® были рассмотрены rj-схожие линейные порядки. Линейный порядок называется ^-схожим. если он не содержит бесконечных блоков (по определению, элементы лежат в одном блоке, если между ними не более конечного числа различных элементов). Дж. Розенштейн доказал, что если £ вычислимый 77-схожий линейный порядок, то существует такая Д°
функция F : Q —> ]N, что L = Y1 F(q)- Используя технику, аналогичную
?е Q
доказательству теоремы Ватника, в частности, представление П® множеств
на деревьях, С. Феллнер7 показал, что если F является П^-функцией, то
линейный порядок ^ F(q) имеет вычислимое представление. Аналогичный veQ
результат имеет место и для Е^-функций. Возникает естественный вопрос,
можно ли эти результаты распространить на Дз-уровень арифметической
иерархии? М. Лерман и Дж. Розенштейн8 построили такую Д^-функцию, что
порядок У^ F(q) не имеет вычислимой копии. Более того, Р. Доуни9 показал, ieQ
что при этом функция F может иметь конечное число значений.
Эти результаты оставляют открытым следующий вопрос: если L — вычислимый г;-схожий линейный порядок, то существует ли такая П^-функцня
F : Q —» W, что С = F{q)? Этот вопрос ставился в шм-.кольких работах.10
«eQ
Аналогично определению (-представимых и сильно (^-представимых мио-
''lloseusteni .I. Lim ar ordering*. - New York: Academic Picas. 1 - 1X7 P.
'Fellner S. Recursive and Finite Axiomaiizahility of Linear Orderingл /;' Ph.D. Thesis. - Rutgers Univsity. - 1976.
^Lermaii M., Roseusteiü J. G. Recursive linear orderings // Stud. Logic Found. iVIatli. - 1932. - V.109, -P.132-142.
9 Downey R. G. Сomput ability theory and linear ordeiings ,// Handbook of computable algebra. — Amsterdam: Elsevier. 1998. - V.2. - P.823-976.
luR.nsens1ciii .J. Lnujir imhtrings. - New York: Academic Press. 1982. - P.
жеста, можно определить jj-представимые и сильно 77-представимые множества, соответственно заменив в исходных определениях £ на 77 — тип упорядочения рациональных чисел. Как видно из определения, ^-представления являются 77-схожими линейными порядками. Нетрудно доказать, что 77-представимые множества (то есть множества, имеющие вычислимые ^-представления) принадлежат ЕЦ-уровню арифметической иерархии.11 Дж. Розенштейн12 и С. Феллнер1"', соответственно, показали, что любое Е®- или П^-множество является сильно 77-иредставнмым. С другой стороны, М. Лерман14 построил Аз-множество, не имеющее вычислимого ^-представления. Также М. Лерман дал полное описание т^-представимых степеней. А именно, он доказал, что каждая Ез-степепь rj-представима. Дж. Розенштейн15 показал, что любое сильно 77-представимое множество лежит в классе A3. Он, фактически, доказал, что каждое ?7-предета.вимое по неубыванию множество лежит в классе A3 (множество rj-представимо по неубыванию, если оно имеет вычислимое ^-представление, для некоторого неубывающего перечисления данного множества) .
В связи с этими результатами Р. Доуни16 поставил вопрос об описании сильно ту-представимых степеней и, в частности, спросил, верно ли, что каж-
Lcrman М., Rosenstein J. С. Recursive linear ordering* /'/ Stud. Logic: Found. Math. - 1982. - V.109. - P.132-142.
Downey R. G. Compvlability theory and linear orderings // Handbook of computable algebra. - Amsterdam: Elsevier, 19Я8. - V.2. - Р.823-Н7П.
"Feiner L. J. Hierarchies of Boolean algebras // J. Symbolic Logic. - 1970. - V.35. - P.365-374.
12Rosenstein .1. Linear orderings. - New York: Academic Preys, 1982. - 187 P.
13Fellner S, Recursive and Finite Axiomatizabilliy of Linear Orderinga /,' Ph.D. Thesis. -■ Rutgers Univsity. - 197(i.
HLerman M. On recurs/re linear ordering! jj Lecture No!es in Mathematics. - Berlin: Springer-Verlag. -
10K1. - V.859. •• P.132-142.
'^Rosenstein .1. Linear orderings. - New York: Academic Press, 1982. - 487 P.
,r'Downey R. G. Ccm/iidalnlily theoiy and linear orderinga // Handbook of computable algebra. - Amsterdam: Elsevier. 1998. - V.2. - Р.Ш-97С.
дая ДЦ-степень содержит сильно т^-предстдвимые множества? К. Харрис17 построил такую Д^-степень, что она не содержит сильно 77-представимых множеств, получив, таким образом, отрицательный ответ на второй вопрос.
Н. Хисамиевым18, при исследовании конструктивизируемости абелсвых групп специального вида, были введены предельно монотонные функции. В настоящее время они играют важную роль в изучении (с точки зрения теории вычислимости) различных структур, в том числе, линейных порядков.19 К. Харрисом20, была получена характеризация 77-представимых с использованием предельно монотонных функций. Он доказал, что множество является 77-представимым тогда п только тогда, когда оно является множеством значений некоторой О'-пределыю монотонной функции. Однако, пока не удалось получить подобного критерия для сильно 77-предетавимых множеств. Так К. Харрис21 построил пример сильно 77-предста.вимого множества, которое не является областью значений никакой возрастающей О'-предельно монотонной функции определенной на и. В работе А. Каца и Д. Турецкого22 было предложено рассматривать функции, определенные на множестве рациональных чисел и возрастающие не на всей области определения, а на своем
"Harris К. q-Represetation of Sets and Degrees //' J. Symbolic Logic - 2008. - V.73. - P.1097-1121. 'dXi:caf.n:rfj li. Г. Критерий конструюгтымируемости прямой сум.ны цик-мчеекуз: р-групп /,< Изв. АН Ка). ПСР., г ср. фт.-мят. - 1081. - T.98. - №1. - 0.51-55.
19Csima В. F.. Hir.slifeldt. D. R., Knight J. F.. Soare R. I- Bounding pjime mudéis // J. Symbolic Logic. -2004. - V.69. - .4' 4. - P. 1117-1142.
Hirehfcldt D., Miller R., Podzorov S. Order-compulahlc sets // Notre Dam J.Formal Logic:.- 2007. - V.4S. -»З. - P.317-347.
Kbi.samiev X. G. ConstriLctiee abdian tjroups /./ Handbook of computable' algebra- - Amsterdam: FJsevier. 1998. - V.2. - P.1177-1231.
Khoussainov В., N'ie.-: A., Shore 1Ï. Computable models of Ovaries with Jeu models // Notre Dam .1. Formal Logic. ••■ 1997. - V.,'18. - »2. - P.165-178. 2t>Harris K. r¡-Represetalxon of Sets and Degrees Ц .). Symbolic Logic - 2008. - V.73. - P. 1097-1121. 2'Там же.
¿¿Kach A. M. and Turetsky D. Limitvxse Monotonie Functions, Sets and Degrees on Computable Domaine /; J. Symbolic Logic, принято к печати.
нЬсителе. В нашей работе предложенные ими функции нашли применение при описании сильно 77-предста.вимых степеней.
Цель диссертационной работы. Исследование сильиых ^-представлений множеств и их связи с предельно монотонными функциями, а также описание уровней в релятивизованной иерархии Ершова, содержащих сильно т?-представимые множества.
Научная новизна. Все основные, результаты диссертации являются новыми.
Практическая ценность. Диссертация носит теоретический характер, её результаты могут использоваться в дальнейших исследованиях по теории конструктивных моделей. Материалы диссертации могут быть использованы при чтении спецкурсов для студентов и аспирантов в университетах.
Основные результаты диссертации.
1. Получено описание сильно т?-представимых тьюринговых степеней в терминах О'-предельно монотонных функций.
2. Доказано, что каждое таблично сводящееся к О" множество (в частности, каждое множество из конечного уровня релятивизованной относительно 0' иерархии Ершова) т-эквивалентно некоторому сильно т;-предетавимому множеству.
3. Построены вычислимые структуры (Ь, <£, Б с) " (■£>, <£, ^с), содержащие иеконструктивизируемые П° начальные сегменты.
Апробация работы.
По результатам диссертации были сделаны доклады:
• на международной конференции "Мальцевские чтения 2005" (Новосибирск, 2005 г.);
• на международной конференции "Logic Colloquium 2006" (Неймеген, Нидерланды, 200G г.);
• на между нар одной конференции "Мальцевские чтения 2007' (Новосибирск, 2007 г.);
• на международной конференции "Logic Colloquium 2008" (Берн, Швейцария, 2008 г.);
• на научных семинарах и итоговых конференциях кафедры алгебры и математической логики Казанского государственного университета (Казань, 2005-2009 гг.).
• на совместных семинарах НГУ и ИМ СО РАН "Конструктивные модели", "Алгебра и Логика" (Новосибирск, 2009 г.)
Публикации. Основные результаты опубликованы в работах [1]-[6]
Личный вклад автора. Основные результаты диссертации получены автором. Результаты, из совместной с А. Н. Фроловым работы [5], получены авторами в процессе нераздельного сотрудничества.
Структура и объем диссертации. Диссертационная работа изложена на 83 страницах и состоит из списка обозначений, введения, трех глав, разделенных на параграфы, и списка литературы, содержащего 38 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, приведен обзор результатов исследований по ее тематике. Приведены необходимые определения и обозначения.
Глава 1 посвящена изучению предельно монотонных и псевдовозрастаю-щих на Q функций и их связи с линейными порядками.
Определение 1.1.1. Функция F называется X-предельно монотонной, если существует X-вычислимая функция f(x, s) такая, что
1) (Vz)(Vs)[/(x, s)<f(x,s + 1)];
2) Vx)[F{x) = lim /(x, s)].
s—toc
Определение 1.1.9. Множество supp(F) = {x € Q [ F(x) > 1} называется носит.е.ием функции F : Q —> ш.
Определение 1.1.10. Пусть £ = (L; <c) — линейный порядок и F : L —» uj т.акая функция, что для любого п > 1 множество = {у | F(y) =
п.} конечно. Тогда ф>ункция F называется.
1) псевдовозрастаюгцей на £, если (Vx, у € supp(F))[i <с у F(x) < F{y)];
2) псевдонеубывающей на С, ec.iu (Vx, у ÇL supp(F))[x <с у F(x) <
Первый параграф носит преимущественно технический характер. В частности, доказывается следующее предложение, которое упрощает построение исевдовозрастающих предельно монотонных функций с требуемыми свойствами.
Предложение 1.1.12. Пусть J:Qxu —» и> такая, что
1) дли. любого q 6 Q существует конечный предел lim f(q, 5);
s—»0с
2) множество {lim /(g, 5) | q 6 Q} бесконечно;
$—+oo
3) ({q € Q I lim /(<?, s) > 1}; <q) S (ш: <);
s—• 00
4) для любого s £ uj функция /(•, s) псевдовозрастающая (псевдонеубывающая) на Q.
Тогда функция F, определяемая, равенством F{q) = lim f(q, s), также
s—*oo
псевдовозрастающая (псевдонеубывающая) на Q.
Во втором параграфе изучается связь ту-схожих линейных порядков и предельно монотонных функций. Центральной в этом параграфе является следующая теорема.
Теорема 1.2.2. Пусть £ есть г/-схожий линейный порядок. Тогда следующие условия эквивалентны:
1) С имеет. А^-копию с А%-отношениями соседства и блока;
2) С имеет А^-копию с А^-отношением блока;
3) С= J2 Fil), здесь F : Q —-Ич epigr(F) £ Ii!?;
«eQ
4) С = Y, F{<l)i здесь F : Q —> N и F(q) = liminf/(g,s) для любого
qe Q s-0°
q € Q и некоторой вычислимой функции f;
5) С имеет вычислимую копию с П®-отношением блока.
Эта теорема позволяет получить несколько путей построения вычислимых т)-схожих линейных порядков и, в частности, различных 77-представлр-ний. что будет широко использоваться во второй главе.
Глава 2 посвящена, в основном, исследованию сильно 77-представнмых множеств, определение которых приведено в первом параграфе указанной главы.
Определение 2.1.1. Пусть {ао, aj, аг • • - } ~ перечисление, возможно с
повторениями, множества А Си. Тогда порядок С типа
Т] + С10 + Т] +(11 + Г] +0.2 + 7] + ...
называется г}-представлением множества А. Если ац < а1 < а,2..., то С напивается г]-представлением по неубыванию. Если же ао < а,\ < а^..., то С называется сильным т)-пре.дс.та,вленис.м..
Множество А называется т]-представимым (■"ц-представимым по неубыванию, сильно г)-представимым), если существует вычислимое г)-представление (соответственно, 77-представление по неубыванию, сильное представление) множества А.
Обобщаются приведенные ранее результаты Дж. Розенштейна и С. Фелл-нера о сильной ^-представимости и Ш-множеств, что является продвижением описания сильно 77-цредставимых множеств и, следовательно, степеней в арифметической иерархии. Основным результатом первого параграфа является доказательство следующей теоремы.
Теорема 2.1.3. Пусть А — В и С бесконечное множество, где В е Е° и С € П®. Тогда А сильно у-представимо.
Пусть А = ВиС, где В ¡Е С € Ш. Тогда А = СГ)В = С- В, то есть дополнение А можно представить в виде разности двух Е^-множеств. Таким образом, имеет место следующее следствие.
Следствие 2.1.8. Если А = Ах — Ач, где Л; 6 Е®, то существует сильно т]-предст.ав1ш,ое множество В =т А.
Во втором параграфе получено описание т^-представпмых по неубыванию степеней. А именно, доказана следующая теорема.
Теорема 2.2.1. Пусть А £ Дд. Тогда Афи множество г]-представимое по неубыванию. Так как А(&и =т А, каждая Ау степень содержит rj-npedcma-вимое по неубыванию множество.
Учитывая результат К. Харрис.а23 о существовании Дз-степени, не содержащей сильно 7/-нредставимых множеств, получаем, что существует rj-лредставимое по неубыванию множество, не имеющее вычислимого сильного ^-представления. Более того, оно не является Т-эквивалентным ни какому сильно 7)-представимому множеству. Таким образом, как классы сильно 77-предстпвимых множеств и множеств 77-предетавимых по неубыванию, так и классы соответствующих степеней, различны.
Другим результатом этого параграфа является описание сильно 77-предс-тавимых степеней в терминах предельно монотонных псевдовозрастающпх на Q функций, что является ответом на приведенный выше вопрос Р. Доунн. А именно, доказана следующая теорема.
Теорема 2.2.11. Если А сильно г)-предс7п.ави.м.ос множество, то существует такая 0'-предельно монотонная псевдовозрастающая на Q функция Н, что rang(H) =г А.
Так как каждый ранг О'-предельно монотонной псевдовозрастающей на Q функции является сильно 7/-нредставимым, то получаем, что тыоринговая степень 77-представима тогда и только тогда, когда она содержит множество, являющееся рангом некоторой О'-предельно монотонной псевдовозрастающей на Q функции.
В третьем параграфе .продолжается изучение вопроса, частично затронутого в параграфе один, а именно, уровней в разностной иерархии степеней (релятивизованной относительно 0') содержащих сильно ?7-представимыс
23Harris К. q-Rqir^elatmn of Sets and Degrees // J. Symbolic Logic - 200*. - V.73. - P. 1097-1121.
множества. В первом параграфе было установлено, что каждая степень, содержащая множество уровня 2, содержит сильно ?;-представимое множество. Однако это построение не удается продолжить естественным образом на более высокие уровни. Нами предложена новая конструкция, которая позволяет доказать следующую теорему, которая имеет важные следствия.
Теорема 2.3.7. Пусть h : и> х и —> {0, 1} и п : а> —> ш такие X-вычислимые функции, что для любого х выполняется неравенство |{s 6 ы | h(x, s) ф h(x, s + 1)}| < п(х).
Тогда существует т,акая X-предельно монотонная, псевдовозрастающая на Q функция F, что rang(F) =т graph(H) © graph(n), где функция Н определяется равенством Н(х) = lim h{x, s).
s—* oo
Если же n — вычислимая функция, то rang(F) =ш graph(H)(Bgraph(n).
Из этой теоремы выводятся следующие следствия.
Следствие 2.3.11. Каждое таблично сводящееся к0" множество т-жви-валептно некоторому сильно т]-прсдставимом.у множеству.
В частности, все степени из конечных уровней разностной иерархии множеств содержат сильно 77-представимые множества.
Следствие 2.3.12. Любая п-в.п. относительно 0' т-степень содержит сильно г]-представимое множество.
Кроме того, результаты -второй главы вместе с результатами К. Харри-са показывают, что нет хорошего описания в арифметической иерархии ни сильно ^-представим ых множеств, ни ихстепенсй.
В главе 3 рассматриваются линейные порядки с добавленными предикатами — отношениями соседства и блока. Другими словами, такие струк-
туры (L; <£, Se) и (L; <£, где (L; <c) — линейный порядок. Начальный сегмент порядка С с индуцированным отношением соседства или отношением блока называется начальным сегментом структуры {L; <£, Se) или (L; <£. i-e), соответственно. Таким образом, начальные сегменты этих структур имеют такую же сигнатуру. Сложность начального сегмента вычислимого линейного порядка может быть очень высокой. Например, согласно результатам Р. Ганди24 и Дж. Харрисона2', существует вычислимый линейный порядок с начальным сегментом, изоморфным u>fK — наименьшему неконструктивному ординалу. М. Роу2С показал, что если отношение соседства в вычислимом линейном порядке вычислимо, то любой П® начальный сегмент имеет вычислимую копню. С другой стороны, им был построен вычислимый линейный порядок с П® начальным сегментом, не имеющим вычислимой копии. Первый результат М. Pov был обобщен К. Амбос-Шписом, Б. Купером н С. Лемппом27, которые доказали, что любой начальный сегмент вычислимого линейного порядка имеет вычислимую копию. Р. Доуни, Р. Коулз и Б. Хусаинов28 построили вычислимый линейный порядок с П® начальным сегментом, не имеющим вычислимой копии, тем самым получив полное описание начальных сегментов вычислимых линейных порядков, имеющих вычислимую копию.
В первом параграфе третьей главы построены вычислимые структуры (L; <£, Se) и (L; <£, Fe)-, содержащие неконструктивизируемые началь-
24Gandy R. О- Genual recursutt- of finite type and hierarchies of functions // Anil. Fac. .Sn. Univ. Clemmont-Ferrand. - 1967. - V..'i.i. - P.5-24.
"''Harrison .1. Recursive pseudo-welt orderings // Trans. AMS. - 19G8. - V.l.'ll.- P.52ÍÍ-M3.
26Haw M. .]. S. Complexity of .automorphisms of recursive henar orders. - Ph. D. Thesis. - University of Wisconsin-Madison. - 199.ri.
27Ambos-Spies K-, Cooper S. В.. Lempp S. Initial segments of recursive linear orders //' Order. - 1997. -V. 14. - P.101-105.
28Coles R. J.. Downey H Khoussainov B. On initial segments of computable linear orders /■' Order. -1997/1998,- V.14. - P.107-124.
ные сегменты. С другой стороны, нетрудно показать, что каждый начальный сегмент (Ь\ <с, Бс) или (Ц <г_, ^г) имеет вычислимую копию, то есть изоморфен некоторому вычислимому линейному порядку с вычислимым отношением соседства или блока, соответственно. Во втором параграфе получено более простое доказательство вышеупомянутого результата Доуни, Коулза и Хусаинова.
Такая постановка вопроса, и формулировка результатов не предусматривают ограничений на. тин ни самого линейного порядка, ни его начального сегмента, но, фактически, упомянутые начальные сегменты суть 77-с.хожие линейные порядки. Более того, при несущественных дополнительных условиях они будут ^-представлениями некоторых множеств (мы не будем па этом останавливаться). Естественно, что техника построения таких порядков близка к методам и подходам предыдущих глав, и здесь важную роль играют предельно-монотонные функции. В первом параграфе основными являются следующие теоремы.
Теорема 3.1.5. Для любого непустого множества М е не содержащего 0, существует такой вычислимый линейный порядок С = Л + ш* с вычислимым, предикатом ¿>£ , что Л — г)-схожий и Б (Л) = М.
Следствие 3.1.8. Существуют вычислимая структура (Ь\ <с, Бц) и П; начальный сегмент 1 данной структуры, что X не имеет вычислимой копии.
Для предиката блока вместо предиката соседства аналог предыдущей теоремы не имеет места, однако аналог следствия остается верен. А именно доказана следующая теорема.
Теорема 3.1.9. Существуют вычислимая структура (Ь\ <с, Рс) и П® начальный сегмент Т. данной структуры такие, что X не имеет вычислимой
копии.
Во втором параграфе основной является следующая теорема..
Теорема 3.2.2. Пусть £, — А + и>* - О-вычислимый линейный порядок, с 0-вычислимым предикатом соседства Б с- Тогда существует вычислимый линейный порядок С! = В + и* такой, что ¿>(.4) = 5(5). Здесь А и В — Г)-схожие, линейные порядки.
Из этой теоремы легко следует упомянутый результат Доуни, Коулза и Хуса-инова. Их доказательство использует метод приоритета с бесконечными нарушениями. Доказательство же нашей теоремы, как и необходимых теорем из первого параграфа третьей главы, используют только методы приоритета с конечными нарушениями. Кроме того, в качестве следствия она дает следующий результат.
Следствие 3.2.7. Существует такой вычислимый порядок С, что С/Рс = г/, и никакая Д®-копия которого не имеет. /^-вычислимого отношения блока.
В заключение, автор выражает глубокую благодарность своим научным руководителям Марату Мирзаевичу Арсланову и Андрею Николаевичу Фролову за постановку задач, внимательное отношение к исследованиям автора и поддержку.
Публикации автора по теме диссертации
[1 ] Зубков М. В. Сильно т]-предсгпавимые множества // Труды математического центра им. Н.И. Лобачевского. - 2006. - Т. 34. - С. 111-112.
[2 ] Zubkov M.V. Strongly r)-representable sets // Bulletin of Symbolic Logic.
- 2007. - V. 13.-P. 292-293.
[3 ] Zubkov M. On eta-representable sets /. Bulletin of Symbolic Logic. - 2009.
- V. 15. - P. 131.
[4 ] Зубков M. В. Одна теорема о сильно г}-предст.авимых множествах: Ц Известия вузов. Математика. - 2009. - №7,- С. 77-81.
[5 j Frolov A. N.: Zubkov M.V. Increasing rj-rcpresentable degrees / / Mathematical Logic Quarterly. - 2009. - V. 55. - N.6. - P. 561-564.
[6 ] Зубков M.B. Начальные сегменты вычислимых линейных порядков с дополнительными вычислимыми предикатами // Алгебра и логика, принято к печати.
Отпечатано с готового оригинала-макета в типографии издательства Казанского государственного университета Тираж 100 экз. Заказ 39/7
420008, ул. Профессора Нужина, 1/37 тел.: 231-53-59, 292-65-60
Введение
Глава 1. Предельно монотонные функции и г/-схожие линейные порядки
§1.1. Некоторые свойства предельно монотонных функций.
§1.2. 77-схожие линейные порядки
Глава 2. Сильно 77-представимые множества и степени
§2.1. Объединение Е®— и П®—множеств.
§2.2. Множества и степени сильно ту-представимые и т/-представимые по неубыванию.
§2.3. Сильно 77-представимые степени в разностной иерархии
Глава 3. Начальные сегменты вычислимых линейных порядков с дополнительными вычислимыми предикатами
§3.1. П^ начальные сегменты.
§3.2. П® начальные сегменты.
В представленной работе изучаются конструктивные или, другими словами, алгоритмические свойства линейных порядков и их типов. Исследование конструктивных свойств алгебраических структур началось в 50-ых годах XX века с работ А. И. Мальцева, М. Рабина и других математиков и с тех пор активно развивается.
Одно из направлений исследований конструктивных свойств линейных порядков было начато К. Джокушем. Он ввел понятие степени типа изоморфизма структуры Л, как наименьшую из степеней, содержащих представление структуры Л. Применительно к линейным порядкам это определение оказалось не очень полезным. Л. Рихтер [30] установила, что если Л — порядковый тип имеющий степень, то эта степень вычислима, и если Л — подпоря-док С^, то существует такой подпорядок В = Л, что нижняя грань степеней Л и В есть 0. Техника доказательства этих утверждний может быть расширена на широкий класс структур. Л. Рихтер получила теоретико-структурный результат, который включает, как частный случай, результат о линейных порядках. Некоторые структуры могут иметь отличную от 0 степень, например, группы или решетки [30].
Естественным вопросом является проблема существования вычислимой структуры, изоморфной дайной. Эта проблема получила наибольшее развитие в исследованиях отечественных и зарубежных математиков, например, Л. Фейнера, С. С. Гончарова, К. Джокуша, Дж. Найт. Диссертационная работа лежит в русле этих исследований. Так как существует континуум попарно пеизоморфных друг другу счетных линейных порядков, сложно надеяться на получение простого описания порядковых типов, имеющих вычислимые представления. Поэтому, как правило, рассматриваются типы линейных порядков с какими-либо дополнительными ограничениями. Так, характеризация вычислимо представимых вполне упорядоченных типов не представляет большой сложности. В самом деле, если Л какое-либо вполне упорядоченное арифметическое подмножество С}, тогда порядковый тип А есть вычислимый ординал, следовательно, вычислимо представим [29], [31].
Для другого естественного типа линейных порядков — дискретного линейного порядка, Р. Ватником [32] было показано, что (р имеет вычислимое представление тогда и только тогда, когда р имеет П® представление (ясно, что любой дискретный линейный порядок представим в виде (р, где С — тип естественного упорядочения целых чисел).
Доказательство этой теоремы предоставляет важный метод построения вычислимых представлений различных порядковых типов. М. Лерман [25], используя конструкцию, похожую на конструкцию в доказательстве теоремы Ватника, методом приоритета с бесконечными нарушениями на деревьях получил, что если А бесконечное Ед-множество, то существует вычислимый линейный порядок, имеющий порядковый тип:
С + п0 + С + п1 + • • • где по, щ, . — перечисление А в порядке возрастания. (Здесь предполагается, что 0 £ А).
Линейный порядок такого типа называется сильным (-представлением множества А. Если перечисление множества А берется не обязательно в порядке возрастания и, возможно, с повторениями, то такой порядок называется просто ("-представимым. С помощью алгоритма Тарского-Куратовского и результата М. Лермана легко проверить, что множество А имеет вычислимое ("-представление тогда и только тогда, когда имеет вычислимое сильное 4 ("-представление, тогда и только тогда, когда А е
Дж. Розенштейном [31] были рассмотрены г)-схожие линейные порядки. Линейный порядок называется 77-схожим, если он не содержит бесконечных 5 блоков (по определению, что элементы лежат в одном блоке, если между ними не более конечного числа различных элементов). Дж. Розенштейн доказал, что если С вычислимый ^-схожий линейный порядок, то существует такая Д§-фупкция Г : <9 —> ДО, что С, = ^ ^(о)- Используя технику, аналогичную доказательству теоремы Ватника, в частности, представление П^-множеств на деревьях, С. Феллнер [16] показал, что если ^ является П^-функцией, то линейный порядок ^ -^((7) имеет вычислимое представление. Аналогичный результат имеет место и для Е^-функций. Возникает естественный вопрос, можно ли эти результаты распространить на ДЦ-уровень арифметической иерархии? М. Лерман и Дж. Розенштейн [26] построили такую Дз-функцию, что порядок ^ не имеет вычислимой копии. Более того, Р. Доуни [14] показал, что при этом функция / может иметь конечное число значений.
Эти результаты оставляют открытым следующий вопрос: если С — вычислимый ^-схожий линейный порядок, то существует ли такая ПЦ-функция ДО, что С, = ^{ч)^ Этот вопрос ставился в нескольких работах [31], [26], [14]. В работе [8], фактически, было показано, что если £ некоторый 77-схожий линейный порядок, мощность блоков которого ограничена некоторым числом, то С имеет вычислимую копию тогда и только тогда, когда существует такая функция ^ : —> ДО, что £ = ^ Р{ч) и ергдг(Р) Е ПЦ.
Аналогично определению £-представимых и сильно ("-представимых множеств, можно определить 77-представимые и сильно г^-представимые множества, соответственно заменив в исходных определениях С на г] — тип упорядочения рациональных чисел. Как видно из определения, 77-представления являются г/-схожи ми линейными порядками. Нетрудно доказать, что 77-предста-вимые множества (то есть множества, имеющие вычислимые ^-представления) принадлежат £3 уровню арифметической иерархии [15]. Дж. Розенштейн [31] и С. Феллнер [16], соответственно, показали, что любое £[>- или
П^-множество является сильно ту-представимым. С другой стороны, М. Лер-ман [25] построил Д^-множество, не имеющее вычислимого ^-представления. Он также дал полное описание ту-представимых степеней. А именно, он доказал, что каждая Ед-степень 77-представима. Дж. Розенштейн [31] показал, что любое сильно 77-представимое множество лежит в классе А®. Он доказал, фактически, что каждое 77-представимое по неубыванию множество лежит в классе ДЦ (множество 77-представимо по неубыванию, если оно имеет вычислимое 77-представление, для некоторого неубывающего перечисления данного множества).
В связи с этими результатами Р. Доуни [13] поставил вопрос об описании сильно ?7-представимых степеней и, в частности, спросил, верно ли, что каждая ДЦ-степень содержит сильно 77-представимые множества? К. Харрис [18] построил такую Дд-степень, что она не содержит сильно 77-представимых множеств, получив, таким образом, отрицательный ответ на второй вопрос.
Н. Г. Хисамиевым [9], при исследовании конструктивизируемости абеле-вых групп специального вида, были введены предельно монотонные функции. В настоящее время они играют важную роль в изучении (с точки зрения теории вычислимости) различных структур, в том числе линейных порядков [12], [20], [24], [23]. К. Харрисом [18] была получена характеризация 77-представимых множеств в терминах предельно монотонных функций. Он доказал, что множество является 77-представимым тогда и только тогда, когда оно является множеством значений некоторой О'-предельно монотонной функции. Однако, пока не удалось получить подобного критерия для сильно 77-представимых множеств. Так К. Харрис [18] построил пример сильно 77-представимого множества, которое не является областью значений никакой возрастающей О'-предельно монотонной функции, определенной на ал В работе А. Каца и Д. Турецкого [22] было предложено рассматривать функции, определенные на множестве рациональных чисел и возрастающие не на всей области определения, а на своем носителе. В данной работе предложенные функции нашли применение при описании сильно 77-представимых степеней.
Все стандартные определения и обозначения, а также необходимые сведения из теории вычислимости и теории линейных порядков, будут даны в конце введения. Перейдем к содержанию работы.
Первая глава посвящена изучению предельно монотонных и псевдовозрас-тающих на Q функций и их связи с линейными порядками. Первый параграф носит преимущественно технический характер.
В частности, доказывается следующее предложение, которое упрощает построение псевдовозрастающих предельно монотонных функций с требуемыми свойствами.
Предложение 1.1.12. Пусть f : (Q х и —у ш такая, что
1) для любого q € Q существует конечный предел lim /(g, s); s—>00
2) множество {lim f(q, s) | q € Q} бесконечно; s—»00
3) ({q e Q I lim f(q, s) > 1}; <Q) (ш; <>; s—>00
4) для любого s € ш функция /(•, s) псевдовозрастающая (псевдонеубывающая) на <Q.
Тогда функция F, определяемая равенством F(q) = lim f(q, s), таксисе s—> 00 псевдовозрастающая (псевдонеубывающая) на Q.
Во втором параграфе изучается связь 77-схожих линейных порядков и предельно монотонных функций. Центральной в этом параграфе является следующая теорема.
Теорема 1.2.2. Пусть С есть г]-схожий линейный порядок. Тогда следующие условия эквивалентны:
1) С имеет А^-копию с А®-отношениями соседства и блока;
2) С имеет А^-копию с А ^-отношением блока;
3) С ^ X) здесь Р-Ч —и ергдг(Г) Е П°;
4) С ^ £ Ня), здесь р ■ ^ —" ^ и Р{ч) = Лял любого <7 Е <1^ и некоторой вычислимой функции f;
5) С имеет вычислимую копию с И\-отношением блока.
Эта теорема позволяет получить несколько путей построения вычислимых ту-схожих линейных порядков и, в частности, различных ^-представлений, что будет широко использоваться во второй главе.
Вторая глава посвящена, в основном, исследованию сильно ту-представимых множеств.
Определение 2.1.1. Пусть {ао, а2 .} ~ перечисление, возможно с повторениями, множества АС. ш. Тогда порядок С типа
77 + а0 + 77 + а\ + г) + а2 + 77 + . называется г/-представлением множества А. Если ао < ец < а2., то С называется г]-представлением по неубыванию. Если же ао < а\ < а2 ■ ■., то С называется сильным г]-представлением.
Мнооюество А называется г/-представимым (г}-представимым по неубыванию, сильно г]-представимым), если существует вычислимое ^-представление (соответственно, г]-представление по неубыванию, сильное Г)-представление) множества А.
Обобщаются приведенные ранее результаты Дж. Розенштейна и С. Фелл-нера о сильной 77-представимости £[>- и П^-множеств, что является продвижением описания сильно 77-представимых множеств и, следовательно, степеней в арифметической иерархии. Основным результатом первого параграфа является доказательство следующей теоремы.
Теорема 2.1.3. Пусть А = В и С бесконечное множество, где В € Е® и С € П^. Тогда А сильно г)-представимо. 9
Пусть А = BUC, где В G Е§, С <= П§. Тогда А = СПБ - С-В, то есть дополнение А можно представить в виде разности двух Е^-множеств. Таким образом, имеет место следующее следствие.
Следствие 2.1.8. Если А = А\ — Ач, где Ai Е то существует сильно ■ц-представимое множество В =т А.
Во втором параграфе получено описание 77-представимых по неубыванию степеней. Была доказана следующая теорема.
Теорема 2.2.1. Пусть А € ДЦ. Тогда А®и) множество г]-представимое по неубыванию. Так как А®ш А, каогсдая А^-степень содержит rf-npedcma-вимое по неубыванию множество .
Учитывая результат К. Харриса [18] о существовании Ад-степени, не содержащей сильно 77-представимых множеств, получаем, что существует 77-представимое по неубыванию множество, не имеющее вычислимого сильного 77-представления. Более того, оно не является Т-эквивалентным ни какому сильно 77-представимому множеству. Таким образом, как классы сильно 77-представимых множеств и множеств 77-нредставимых по неубыванию, так и классы соответствующих степеней, различны.
Другим результатом этого параграфа является описание сильно 77-представимых степеней в терминах предельно монотонных псевдовозрастающих на Q функций, что является ответом на вопрос Р. Доуни. А именно, доказана следующая теорема.
Теорема 2.2.11. Если А сильно г]-представимое множество, то существует такая 0'-предельно монотонная псевдовозрастающая на (Q функция Н, что rang(H) =т А.
Так как каждый ранг О'-предельно монотонной псевдовозрастающей на Q функции является сильно ту-пред ставимым, то получаем, что тьюринговая степень 77-представима тогда и только тогда, когда она содержит множество, являющееся рангом некоторой О'-предельно монотонной псевдовозрастающей на Q функции.
В третьем параграфе продолжается изучение вопроса, частично затронутого в параграфе 1, а именно, уровней в разностной иерархии степеней (реля-тивизованной относительно 0') содержащих сильно ту-представимые множества. В первом параграфе было получено, что каждая степень, содержащая множество уровня 2, содержит сильно ?у-представимое множество. Однако это построение не удается естественным образом продолжить на более высокие уровни. Нами предложена новая конструкция, которая позволяет доказать следующую теорему, которая имеет важные следствия.
Теорема 2.3.7. Пусть h : и х и —> {0, 1} и п : со —> ш такие X-вычислимые функции, что для любого х выполняется неравенство |{s € ш | h(x, s) ^ h(x, s -f 1)}| < n(x).
Тогда существует такая X-предельно монотонная псевдовозрастающая на Q функция F, что rang(F) =т graph(H) ф graph(n), где функция Н определяется равенством Н{х) = lim h(x, s). s—> 00
Если otce n — вычислимая функция, то rang(F) =m graph(H)®graph(n).
Эта теорема дает следующие следствия.
Следствие 2.3.11. Каждое таблично сводящееся к 0" множество т-экви-валентно некоторому сильно 7]-представимому множеству.
В частности, все степени из конечных уровней разностной иерархии Е®-множеств содержат сильно ту-представимые множества.
Следствие 2.3.12. Любая п-в.п. относительно 0' т-степенъ содержит сильно г]-представимое множество.
Кроме того, результаты второй главы вместе с результатами К. Харри-са показывают, что нет хорошего описания в арифметической иерархии ни сильно 77-представимых множеств, ни их степеней.
В третьей главе рассматриваются линейные порядки с добавленными предикатами — отношением соседства и блока. Другими словами, такие структуры (Ц <£, вс) и (Ц <£, Ее), где {Ь\ <с) — линейный порядок. Начальный сегмент порядка С с индуцированным отношением соседства или отношением называется начальным сегментом структуры (Ь; <£, ¿х) или (Ц <£, Ее), соответственно. Таким образом, сигнатуры исходной структуры и ее начального сегмента совпадают. Сложность начального сегмента вычислимого линейного порядка может быть очень высокой. Например, согласно результатам Р. Ганди [17] и Дж. Харрисона [19], существует вычислимый линейный порядок с начальным сегментом, изоморфным и>1К — наименьшему неконструктивному ординалу. М. Роу [28] показал, что если отношение соседства в вычислимом линейном порядке вычислимо, то любой П? начальный сегмент имеет вычислимую копию. С другой стороны, им был построен вычислимый линейный порядок с П3 начальным сегментом, не имеющим вычислимой копии. Первый результат М. Роу был обобщен К. Амбос-Шписом, Б. Купером и С. Лемппом [10]. Они доказали, что любой Е® начальный сегмент вычислимого линейного порядка имеет вычислимую копию. Р. Доуни, Р. Коулз и Б. Хусаинов [13] построили вычислимый линейный порядок с П® начальным сегментом, не имеющим вычислимой копии, тем самым получив полное описание начальных сегментов вычислимых линейных порядков, имеющих вычислимую копию.
В первом параграфе третьей главы построены вычислимые структуры
Ь; <£, Бс) и (Ь\ <£, Рс), содержащие П® неконструктивизируемые начальные сегменты. С другой стороны, нетрудно показать, что каждый X® начальный сегмент (Ь\ <£, Б^} или (£-; <£, имеет вычислимую копию, то есть изоморфен некоторому вычислимому линейному порядку с вычислимым отношением соседства или блока, соответственно. Во втором параграфе получено более простое доказательство вышеупомянутого результата Доуни, Коулза и Хусаинова.
Такая постановка вопроса и формулировка результатов не предусматривают ограничений на тип ни самого линейного порядка, ни его начального сегмента, но, фактически, упомянутые начальные сегменты суть 77-схожие линейные порядки. Более того, при несущественных дополнительных условиях они будут 77-представлениями некоторых множеств (однако мы не будем на этом останавливаться). Естественно, что техника построения таких порядков близка к методам и подходам предыдущих глав, и здесь важную роль играют предельно монотонные функции. Итак, в первом параграфе основными являются следующие теоремы.
Теорема 3.1.5. Для любого непустого множества М Е не содержащего 07 существует такой вычислимый линейный порядок £ = И. + ш* с вычислимым предикатом Б с, что Л — г]-схожий и Б (А) = М.
Следствие 3.1.8. Существуют вычислимая структура (Ь; <£, Яс) и П^ начальный сегмент X данной структуры, что X не имеет вычислимой копии.
Для предиката блока вместо предиката соседства аналог предыдущей тео ремы не имеет места, однако аналог следствия остается верен. А именно доказана следующая теорема.
Теорема 3.1.9. Существуют вычислимая структура {Ь\ <£, и начальный сегмент X данной структуры такие, что X не имеет вычислимой копии.
Во втором параграфе основной является следующая теорема.
Теорема 3.2.2. Пусть С = А + ои* — О-вычислимый линейный порядок с О!-вычислимым предикатом соседства Б с- Тогда существует вычислимый линейный порядок С! — В + со* такой, что в (А) = Б (В). Здесь А и В — г]-схожие линейные порядки.
Из этой теоремы легко следует упомянутый результат Доуни, Коулза и Хусаинова, оригинальное доказательство которой использует метод приоритета с бесконечными нарушениями. Доказательство же нашей теоремы, как и необходимых теорем из первого параграфа третьей главы, используют только методы приоритета с конечными нарушениями. Кроме того, в качестве следствия она дает следующий результат.
Следствие 3.2.7. Существует такой вычислимый порядок С, что £/Рц = 7] и никакая его А^-копия не имеет Д^-вычислимого отношения блока.
Приведем необходимые определения и обозначения из теории вычислимости и теории линейных порядков. Множество неотрицательных целых чисел обозначается ш = {0,1,2,.}. Множества рассматриваемые в данной работе, если не оговорено другое, являются подмножествами со. Аналогично, у рассматриваемых функций, если специально не оговорено другое, область определения и область значения являются подмножествами ш. Греческими буквами, малыми и большими латинскими буквами (как правило из середины алфавита) обозначаются функции, большими латинскими буквами (как
14 правило из начала алфавита) обозначаются множества. Если А множество, то ха(х) обозначает его характеристическую функцию, а именно:
Если А, В С со, то А (или со—А) и А—В (или А\В) обозначают теоретико-множественные операции дополнения и разности, соответственно. Пусть А © В = {2х \ х £ А} + 1 | х 6 В}. Мощность множества А обозначается через |Л|.
Квантор 3! является сокращенной записью формулы "существует и единственный", то есть для любого предиката Р полагаем (3!:с)[Р(а;)] тогда и только тогда, когда (3x)(Vy)[P(x)Sz((P(y) —> у = я)]. Квантор 3°° является сокращенной записью формулы "существует бесконечно много", то есть, для любого предиката Р, если х е со, полагаем (3°°ж)[Р(ж)] тогда и только тогда, когда (уу)(За; > у)[Р(х)].
Двухместная функция (х, у), определенная как (х, у) := +^х+у для х, у € со и осуществляющая биективное отображение и2 на со, называется канторовской нумерующей функцией. Через I и г обозначаются однозначно определенные функции такие, что для всех х, у £ и, (1(х),г(х)) = х, 1((х, у}) — х,г((х, у}) = у, n-местная функция (xi, ., хп) при п > 2 определяется так: (xi, ., хп) = ((. (xi, хг), %з), •., хп). Если функция ip определена на аргументе х, то пишем ср(х) J., в противном случае пишем (р(х) Область определения функции / обозначается через dom(f) = {х \ f(x) j.}, область ее значений — через rang(f) = {х | (Зг/ € dom(f))[f(y) = ж]}. Положим f(A) = {/(ж) | х G Andom(f)}. Аналогично, для п множеств и функции п аргументов. Если / функция от двух аргументов, то запись /(-, s) обозначает функцию от одного аргумента, получаемую из / подстановкой вместо
О, если х ^ А.
1, если х Е А, второго аргумента фиксированного значения s. Запись х —у обозначает ограниченную разность, а именно, х—у = х — у, если х > у, и х — у = 0, в противном случае. Пусть f : Ахи —> ш, тогда lim f(x, s) определен и конечен, есs—>оо ли существует такое число ах, что (3s0)(Vs > so)[f(x, s) = аж]. В этом случае lim f(x, s) = ах. Не трудно видеть, что если f(x, s) для некоторого х моно
S—>00 тонна по s и ограничена, то существует конечный предел lim /(ж, s). Кроме s—»оо того, liminf/(ж, s) = ах, если (3s0)(Vs > s0)[f(x, s) > ах] и (3°°s)[f(x, s) == ах]. Обозначим / функцию, задаваемую равенством /(ж) = liminf/(ж, s). s—»oo
Пусть Фо,ФьФ2,. — некоторая эффективная нумерация всех частично-вычислимых (ч.в.) функций. Множество А сводится по Тьюрингу (или Т-сводится) к множеству В {А <т В), если (Зп)(Ух)[А(х) = Ф^(ж)], где Ф^ — некоторая вычислимая относительно В функция.
Множество А много-одно сводится (или га-сводится) к множеству В (обозначается А <т В), если существует такая вычислимая функция /, что (Уж)[ж <Е А <—► /(ж) Е В].
Множество А принадлежит классу Е^ (или является Е^-множеством) для п > 0, если существует такое вычислимое отношение R(x, у\, у2,., уп), что х е А тогда и только тогда, когда (3yi)(Vy2)(3y3).(Qyn)[R(x, уъ ., уп)], где Q является квантором 3, если п нечетно, и квантором V, если п четно. Множество А принадлежит классу П®, если ш — А принадлежит классу Е°. Множество А принадлежит классу А®, если А е П П®.
Множество А называется n-вычислимо-перечислимым (п-в. п.) множеством (или принадлежит классу Е"1) для некоторого п > 1, если существует такая вычислимая функция / : и х и —> {0,1}, что для каждого х выполняется:
1) /(ж, 0) = 0;
2) Ха{х) = lim f(x,s)) s—»00
3) \{s\f(x, 5)^/(ж,5 + 1)}|<П.
Пусть <r — любая из вышеперечисленных сводимостей, тогда <г является рефлексивным и транзитивным отношением, поэтому для каждой такой сводимости можно определить отношение эквивалентности множеств относительно этой сводимости: говорим, что множества А и В г-эквивалентны (А =г В), если А <г В и В <г А. Для каждого множества А определим его r-степень: degr(A) = {В С и | В =г А}.
Степень а называется n-вычислимо-перечислимой степенью для n > 1, если она содержит п-в. п. множество, и она называется собственно п-в. п. степенью, если она содержит п-в. п. множество, но не содержит т-в. п. множеств для т < п.
Линейный порядок С — это алгебраическая система (L; <с) с одним бинарными отношением, обладающим свойствами антирефлексивности, антисимметричности, транзитивности и для любых ж, у Е L либо х <с У, либо у <£ х (где, х <су^ х = у V х <су). Если С — (L; — линейный порядок, то С* определяется следующим образом £* — (L;<£*), где (Va;)(\/у)[ж <£* у <—> у <с х]. Линейный порядок (М; <м) называется под-порядком (Ц <с), если М С L и (Ух € M)(V?/ € М)[х <м У *—> % <с у]-В этом случае также будем писать Л4 = (М; <с)- Замкнутым интервалом в линейном порядке С с концами хну называется множество [ж, у]с = {z € L | х <с z <с у}. Открытым интервалом в линейном порядке £ с концами х и у называется множество (х, у)с — {z 6 L | х <£ z <ц у]. Интервал относительно естественного порядка на и обозначается [ж, у]. Множество R С L называется сегментом линейного порядка если (Vx)(Vy)(Vz)[(x <с z <с укх € Rky е R)—
Линейные порядки С = (L; <с) и М = (М; <м) называются изоморфными (£ = Л4), если существует такая биекция ip : L —> М, что (Va; 6 L)(\fy € L)[x <с у ^ ip(x) <м <р(у)]- Если два линейных порядка изоморфны, будем говорить, что они имеют одинаковый порядковый тип.
Стандартное отношение порядка на и) обозначается "<". Символами 14 и (1^ будем обозначать множество натуральных и множество рациональных чисел, соответственно, а также, для удобства, естественные линейные порядки на них определенные. Кроме множества неотрицательных целых чисел, символ со, также обозначает естественный линейный порядок на нем и тип этого порядка. Каждый раз из контекста будет ясно о чем идет речь. Тип рациональных чисел обозначается г], тип целых чисел —
Пусть М. = (М; <м) и £г = (£>г> <с{) € М) — линейные порядки. Предположим, что Ьг П М = 0 (г £ М) и Ьг П = 0 для любых г ф з г, 2 ^ М), тогда определен линейный порядок С — ]Г) где Ь — и Ь{, гем ¿ем а отношение "<£" задается следующим образом: если х Е Ьг, у Е Ь^, то х <£ у тогда и только тогда, когда (г <м з) V (г = г/). Если £7 = то по определению £.М = А- Вообще говоря, умножение гем определено не однозначно для данных линейных порядков С, Л4 и зависит от выбора последовательности £{. Однако, не трудно видеть, что если = С! ^ и М = М', то С,г = и) следовательно, если С = /У и Л4 = гбМ гбМ' то = СМ.'. Таким образом, эти две операции корректно и однозначно определены для порядковых типов.
Конечный линейный порядок с точностью до изоморфизма определяется числом своих элементов. С учетом операции сложения и умножения на порядковых типах, естественно отождествить тип конечного линейного порядка состоящего из п элементов с числом п.
Эти определения, а также основные результаты, касающиеся данной тематики, могут быть найдены в книгах [1], [2], [6], [7], [27], [31].
1. Арсланов М. М. Рекурсивно перечислимые множества и степени неразрешимости. - Казань: изд-во КГУ. - 1986. - 206 с.
2. Арсланов М. М. Иерархия Ершова. Спецкурс для студентов мехмата. -Казань: Казанский государственный университет. 2007. - 86 с.
3. Ершов Ю. JI. Об одной иерархии множеств, I // Алгебра и Логика. -1968. Т. 7. - №3. - С. 47-75.
4. Ершов Ю. JI. Об одной иерархии множеств, II // Алгебра и Логика. -1968. Т. 7. -т. - С. 15-48.
5. Ершов Ю. Л. Об одной иерархии множеств, III // Алгебра и Логика.- 1970. Т. 9. - т. - С. 34-52.
6. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир. - 1972. - 624 с.
7. Соар Р. И. Вычислимо перечислимые множества и степени. Казань: Казанское математическое общество. - 2000. - 576 с.
8. Фролов А. Н. ДЦ копии линейных порядоков // Алгебра и логика. — 2006.- Т. 45. С. 354-370.
9. Хисамиев Н. Г. Критерий конструктивизируемости прямой суммы циклических р-групп // Изв. АН Каз. ССР., сер. физ.-мат. 1981. - Т. 98. -т.- С. 51-55.
10. Ambos-Spies К., Cooper S. В., Lempp S. Initial segments of recursive linear orders // Order. 1997. - V. 14. - P. 101-105.
11. Ash C. J., Jockusch C. G., Knight J. F. Jumps of orderings// Trans. AMS. 1990. - V. 319. - P. 573-599.
12. Csima B. F., Hirshfeldt D. R., Knight J. F., Soare R. I. Bounding prime models // Journal of Symbolic Logic. 2004. - V. 69 - №4. - P. 1117-1142.
13. Coles R. J., Downey R., Khoussainov B. On initial segments of computable linear orders // Order. 1997/1998. - V. 14. - P. 107-124.
14. Downey R. G. Computability theory and linear orderings // Handbook of computable algebra. Amsterdam: Elsevier. - 1998. - V. 2. - P. 823-976.
15. Feiner L. J. Hierarchies of Boolean algebras // Journal of Symbolic Logic. -1970. V. 35. - P. 365-374.
16. Fellner S. Recursive and Finite Axiomatizability of Linear Orderings // Ph.D. Thesis. Rutgers Univsity. - 1976.
17. Gandy R. O. General recursive of finite type and hierarchies of functions // Ann. Fac. Sci. Univ. Clemmont-Ferrand. 1967. - V. 35. - P. 5-24.
18. Harris K. r]-Represetation of Sets and Degrees // Journal of Symbolic Logic- 2008. V. 73. - P. 1097-1121.
19. Harrison J. Recursive pseudo-well orderings // Trans. AMS. 1968. -V. 131.- P. 526-543.
20. Hirshfeldt D., Miller R., Podzorov S. Order-computable sets // Notre Dam Journal of Formal Logic. 2007. - V. 48. - №3. - P. 317-347.
21. Kach A. M. Computable shuffle sums of ordinals // Archive for Mathematical Logic. 2008. - V. 47. - №3. - P. 211-219.
22. Kach A. M., Turetsky D. Limitwise Monotonic Functions, Sets and Degrees on Computable Domaine // Journal of Symbolic Logic, принято к печати.
23. Khoussainov В., Nies A., Shore R. Computable models of theories with few models // Notre Dam Journal of Formal Logic. 1997. - V.38. - №2. -P. 165-178.
24. Khisamiev N. G. Constructive abelian groups // Handbook of computable algebra. Amsterdam: Elsevier, 1998. - V. 2. - P. 1177-1231.
25. Lerman M. On recursive linear orderings // Lecture Notes in Mathematics.- Berlin: Springer-Verlag. 1981. - V. 859. - P. 132-142.
26. Lerman M., Rosenstein J. G. Recursive linear orderings // Stud. Logic Found. Math. 1982. - V. 109. - P. 132-142.
27. Odifreddi P. Classical recursion theory. Amsterdam: North-Holland. - 1989.- 610 P.
28. Raw M. J. S. Complexity of automorphisms of recursive lienar orders. -Ph. D. Thesis. University of Wisconsin-Madison. - 1995.
29. Rice H. G. Recursive and recursively enumerable orders // Trans. AMS. -1956. V. 83. - P. 713-746.
30. Richter L. J. Degrees of Unsolvability of Models. Ph.D. Thesis. - Urbana: University of Illinois at Urbana-Champaing. - 1997.
31. Rosenstein J. Linear orderings. New York: Academic Press. - 1982. - 487 P.
32. Watnik R. A generalization of Tennenbaum's Theorem on effectively finite recursive linear orderings // Journal of Symbolic Logic. 1966. - V. 31. -P. 159-168.
33. Зубков М. В. Сильно т]-представимые множества // Труды математического центра им. Н. И. Лобачевского. 2006. - Т. 34. - с. 111-112.
34. Zubkov М. V. Strongly rj-representable sets // Bulletin of Symbolic Logic. -2007. V. 13. - P. 292-293.
35. Zubkov M. On eta-representable sets // Bulletin of Symbolic Logic. 2009. - V.15. - P. 131.
36. Зубков M. В. Одна теорема о сильно rj-представимых множествах // Известия вузов. Математика. 2009. - №7 - с. 77-81.
37. Frolov A. N., Zubkov М. V. Increasing rj-representable degrees // Mathematical Logic Quarterly. 2009. - V. 55. - №6. - P. 561-564.
38. Зубков M. В. Начальные сегменты вычислимых линейных порядков с дополнительными вычислимыми предикатами // Алгебра и логика, принято к печати.
