Гиперарифметическая теория - 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}}$

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

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

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

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

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

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

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

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

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

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

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

Третья характеризация гиперарифметических множеств, разработанная Клини, использует вычислимые функционалы более высокого типа . Функционал типа 2 определяется следующими правилами: ${\ displaystyle {} ^ {2} E \ двоеточие \ 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 чисел Гёделя формул арифметики Пеано , истинных в стандартных натуральных числах . Множество Т является Тьюринг эквивалентно множества , и поэтому не высоко в гиперарифметической иерархии, хотя это не является арифметический определяемым с помощью теоремы Тарской неопределимости . ${\ 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 _ {е} (х, у)}$
Множество элементов пространства Бэра, которые являются характеристическими функциями хорошего упорядочения натуральных чисел (с использованием эффективного изоморфизма . ${\ 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 \ альфа <\ omega _ {1} ^ {СК}}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ Sigma _ {1} ^ {1}}$ ${\ Displaystyle \ альфа <\ omega _ {1} ^ {СК}}$ ${\ 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 ^ {(\ дельта)}}$ ${\ displaystyle X}$ ${\ displaystyle X ^ {(0)}}$ ${\ Displaystyle X ^ {(1)} = X '}$ ${\ displaystyle \ omega _ {1} ^ {CK}}$ ${\ displaystyle \ omega _ {1} ^ {X}}$

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

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

Обобщения

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

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

Lightface		Жирный шрифт
Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (иногда то же, что Δ⁰ ₁)		Σ⁰ ₀= Π⁰ ₀= Δ⁰ ₀ (если определено)
Δ⁰ ₁= рекурсивный		Δ⁰ ₁= clopen
Σ⁰ ₁= рекурсивно перечислимый	Π⁰ ₁ = ко-рекурсивно перечислимый	Σ⁰ ₁= G = открытый	Π⁰ ₁= F = закрыто
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂= F _σ	Π⁰ ₂= G _δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃= G _δσ	Π⁰ ₃= F _σδ
⋮		⋮
Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀= арифметический		Σ⁰ _<ω= Π⁰ _<ω= Δ⁰ _<ω= Σ¹ ₀= Π¹ ₀= Δ¹ ₀ = жирный арифметический
⋮		⋮
Δ⁰ _α(α рекурсивный )		Δ⁰ _α(α счетно )
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^СК ₁ = Π⁰ _ω^СК ₁ = Δ⁰ _ω^СК ₁ = Δ¹ ₁= гиперарифметический		Σ⁰ _{ω ₁}= Π⁰ _{ω ₁}= Δ⁰ _{ω ₁}= Δ¹ ₁= B = Борель
Σ¹ ₁ = лайтфейс аналитический	Π¹ ₁ = лайтфейс коаналитический	Σ¹ ₁= A = аналитический	Π¹ ₁= CA = коаналитический
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂ = PCA	Π¹ ₂ = CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃ = PCPCA	Π¹ ₃ = CPCPCA
⋮		⋮
Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀= аналитический		Σ¹ _<ω= Π¹ _<ω= Δ¹ _<ω= Σ² ₀= Π² ₀= Δ² ₀= 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.
CJ Ash, JF Knight , 2000. Вычислимые структуры и гиперарифметическая иерархия , Elsevier. ISBN 0-444-50072-3

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

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

Languages

In other projects