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

В математической логике иерархия Бореля представляет собой стратификацию борелевской алгебры , порожденную открытыми подмножествами польского пространства ; элементы этой алгебры называются борелевскими множествами . Каждому множеству Бореля присвоен уникальный счетный порядковый номер, называемый рангом множества Бореля. Иерархия Бореля представляет особый интерес в дескриптивной теории множеств .

Одним из распространенных применений иерархии Бореля является доказательство фактов о борелевских множествах с использованием трансфинитной индукции по рангу. Свойства множеств малых конечных рангов важны в теории меры и анализе .

Борелевские множества [ править ]

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

Краткое доказательство того, что борелевская алгебра корректно определена, основано на показе того, что все множество степеней пространства замкнуто относительно дополнений и счетных объединений, и, таким образом, борелевская алгебра является пересечением всех семейств подмножеств пространства, которые обладают этими свойствами замыкания. . Это доказательство не дает простой процедуры определения того, является ли множество борелевским. Целью создания иерархии Бореля является предоставление более явной характеристики борелевских множеств.

Иерархия Бореля, жирным шрифтом выделенная

Иерархия Бореля или иерархия Бореля, выделенная жирным шрифтом, в пространстве X состоит из классов $\mathbf {\Sigma } _{\alpha }^{0}$ , $\mathbf {\Pi } _{\alpha }^{0}$ , и $\mathbf {\Delta } _{\alpha }^{0}$ для каждого счетного ординала $\alpha$ больше нуля. классов состоит из подмножеств X. Каждый из этих Классы определяются индуктивно по следующим правилам:

Набор находится в $\mathbf {\Sigma } _{1}^{0}$ тогда и только тогда, когда он открыт.
Набор находится в $\mathbf {\Pi } _{\alpha }^{0}$ тогда и только тогда, когда его дополнение находится в $\mathbf {\Sigma } _{\alpha }^{0}$ .
Набор $A$ находится в $\mathbf {\Sigma } _{\alpha }^{0}$ для $\alpha >1$ тогда и только тогда, когда существует последовательность множеств $A_{1},A_{2},\ldots$ такой, что каждый $A_{i}$ находится в $\mathbf {\Pi } _{\alpha _{i}}^{0}$ для некоторых $\alpha _{i}<\alpha$ и $A=\bigcup A_{i}$ .
Набор находится в $\mathbf {\Delta } _{\alpha }^{0}$ тогда и только тогда, когда оно одновременно находится в $\mathbf {\Sigma } _{\alpha }^{0}$ и в $\mathbf {\Pi } _{\alpha }^{0}$ .

Мотивация создания иерархии состоит в том, чтобы следовать тому, как борелевское множество может быть построено из открытых множеств с использованием дополнения и счетных объединений. Говорят, что борелевское множество имеет конечный ранг , если оно принадлежит $\mathbf {\Sigma } _{\alpha }^{0}$ для некоторого конечного ординала $\alpha$ ; в противном случае он имеет бесконечный ранг .

Если $\mathbf {\Sigma } _{1}^{0}\subseteq \mathbf {\Sigma } _{2}^{0}$ тогда можно показать, что иерархия имеет следующие свойства:

Для каждого α , $\mathbf {\Sigma } _{\alpha }^{0}\cup \mathbf {\Pi } _{\alpha }^{0}\subseteq \mathbf {\Delta } _{\alpha +1}^{0}$ . Таким образом, как только набор окажется в $\mathbf {\Sigma } _{\alpha }^{0}$ или $\mathbf {\Pi } _{\alpha }^{0}$ , этот набор будет во всех классах иерархии, соответствующих порядковым номерам больше α
$\bigcup _{\alpha <\omega _{1}}\mathbf {\Sigma } _{\alpha }^{0}=\bigcup _{\alpha <\omega _{1}}\mathbf {\Pi } _{\alpha }^{0}=\bigcup _{\alpha <\omega _{1}}\mathbf {\Delta } _{\alpha }^{0}$ . Более того, множество входит в это объединение тогда и только тогда, когда оно борелевское.
Если $X$ — несчетное польское пространство, можно показать, что $\mathbf {\Sigma } _{\alpha }^{0}$ не содержится в $\mathbf {\Pi } _{\alpha }^{0}$ для любого $\alpha <\omega _{1}$ , и, таким образом, иерархия не разрушается.

Борелевские множества малого ранга [ править ]

Классы малого ранга известны под альтернативными названиями в классической дескриптивной теории множеств.

The $\mathbf {\Sigma } _{1}^{0}$ множества являются открытыми множествами. $\mathbf {\Pi } _{1}^{0}$ множества являются закрытыми множествами.
The $\mathbf {\Sigma } _{2}^{0}$ множества представляют собой счетные объединения замкнутых множеств и называются F _σ множествами . $\mathbf {\Pi } _{2}^{0}$ множества являются двойственным классом и могут быть записаны как счетное пересечение открытых множеств. называются Gδ _{множествами} Эти множества .

Иерархия Lightface [ править ]

