Гиперарифметическая теория

В теории вычислимости теория гиперарифметики является обобщением вычислимости по Тьюрингу . Он имеет тесные связи с определимостью в арифметике второго порядка и со слабыми системами теории множеств, такими как теория множеств Крипке-Платека . Это важный инструмент эффективной дескриптивной теории множеств .

В центре внимания теории гиперарифметики находятся множества натуральных чисел, известные как гиперарифметические множества . Есть три эквивалентных способа определения этого класса множеств; изучение взаимосвязей между этими различными определениями является одной из причин изучения гиперарифметической теории.

Гиперарифметические множества и определимость

Первое определение гиперарифметических множеств использует аналитическую иерархию . Набор натуральных чисел классифицируется на уровне $\Sigma _{1}^{1}$ этой иерархии, если ее можно определить формулой арифметики второго порядка с использованием только кванторов экзистенциального множества и без каких-либо других кванторов множеств. Набор классифицируется на уровне $\Pi _{1}^{1}$ аналитической иерархии, если она может быть определена формулой арифметики второго порядка с использованием только кванторов универсального множества и без каких-либо других кванторов множеств. Набор $\Delta _{1}^{1}$ если это оба $\Sigma _{1}^{1}$ и $\Pi _{1}^{1}$. Гиперарифметические множества — это в точности $\Delta _{1}^{1}$ наборы.

Гиперарифметические множества и итерированные прыжки Тьюринга: гиперарифметическая иерархия

Определение гиперарифметических множеств как $\Delta _{1}^{1}$ не зависит напрямую от результатов вычислимости. Второе, эквивалентное определение показывает, что гиперарифметические множества могут быть определены с помощью бесконечно повторяющихся прыжков Тьюринга . Это второе определение также показывает, что гиперарифметические множества можно классифицировать в иерархию, расширяющую арифметическую иерархию ; гиперарифметические множества — это именно те множества, которым присвоен ранг в этой иерархии.

Каждый уровень гиперарифметической иерархии индексируется счетным порядковым числом (ординалом), но не все счетные порядковые номера соответствуют уровню иерархии. Порядковые номера, используемые в иерархии, имеют порядковую нотацию , которая представляет собой конкретное и эффективное описание порядкового номера.

Порядковая запись — это эффективное описание счетного порядкового номера натуральным числом. Для определения гиперарифметической иерархии необходима система порядковых обозначений. Фундаментальное свойство, которым должна обладать порядковая запись, заключается в том, что она эффективно описывает порядковый номер в терминах меньших порядковых чисел. Типично следующее индуктивное определение; он использует функцию сопряжения $\langle \cdot ,\cdot \rangle$.

• Число 0 является обозначением порядкового номера 0.
• Если n — обозначение ординала λ , то $\langle 1,n\rangle$ — обозначение λ + 1;
• Предположим, что δ — предельный ординал . Обозначением δ является число вида $\langle 2,e\rangle$, где e — индекс полной вычислимой функции $\phi _{e}$ что для каждого n такой , $\phi _{e}(n)$ — обозначение порядкового номера λ _n меньше δ , а δ — это sup множества $\{\lambda _{n}\mid n\in \mathbb {N} \}$.

Это также можно определить, используя эффективные соединения на всех уровнях вместо только обозначений предельных порядковых номеров.

Существует только счетное число порядковых обозначений, поскольку каждое обозначение представляет собой натуральное число; таким образом, существует счетный ординал, который является верхним числом всех ординалов, имеющих обозначение. Этот порядковый номер известен как порядковый номер Чёрча-Клин и обозначается $\omega _{1}^{CK}$. Обратите внимание, что этот порядковый номер по-прежнему счетен, а символ является лишь аналогией с первым неисчисляемым порядковым номером: $\omega _{1}$. Множество всех натуральных чисел, являющихся порядковыми обозначениями, обозначается ${\mathcal {O}}$ и позвонил Клини ${\mathcal {O}}$.

Порядковые обозначения используются для определения итерированных прыжков Тьюринга. Наборы натуральных чисел, используемые для определения иерархии: $0^{(\delta )}$ для каждого $\delta <\omega _{1}^{CK}$. $0^{(\delta )}$ иногда также обозначается $H(\delta )$, или $H_{e}$ для обозначения $e$ для $\delta$. Предположим, что δ имеет обозначение e . Эти множества были впервые определены Дэвисом (1950) и Мостовским (1951). Набор $0^{(\delta )}$ определяется с помощью e следующим образом.

