В теории рекурсии , гиперарифметическая теория является обобщением Тьюринга вычислимости . Он тесно связан с определимостью в арифметике второго порядка и со слабыми системами теории множеств, такими как теория множеств Крипке – Платека . Это важный инструмент в эффективной дескриптивной теории множеств .
В центре внимания теории гиперарифметики находятся наборы натуральных чисел, известные как гиперарифметические множества . Есть три эквивалентных способа определения этого класса множеств; изучение отношений между этими различными определениями - одна из причин изучения гиперарифметической теории.
Гиперарифметические множества и определимость
Первое определение гиперарифметических множеств использует аналитическую иерархию . Набор натуральных чисел классифицируется на уровнеэтой иерархии, если она определяется формулой арифметики второго порядка только с кванторами существования и без других кванторов множества. Набор классифицируется на уровнеаналитической иерархии, если она определяется формулой арифметики второго порядка только с универсальными кванторами множеств и без других кванторов множеств. Набор есть если это оба а также . Гиперарифметические множества - это в точности наборы.
Гиперарифметические множества и повторные скачки Тьюринга: гиперарифметическая иерархия
Определение гиперарифметических множеств как не зависит напрямую от результатов вычислимости. Второе, эквивалентное определение показывает, что гиперарифметические множества могут быть определены с помощью бесконечно повторяющихся скачков Тьюринга . Это второе определение также показывает, что гиперарифметические множества могут быть классифицированы в иерархию, расширяющую арифметическую иерархию ; гиперарифметические множества - это именно те множества, которым присвоен ранг в этой иерархии.
Каждый уровень гиперарифметической иерархии соответствует счетному порядковому номеру ( порядковому номеру ), но не все счетные порядковые номера соответствуют уровню иерархии. Порядковые номера , используемые иерархией, имеют порядковую нотацию , которая является конкретным и эффективным описанием порядкового номера.
Порядковые обозначения - это эффективное описание счетного порядкового числа натуральным числом. Для определения гиперарифметической иерархии требуется система порядковых обозначений. Основное свойство, которым должна обладать порядковая запись, состоит в том, что она эффективно описывает порядковый номер в терминах малых порядковых чисел. Следующее индуктивное определение является типичным; он использует функцию сопряжения .
- Число 0 - это обозначение порядкового номера 0.
- Если n - обозначение ординала λ, то обозначение λ + 1;
- Предположим, что δ - предельный ординал . Обозначение для δ - это число вида, где e - индекс полной вычислимой функциитакое, что для каждого n ,обозначает порядковый номер λ n, меньший, чем δ, а δ - вершина множества.
Существует только счетное количество порядковых обозначений, поскольку каждое обозначение является натуральным числом; таким образом, существует счетный ординал, который является верхней гранью всех ординалов, имеющих обозначение. Этот порядковый номер известен как порядковый номер Черча-Клини и обозначается. Обратите внимание, что этот порядковый номер по-прежнему является счетным, поскольку символ является лишь аналогией с первым несчетным порядковым номером,. Множество всех натуральных чисел, являющихся порядковыми обозначениями, обозначаетсяи позвонил Клини.
Порядковые обозначения используются для определения повторных переходов Тьюринга. Это наборы натуральных чисел, обозначаемые для каждого . Предположим, что δ имеет обозначение e . Наборопределяется с помощью e следующим образом.
- Если δ = 0, то это пустое множество.
- Если δ = λ + 1, то это скачок Тьюринга . Обозначения а также обычно используются для а также , соответственно.
- Если δ - предельный ординал, пусть - последовательность ординалов меньше δ, заданная обозначением e . Набор дается правилом . Это эффективное соединение множеств.
Хотя строительство зависит от наличия фиксированного обозначения для б, и каждый бесконечные порядковые имеет множество обозначений, теорему Spector показывает , что степень Тюринга из зависит только от δ, а не от конкретных используемых обозначений, и, таким образом, хорошо определена с точностью до степени Тьюринга.
Гиперарифметическая иерархия определяется этими повторяющимися скачками Тьюринга. Множество натуральных чисел X классифицируется на уровне δ гиперарифметической иерархии, так как, Если X является Тьюрингу To. Всегда будет наименьшее такое δ, если оно есть; именно этот минимум δ , который измеряет уровень uncomputability из X .
Гиперарифметические множества и рекурсия в высших типах
Третья характеризация гиперарифметических множеств, разработанная Клини, использует вычислимые функционалы более высокого типа . Функционал типа 2 определяется следующими правилами:
- если существует такое i , что f ( i )> 0,
- если не существует такого i , что f ( i )> 0.
Используя точное определение вычислимости относительно функционала типа 2, Клини показал, что набор натуральных чисел гиперарифметичен тогда и только тогда, когда он вычислим относительно .
Пример: набор истинности арифметики
Каждый арифметический набор гиперарифметичен, но есть много других гиперарифметических множеств. Одним из примеров гиперарифметического, неарифметического множества является множество T чисел Гёделя формул арифметики Пеано , истинных в стандартных натуральных числах.. Множество Т является Тьюринг эквивалентно множеству, и поэтому не находится на высоком уровне в гиперарифметической иерархии, хотя и не определяется арифметически теоремой Тарского о неопределимости .
Фундаментальные результаты
Основные результаты теории гиперарифметики показывают, что три приведенных выше определения определяют один и тот же набор наборов натуральных чисел. Эти эквивалентности принадлежат Клини.
Результаты о полноте также имеют фундаментальное значение для теории. Набор натуральных чиселзавершить, если он на уровнеиз аналитической иерархии и каждыймножество натуральных чисел сводится к нему. Определение полное подмножество пространства Бэра () похож. Несколько наборов, связанных с теорией гиперарифметики: полный:
- Клини , множество натуральных чисел, которые являются обозначениями порядковых чисел
- Множество натуральных чисел e таких, что вычислимая функциявычисляет характеристическую функцию хорошего упорядочения натуральных чисел. Это индексы рекурсивных ординалов .
- Множество элементов пространства Бэра, которые являются характеристическими функциями хорошего упорядочения натуральных чисел (с использованием эффективного изоморфизма.
Результаты, известные как ограничения следуют из этих результатов о полноте. Для любоймножество S порядковых обозначений, существуеттакой, что каждый элемент S является обозначением для порядкового номера меньше, чем. Для любого подмножества T пространства Бэра, состоящего только из характеристических функций порядков скважин, существуеттакой, что каждый порядковый номер, представленный в T , меньше, чем.
Релятивизированная гиперарифметичность и гиперградусы
Определение можно относить к набору X натуральных чисел: в определении порядковой нотации условие для предельных порядковых номеров изменено так, что вычислимому перечислению последовательности порядковых нотаций разрешено использовать X в качестве оракула. Набор чисел, являющихся порядковыми обозначениями относительно X , обозначается. Верхняя грань ординалов, представленных в обозначается ; это счетный порядковый номер не меньше, чем.
Определение можно также относить к произвольному множеству натуральных чисел. Единственное изменение в определении состоит в том, чтоопределяется как X, а не как пустое множество, так чтоэто скачок Тьюринга X и т. д. Вместо того, чтобы заканчиваться наиерархия относительно X проходит через все порядковые номера меньше, чем.
Релятивизированная гиперарифметическая иерархия используется для определения гиперарифметической сводимости . Учитывая множества X и Y , мы говорим тогда и только тогда, когда есть такое, что X сводится по Тьюрингу к. Если а также тогда обозначение используется для указания X и Y являются hyperarithmetically эквивалентны . Это более грубое отношение эквивалентности, чем эквивалентность по Тьюрингу ; например, каждый набор натуральных чисел гиперарифметически эквивалентен прыжку Тьюринга, но не эквивалентен прыжку Тьюринга. Классы эквивалентности гиперарифметической эквивалентности известны как гиперстепени .
Функция, которая переводит набор X визвестен как гиперпрыжок по аналогии с прыжком Тьюринга. Установлены многие свойства гиперскачка и гиперстепеней. В частности, известно, что проблема Поста для гиперстепеней имеет положительный ответ: для любого множества натуральных чисел X существует множество натуральных чисел Y такое, что.
Обобщения
Гиперарифметическая теория обобщается теорией α-рекурсии , которая представляет собой исследование определимых подмножеств допустимых ординалов . Гиперарифметическая теория - это частный случай, когда α является.
Отношение к другим иерархиям
Lightface | Жирный шрифт | ||
Σ0 0 = Π0 0 = Δ0 0 (иногда то же самое, что Δ0 1) | Σ0 0= Π0 0= Δ0 0 (если определено) | ||
Δ0 1= рекурсивный | Δ0 1= clopen | ||
Σ0 1= рекурсивно перечислимый | Π0 1 = ко-рекурсивно перечислимый | Σ0 1= G = открытый | Π0 1= F = закрыто |
Δ0 2 | Δ0 2 | ||
Σ0 2 | Π0 2 | Σ0 2= F σ | Π0 2= G δ |
Δ0 3 | Δ0 3 | ||
Σ0 3 | Π0 3 | Σ0 3= G δσ | Π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= A = аналитический | Π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= 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 г.