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

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

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

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

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

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

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

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

Порядковые обозначения - это эффективное описание счетного порядкового числа натуральным числом. Система порядковых обозначений необходима для определения гиперарифметической иерархии. Основное свойство, которым должна обладать порядковая запись, состоит в том, что она эффективно описывает порядковый номер в терминах малых порядковых чисел. Следующее индуктивное определение является типичным; он использует функция сопряжения ${displaystyle langle cdot ,cdot angle }$.

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

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

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

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

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

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

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

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

${displaystyle {}^{2}E(f)=1quad }$ если есть я такой, что ж(я) > 0,

${displaystyle {}^{2}E(f)=0quad }$ если нет я такой, что ж(я) > 0.

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

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

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

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

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

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

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

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

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

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

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

Релятивизированная гиперарифметическая иерархия используется для определения гиперарифметическая сводимость. Данные наборы Икс и Y, мы говорим ${displaystyle Xleq _{HYP}Y}$ тогда и только тогда, когда есть ${displaystyle delta <omega _{1}^{Y}}$ такой, что Икс сводится ли Тьюринг к ${displaystyle Y^{(delta )}}$. Если ${displaystyle Xleq _{HYP}Y}$ и ${displaystyle Yleq _{HYP}X}$ тогда обозначение ${displaystyle Xequiv _{HYP}Y}$ используется для обозначения Икс и Y находятся гиперарифметически эквивалентный. Это более грубое отношение эквивалентности, чем Эквивалентность Тьюринга; например, каждый набор натуральных чисел гиперарифметически эквивалентен своему Прыжок Тьюринга но не эквивалент Тьюринга прыжку Тьюринга. Классы эквивалентности гиперарифметической эквивалентности известны как гиперградусы.

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

Обобщения

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

Отношение к другим иерархиям

Lightface		Жирный шрифт
Σ^0 0 = Π^0 0 = Δ^0 0 (иногда то же самое, что Δ^0 1)		Σ^0 0 = Π^0 0 = Δ^0 0 (если определено)
Δ^0 1 = рекурсивный		Δ^0 1 = прищемить
Σ^0 1 = рекурсивно перечислимый	Π^0 1 = ко-рекурсивно перечислимый	Σ^0 1 = грамм = открыто	Π^0 1 = F = закрыто
Δ^0 2		Δ^0 2
Σ^0 2	Π^0 2	Σ^0 2 = Fσ	Π^0 2 = граммδ
Δ^0 3		Δ^0 3
Σ^0 3	Π^0 3	Σ^0 3 = граммδσ	Π^0 3 = Fσδ
⋮		⋮
Σ^0 <ω = Π^0 <ω = Δ^0 <ω = Σ^1 0 = Π^1 0 = Δ^1 0 = арифметический		Σ^0 <ω = Π^0 <ω = Δ^0 <ω = Σ^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 = B = Борель
Σ^1 1 = лайтфейс аналитический	Π^1 1 = световой коаналитический	Σ^1 1 = А = аналитический	Π^1 1 = CA = коаналитический
Δ^1 2		Δ^1 2
Σ^1 2	Π^1 2	Σ^1 2 = PCA	Π^1 2 = CPCA
Δ^1 3		Δ^1 3
Σ^1 3	Π^1 3	Σ^1 3 = PCPCA	Π^1 3 = CPCPCA
⋮		⋮
Σ^1 <ω = Π^1 <ω = Δ^1 <ω = Σ^2 0 = Π^2 0 = Δ^2 0 = аналитический		Σ^1 <ω = Π^1 <ω = Δ^1 <ω = Σ^2 0 = Π^2 0 = Δ^2 0 = п = проективный
⋮		⋮

Рекомендации

• Х. Роджерс-младший, 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. Вычислимые структуры и гиперарифметическая иерархия, Эльзевир. ISBN  0-444-50072-3

внешняя ссылка

• Теория описательных множеств. Примечания Дэвида Маркера, Иллинойсский университет в Чикаго. 2002 г.
• Математическая логика II. Примечания Дага Нормана, Университет Осло. 2005 г.