• Если δ = 0, то $0^{(\delta )}=0$ пустое множество.
• Если δ = λ + 1, то $0^{(\delta )}$ это прыжок Тьюринга $0^{(\lambda )}$. Наборы $0^{(1)}$ и $0^{(2)}$ являются $0'$ и $0''$, соответственно.
• Если δ — предельный ординал, пусть $\langle \lambda _{n}\mid n\in \mathbb {N} \rangle$ — последовательность ординалов меньше δ, заданная обозначением e . Набор $0^{(\delta )}$ дается по правилу $0^{(\delta )}=\{\langle n,i\rangle \mid i\in 0^{(\lambda _{n})}\}$. Это эффективное соединение множеств $0^{(\lambda _{n})}$.

Несмотря на то, что строительство $0^{(\delta )}$ зависит от наличия фиксированного обозначения для δ , а каждый бесконечный ординал имеет множество обозначений, теорема Клиффорда Спектора показывает, что Тьюринга степень $0^{(\delta )}$ зависит только от δ , а не от конкретных используемых обозначений, и, следовательно, $0^{(\delta )}$ хорошо определена с точностью до степени Тьюринга.

Гиперарифметическая иерархия определяется этими повторяющимися прыжками Тьюринга. Множество X натуральных чисел классифицируется на уровне δ гиперарифметической иерархии, поскольку $\delta <\omega _{1}^{CK}$, если X сводится по Тьюрингу к $0^{(\delta )}$. Всегда будет наименьшее такое δ , если оно вообще существует; именно это наименьшее δ измеряет уровень невычислимости X .

Гиперарифметические множества и конструктивность

Позволять $L_{\alpha }$ обозначают $\alpha$-й уровень конструктивной иерархии , и пусть $n:{\mathcal {O}}\to \omega _{1}^{CK}$ быть отображением члена О Клини до порядкового номера, который он представляет. Подмножество $\mathbb {N}$ является гиперарифметическим тогда и только тогда, когда оно является членом $L_{\omega _{1}^{CK}}$. Подмножество $\mathbb {N}$ определяется с помощью $\Pi _{1}^{1}$ формула тогда и только тогда, когда ее изображение под $n$ является $\Sigma _{1}$-определяемый на $L_{\omega _{1}^{CK}}$, где $\Sigma _{1}$ взято из Леви . иерархии формул

Гиперарифметические множества и рекурсия в высших типах

Третья характеристика гиперарифметических множеств, предложенная Клини, использует более высокого типа вычислимые функционалы . Функционал типа 2 ${}^{2}E\colon \mathbb {N} ^{\mathbb {N} }\to \mathbb {N}$ определяется следующими правилами:

${}^{2}E(f)=1\quad$ если существует i такое, что f ( i ) > 0,

${}^{2}E(f)=0\quad$ если не существует i такого, что f ( i ) > 0.

Используя точное определение вычислимости относительно функционала типа 2, Клини показала, что набор натуральных чисел является гиперарифметическим тогда и только тогда, когда он вычислим относительно ${}^{2}E$.

Пример: набор истинностей арифметики.

Каждое арифметическое множество является гиперарифметическим, но существует множество других гиперарифметических множеств. Одним из примеров гиперарифметического и неарифметического набора является набор T чисел Гёделя формул арифметики Пеано , которые верны для стандартных натуральных чисел. $\mathbb {N}$. Множество T тьюринг- эквивалентно множеству $0^{(\omega )}$, и поэтому не занимает высокого места в гиперарифметической иерархии, хотя его нельзя арифметически определить с помощью теоремы неопределимости Тарского .

Фундаментальные результаты

Фундаментальные результаты теории гиперарифметики показывают, что три приведенных выше определения определяют один и тот же набор множеств натуральных чисел. Эти эквивалентности принадлежат Клини.

Результаты о полноте также имеют фундаментальное значение для теории. Набор натуральных чисел – это $\Pi _{1}^{1}$ завершено, если оно находится на уровне $\Pi _{1}^{1}$ аналитической иерархии и каждого $\Pi _{1}^{1}$ множество натуральных чисел сводится к нему многими-единицами . Определение $\Pi _{1}^{1}$ полное подмножество пространства Бэра ( $\mathbb {N} ^{\mathbb {N} }$) аналогично. Несколько множеств, связанных с теорией гиперарифметики: $\Pi _{1}^{1}$ полный:

