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

редактировать

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

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

СОДЕРЖАНИЕ

1 Гиперарифметические множества и определимость
2 Гиперарифметические множества и повторные скачки Тьюринга: гиперарифметическая иерархия
3 Гиперарифметические множества и рекурсия в высших типах
4 Пример: набор истинности арифметики
5 Основные результаты
6 Релятивизированная гиперарифметичность и гиперградусы
7 Обобщения
8 Отношение к другим иерархиям
9 ссылки
10 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{\ displaystyle {} ^ {2} E (f) = 1 \ quad}

{} ^ {2} E (f) = 1 \ quad

если существует такое i, что f ( i)gt; 0,

{\ displaystyle {} ^ {2} E (f) = 0 \ quad}

{} ^ {2} E (f) = 0 \ quad

если не существует такого i, что f ( i)gt; 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

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