Ієрархічна класифікація арифметичних множин та індексні множини
Дана дисертаційна робота має надійти до бібліотек найближчим часом Повідомити про вступ
Дисертація, - 480 руб., Доставка 1-3 години, з 10-19 (Московський час), крім неділі
Автореферат -безкоштовно, доставка10 хвилин, цілодобово, без вихідних та свят
Введення в роботу
Робота присвячена двом великим розділам теорії алгоритмів – теорії ієрархи? і іг -.ексним безлічі. Обидва розділи виникли в період формованої теорії алгоритмів і відіграють у увй цв-j нтральну роль. У чудові роботах 30-х років Чорча, Кліни, Тьюринга і Геделя були отримані основоположні факту про природу алгоритмів: доведена еквівалентність різних уточ-; ній поняття обчислюваної функції, сформульована і обґрунтована теза Черча, доведені теореми про універсальну функцію, на основі якої далося довести нерозв'язність багатьох найважливіших алгоритмічних проблем математики. , що продовжується і. зараз.
Дослідження рекурсивних ієрархій почалося з рр^від Кліні; [Z&] і Мостоєського [32] , в яких зведена та вивчена ієрархія, звана тепер ієрархією Кліні-Мосовського. Клас 2ц 1п:; вешати і квантори за функціями з Шво). Відразу було замі-'
чено, що -»- *» сД,, і виникла проблема характеризації і
класу Л через більш престі безлічі. Аддісон зауважив [15] , що ця проблема аналогічна відомої проблеми з дес-
; кркптивної теорії множин, якщо вважати арифметичну ієрар-
I хію аналоюм борелівської, а аналітичну – аналогом проектив-.
'ної ієрархії Н.Н.Лузіна.Ця аналогія виявилася виключно глибокою та плідною. Як з'ясувалося, у разі ієрархій класів функцій лише по суті маємо справу з єдиною теорією, в якій класичні ієрархії є "граничними" випадками [рекурсивні. Аналогія Аддісона добре пояснює вирішення проблеми характеризації. h1. Потрібно побудувати трансфінітне продовження арифметичної ієрархії по асем рекурсивним ординалам-аналог ієрархії Єорнля по всіх рахункових ординачах. Ця теорема Сусліна-Кліні чудова тим, що дає інформацію про визначення в логіці другого порядку.
'З інших грубих ієрархій помітну роль грає ієрархія, одержувана ітеруванням операції гіперскачка [ЗІГ], вона аналогічна ієрархії С-множини,
У цій роботі нас в основному цікавитимуть тонкі ієрархії, оскільки вони найбільш корисні у вивченні/ндексних множин. Першим прикладом такої ієрархії (не рахуючи субрекур-'сильних, які тут не розглядаємо) була ієрархія Єршова Ч^іі)а^і> Г 4 1 Виявилося, що «УЗЕ^Яйг» виникла Аналогічна розглянутій вище проблемі завдання характеризації Wtfeca h^. Вона вирішується \4, ч.й\ також шляхом транефкнітного Едродолжнья ієрархії Єршова по всіх рекурсивних ординалів: ,Aj'"Z-a = А » г^е (,0'і^о) - клінієвська система орди-
Анальних позначень. [4, ч.Пу отримано опис ієрархії ЕрмБй через m-ікачок, аналогічний опис арифметичної ієрархії через Т-стрибок. Аналогом ієрархії Єршова в дескриптивній теорії інонеств є різницева ієрархія, що сягає Куато провідному ч Хаусдорфу. Ієрархія Єршова вивче-;. на настільки повно, як ар -иетична. Так, [4, ч.Ш] залиш-; лени отари*, jmh два питання про релятивізовані варіанти "тієї
-множин і про зв'язок ієрархії Єршова з клас-j сифікацією високих-низьких множин ЗбЗ. Ці питання будуть розглядатися і в.е'^ой роботі. :
Аналіз теореми -'д. шт-Клмні, характеризаційно Аг, та багатьох аналогічних фактів з дескриптивної теорії множин (С-множини, R-множини та ін.) показує природність і важливість наступного завдання: знайти природний клас ієрархій 3 такий, що: гіперарифметична ієрархія належить З І якщоІєЗ дискретна в даному рівні, то найп'ється ієрархія
1 « 9 , є щільним витонченням ї на цьому рівні*, будь-яка; 1^9 , крім гілерарнфмзтичної, є щільністю витонченості.
єм відповідної І Є 3 на деякому рівні; любив послідовник-; ність ієрархій з 3, кожна з яких витончує яредицущу», I кінцева. Використані поняття буду? уточнено нижче. ': сенс! зрозумілий з прикладів: гіперарифметична ієрархія - щільне викрадення - ченці аналітичної в першому рівні,, ієрархія Єршова - щільне! витончення гіперарифметичної в другій.урочне, ієрархія Єршо-1 ва дискретна, тобто. не має витонченості в жодному рівні.
ми. Ситуацію пояснимо на рис. I. [Тут Ct0, Q(l - га-ступеня, і
оп_ .є відповідно мно жествами 0 і з , а "конус" зі- / стоїть з інших Ш-ступенів. Відомий метод кодування кон структивних об'єктів натуральні ми числами сильно розширює про ласть застосовності, ієрархій. По скільки ієрархії - інструмент більш грубий, ніж ступеня не раз решимості, на перший погляд ка- Мал. I жається, що можливість їх приме-
ня невелика. Насправді це не так; природно виникаючі множини, як правило, універсальні б деякому кінцевому рівні відповідної ієрархії і тому можуть бути "виміряні" крапки (з точністю до рекурсивногоізоморфізму). Цей "емпіри- чеський" факт у лрдаенеьії до індексних множин вперше сформульований Роджерсом, тому будемо його називати тезою Род-
,Для прикладу розглянемо деякі застосування до логіки. Хоча відомий результат бефор-.іана (див. [ІІЗ) показує, що в будь-якій рекурсивно перераховані результати по характеризації складності різних класів. прв,ілоаєній отримані М.Г.Перетятькіним [ДОЗ. Наприклад, якщо (рп має j просту модель) -в Хг
Перейдемо до індексних множин, Слідуючи А.І.Мальцеву, сіандартку нумерацію всіх частково рекурсивних функцій;! '.
(ч.р.ф.) називатимемо нумерацією Клині і позначатимемо X , а номери всіх рекурсивно перерахованих множин (р.п.м.) будемо називати нумерацією Посту і позначати ЗІ . Індексною безліччю сієїства ч.р.ф. f називаю 1 "ес" ЧА) в -rte А), анаяогічна.для р.пі. «пл .яна визначення нумерації Кліні,
бачимо, що X можна ототожнити із сукупністю всіх ал-! га ритмів, що обчислюють функції з А „ Відомі результати теорії нумерацій показують, що індексна множина визначена досить інваріантно: індексні множини одного л того до сімейства у двох главгчс обчислюваних нумер; щих рекурсивно ізоморфні. Все це показує, що індексні кнсжеств є природними і найважливішими об'єктами (і обумовлює корисність ух вивчення» Дослідження індексних множин іокго розбити на 3 напрямки! I) екстенсіонально;;, тобто. по можливості без посилань на номери, опис сімейств, індексних і горитмів індексних множин і 3) змінивши ступенів індексних множин за даною алгоритмічною сеодимістю.
" 7
проблема залишалася невирішеною. ',
Багато уваги у літературі приділялося напрямку 2), По! суті, запровадження будь-якого нового класу р.п.м.супроводжувалося спробами обчислити складність його індексної множини. Це і пояснюється, крім природності такого питання, несподіваними і глибокими застосуваннями деяких з цих результатів. Так, 1 Ейтс [373] використав свою теорему про те, що для будь-якого р.п.м. 1 Т безліч т т) універсально в "2З" т , для відносі- I льни простого доказу теореми Сакса про щільність р.п. р.п.м.Цікаві результати отримані Ейтсом" [38> і С.Каллібековим [7]: для будь-якого р.п.м. Т множини
WKnsmT> , m3rft\ і nsmTi у нетривіальних випадках універсальні в Zg , а безліч a*mT ^=/^, - в П3 З інших результатів відзначимо отриману незалежно Ю. Л. Єршовим та Л. Хей ( [4, ч. Ґ] та [193 ) класифікацію індексних множин кінцевих сімейств кінцевих множин. Виявилося, що будь-яка така індексна множина універсальна в одному з 21 п,
Ми приділимо велику увагу цій проблематиці, причому вперше завдання буде розглядатися у великій спільності: спробуємо класифікувати індексні множини предикатів, які формульно визначать у ґратах р.п.м. (8; і, П). Очевидним є зв'язок цього завдання зі складністю елементарної теорії ТЬ(Б) і з модельними властивостями Th(S). При цьому виявляються необхідні описані вище ієрархії з 3 . Наприклад, з наших результатів буде випливати, що безліч і 1Ят «ЯпЛ (Ят#0 У "%пФш)» не можна охарактеризувати за допомогою арифметичної ієрархії та релятивізованих варіантів ієрархії Єршова. Якщо ми хочемо зберегти згадану вище тезу Роджерса, треба шукати нові і , що дозволяють оцінювати такі множини: Аналогія з ситуацією, коли бажання виміряти діагональ одиничного квадрата призводить до необхідностірозширення системи раціональних чисел Зазначимо, що такого роду міркування зіграли велику роль у формулюванні та вирішенні проблеми повної ієрархічної класифікації арифметичних множин.
У напрямку 3 вивчалися в основному структури т-і Т-ступенів індексних множин. Інтерес до цього пояснюється тим, що це завдання є в певному значенні граничному: випадково задачі 2) і тісно пов'язана з вивченням фактор-об'єктів даної нумерації. У цьому напрямі багато працювала Хей [20-22] , проте отримані результати косили переважно локальний! характер. Не було отримано результатів, що належать до всієї і структури m - ступенів індексних множин.
Метою дисертації є продовження досліджень у хвилинах питань, а саме: I) дослідження релятивкзованих ! варіантів ієрархії Єрлова та її співвідношення з ієрархією високих 1-низьких множин, 2) побудова повної ієрархічної класифікації арифметичних множин та дослідження побудованих ієр-. рхий, 3) розробка загальних методів обчислення складності індексних множин, визначальних у природній мові, за допомогою побудованих ієрархій; 4) отримання загальних результатів про структуру гп-ступенів індексних множин; арифметичній ієрархії.
Відповідно до цього дисертація розбита на 5 розділів. Кожен розділ розбитий на 4 параграфи, нумерація яких наскрізна. Загальний обсяг роботи 245 с., Список літератури являє собою 94 найменування.
Найбільш важливі результати названі теоремами, їх 10 та їх нумерація наскрізна по всьому тексту. Нумерація інших тверджень своя у кожному параграфі. Так, пропозиція 5.1 - це передлопіння 1 з 5. На "якісному" рівні основні результатисформулювати так: а) повністю вивчено взаємне розташування ієрархії Єрлова та ієрархії високих-низьких множин; ієрархій, що повністю класифікує арифметичні множини, г) знайдено опис побудованих ієрархій за допомогою теоретико-множинних операцій, який показує, що ці ієрархії почнеться рекурсивним аналогом ступенів Уеджа борелівських множин [29] , д) знайдено застосування збудованих НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ НІШ ВК 'Ш НІШ ВК 'ІК 10 10 10 10 10 10 10 10 10 15
дехснкх множин, що дозволило повністю класифікувати булеві комбінації А-прелікаїв Яахлана та відповісти на одне запитання! З ара [ЗбЗ, е) показано, що проблема екстенсіонального опі-і саніандк них множин вирішується позитивно при І>3 і j негативно при п.-'. , і) знайдено глибокий зв'язок м. отруту теорією повних нумзраций w деякою питаннями теорії алгоритмів, що призводить до численних застосувань теорії повних нумерацій до ступенів нерозв'язності, обчислення складності конкретних індексних множин і вивчення структури m-ступенів ІН-! декених множин.
Застосовувані методи дослідження дуже різноманітні. Орі-; гянальні алгебраїчні катоди в розділах 2 і 3, де проблеми- вирішуються шляхом "наведення" підходящої. алгебраїчної структури та досить глибокого її вивчення. Протягом всієї роботи використовують теорема про рекурсії для предповних нумерацій, нумеровані безлічі з апроксимацією і теорія, повних нумерацій, У розділах 2, '4 і'5 використовуються ідеї з теорії операцій над ьножестза?.Пл, а в розділах 3 і . теорії конструктивних до: р.п. алгебраїчним сирієм. У розділі I використовуєтьсяоригінальна комбінація методу пріоритету та методу "китайських ящиків" Лахлана.
Результати дисертації доповідалися на семінарах "Теорія нумерацій" та "Алгебра і логіка" в Новосибірському університеті, -на семінарах з математичної логіки та теорії алгоритмів у Казанському, Московському, Казахському та Латвійському університетах, в, ЛСМ; - АН СРСР, в пленар на 8 і 9 Всесоюзних конфе-, ренцнях з математичної логіки, в секційній доповіді на 8 М-адутародном конгресі з логіки, методології та філософії науки е. Москва.