Аналитическая иерархия

В математической логике и описательной теории множеств аналитическая иерархия является расширением арифметической иерархии . В аналитическую иерархию формул входят формулы на языке арифметики второго порядка , которые могут иметь кванторы как над множеством натуральных чисел, так и над множеством натуральных чисел . $\mathbb {N}$ , и над функциями из $\mathbb {N}$ к $\mathbb {N}$ . Аналитическая иерархия множеств классифицирует множества по формулам, которые можно использовать для их определения; это облегченная версия проективной иерархии .

Аналитическая иерархия формул

Обозначения $\Sigma _{0}^{1}=\Pi _{0}^{1}=\Delta _{0}^{1}$ указывает на класс формул языка арифметики второго порядка с кванторами чисел, но без кванторов множеств. Этот язык не содержит заданных параметров. Греческие буквы здесь являются светлыми символами, обозначающими выбор языка. Каждый соответствующий символ жирного шрифта обозначает соответствующий класс формул расширенного языка с параметром для каждого вещественного числа ; см. в проективной иерархии подробности .

Формула на языке арифметики второго порядка определяется как $\Sigma _{n+1}^{1}$ если она логически эквивалентна формуле вида $\exists X_{1}\cdots \exists X_{k}\psi$ где $\psi$ является $\Pi _{n}^{1}$ . Формула определяется как $\Pi _{n+1}^{1}$ если она логически эквивалентна формуле вида $\forall X_{1}\cdots \forall X_{k}\psi$ где $\psi$ является $\Sigma _{n}^{1}$ . Это индуктивное определение определяет классы $\Sigma _{n}^{1}$ и $\Pi _{n}^{1}$ для каждого натурального числа $n$ .

Куратовский и Тарский показали в 1931 году, что каждая формула языка арифметики второго порядка имеет пренексную нормальную форму : ^{[ 1 ]} и поэтому является $\Sigma _{n}^{1}$ или $\Pi _{n}^{1}$ для некоторых $n$ . Поскольку к любой формуле можно добавить бессмысленные квантификаторы, как только формуле будет присвоена классификация $\Sigma _{n}^{1}$ или $\Pi _{n}^{1}$ для некоторых $n$ ему будут даны классификации $\Sigma _{m}^{1}$ и $\Pi _{m}^{1}$ для всех $m$ больше, чем $n$ .

Аналитическая иерархия множеств натуральных чисел

Совокупности натуральных чисел присваивается классификация $\Sigma _{n}^{1}$ если оно определяется $\Sigma _{n}^{1}$ формула (с одной свободной числовой переменной и без свободных переменных). Набору присвоена классификация $\Pi _{n}^{1}$ если оно определяется $\Pi _{n}^{1}$ формула. Если набор состоит из обоих $\Sigma _{n}^{1}$ и $\Pi _{n}^{1}$ то ему дается дополнительная классификация $\Delta _{n}^{1}$ .

The $\Delta _{1}^{1}$ множества называются гиперарифметическими . Альтернативную классификацию этих множеств с помощью итерированных вычислимых функционалов обеспечивает гиперарифметическая теория .

Аналитическая иерархия подмножеств пространства Кантора и Бэра

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

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

Подмножество пространства Бэра имеет соответствующее подмножество пространства Кантора под отображением, которое берет каждую функцию из $\omega$ к $\omega$ к характеристической функции ее графика. Подмножеству пространства Бэра присвоена классификация $\Sigma _{n}^{1}$ , $\Pi _{n}^{1}$ , или $\Delta _{n}^{1}$ тогда и только тогда, когда соответствующее подмножество канторова пространства имеет ту же классификацию. Эквивалентное определение аналитической иерархии в пространстве Бэра дается путем определения аналитической иерархии формул с использованием функциональной версии арифметики второго порядка; тогда аналитическую иерархию подмножеств канторового пространства можно определить из иерархии пространства Бэра. Это альтернативное определение дает точно такую же классификацию, что и первое определение.

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

Расширения

