ボレル階層

数理論理学において、ボレル階層（英語: Borel hierarchy）はポーランド空間の開集合によって生成されるボレル代数の階層化である; この代数の要素はボレル集合と呼ばれる。各ボレル集合にはランクと呼ばれる一意的な可算順序数が割り当てられる。ボレル階層は記述集合論において特に注目されている。 ボレル階層の一般的な使用法の1つは、ランクに関する超限帰納法を使用してボレル集合に関する事実を証明することである。小さい有限なランクの集合の性質は測度論や解析学で重要である。 任意の位相空間においてのボレル代数とは、全ての開集合を含んでいて可算和と補集合を取る操作について閉じている最小の集合族である。ボレル代数は可算交叉についても閉じている。 ボレル代数が正しく定義されていることの短い証明は、空間の冪集合全体が補集合と可算和のもとで閉じていること、したがって、ボレル代数は全ての開集合を含んでいてかつこれらで閉じた性質を持つような集合族全ての共通部分であることを示すことによって進行する。 この証明は、集合がボレルであるかどうかを決定する簡単な手続きを与えるものではない。ボレル階層を考える動機は、ボレル集合のより明確な特徴づけを与えることである。 空間Xにおけるボレル階層または太字のボレル階層は0以上の可算順序数 α {\displaystyle \alpha } についてのクラス Σ α 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}} , Π α 0 {\displaystyle \mathbf {\Pi } _{\alpha }^{0}} , Δ α 0 {\displaystyle \mathbf {\Delta } _{\alpha }^{0}} からなる。 これらのクラスはそれぞれXの部分集合からなり、以下のルールで帰納的に定義される： 集合が Σ 1 0 {\displaystyle \mathbf {\Sigma } _{1}^{0}} に属することはそれが開集合であることと同値である。 集合が Π α 0 {\displaystyle \mathbf {\Pi } _{\alpha }^{0}} に属することは、その補集合が Σ α 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}} に属することと同値である。 集合 A {\displaystyle A} が Σ α 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}} （ α > 1 {\displaystyle \alpha >1} ）に属することは、ある集合列 A 1 , A 2 , … {\displaystyle A_{1},A_{2},\ldots } について各 A i {\displaystyle A_{i}} が Π α i 0 {\displaystyle \mathbf {\Pi } _{\alpha _{i}}^{0}} （ α i < α {\displaystyle \alpha _{i}<\alpha } ）に属していて A = ⋃ A i {\displaystyle A=\bigcup A_{i}} となることと同値である。 集合が Δ α 0 {\displaystyle \mathbf {\Delta } _{\alpha }^{0}} に属することは、 Σ α 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}} と Π α 0 {\displaystyle \mathbf {\Pi } _{\alpha }^{0}} の両方に属することと同値である。 この階層を考える動機は、ボレル集合が補集合と可算和を用いて開集合から構成される方法に倣うためである。 ボレル集合が有限ランクを持つとは、それがある有限順序数 α {\displaystyle \alpha } に対する Σ α 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}} に属することである; そうでなければ無限ランクを持つという。 一般の位相空間で成り立つわけではないが、もし Σ 1 0 ⊆ Σ 2 0 {\displaystyle \mathbf {\Sigma } _{1}^{0}\subseteq \mathbf {\Sigma } _{2}^{0}} であれば、そのボレル階層では次の性質が成立することが示せる: 全ての α について、 Σ α 0 ∪ Π α 0 ⊆ Δ α + 1 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}\cup \mathbf {\Pi } _{\alpha }^{0}\subseteq \mathbf {\Delta } _{\alpha +1}^{0}} である。したがって、一度 Σ α 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}} か Π α 0 {\displaystyle \mathbf {\Pi } _{\alpha }^{0}} に属した集合は、その α より大きい順序数に対応する全ての階層にも属する。 ⋃ α < ω 1 Σ α 0 = ⋃ α < ω 1 Π α 0 = ⋃ α < ω 1 Δ α 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}} . そして、この和に集合が属することは、それがボレルであることと同値である。 X {\displaystyle X} が不可算なポーランド空間である場合、全ての α < ω 1 {\displaystyle \alpha <\omega _{1}} において Σ α 0 {\displaystyle \mathbf {\Sigma } _{\alpha }^{0}} は Π α 0 {\displaystyle \mathbf {\Pi } _{\alpha }^{0}} に部分集合として含まれてはいないことが示せる。したがって、この階層は潰れない。 古典的な記述集合論において、低ランクのボレル階層は別の名前でも知られている。 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「http://localhost:6011/ja.wikipedia.org/v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): \mathbf{\Sigma}^0_1 集合は開集合である. Π 1 0 {\displaystyle \mathbf {\Pi } _{1}^{0}} 集合は閉集合である。 Σ 2 0 {\displaystyle \mathbf {\Sigma } _{2}^{0}} 集合は閉集合の可算和であるが、これはFσ 集合と呼ばれている。 Π 2 0 {\displaystyle \mathbf {\Pi } _{2}^{0}} 集合はその双対クラスであり、開集合の可算交叉で書ける。これらの集合はGδ 集合と呼ばれている。 細字のボレル階層 (実効的ボレル階層とも呼ばれるpp.163--164) は太字のボレル階層の実効的バージョンである。これは実効的記述集合論や再帰理論において重要である。細字のボレル階層は実効ポーランド空間の部分集合の算術的階層を拡張したものであり、超算術的階層と密接な関係がある。 細字のボレル階層は任意の実効ポーランド空間上で定義できる。これは、チャーチ・クリーネ順序数 ω 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 は基本開集合列を列挙するプログラムのインデックスである。 集合が Π α 0 {\displaystyle \Pi _{\alpha }^{0}} であることは、その補集合が Σ α 0 {\displaystyle \Sigma _{\alpha }^{0}} であることと同値である。このような集合のコードはペア (1,c) であり、ここで c は補集合のコードである。 集合が Σ α 0 {\displaystyle \Sigma _{\alpha }^{0}} であることは、ある帰納的可算な列が存在して、それが列 A 1 , A 2 , … {\displaystyle A_{1},A_{2},\ldots } （ただし、各 A i {\displaystyle A_{i}} は Π α i 0 {\displaystyle \Pi _{\alpha _{i}}^{0}} 集合で、 α i < α {\displaystyle \alpha _{i}<\alpha } ）の各要素のコードからなる列であって、 A = ⋃ A i {\displaystyle A=\bigcup A_{i}} となっていること。 Σ α 0 {\displaystyle \Sigma _{\alpha }^{0}} 集合のコードはペア (2,e) であり、ここで e は列 A i {\displaystyle A_{i}} のコードを列挙するプログラムのインデックスである。 細字のボレル集合のコードは、より小さなランクの集合からその集合を復元する方法に関する完全な情報を与える。 これは、そのような実効性が要求されない太字の階層とは対照的である。各細字のボレル集合は、無限に多くの異なるコードを持つ。 他のコード体系を用いることも可能である。採用可能なコード体系の重要な点は、そのコードが実効的開集合、既出のコードで表現された集合の補集合、コード列の計算可能な枚挙を実効的に区別しなければならないということである。 各 α < ω 1 C K {\displaystyle \alpha <\omega _{1}^{\mathrm {CK} }} において、 Σ α 0 ∖ Π α 0 {\displaystyle \Sigma _{\alpha }^{0}\setminus \Pi _{\alpha }^{0}} に属する集合が存在し、この階層は潰れない。ただし、 ω 1 C K {\displaystyle \omega _{1}^{\mathrm {CK} }} まで到達すると新しい集合は付加されない。 スペクターとクリーネによる有名な定理で、集合が細字のボレル階層にあることと解析的階層の Δ 1 1 {\displaystyle \Delta _{1}^{1}} にあることとが同値であることが知られている。これらの集合は超算術的集合とも呼ばれる。加えて、自然数 n > 0 {\displaystyle n>0} について実効的ボレル階層の Σ n 0 {\displaystyle \Sigma _{n}^{0}} , 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「http://localhost:6011/ja.wikipedia.org/v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): \Pi _{n}^{0} と算術的階層の Σ n 0 {\displaystyle \Sigma _{n}^{0}} , Π n 0 {\displaystyle \Pi _{n}^{0}} は同じ名称であるが、実際等しいものである。p.168 細字のボレル集合Aのコードは、ノードがコードでラベル付けされた木を帰納的に定義するために使用できる。木の根はAのコードでラベル付けされる。あるノードが(1,c)という形のコードでラベル付けされている場合、そのノードはコードがcである子ノードを持つ。あるノードが (2,e) という形式のコードでラベル付けされている場合、そのノードはプログラムによってインデックス e で列挙された各コードに対して1つの子を持つ。ノードが(0,e)という形のコードでラベル付けされている場合、そのノードは子を持たない。このツリーは、Aがどのように小さなランクの集合から構築されるかを説明している。Aの構成に使われる順序数によって、この木が無限パスを持たないことが保証される。なぜなら、この木を通る無限パスは2から始まるコードを無限に含まなければならず、順序数の無限減少列を与えるからである。 逆に、 ω < ω {\displaystyle \omega ^{<\omega }\,} の任意の部分木が一貫した方法でノードがコードでラベル付けされ、木が無限パスを持たない場合、木の根のコードは細字ボレル集合のコードである。この集合のランクは、木のクリーネ・ブラウワー式順序における順序型で抑えられる。木は算術的に定義可能なので、このランクは ω 1 C K {\displaystyle \omega _{1}^{\mathrm {CK} }} より小さくなければならない。これは細字階層の定義におけるチャーチ・クリーネ順序数の起源である。 このボックス: 表示 ノート 編集 履歴