Иерархия Бореля светлой грани (также называемая эффективной иерархией Бореля). ^[1]^{стр.163--164}) является эффективной версией иерархии Бореля, выделенной жирным шрифтом. Это важно для эффективной описательной теории множеств и теории рекурсии . Иерархия Бореля с легким лицом расширяет арифметическую иерархию подмножеств эффективного польского пространства . Это тесно связано с гиперарифметической иерархией .

Иерархию Бореля с легкими гранями можно определить в любом эффективном польском пространстве. Состоит из классов $\Sigma _{\alpha }^{0}$ , $\Pi _{\alpha }^{0}$ и $\Delta _{\alpha }^{0}$ для каждого ненулевого счетного порядкового номера $\alpha$ меньше, чем порядковый номер Чёрча-Клин $\omega _{1}^{\mathrm {CK} }$ . Каждый класс состоит из подмножеств пространства. Классы и коды элементов классов индуктивно определяются следующим образом: ^[2]

Набор $\Sigma _{1}^{0}$ тогда и только тогда, когда оно эффективно открыто , то есть открытое множество, которое является объединением вычислимо перечислимой последовательности базовых открытых множеств. Кодом такого набора является пара (0,e) , где e — индекс программы, перечисляющей последовательность базовых открытых множеств.
Набор $\Pi _{\alpha }^{0}$ тогда и только тогда, когда его дополнение $\Sigma _{\alpha }^{0}$ . Кодом одного из этих наборов является пара (1,c) , где c — код дополнительного набора.
Набор $\Sigma _{\alpha }^{0}$ если существует вычислимо перечислимая последовательность кодов для последовательности $A_{1},A_{2},\ldots$ наборов таких, что каждое $A_{i}$ является $\Pi _{\alpha _{i}}^{0}$ для некоторых $\alpha _{i}<\alpha$ и $A=\bigcup A_{i}$ . Код для $\Sigma _{\alpha }^{0}$ set — пара (2,e) , где e — индекс программы, перечисляющей коды последовательности $A_{i}$ .

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

Можно показать, что для каждого $\alpha <\omega _{1}^{\mathrm {CK} }$ есть наборы $\Sigma _{\alpha }^{0}\setminus \Pi _{\alpha }^{0}$ , и, таким образом, иерархия не разрушается. На этом этапе новые наборы добавляться не будут. $\omega _{1}^{\mathrm {CK} }$ , однако.

Знаменитая теорема Спектора и Клини гласит, что множество находится в иерархии Бореля с легкой гранью тогда и только тогда, когда оно находится на уровне $\Delta _{1}^{1}$ иерархии аналитической . Эти множества еще называют гиперарифметическими . Кроме того, для всех натуральных чисел $n>0$ , классы $\Sigma _{n}^{0}$ и $\Pi _{n}^{0}$ эффективной иерархии Бореля совпадают с классами $\Sigma _{n}^{0}$ и $\Pi _{n}^{0}$ одноименной арифметической иерархии . ^[1]^стр.168

Код для борелевского множества A светлой грани можно использовать для индуктивного определения дерева, узлы которого помечены кодами. помечен кодом A. Корень дерева Если узел помечен кодом вида (1,c) , то у него есть дочерний узел с кодом c . Если узел помечен кодом вида (2,e), то он имеет по одному дочернему элементу для каждого кода, перечисленного программой с индексом e . Если узел помечен кодом вида (0,e), то у него нет дочерних элементов. Это дерево описывает, как A строится из множеств меньшего ранга. Порядковые номера, используемые при построении A, гарантируют, что это дерево не имеет бесконечного пути, поскольку любой бесконечный путь через дерево должен включать в себя бесконечное количество кодов, начинающихся с 2 , и, таким образом, давать бесконечную убывающую последовательность ординалов. Обратно, если произвольное поддерево $\omega ^{<\omega }\,$ имеет свои узлы, последовательно помеченные кодами, и дерево не имеет бесконечных путей, то код в корне дерева является кодом для борелевского множества с легкой гранью. Ранг этого множества ограничен порядковым типом дерева в порядке Клини–Брауэра . Поскольку дерево арифметически определимо, этот ранг должен быть меньше $\omega _{1}^{\mathrm {CK} }$ . Это происхождение ординала Чёрча-Клин в определении иерархии светлых лиц.

Связь с другими иерархиями [ править ]

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

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

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

^ Jump up to: Перейти обратно: ^а ^б П.Г. Хинман, *Теоретико-рекурсивные иерархии*. Перспективы математической логики, Springer-Verlag (1978). ISBN 3-540-07904-1.
^ Д. Мартин, Определенность Бореля , Анналы математики, том. 102, стр. 363--371 (1975)

Источники [ править ]

Кехрис, Александр . Классическая описательная теория множеств . Тексты для аспирантов по математике, т. 156, Springer-Verlag, 1995. ISBN 3-540-94374-9 .
Джек, Томас . Теория множеств , 3-е издание. Спрингер, 2003. ISBN 3-540-44085-2 .

[Hinman78-1] Jump up to: Перейти обратно: ^а ^б П.Г. Хинман, *Теоретико-рекурсивные иерархии*. Перспективы математической логики, Springer-Verlag (1978). ISBN 3-540-07904-1.

[2] Д. Мартин, Определенность Бореля , Анналы математики, том. 102, стр. 363--371 (1975)

[1]

[2]