Проективная иерархия

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

концепция теории описательных множеств

В математической области теории описательных множеств, подмножество $A {\ displaystyle A}$ $A$ из польского пространства $X {\ displaystyle X}$ $X$ является проективным, если он равно $Σ n 1 {\ displaystyle {\ boldsymbol {\ Sigma}} _ {n} ^ {1}}$ ${\ boldsymbol {\ Sigma}} _ {n} ^ {1}$ для некоторого положительного целого числа $n {\ displaystyle n}$ $n$ . Здесь $A {\ displaystyle A}$ $A$ равно

$Σ 1 1 {\ displaystyle {\ boldsymbol {\ Sigma}} _ {1} ^ {1}}$ ${\ boldsymbol {\ Sigma}} _ {1} ^ {1}$ если $A {\ displaystyle A}$ $A$ аналитический
$Π n 1 {\ displaystyle {\ boldsymbol {\ Pi}} _ {n} ^ {1}}$ ${\ boldsymbol {\ Pi}} _ {n} ^ {1}$ , если дополнение к $A {\ displaystyle A}$ $A$ , $X ∖ A {\ displaystyle X \ setminus A}$ $X \ setminus A$ , будет $Σ n 1 { \ displaystyle {\ boldsymbol {\ Sigma}} _ {n} ^ {1}}$ ${\ boldsymbol {\ Sigma}} _ {n} ^ {1}$
$Σ n + 1 1 {\ displaystyle {\ boldsymbol {\ Sigma}} _ {n + 1} ^ {1}}$ ${\ boldsymbol {\ Sigma}} _ {{n + 1}} ^ {1}$ , если есть польский пробел $Y {\ displaystyle Y}$ $Y$ и $Π n 1 {\ displaystyle {\ boldsymbol {\ Pi}} _ {n} ^ {1}}$ ${\ boldsymbol {\ Pi}} _ {n} ^ {1}$ подмножество $C ⊆ X × Y {\ displaystyle C \ substeq X \ times Y}$ $C \ substeq X \ times Y$ такое, что $A {\ displaystyle A}$ $A$ - проекция $C {\ displaystyle C}$ $C$ ; то есть $A = {x ∈ X ∣ ∃ y ∈ Y (x, y) ∈ C} {\ displaystyle A = \ {x \ in X \ mid \ exists y \ in Y (x, y) \ in C \}}$ $A = \ {x \ in X \ mid \ существует y \ in Y (x, y) \ in C \}$

Выбор польского пробела $Y {\ displaystyle Y}$ $Y$ в третьем предложении выше не очень важен; его можно заменить в определении фиксированным бесчисленным польским пространством, скажем пространство Бэра или пространство Кантора или вещественная линия.

Связь с аналитической иерархией

Существует тесная взаимосвязь между релятивизированной аналитической иерархией на подмножествах пространства Бэра (обозначается светлыми буквами $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ и $Π {\ displaystyle \ Pi}$ $\ Pi$ ) и проективную иерархию на подмножествах пространства Бэра (обозначается жирными буквами $Σ {\ displaystyle {\ boldsymbol {\ Sigma}}}$ $\boldsymbol{\Sigma}$ и $Π {\ displaystyle {\ boldsymbol {\ Pi}}}$ $\ boldsymbol {\ Pi}$ ). Не каждое $Σ n 1 {\ displaystyle {\ boldsymbol {\ Sigma}} _ {n} ^ {1}}$ ${\ boldsymbol {\ Sigma}} _ {n} ^ {1}$ подмножество пространства Бэра равно $Σ n 1 {\ displaystyle \ Sigma _ {n} ^ {1}}$ $\ Sigma ^ 1_n$ . Однако верно, что если подмножество X пространства Бэра равно $Σ n 1 {\ displaystyle {\ boldsymbol {\ Sigma}} _ {n} ^ {1}}$ ${\ boldsymbol {\ Sigma}} _ {n} ^ {1}$ , тогда существует набор натуральных чисел A таких, что X равен $Σ n 1, A {\ displaystyle \ Sigma _ {n} ^ {1, A}}$ $\ Sigma _ {n} ^ {{1, A}}$ . Аналогичное утверждение справедливо для наборов $Π n 1 {\ displaystyle {\ boldsymbol {\ Pi}} _ {n} ^ {1}}$ ${\ boldsymbol {\ Pi}} _ {n} ^ {1}$ . Таким образом, множества, классифицируемые проективной иерархией, являются в точности наборами, классифицируемыми релятивизированной версией аналитической иерархии. Эта взаимосвязь важна в теории эффективных описательных множеств.

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

Таблица

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= проективный
⋮		⋮

Ссылки

Kechris, AS (1995), Classical Descriptive Set Theory, Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-0-387-94374-9
Rogers, Hartley (1987) [1967], Theory of Recursive Functions and Effective Computability, Первое издание MIT в мягкой обложке, ISBN 978-0-262-68052-3