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

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

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

Наборы Бореля

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

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

Жирный шрифт Бореля иерархия

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

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

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

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

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

Борелевские множества малого ранга

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

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

Иерархия Lightface

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

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

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

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

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

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

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

Отношение к другим иерархиям

Эта коробка:

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

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

• Проективная иерархия
• Иерархия Вейджа
• Иерархия Веблена

Ссылки

1. PG Hinman, *Иерархии теории рекурсии*. Перспективы математической логики, Springer-Verlag (1978). ISBN 3-540-07904-1.
2. Д. Мартин, Определенность Бореля, Annals of Mathematics, т. 102, стр. 363--371 (1975)

Источники

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