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

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

${\boldsymbol {\Sigma }}_{1}^{1}$ если $A$ аналитический
${\boldsymbol {\Pi }}_{n}^{1}$ если дополнение $A$ , $X\setminus A$ , является ${\boldsymbol {\Sigma }}_{n}^{1}$
${\boldsymbol {\Sigma }}_{n+1}^{1}$ если есть польское место $Y$ и ${\boldsymbol {\Pi }}_{n}^{1}$ подмножество $C\subseteq X\times Y$ такой, что $A$ это проекция $C$ на $X$ ; то есть, $A=\{x\in X\mid \exists y\in Y:(x,y)\in C\}.$

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

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

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

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

Таблица [ править ]

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

См. также [ править ]

Иерархия Бореля

Ссылки [ править ]

^ Дж. Стил, « Что такое... кардинал Вудина? ». Уведомления Американского математического общества, том. 54, нет. 9 (2007), с.1147.

Кехрис, А.С. (1995), Классическая описательная теория множеств , Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-94374-9
Роджерс, Хартли (1987) [1967], Теория рекурсивных функций и эффективная вычислимость , Первое издание MIT в мягкой обложке, ISBN 978-0-262-68052-3

[1] Дж. Стил, « Что такое... кардинал Вудина? ». Уведомления Американского математического общества, том. 54, нет. 9 (2007), с.1147.

[1]