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

«Проективный набор» перенаправляется сюда. Для карточной игры см. Проективный набор (игра).

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

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

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

Отношение к аналитической иерархии

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

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

Стол

Lightface		Жирный шрифт
Σ^0 0 = Π^0 0 = Δ^0 0 (иногда то же самое, что Δ^0 1)		Σ^0 0 = Π^0 0 = Δ^0 0 (если определено)
Δ^0 1 = рекурсивный		Δ^0 1 = прищемить
Σ^0 1 = рекурсивно перечислимый	Π^0 1 = ко-рекурсивно перечислимый	Σ^0 1 = грамм = открыто	Π^0 1 = F = закрыто
Δ^0 2		Δ^0 2
Σ^0 2	Π^0 2	Σ^0 2 = Fσ	Π^0 2 = граммδ
Δ^0 3		Δ^0 3
Σ^0 3	Π^0 3	Σ^0 3 = граммδσ	Π^0 3 = Fσδ
⋮		⋮
Σ^0 <ω = Π^0 <ω = Δ^0 <ω = Σ^1 0 = Π^1 0 = Δ^1 0 = арифметический		Σ^0 <ω = Π^0 <ω = Δ^0 <ω = Σ^1 0 = Π^1 0 = Δ^1 0 = жирный арифметический
⋮		⋮
Δ^0 α (α рекурсивный )		Δ^0 α (α счетный )
Σ^0 α	Π^0 α	Σ^0 α	Π^0 α
⋮		⋮
Σ^0 ω^СК 1 = Π^0 ω^СК 1 = Δ^0 ω^СК 1 = Δ^1 1 = гиперарифметический		Σ^0 ω1 = Π^0 ω1 = Δ^0 ω1 = Δ^1 1 = B = Борель
Σ^1 1 = лайтфейс аналитический	Π^1 1 = световой коаналитический	Σ^1 1 = А = аналитический	Π^1 1 = CA = коаналитический
Δ^1 2		Δ^1 2
Σ^1 2	Π^1 2	Σ^1 2 = PCA	Π^1 2 = CPCA
Δ^1 3		Δ^1 3
Σ^1 3	Π^1 3	Σ^1 3 = PCPCA	Π^1 3 = CPCPCA
⋮		⋮
Σ^1 <ω = Π^1 <ω = Δ^1 <ω = Σ^2 0 = Π^2 0 = Δ^2 0 = аналитический		Σ^1 <ω = Π^1 <ω = Δ^1 <ω = Σ^2 0 = Π^2 0 = Δ^2 0 = п = проективный
⋮		⋮

Рекомендации

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