Гиперарифметическая теория
В теории вычислимости теория гиперарифметики является обобщением вычислимости по Тьюрингу . Он имеет тесные связи с определимостью в арифметике второго порядка и со слабыми системами теории множеств, такими как теория множеств Крипке-Платека . Это важный инструмент эффективной дескриптивной теории множеств . [1]
В центре внимания теории гиперарифметики находятся множества натуральных чисел, известные как гиперарифметические множества . Есть три эквивалентных способа определения этого класса множеств; изучение взаимосвязей между этими различными определениями является одной из причин изучения гиперарифметической теории.
и Гиперарифметические определимость множества
Первое определение гиперарифметических множеств использует аналитическую иерархию . Набор натуральных чисел классифицируется на уровне этой иерархии, если ее можно определить формулой арифметики второго порядка с использованием только кванторов экзистенциального множества и без каких-либо других кванторов множеств. Набор классифицируется на уровне аналитической иерархии, если она может быть определена формулой арифметики второго порядка только с кванторами универсального множества и без каких-либо других кванторов множеств. Набор если это оба и . Гиперарифметические множества — это в точности наборы.
итерированные прыжки Тьюринга: гиперарифметическая Гиперарифметические множества и иерархия
Определение гиперарифметических множеств как не зависит напрямую от результатов вычислимости. Второе, эквивалентное определение показывает, что гиперарифметические множества могут быть определены с помощью бесконечно повторяющихся прыжков Тьюринга . Это второе определение также показывает, что гиперарифметические множества можно классифицировать в иерархию, расширяющую арифметическую иерархию ; гиперарифметические множества — это именно те множества, которым присвоен ранг в этой иерархии.
Каждый уровень гиперарифметической иерархии индексируется счетным порядковым числом (ординалом), но не все счетные порядковые номера соответствуют уровню иерархии. Порядковые номера, используемые в иерархии, имеют порядковую нотацию , которая представляет собой конкретное и эффективное описание порядкового номера.
Порядковая запись — это эффективное описание счетного порядкового номера натуральным числом. Для определения гиперарифметической иерархии необходима система порядковых обозначений. Фундаментальное свойство, которым должна обладать порядковая запись, заключается в том, что она эффективно описывает порядковый номер в терминах меньших порядковых чисел. Типично следующее индуктивное определение; он использует функцию сопряжения .
- Число 0 является обозначением порядкового номера 0.
- Если n — обозначение ординала λ , то — обозначение λ + 1;
- Предположим, что δ — предельный ординал . Обозначением δ является число вида , где e — индекс полной вычислимой функции что для каждого n такой , — обозначение порядкового номера λ n меньше δ , а δ — это sup множества .
Это также можно определить, используя эффективные соединения на всех уровнях вместо только обозначений предельных порядковых номеров. [2]
Существует только счетное число порядковых обозначений, поскольку каждое обозначение представляет собой натуральное число; таким образом, существует счетный ординал, который является верхним числом всех ординалов, имеющих обозначение. Этот порядковый номер известен как порядковый номер Чёрча-Клин и обозначается . Обратите внимание, что этот порядковый номер по-прежнему счетен, а символ является лишь аналогией с первым неисчисляемым порядковым номером: . Множество всех натуральных чисел, являющихся порядковыми обозначениями, обозначается и позвонил Клини .
Порядковые обозначения используются для определения итерированных прыжков Тьюринга. Наборы натуральных чисел, используемые для определения иерархии: для каждого . иногда также обозначается , [3] или для обозначения для . [2] Предположим, что δ имеет обозначение e . Эти множества были впервые определены Дэвисом (1950) и Мостовски (1951). [2] Набор определяется с помощью e следующим образом.
- Если δ = 0, то пустое множество.
- Если δ = λ + 1, то это прыжок Тьюринга . Наборы и являются и , соответственно.
- Если δ — предельный ординал, пусть — последовательность ординалов меньше δ, заданная обозначением e . Набор дается по правилу . Это эффективное соединение множеств .
Несмотря на то, что строительство зависит от наличия фиксированного обозначения для δ , а каждый бесконечный ординал имеет множество обозначений, теорема Клиффорда Спектора показывает, что Тьюринга степень зависит только от δ , а не от конкретных используемых обозначений, и, следовательно, хорошо определена с точностью до степени Тьюринга. [2]
Гиперарифметическая иерархия определяется этими повторяющимися прыжками Тьюринга. Множество X натуральных чисел классифицируется на уровне δ гиперарифметической иерархии, поскольку , если X сводится по Тьюрингу к . Всегда будет наименьшее такое δ , если оно вообще существует; именно это наименьшее δ измеряет уровень невычислимости X .
Гиперарифметические множества и конструктивность [ править ]
Позволять обозначают -й уровень конструктивной иерархии , и пусть быть отображением члена О Клини до порядкового номера, который он представляет. Подмножество является гиперарифметическим тогда и только тогда, когда оно является членом . Подмножество определяется с помощью формула тогда и только тогда, когда ее изображение под является -определяемый на , где взято из Леви . иерархии формул [4]
множества и рекурсия в Гиперарифметические типах высших
Третья характеристика гиперарифметических множеств, предложенная Клини, использует более высокого типа вычислимые функционалы . Функционал типа 2 определяется следующими правилами:
- если существует i такое, что f ( i ) > 0,
- если не существует i такого, что f ( i ) > 0.
Используя точное определение вычислимости относительно функционала типа 2, Клини показала, что набор натуральных чисел является гиперарифметическим тогда и только тогда, когда он вычислим относительно .
Пример: набор истинностей арифметики [ править ]
Каждое арифметическое множество является гиперарифметическим, но существует множество других гиперарифметических множеств. Одним из примеров гиперарифметического и неарифметического набора является набор T чисел Гёделя формул арифметики Пеано , которые верны для стандартных натуральных чисел. . Множество T тьюринг- эквивалентно множеству , и поэтому не занимает высокого места в гиперарифметической иерархии, хотя его нельзя арифметически определить с помощью теоремы неопределимости Тарского .
результаты Фундаментальные
Фундаментальные результаты теории гиперарифметики показывают, что три приведенных выше определения определяют один и тот же набор множеств натуральных чисел. Эти эквивалентности принадлежат Клини.
Результаты о полноте также имеют фундаментальное значение для теории. Набор натуральных чисел – это завершено, если оно находится на уровне аналитической иерархии и каждого множество натуральных чисел сводится к нему многими-единицами . Определение полное подмножество пространства Бэра ( ) аналогично. Несколько множеств, связанных с теорией гиперарифметики: полный:
- Клини , набор натуральных чисел, которые являются обозначениями порядковых чисел
- Множество натуральных чисел e таких, что вычислимая функция вычисляет характеристическую функцию хорошего порядка натуральных чисел. Это индексы рекурсивных ординалов .
- Множество элементов пространства Бэра , которые являются характеристическими функциями хорошего упорядочения натуральных чисел (с использованием эффективного изоморфизма .
Результаты, известные как оценки следуют из этих результатов о полноте. Для любого множество S порядковых обозначений, существует такой, что каждый элемент S является обозначением порядкового номера меньше . Для любого подмножества T пространства Бэра, состоящего только из характеристических функций хорошего порядка, существует такой, что каждый порядковый номер, представленный в T, меньше, чем .
и Релятивизированная гиперстепени гиперарифметичность
Определение может быть релятивизировано к набору X натуральных чисел: в определении порядковой записи предложение о предельных ординалах изменено так, что вычислимое перечисление последовательности порядковых обозначений позволяет использовать X в качестве оракула. Множество чисел, являющихся порядковыми обозначениями относительно X , обозначается . Верхняя грань ординалов, представленных в обозначается ; это счетный ординал не меньше .
Определение также может быть релятивизировано к произвольному множеству натуральных чисел. Единственное изменение в определении состоит в том, что определяется как X, а не как пустое множество, так что является прыжком Тьюринга X и так далее. Вместо завершения на иерархия относительно X проходит через все порядковые номера меньше .
Релятивизированная гиперарифметическая иерархия используется для определения гиперарифметической сводимости . Учитывая множества X и Y , мы говорим тогда и только тогда, когда существует такой, что X сводится по Тьюрингу к . Если и тогда обозначение используется для обозначения того, X и Y что гиперарифметически эквивалентны . Это более грубое отношение эквивалентности, чем эквивалентность Тьюринга ; например, каждый набор натуральных чисел гиперарифметически эквивалентен своему скачку Тьюринга , но не эквивалентен Тьюрингу своему скачку Тьюринга. Классы эквивалентности гиперарифметической эквивалентности известны как гиперстепени .
Функция, которая переводит множество X в известен как гиперпрыжок по аналогии со скачком Тьюринга. Установлены многие свойства гиперпрыжка и гиперстепеней. В частности, известно, что проблема Поста для гиперстепеней имеет положительный ответ: для каждого множества X натуральных чисел существует множество Y натуральных чисел такое, что .
Обобщения [ править ]
Гиперарифметическая теория обобщается теорией α -рекурсии , которая изучает определимые подмножества допустимых ординалов . Гиперарифметическая теория — это частный случай, когда α равно .
Связь с другими иерархиями [ править ]
Светлое лицо | Жирный шрифт | ||
---|---|---|---|
С 0 0 = П 0 0 = Д 0 0 (иногда то же, что ∆ 0 1 ) | С 0 0 = П 0 0 = Д 0 0 (если определено) | ||
Д 0 1 = рекурсивный | Д 0 1 = закрыто открыто | ||
С 0 1 = рекурсивно перечисляемый | П 0 1 = корекурсивно перечисляемый | С 0 1 = G = открыто | П 0 1 = F = закрыто |
Д 0 2 | Д 0 2 | ||
С 0 2 | П 0 2 | С 0 2 = Ф п | П 0 2 = г δ |
Д 0 3 | Д 0 3 | ||
С 0 3 | П 0 3 | С 0 3 = г дс | П 0 3 = Ф сд |
⋮ | ⋮ | ||
С 0 <ω = Р 0 <ω = D 0 <ω = S 1 0 = П 1 0 = Д 1 0 = арифметический | С 0 <ω = Р 0 <ω = D 0 <ω = S 1 0 = П 1 0 = Д 1 0 = жирный арифметический шрифт | ||
⋮ | ⋮ | ||
Д 0 а ( рекурсивный ) | Д 0 а ( счетное ) | ||
С 0 а | П 0 а | С 0 а | П 0 а |
⋮ | ⋮ | ||
С 0 ой СК 1 = П 0 ой СК 1 = Д 0 ой СК 1 = Д 1 1 = гиперарифметический | С 0 ω 1 = Р 0 ω 1 = Д 0 ω 1 = Д 1 1 = Б = Борель | ||
С 1 1 = аналитика светлого лица | П 1 1 = коаналитик светлой поверхности | С 1 1 = А = аналитический | П 1 1 = СА = коаналитический |
Д 1 2 | Д 1 2 | ||
С 1 2 | П 1 2 | С 1 2 = PCA | П 1 2 = КПКА |
Д 1 3 | Д 1 3 | ||
С 1 3 | П 1 3 | С 1 3 = ПКПККА | П 1 3 = CPCPCA |
⋮ | ⋮ | ||
С 1 <ω = Р 1 <ω = D 1 <ω = S 2 0 = П 2 0 = Д 2 0 = аналитический | С 1 <ω = Р 1 <ω = D 1 <ω = S 2 0 = П 2 0 = Д 2 0 = P = проективный | ||
⋮ | ⋮ |
Ссылки [ править ]
- Х. Роджерс -младший, 1967. Теория рекурсивных функций и эффективная вычислимость , второе издание, 1987, MIT Press. ISBN 0-262-68052-1 (мягкая обложка), ISBN 0-07-053522-1
- Г. Сакс , 1990. Теория высшей рекурсии , Springer-Verlag. ISBN 3-540-19305-7
- С. Симпсон , 1999. Подсистемы арифметики второго порядка , Springer-Verlag.
- Си Джей Эш, Дж. Ф. Найт , 2000. Вычислимые структуры и гиперарифметическая иерархия , Elsevier. ISBN 0-444-50072-3
Цитаты [ править ]
- ^ Теория вычислимости гиперарифметических множеств
- ^ Jump up to: Перейти обратно: а б с д С.Г. Симпсон, Иерархия, основанная на операторе перехода , стр. 268–269. Симпозиум Клини (Северная Голландия, 1980 г.)
- ^ CJ Эш, Дж. Найт, Вычислимые структуры и гиперарифметическая иерархия (Исследования в области логики и основы математики, 2000), гл. 5
- ^ Д. Натингга, Теорема вложения для группы автоморфизмов степеней α-перечисления (стр. 27), докторская диссертация, Университет Лидса, 2019.
Внешние ссылки [ править ]
- Описательная теория множеств . Заметки Дэвида Маркера, Университет Иллинойса в Чикаго. 2002.
- Математическая логика II . Заметки Дага Норманна, Университет Осло. 2005.
- Антонио Монтальбан: Калифорнийский университет в Беркли и создатель контента на YouTube.