Как и в случае с арифметической иерархией , можно определить релятивизированную версию аналитической иерархии. Язык расширен за счет добавления символа постоянного A. множества Формула расширенного языка индуктивно определяется как $\Sigma _{n}^{1,A}$ или $\Pi _{n}^{1,A}$ используя то же индуктивное определение, что и выше. Учитывая набор $Y$ , набор определяется как $\Sigma _{n}^{1,Y}$ если оно определяется $\Sigma _{n}^{1,A}$ формула, в которой символ $A$ интерпретируется как $Y$ ; аналогичные определения для $\Pi _{n}^{1,Y}$ и $\Delta _{n}^{1,Y}$ применять. Наборы, которые есть $\Sigma _{n}^{1,Y}$ или $\Pi _{n}^{1,Y}$ для любого параметра Y классифицируются в проективной иерархии и часто обозначаются жирным шрифтом греческих букв для обозначения использования параметров. ^{[ 2 ]}

Примеры

Для отношений $\prec$ на $\mathbb {N} ^{2}$ , заявление " $\prec$ это хороший заказ на $\mathbb {N}$ " является $\Pi _{1}^{1}$ . (Не путать с общим случаем обоснованных отношений на множествах, см. Иерархию Леви )
Множество всех натуральных чисел, являющихся индексами вычислимых ординалов, представляет собой $\Pi _{1}^{1}$ $\Pi _{1}^{1}$ набор, которого нет $\Sigma _{1}^{1}$ $\Sigma _{1}^{1}$ .
- Эти наборы именно те $\omega _{1}^{CK}$ -рекурсивно-перечислимые подмножества $\omega$ . [Бар75, с. 168]
Функция $f:\mathbb {N} \to \mathbb {N}$ определяется Эрбрана 1931 года тогда и только тогда, когда формализмом систем уравнений $f$ является гиперарифметическим. ^{[ 3 ]}
Набор непрерывных функций $f:[0,1]\to \mathbb {[} 0,1]$ которые имеют свойство среднего значения не ниже, чем $\Delta _{2}^{1}$ по иерархии. ^{[ 4 ]}
Набор элементов канторова пространства, которые являются характеристическими функциями хорошего упорядочения $\omega$ это $\Pi _{1}^{1}$ набор, которого нет $\Sigma _{1}^{1}$ . На самом деле этот набор не $\Sigma _{1}^{1,Y}$ для любого элемента $Y$ пространства Бэра.
Если аксиома конструктивности верна, то существует подмножество произведения пространства Бэра само на себя, которое есть $\Delta _{2}^{1}$ и является графиком хорошего упорядочения пространства Бэра. Если аксиома верна, то существует также $\Delta _{2}^{1}$ хорошая упорядоченность канторова пространства.

Характеристики

Для каждого $n$ у нас есть следующие строгие ограничения:

\Pi _{n}^{1}\subset \Sigma _{n+1}^{1}

,

\Pi _{n}^{1}\subset \Pi _{n+1}^{1}

,

\Sigma _{n}^{1}\subset \Pi _{n+1}^{1}

,

\Sigma _{n}^{1}\subset \Sigma _{n+1}^{1}

.

Набор, который находится в $\Sigma _{n}^{1}$ для некоторого n называется аналитическим . Необходимо с осторожностью отличать это использование от термина «аналитическое множество» , который имеет другое значение, а именно: ${\boldsymbol {\Sigma }}_{1}^{1}$ . ^{[ 5 ]}

Стол

