ボレル階層
古典的な記述集合論において、低ランクのボレル階層は別の名前でも知られている。
Σ 1 0 {\displaystyle \mathbf {\Sigma } _{1}^{0}} 集合は開集合である. Π 1 0 {\displaystyle \mathbf {\Pi } _{1}^{0}} 集合は閉集合である。
Σ 2 0 {\displaystyle \mathbf {\Sigma } _{2}^{0}} 集合は閉集合の可算和であるが、これはFσ 集合と呼ばれている。 Π 2 0 {\displaystyle \mathbf {\Pi } _{2}^{0}} 集合はその双対クラスであり、開集合の可算交叉で書ける。これらの集合はGδ 集合と呼ばれている。
細字のボレル階層 (実効的ボレル階層とも呼ばれる) は太字のボレル階層の実効的バージョンである。これは実効的記述集合論や再帰理論において重要である。細字のボレル階層は実効ポーランド空間の部分集合の算術的階層を拡張したものであり、超算術的階層と密接な関係がある。
細字のボレル階層は任意の実効ポーランド空間上で定義できる。これは、チャーチ・クリーネ順序数 ω 1 C K {\displaystyle \omega _{1}^{\mathrm {CK} }} 未満の0でない可算順序数 α {\displaystyle \alpha } についてのクラス Σ α 0 {\displaystyle \Sigma _{\alpha }^{0}} , Π α 0 {\displaystyle \Pi _{\alpha }^{0}} , Δ α 0 {\displaystyle \Delta _{\alpha }^{0}} から構成される。各クラスは空間の部分集合からなる。これらのクラス、およびクラスの要素に対する'コードは帰納的に以下のように定義される:
集合が Σ 1 0 {\displaystyle \Sigma _{1}^{0}} であることは、それが実効的開集合であることと同値である。すなわち、開集合であって基本開集合の列の帰納的可算な和になっていることである。そのような集合のコードはペア (0,e) であり、ここで e は基本開集合列を列挙するプログラムのインデックスである。