ボレル階層
他のコード体系を用いることも可能である。採用可能なコード体系の重要な点は、そのコードが実効的開集合、既出のコードで表現された集合の補集合、コード列の計算可能な枚挙を実効的に区別しなければならないということである。
各 α < ω 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}} , Π n 0 {\displaystyle \Pi _{n}^{0}} と算術的階層の Σ n 0 {\displaystyle \Sigma _{n}^{0}} , Π n 0 {\displaystyle \Pi _{n}^{0}} は同じ名称であるが、実際等しいものである。
細字のボレル集合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} }} より小さくなければならない。これは細字階層の定義におけるチャーチ・クリーネ順序数の起源である。