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

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

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

Содержание

1 Аналитическая иерархия формул
2 Аналитическая иерархия множеств натуральных чисел
3 Аналитическая иерархия на подмножествах пространства Кантора и Бэра
4 Расширения
5 Примеры
6 Свойства
7 Таблица
8 См. также
9 Ссылки

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

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

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

Поскольку каждая формула имеет предваренную нормальную форму , каждая формула на языке арифметики второго порядка равно $Σ n 1 {\ displaystyle \ Sigma _ {n} ^ {1}}$ $\ Sigma ^ 1_n$ или $Π n 1 {\ displaystyle \ Pi _ {n} ^ {1}}$ $\Pi^1_n$ для некоторых $n {\ displaystyle n}$ $n$ . Поскольку бессмысленные кванторы могут быть добавлены к любой формуле, если формуле присвоена классификация $Σ n 1 {\ displaystyle \ Sigma _ {n} ^ {1}}$ $\ Sigma ^ 1_n$ или $Π n 1 {\ displaystyle \ Pi _ {n} ^ {1}}$ $\Pi^1_n$ для некоторого $n {\ displaystyle n}$ $n$ ему будут присвоены классификации $Σ m 1 { \ displaystyle \ Sigma _ {m} ^ {1}}$ $\ Sigma _ {m} ^ {1}$ и $Π m 1 {\ displaystyle \ Pi _ {m} ^ {1}}$ $\ Pi _ {m} ^ {1}$ для всех $m {\ displaystyle m}$ $m$ больше, чем $n {\ displaystyle n}$ $n$ .

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

Набору натуральных чисел присваивается классификация $Σ n 1 {\ displaystyle \ Sigma _ {n} ^ {1}}$ $\ Sigma ^ 1_n$ , если он определяется с помощью $Σ n 1 {\ displaystyle \ Sigma _ {n} ^ {1 }}$ $\ Sigma ^ 1_n$ формула. Набору присваивается классификация $Π n 1 {\ displaystyle \ Pi _ {n} ^ {1}}$ $\Pi^1_n$ , если он определяется с помощью $Π n 1 {\ displaystyle \ Pi _ {n} ^ {1}}$ $\Pi^1_n$ формула. Если оба набора - $Σ n 1 {\ displaystyle \ Sigma _ {n} ^ {1}}$ $\ Sigma ^ 1_n$ и $Π n 1 {\ displaystyle \ Pi _ {n} ^ {1 }}$ $\Pi^1_n$ затем ему дается дополнительная классификация $Δ n 1 {\ displaystyle \ Delta _ {n} ^ {1}}$ $\ Delta _ {n} ^ {1}$ .

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

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

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

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

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

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

Расширения

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

Примеры

Набор всех натуральных чисел, которые являются индексами вычислимых ординалов, есть a $Π 1 1 {\ displaystyle \ Pi _ {1} ^ {1}}$ $\ Pi _ {1} ^ {1}$ набор, который не является $Σ 1 1 {\ displaystyle \ Sigma _ {1} ^ {1} }$ $\ Sigma _ {1} ^ {1}$ .
Набор элементов пространства Кантора, которые являются характеристическими функциями упорядочения скважин $ω {\ displaystyle \ omega}$ $\ omega$ , представляет собой $Π 1 1 {\ displaystyle \ Pi _ {1} ^ {1}}$ $\ Pi _ {1} ^ {1}$ набор, отличный от $Σ 1 1 {\ displaystyle \ Sigma _ {1} ^ {1}}$ $\ Sigma _ {1} ^ {1}$ . Фактически, этот набор не является $Σ 1 1, Y {\ displaystyle \ Sigma _ {1} ^ {1, Y}}$ $\ Sigma _ {1} ^ {{1, Y}}$ для любого элемента $Y {\ displaystyle Y}$ $Y$ пространства Бэра.
Если выполняется аксиома конструктивности, то существует подмножество произведения пространства Бэра на себя, которое равно $Δ 2 1 { \ displaystyle \ Delta _ {2} ^ {1}}$ $\ Дельта _ {2} ^ {1}$ и является графиком упорядочения скважины пространства Бэра. Если аксиома верна, то также существует $Δ 2 1 {\ displaystyle \ Delta _ {2} ^ {1}}$ $\ Дельта _ {2} ^ {1}$ хорошее упорядочение пространства Кантора.

Свойства

Для каждого $n {\ displaystyle n}$ $n$ мы имеем следующие строгие ограничения:

Π n 1 ⊂ Σ n + 1 1 {\ displaystyle \ Pi _ {n} ^ {1} \ подмножество \ Sigma _ {n + 1} ^ {1}}

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

Π N 1 ⊂ Π n + 1 1 {\ displaystyle \ Pi _ {n} ^ {1} \ subset \ Pi _ {n + 1} ^ {1}}

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

Σ n 1 ⊂ Π n + 1 1 {\ displaystyle \ Sigma _ {n} ^ {1} \ subset \ Pi _ {n + 1} ^ {1}}

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

Σ n 1 ⊂ Σ n + 1 1 {\ displaystyle \ Sigma _ {n} ^ {1} \ subset \ Sigma _ {n + 1} ^ {1}}

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

Набор, который находится в $Σ n 1 { \ displaystyle \ Sigma _ {n} ^ {1}}$ $\ Sigma ^ 1_n$ для некоторого n называется аналитическим . Требуется осторожность, чтобы отличать это использование от термина аналитическая совокупность, который имеет другое значение.

Таблица

Lightface		Boldface
Σ. 0= Π. 0= Δ. 0(иногда то же самое, что Δ. 1)		Σ. 0= Π. 0= Δ. 0(если определено)
Δ. 1= рекурсивный		Δ. 1= clopen
Σ. 1= рекурсивно перечисляемый	Π. 1= ко-рекурсивно перечисляемый	Σ. 1= G = открытый	Π. 1= F = закрытый
Δ. 2		Δ. 2
Σ. 2	Π. 2	Σ. 2= Fσ	Π. 2= Gδ
Δ. 3		Δ. 3
Σ. 3	Π. 3	Σ. 3= G δσ	Π. 3= F σδ
⋮		⋮
Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= арифметический		Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= жирный арифметический
⋮		⋮
Δ. α(α рекурсивный )		Δ. α(α счетный )
Σ. α	Π. α	Σ. α	Π. α
⋮		⋮
Σ. ω. 1 = Π. ω. 1 = Δ. ω. 1 = Δ. 1= гиперарифметический		Σ. ω1= Π. ω1= Δ. ω1= Δ. 1= B= Борель
Σ. 1= светолицый аналитический	Π. 1= светолицый коаналитический	Σ. 1= A = аналитический	Π. 1= CA = коаналитический
Δ. 2		Δ. 2
Σ. 2	Π. 2	Σ. 2= PCA	Π. 2= CPCA
Δ. 3		Δ. 3
Σ. 3	Π. 3	Σ. 3= PCPCA	Π. 3= CPCPCA
⋮		⋮
Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= аналитический		Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= P= проективный
⋮		⋮

См. Также

Быстрорастущая иерархия

Ссылки

Rogers, H. (1967). Теория рекурсивных функций и эффективная вычислимость. McGraw-Hill.
Kechris, A. (1995). Classical Descriptive Set Theory (Graduate Texts in Mathematics 156 ed.). Springer. ISBN 0-387-94374-9.

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