Светлое лицо		Жирный шрифт
С ⁰ ₀ = П ⁰ ₀ = Д ⁰ ₀ (иногда то же, что ∆ ⁰ ₁)		С ⁰ ₀ = П ⁰ ₀ = Д ⁰ ₀ (если определено)
Д ⁰ ₁ = рекурсивный		Д ⁰ ₁ = закрыто открыто
С ⁰ ₁ = рекурсивно перечисляемый	П ⁰ ₁ = ко-рекурсивно перечисляемый	С ⁰ ₁ = G = открыто	П ⁰ ₁ = F = закрыто
Д ⁰ ₂		Д ⁰ ₂
С ⁰ ₂	П ⁰ ₂	С ⁰ ₂ = Ф _п	П ⁰ ₂ = г _δ
Д ⁰ ₃		Д ⁰ ₃
С ⁰ ₃	П ⁰ ₃	С ⁰ ₃ = г _дс	П ⁰ ₃ = Ф _сд
⋮		⋮
С ⁰ _<ω = Р ⁰ _<ω = ∆ ⁰ _<ω = S ¹ ₀ = П ¹ ₀ = Д ¹ ₀ = арифметический		С ⁰ _<ω = Р ⁰ _<ω = ∆ ⁰ _<ω = S ¹ ₀ = П ¹ ₀ = Д ¹ ₀ = жирный арифметический шрифт
⋮		⋮
Д ⁰ _а ( рекурсивный )		Д ⁰ _а ( счетное )
С ⁰ _а	П ⁰ _а	С ⁰ _а	П ⁰ _а
⋮		⋮
С ⁰ _{ой ^СК ₁} = П ⁰ _{ой ^СК ₁} = Д ⁰ _{ой ^СК ₁} = Д ¹ ₁ = гиперарифметический		С ⁰ _{ω ₁} = Р ⁰ _{ω ₁} = Д ⁰ _{ω ₁} = Д ¹ ₁ = Б = Борель
С ¹ ₁ = аналитика светлого лица	П ¹ ₁ = коаналитик светлой поверхности	С ¹ ₁ = А = аналитический	П ¹ ₁ = СА = коаналитический
Д ¹ ₂		Д ¹ ₂
С ¹ ₂	П ¹ ₂	С ¹ ₂ = PCA	П ¹ ₂ = КПКА
Д ¹ ₃		Д ¹ ₃
С ¹ ₃	П ¹ ₃	С ¹ ₃ = ПКПККА	П ¹ ₃ = CPCPCA
⋮		⋮
С ¹ _<ω = Р ¹ _<ω = ∆ ¹ _<ω = S ² ₀ = П ² ₀ = Д ² ₀ = аналитический		С ¹ _<ω = Р ¹ _<ω = ∆ ¹ _<ω = S ² ₀ = П ² ₀ = Д ² ₀ = P = проективный
⋮		⋮

См. также

Ссылки

^ П. Одифредди , Классическая теория рекурсии (1989), стр.378. Северная Голландия, 0-444-87295-7
^ П.Д. Уэлч, «Слабые системы детерминированности и арифметические квазииндуктивные определения» (проект версии 2010 г., стр. 3). По состоянию на 31 июля 2022 г.
^ П. Одифредди, Классическая теория рекурсии (1989), стр.33. Северная Голландия, 0-444-87295-7
^ Кинтанилья, М. (2022). «Числа областей во внутренних моделях теории множеств». arXiv : 2206.10754 [ math.LO ].
^ Т. Джех , « О дивный новый мир детерминированности » (загрузка в формате PDF). Рецензия на книгу, Бюллетень Американского математического общества , вып. 5, номер 3, ноябрь 1981 г. (стр. 339–349).

Роджерс, Х. (1967). Теория рекурсивных функций и эффективная вычислимость . МакГроу-Хилл.
Кекрис, А. (1995). Классическая описательная теория множеств (Тексты для аспирантов по математике, 156 изд.). Спрингер. ISBN 0-387-94374-9 .

Аналитическая иерархия в PlanetMath .

[1] П. Одифредди , Классическая теория рекурсии (1989), стр.378. Северная Голландия, 0-444-87295-7

[2] П.Д. Уэлч, «Слабые системы детерминированности и арифметические квазииндуктивные определения» (проект версии 2010 г., стр. 3). По состоянию на 31 июля 2022 г.

[3] П. Одифредди, Классическая теория рекурсии (1989), стр.33. Северная Голландия, 0-444-87295-7

[4] Кинтанилья, М. (2022). «Числа областей во внутренних моделях теории множеств». arXiv : 2206.10754 [ math.LO ].

[5] Т. Джех , « О дивный новый мир детерминированности » (загрузка в формате PDF). Рецензия на книгу, Бюллетень Американского математического общества , вып. 5, номер 3, ноябрь 1981 г. (стр. 339–349).

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]