実効記述集合論

実効記述集合論（じっこうきじゅつしゅうごうろん、Effective descriptive set theory）は記述集合論で細字の定義をもつ集合や実数を扱う分野である; それはすなわち、定義にいかなる実数パラメータも要さないものである (Moschovakis 1980)。つまり実効記述集合論は、記述集合論と再帰理論を組み合わせたものである。

構成

実効ポーランド空間

→詳細は「実効ポーランド空間」を参照

実効ポーランド空間とは計算可能な表現(en:computable presentation)を持つ完備可分距離空間のことである。このような空間は、実効記述集合論と構成的解析学の両方で研究されている。 特に、実数直線、カントール集合、ベール空間などのポーランド空間の標準的な例は全て実効ポーランド空間である。

算術的階層

→詳細は「算術的階層」を参照

算術的階層、またはクリーネ-モストフスキ階層は、ある集合を、それらを定義する式の複雑さに基づいて分類する。そのような分類を受けた集合は「算術的」と呼ばれる。

より正式には、算術的階層は一階算術の言語における論理式に分類を割り当てる。分類は自然数n（0を含む）に対して${\displaystyle \Sigma _{n}^{0}}$と${\displaystyle \Pi _{n}^{0}}$と表される。ここでのギリシャ文字は細字記号であり、論理式に集合パラメータが含まれていないことを意味する。

論理式 ${\displaystyle \phi }$ が有界量化子のみを持つ論理式に論理的に同値であるとき ${\displaystyle \phi }$ は分類 ${\displaystyle \Sigma _{0}^{0}}$ と ${\displaystyle \Pi _{0}^{0}}$ を両方割り当てる。

0より大きい各自然数 n に対する ${\displaystyle \Sigma _{n}^{0}}$, ${\displaystyle \Pi _{n}^{0}}$ は次のように帰納的に定義される:

• ${\displaystyle \phi }$ が ${\displaystyle \exists n_{1}\exists n_{2}\cdots \exists n_{k}\psi }$（ただし、${\displaystyle \psi }$ は ${\displaystyle \Pi _{n}^{0}}$ 式）の形の式と論理的に同値であるとき、${\displaystyle \phi }$ には分類 ${\displaystyle \Sigma _{n+1}^{0}}$ を割り当てる。
• ${\displaystyle \phi }$ が ${\displaystyle \forall n_{1}\forall n_{2}\cdots \forall n_{k}\psi }$（ただし、${\displaystyle \psi }$ は ${\displaystyle \Sigma _{n}^{0}}$ 式）の形の式と論理的に同値であるとき、${\displaystyle \phi }$ には分類 ${\displaystyle \Pi _{n+1}^{0}}$ を割り当てる。

参考文献

• Mansfield, Richard; Weitkamp, Galen (1985). Recursive Aspects of Descriptive Set Theory. Oxford University Press. pp. 124–38. ISBN 978-0-19-503602-2. MR786122. https://archive.org/details/recursiveaspects0000mans/page/124 
• Moschovakis, Yiannis N. (1980). Descriptive Set Theory. North Holland. ISBN 0-444-70199-0. https://archive.org/details/descriptivesetth0000mosc  Second edition available online