WikiDer > Проективная иерархия - Википедия

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

• ${ displaystyle { boldsymbol { Sigma}} _ {1} ^ {1}}$ если ${ displaystyle A}$ является аналитический
• ${ Displaystyle { boldsymbol { Pi}} _ {п} ^ {1}}$ если дополнять из ${ displaystyle A}$, ${ Displaystyle X setminus A}$, является ${ Displaystyle { boldsymbol { Sigma}} _ {п} ^ {1}}$
• ${ Displaystyle { boldsymbol { Sigma}} _ {п + 1} ^ {1}}$ если есть польское пространство ${ displaystyle Y}$ и ${ Displaystyle { boldsymbol { Pi}} _ {п} ^ {1}}$ подмножество ${ Displaystyle C substeq X раз Y}$ такой, что ${ displaystyle A}$ это проекция ${ displaystyle C}$; то есть, ${ Displaystyle А = {Икс в Икс середине существует у в Y (х, у) в С }}$

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

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

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

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

Стол

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

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