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

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		Жирный шрифт
Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (иногда то же самое, что Δ⁰ ₁)		Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (если определено)
Δ⁰ ₁ = рекурсивный		Δ⁰ ₁ = прищемить
Σ⁰ ₁ = рекурсивно перечислимый	Π⁰ ₁ = ко-рекурсивно перечислимый	Σ⁰ ₁ = грамм = открыто	Π⁰ ₁ = F = закрыто
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂ = F_σ	Π⁰ ₂ = грамм_δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃ = грамм_δσ	Π⁰ ₃ = F_σδ
⋮		⋮
Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = арифметический		Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = жирный арифметический
⋮		⋮
Δ⁰ _α (α рекурсивный)		Δ⁰ _α (α счетный)
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^СК ₁ = Π⁰ _ω^СК ₁ = Δ⁰ _ω^СК ₁ = Δ¹ ₁ = гиперарифметический		Σ⁰ _ω₁ = Π⁰ _ω₁ = Δ⁰ _ω₁ = Δ¹ ₁ = B = Борель
Σ¹ ₁ = лайтфейс аналитический	Π¹ ₁ = световой коаналитический	Σ¹ ₁ = А = аналитический	Π¹ ₁ = CA = коаналитический
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂ = PCA	Π¹ ₂ = CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃ = PCPCA	Π¹ ₃ = CPCPCA
⋮		⋮
Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = аналитический		Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = п = проективный
⋮		⋮

внешняя ссылка

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

Navigation