• Клини ${\mathcal {O}}$, набор натуральных чисел, которые являются обозначениями порядковых чисел
• Множество натуральных чисел e таких, что вычислимая функция $\phi _{e}(x,y)$ вычисляет характеристическую функцию хорошего порядка натуральных чисел. Это индексы рекурсивных ординалов .
• Множество элементов пространства Бэра , которые являются характеристическими функциями хорошего упорядочения натуральных чисел (с использованием эффективного изоморфизма $\mathbb {N} ^{\mathbb {N} }\cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} })$.

Результаты, известные как $\Sigma _{1}^{1}$ оценки следуют из этих результатов о полноте. Для любого $\Sigma _{1}^{1}$ множество S порядковых обозначений, существует $\alpha <\omega _{1}^{CK}$ такой, что каждый элемент S является обозначением порядкового номера меньше $\alpha$. Для любого $\Sigma _{1}^{1}$ подмножества T пространства Бэра, состоящего только из характеристических функций хорошего порядка, существует $\alpha <\omega _{1}^{CK}$ такой, что каждый порядковый номер, представленный в T, меньше, чем $\alpha$.

Релятивизированная гиперарифметичность и гиперстепени

Определение ${\mathcal {O}}$ может быть релятивизировано к множеству X натуральных чисел: в определении порядковой записи предложение о предельных ординалах изменено так, что вычислимое перечисление последовательности порядковых обозначений позволяет использовать X в качестве оракула. Множество чисел, являющихся порядковыми обозначениями относительно X , обозначается ${\mathcal {O}}^{X}$. Верхняя грань ординалов, представленных в ${\mathcal {O}}^{X}$ обозначается $\omega _{1}^{X}$; это счетный ординал не меньше $\omega _{1}^{CK}$.

Определение $0^{(\delta )}$ также может быть релятивизировано к произвольному множеству $X$ натуральных чисел. Единственное изменение в определении состоит в том, что $X^{(0)}$ определяется как X, а не как пустое множество, так что $X^{(1)}=X'$ является прыжком Тьюринга X и так далее. Вместо завершения на $\omega _{1}^{CK}$ иерархия относительно X проходит через все порядковые номера меньше $\omega _{1}^{X}$.

Релятивизированная гиперарифметическая иерархия используется для определения гиперарифметической сводимости . Учитывая множества X и Y , мы говорим $X\leq _{\text{HYP}}Y$ тогда и только тогда, когда существует $\delta <\omega _{1}^{Y}$ такой, что X сводится по Тьюрингу к $Y^{(\delta )}$. Если $X\leq _{\text{HYP}}Y$ и $Y\leq _{\text{HYP}}X$ тогда обозначение $X\equiv _{\text{HYP}}Y$ используется для обозначения того, X и Y что гиперарифметически эквивалентны . Это более грубое отношение эквивалентности, чем эквивалентность Тьюринга ; например, каждый набор натуральных чисел гиперарифметически эквивалентен своему скачку Тьюринга , но не эквивалентен Тьюрингу своему скачку Тьюринга. Классы эквивалентности гиперарифметической эквивалентности известны как гиперстепени .

Функция, которая переводит множество X в ${\mathcal {O}}^{X}$ известен как гиперпрыжок по аналогии со скачком Тьюринга. Установлены многие свойства гиперпрыжка и гиперстепеней. В частности, известно, что проблема Поста для гиперстепеней имеет положительный ответ: для каждого множества X натуральных чисел существует множество Y натуральных чисел такое, что $X<_{\text{HYP}}Y<_{\text{HYP}}{\mathcal {O}}^{X}$.

Обобщения

Гиперарифметическая теория обобщается теорией α -рекурсии , которая изучает определимые подмножества допустимых ординалов . Гиперарифметическая теория — это частный случай, когда α равно $\omega _{1}^{CK}$.

Связь с другими иерархиями

Светлое лицо		Жирный шрифт
С 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

Внешние ссылки

• Описательная теория множеств . Заметки Дэвида Маркера, Университет Иллинойса в Чикаго. 2002.
• Математическая логика II . Заметки Дага Норманна, Университет Осло. 2005.
• Антонио Монтальбан: Калифорнийский университет в Беркли и создатель контента на YouTube.