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

Концепция описательной теории множеств

В математической области дескриптивной теории множеств подмножество польского пространства является проективным , если оно для некоторого положительного целого числа . Вот ${\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 X}$ ${\displaystyle A=\{x\in X\mid \exists y\in Y:(x,y)\in C\}.}$

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

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

Существует тесная связь между релятивизированной аналитической иерархией на подмножествах пространства Бэра (обозначаемой светлыми буквами и ) и проективной иерархией на подмножествах пространства Бэра (обозначаемой жирными буквами и ). Не каждое подмножество пространства Бэра является . Однако верно, что если подмножество X пространства Бэра является , то существует множество натуральных чисел A такое, что X является . Аналогичное утверждение справедливо для множеств. Таким образом, множества, классифицированные проективной иерархией, являются в точности множествами, классифицированными релятивизированной версией аналитической иерархии. Эта связь важна в эффективной дескриптивной теории множеств . Сформулированная в терминах определимости, множество действительных чисел является проективным тогда и только тогда, когда оно определимо на языке арифметики второго порядка с помощью некоторого действительного параметра. ^[1] ${\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}}$

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

Стол

Эта коробка:

• вид
• разговаривать
• редактировать

Смотрите также

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

Ссылки

1. Дж. Стил, «Что такое... кардинал Вудина?». Notices of the American Mathematical Society, т. 54, № 9 (2007), стр. 1147.

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