Гиперарифметическая теория - 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 ^ {(дельта)}}$ для каждого ${displaystyle delta$. Предположим, что δ имеет обозначение е. Набор ${displaystyle 0 ^ {(дельта)}}$ определяется с использованием е следующее.

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

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

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

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

Третья характеристика гиперарифметических множеств, принадлежащая Клини, использует высший тип вычислимые функционалы. Функционал типа 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 ^ {(омега)}}$, и поэтому не находится в верхней части гиперарифметической иерархии, хотя арифметически не определяется Теорема Тарского о неопределимости.

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

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

Результаты о полноте также имеют фундаментальное значение для теории. Набор натуральных чисел ${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$ так что каждый элемент S обозначение порядкового номера меньше, чем ${displaystyle alpha}$. Для любого подмножества Т пространства Бэра, состоящего только из характеристических функций порядков скважин, существует ${displaystyle alpha$ так что каждый порядковый номер, представленный в Т меньше чем ${displaystyle alpha}$.

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

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

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

Релятивизированная гиперарифметическая иерархия используется для определения гиперарифметическая сводимость. Данные наборы Икс и Y, мы говорим ${displaystyle Xleq _ {HYP} Y}$ тогда и только тогда, когда есть ${displaystyle delta$ такой, что Икс сводится ли Тьюринг к ${displaystyle Y ^ {(дельта)}}$. Если ${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 г.