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

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

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

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

Первое определение гиперарифметических множеств использует аналитическую иерархию . Множество натуральных чисел классифицируется на уровне этой иерархии, если оно определяется формулой арифметики второго порядка только с кванторами существования множества и без других кванторов множества. Множество классифицируется на уровне аналитической иерархии, если оно определяется формулой арифметики второго порядка только с кванторами всеобщности множества и без других кванторов множества. Множество является , если оно является и . Гиперарифметические множества — это в точности множества. ${\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 \rangle }$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждое арифметическое множество является гиперарифметическим, но существует множество других гиперарифметических множеств. Одним из примеров гиперарифметического, неарифметического множества является множество T чисел Гёделя формул арифметики Пеано , которые истинны в стандартных натуральных числах . Множество T эквивалентно по Тьюрингу множеству и, таким образом, не находится высоко в гиперарифметической иерархии, хотя оно не является арифметически определимым по теореме Тарского о неопределенности . ${\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}}}$
• Множество натуральных чисел e, такое, что вычислимая функция вычисляет характеристическую функцию полного упорядочения натуральных чисел. Это индексы рекурсивных ординалов . ${\displaystyle \phi _{e}(x,y)}$
• Множество элементов пространства Бэра , которые являются характеристическими функциями полного упорядочения натуральных чисел (с использованием эффективного изоморфизма) . ${\displaystyle \mathbb {N} ^{\mathbb {N} }\cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} })}$

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

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

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

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

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

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

Обобщения

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

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

Эта коробка:

• вид
• разговаривать
• редактировать

Ссылки

• H. Rogers , Jr., 1967. Теория рекурсивных функций и эффективная вычислимость , второе издание 1987, MIT Press. ISBN  0-262-68052-1 (мягкая обложка), ISBN 0-07-053522-1 
• G. Sacks , 1990. Теория высшей рекурсии, Springer-Verlag. ISBN 3-540-19305-7 
• С. Симпсон , 1999. Подсистемы арифметики второго порядка , Springer-Verlag.
• CJ Ash, JF Knight , 2000. Вычислимые структуры и гиперарифметическая иерархия , Elsevier. ISBN 0-444-50072-3 

Цитаты

1. Теория вычислимости гиперарифметических множеств
2. SG Simpson, Иерархия, основанная на операторе перехода, стр. 268--269. Симпозиум Клини (Северная Голландия, 1980)
3. CJ Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Исследования по логике и основаниям математики, 2000), гл. 5
4. Д. Натинга, Теорема вложения для группы автоморфизмов степеней α-перечисления (стр. 27), докторская диссертация, Университет Лидса, 2019.

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

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