解析的階層

同義語:analytical hierarchy

概要

解析的階層(analytical hierarchy)とは、自然数と自然数列の組の関係を、算術的な関係に自然数列を動く量化を交互に付けた回数で分類する階層 $\Sigma^1_n$、$\Pi^1_n$、$\Delta^1_n$ である。$\Sigma^1_1$ は $\exists\beta\,\forall t\,D$($D$ は決定可能)の形をもち、各段は真に増大する。決定可能な木の整礎性は $\Pi^1_1$ 完全であり、$\Delta^1_1$ の自然数の集合は超算術的集合に一致する(Kleene)。パラメータを許したものの和は射影階層に一致する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 算術的階層, 計算可能性理論, 射影階層

解析的階層(analytical hierarchy)は、自然数の集合や関係を、算術的な関係に自然数から自然数への関数を動く量化 $\exists\alpha$、$\forall\alpha$ を交互に何回付けると定義できるかで分類する階層 $\Sigma^1_n$、$\Pi^1_n$、$\Delta^1_n$ である。Kleene が導入した(Mos09 Introduction、p. 5)。算術的階層 の自然数の量化を関数の量化に上げたもので、射影階層 の有効版にあたる。
「解析的」(analytical)は 解析集合(記述集合論)(analytic set)とは別の語である。後者は太字の $\boldsymbol\Sigma^1_1$ を指し、混同を避けるため Mos09 p. 118 は文脈によって $\Sigma^1_1$ と書くことを勧めている。
この記事では、正規形、階層定理、$\Pi^1_1$ の完全な集合が木の整礎性であること、Kleene の基底定理、射影階層との対応を証明し、超算術的集合についての Kleene の定理を述べる。

主張内容この記事で
thm-anh-normal$\Sigma^1_1$ の正規形と閉包性証明する
thm-anh-hierarchy階層定理証明する
thm-anh-wf木の整礎性は $\Pi^1_1$ 完全証明する
prop-anh-truth算術の真理は $\Delta^1_1$ で算術的でない証明する
thm-anh-kleene超算術的 $\iff\Delta^1_1$引用する
thm-anh-basisKleene の基底定理証明する
prop-anh-bold太字の階層との対応証明する

定義

$\mathcal{N}:=\mathbb{N}^{\mathbb{N}}$ とし、積位相を入れる。記号 $T(e,x,s)$、$W_e$、$\varphi_e$ と対の符号 $\langle\cdot,\cdot\rangle$ は 算術的階層 の記事に従う。$\alpha\in\mathcal{N}$ の長さ $t$ の始切片の符号を $\bar\alpha(t):=\langle\alpha(0),\dots,\alpha(t-1)\rangle$(有限列の計算可能な符号)と書く。$\mathbb{N}^k\times\mathcal{N}^l$ の部分集合を 関係 とよぶ。
関係 $R$ が $\Sigma^0_1$ であるとは、決定可能な関係 $D\subset\mathbb{N}^{k+l}$ で
$$ R(\vec x,\vec\alpha)\iff\exists t\ D(\vec x,\bar\alpha_1(t),\dots,\bar\alpha_l(t)) $$
となるものがあることをいう。$\Pi^0_1$ はその補集合で、以下自然数の量化を重ねて $\Sigma^0_n$、$\Pi^0_n$、算術的 な関係を定める。$l=0$ なら 算術的階層 の記事の定義と一致する。

解析的階層

関係のクラスを次で定める。

  1. $R\in\Sigma^1_1$ とは、$\Pi^0_1$ の関係 $S$ で $R(\vec x,\vec\alpha)\iff\exists\beta\ S(\vec x,\vec\alpha,\beta)$($\beta$ は $\mathcal{N}$ を動く)となるものがあることをいう。
  2. $\Pi^1_n$ は $\Sigma^1_n$ の関係の補集合の全体である。
  3. $R\in\Sigma^1_{n+1}$ とは、$\Pi^1_n$ の関係 $S$ で $R(\vec x,\vec\alpha)\iff\exists\beta\ S(\vec x,\vec\alpha,\beta)$ となるものがあることをいう。
  4. $\Delta^1_n:=\Sigma^1_n\cap\Pi^1_n$ とする。
    どれかの $\Sigma^1_n$ に属する関係を 解析的 という。

これは Mos09 3E 節(p. 118)の定義を $\mathbb{N}^k\times\mathcal{N}^l$ に制限したものである。パラメータ $a\in\mathcal{N}$ を固定して代入したクラスを $\Sigma^1_n(a)$ と書く。

関数の量化が要る例

$\alpha\in\mathcal{N}$ で $\mathbb{N}$ 上の 2 項関係 $\{(i,j):\alpha(\langle i,j\rangle)=0\}$ を表す。「$\alpha$ が整列順序を表す」とは、全順序であること(算術的)と、無限降下列がないこと
$$ \forall\beta\ \exists n\ \lnot\bigl(\alpha(\langle\beta(n+1),\beta(n)\rangle)=0\ \land\ \beta(n+1)\ne\beta(n)\bigr) $$
を合わせたものである。よって 整列順序 を表す $\alpha$ の全体は $\Pi^1_1$ である。

正規形

$\Sigma^1_1$ の正規形と閉包性
  1. 関係 $R$ が $\Sigma^1_1$ であることと、決定可能な $D$ で
    $$ R(\vec x,\vec\alpha)\iff\exists\beta\ \forall t\ D(\vec x,\bar\alpha_1(t),\dots,\bar\alpha_l(t),\bar\beta(t)) $$
    となるものがあることは同値である。
  2. $\Sigma^1_1$ は $\land$、$\lor$、$\exists n$、$\forall n$、$\exists\gamma$ で閉じている。
  3. 算術的な関係はすべて $\Delta^1_1$ である。
  4. $n\ge1$ で、$\Sigma^1_n$、$\Pi^1_n$ は $\land$、$\lor$、$\exists n$、$\forall n$ で閉じている。
Skolem 関数で量化を入れ替える

1 の形の関係の族を $\Gamma$ とする。1 は定義そのものである。実際 $\Pi^0_1$ の $S$ は $\forall t\ D$ の形である(Mos09 4A.1、pp. 145–146)。
2 を $\Gamma$ について示す。列の対 $\langle\beta,\gamma\rangle$(偶数番目が $\beta$、奇数番目が $\gamma$)を 1 つの列と見ると、$\exists\beta\exists\gamma$ は 1 つの $\exists$ にまとまり、$\land$ もまとまる。$\exists n$ は $\beta(0)$ を $n$ とすればよい。$\lor$ は $\exists n$ で書ける。$\forall n$ が核心である。$\beta$ から $(\beta)_n(m):=\beta(\langle n,m\rangle)$ で列 $(\beta)_n$ を取り出すと、選択公理により
$$ \forall n\ \exists\beta\ \forall t\ D(n,\bar\beta(t))\iff\exists\beta\ \forall n\ \forall t\ D(n,\overline{(\beta)_n}(t)) $$
である。$\overline{(\beta)_n}(t)$ は十分長い $\bar\beta$ から計算できるので、右辺は $\Gamma$ の形である。
3:$\Pi^0_1\subset\Gamma$ は明らかで、$\Gamma$ は $\exists n$、$\forall n$ で閉じるので、帰納法で算術的な関係はすべて $\Gamma$ に入る。算術的な関係は補集合で閉じるので $\Pi^1_1$ にも入る。
4:$n=1$ は 2 と補集合である。$\Sigma^1_{n+1}$ は $\exists\beta\ S$($S\in\Pi^1_n$)の形で、$\forall m\exists\beta\ S(m,\beta)\iff\exists\beta\forall m\ S(m,(\beta)_m)$ と $\Pi^1_n$ の閉包性から従い、$\land$、$\lor$、$\exists m$ は 2 と同じく $\exists\beta$ を 1 つにまとめて $\Pi^1_n$ の閉包性に帰着する。$\Pi^1_{n+1}$ は補集合である。$\square$

二階算術との関係. 自然数の変数と関数の変数をもち、$+$、$\cdot$、$<$ と関数の適用で書いた論理式で、$(\mathbb{N},\mathcal{N})$ の上で定義できる関係を考える。

解析的な関係と定義可能性

$\mathbb{N}^k\times\mathcal{N}^l$ の関係が解析的であることと、上の意味で定義できることは同値である。

解析的なら、$D$ を 算術的階層 の記事の定理「算術的な関係と定義可能な関係」と同様に論理式で書き、量化を付ければよい。逆に定義可能な関係は、論理式の構成についての帰納法で解析的である。原子式は $\alpha(t)=m$ の形に展開すれば算術的で、量化の段は thm-anh-normal の 4 で処理する。$\square$

集合 $X\subset\mathbb{N}$ を特性関数と同一視すると、関数の量化を集合の量化に替えても同じクラスが得られる(関数はグラフで集合になる)。

階層定理

$V(e,x,\alpha):\iff\exists t\ \exists s\ T(e,\langle x,\bar\alpha(t)\rangle,s)$ とする。$V$ は $\Sigma^0_1$ である。また $\mathbb{N}\times\mathcal{N}$ の $\Sigma^0_1$ の関係 $\exists t\ D(x,\bar\alpha(t))$ は、$D$ を $W_e$ と書けば $V(e,\cdot,\cdot)$ である。
$U_1(e,x,\alpha):\iff\exists\beta\ \lnot V(e,x,\langle\alpha,\beta\rangle)$、$U_{n+1}(e,x,\alpha):\iff\exists\beta\ \lnot U_n(e,x,\langle\alpha,\beta\rangle)$ と定める。

万能な関係

$U_n$ は $\Sigma^1_n$ で、$\mathbb{N}\times\mathcal{N}$ の $\Sigma^1_n$ の関係はすべて、ある $e$ について $U_n(e,\cdot,\cdot)$ である。

$R(x,\alpha)\iff\exists\beta\ S(x,\alpha,\beta)$、$S\in\Pi^1_{n-1}$($n=1$ では $\Pi^0_1$)とする。$\alpha$ と $\beta$ は $\langle\alpha,\beta\rangle$ の始切片から計算できるので、$S(x,\alpha,\beta)\iff S'(x,\langle\alpha,\beta\rangle)$ となる $S'\in\Pi^1_{n-1}$ がある。$\lnot S'$ に帰納法の仮定($n=1$ では上の $V$)を使えばよい。$\square$

階層定理

$n\ge1$ とし、$D_n:=\{x\in\mathbb{N}:U_n(x,x,\mathbf{0})\}$($\mathbf{0}$ は恒等的に $0$ の列)とする。$D_n$ は $\Sigma^1_n$ で $\Pi^1_n$ でない。とくに $\mathbb{N}$ の部分集合のクラスとして、$\Delta^1_n\subsetneq\Sigma^1_n\subsetneq\Delta^1_{n+1}$ である。

対角線論法

$D_n$ は $U_n$ に計算可能な代入をしたものなので $\Sigma^1_n$ である。$\Pi^1_n$ なら、$\mathbb{N}\setminus D_n$ は $\Sigma^1_n$ なので、lem-anh-universal によりある $e$ で $x\notin D_n\iff U_n(e,x,\mathbf{0})$ である。$x=e$ で $e\notin D_n\iff e\in D_n$ となり矛盾する。
包含 $\Sigma^1_n\subset\Delta^1_{n+1}$ は、ダミーの量化と $\Sigma^1_1\subset\Sigma^1_2$(thm-anh-normal の 3 による)から帰納法で従う。$\mathbb{N}\setminus D_n$ は $\Pi^1_n\subset\Delta^1_{n+1}$ に入り $\Sigma^1_n$ に入らないので、この包含は真である。$\square$

Mos09 3F.7(p. 130)は同じ定理を一般の積空間で述べる。

木の整礎性

有限列の符号の集合 $S$ で始切片について閉じたものを 木 といい、無限の枝($\bar\alpha(t)\in S$ がすべての $t$ で成り立つ $\alpha$)がないとき 整礎 という(整礎関係)。
$$ \mathrm{WF}:=\{e:\varphi_e\text{ は全域で }\{s:\varphi_e(s)=1\}\text{ は整礎な木}\} $$
とする。

$\mathrm{WF}$ は $\Pi^1_1$ 完全

$\mathrm{WF}$ は $\Pi^1_1$ である。すべての $\Pi^1_1$ の集合 $A\subset\mathbb{N}$ は 多対一還元 で $\mathrm{WF}$ に還元される。とくに $\mathrm{WF}$ は $\Sigma^1_1$ でない。

正規形を木に読み替える

定義の前半は算術的で、後半は $\forall\beta\ \exists t\ \bar\beta(t)\notin S$ の形なので $\Pi^1_1$ である。
$A$ を $\Pi^1_1$ とする。thm-anh-normal の 1 で $x\notin A\iff\exists\beta\ \forall t\ D(x,\bar\beta(t))$ と書く。$D$ を「すべての始切片で $D$」に置き換えると、$T_x:=\{s:D(x,s)\}$ は始切片で閉じている。$x\in A$ と $T_x$ が整礎であることは同値である。$T_x$ の特性関数の番号 $e(x)$ は s-m-n の定理で計算可能に求まる。よって $x\mapsto e(x)$ が還元である。
$\mathrm{WF}$ が $\Sigma^1_1$ なら、すべての $\Pi^1_1$ の集合が $\Sigma^1_1$ になり、$D_1$ の補集合に thm-anh-hierarchy を当てて矛盾する。$\square$

これは Mos09 4A.3(p. 147)の Lusin–Sierpiński–Kleene の表現定理の木の形である。同所は、計算可能な $f$ で $x\in A\iff f(x)$ が整列順序を表す、という形に書く。$\omega_1^{\mathrm{CK}}$ を計算可能な整列順序の順序型の上限(Church–Kleene の順序数)とする。Mos09 4A.4(p. 149)の有界性定理は、$A$ が $\Delta^1_1$ であることと、$A$ の元での $f(x)$ の順序型の上限が $\omega_1^{\mathrm{CK}}$ より小さいことが同値であることを述べる。

超算術的集合

算術の真理は $\Delta^1_1$

$\mathfrak{N}$ で真な文の Gödel 数の集合 $\mathrm{Tr}$ は $\Delta^1_1$ であり、算術的でない。とくに、算術的な集合の全体は $\Delta^1_1$ の真の部分クラスである。

充足関係の量化

$\alpha\in\mathcal{N}$ で、論理式と変数への割り当ての組の全体の上の $\{0,1\}$ 値関数を表す。「$\alpha$ が Tarski の条件(原子式で正しく、$\lnot,\land$ で整合し、$\alpha(\exists x\varphi,a)=1\iff\exists n\ \alpha(\varphi,a[x:=n])=1$)を満たす」は算術的である。これを $\mathrm{Sat}(\alpha)$ と書く。$\mathrm{Sat}$ を満たす $\alpha$ はちょうど 1 つある。よって、
$$ s\in\mathrm{Tr}\iff\exists\alpha\ (\mathrm{Sat}(\alpha)\land\alpha(s,\emptyset)=1)\iff\forall\alpha\ (\mathrm{Sat}(\alpha)\to\alpha(s,\emptyset)=1) $$
である。thm-anh-normal により中辺は $\Sigma^1_1$、右辺は $\Pi^1_1$ である。算術的でないことは 算術的階層 の記事の系「真理の集合は算術的でない」である。$\square$

$\Delta^1_1$ の集合を内側から作る記述が超算術的集合である。

超算術的集合

集合 $A\subset\mathbb{N}$ が 超算術的 であるとは、$A$ が計算可能な集合から補集合と「計算可能に番号付けられた」可算和を超限回くり返して作られること、すなわち計算可能な Borel 符号をもつことをいう(Mos09 Introduction、p. 5、7B 節の定義、p. 307)。

Kleene の定理

$A\subset\mathbb{N}$ が超算術的であることと、$\Delta^1_1$ であることは同値である。

文献

Kleene(1955 年)の定理で、Mos09 Introduction p. 5 と 7B.6(p. 307)にある。この記事では証明しない。記述集合論 の Suslin の定理($\boldsymbol\Delta^1_1$ は Borel)の有効版にあたる。

算術的な集合は超算術的である。$\mathrm{Tr}$ は算術的でないので、超算術的な集合は算術的な集合より真に多い。

Kleene の基底定理

クラス $\mathcal{B}\subset\mathcal{N}$ が $\Gamma$ の 基底 であるとは、$\Gamma$ に属する空でない $\mathcal{N}$ の部分集合がどれも $\mathcal{B}$ の元を含むことをいう。

Kleene の基底定理

$\{\alpha\in\mathcal{N}:\alpha\text{ は }\mathrm{WF}\text{ に Turing 還元可能}\}$ は $\Sigma^1_1$ の基底である。

最左枝

$Q\subset\mathcal{N}$ を空でない $\Sigma^1_1$ とする。thm-anh-normal の 1 で $Q(\alpha)\iff\exists\beta\ \forall t\ D(\bar\alpha(t),\bar\beta(t))$ と書き、$D$ を始切片について閉じさせる。$\mathbb{N}\times\mathbb{N}$ の列を $\mathbb{N}$ の列と同一視すると、組 $(\bar\alpha(t),\bar\beta(t))$ で $D$ を満たすものの全体は決定可能な木 $S$ であり、$Q\ne\emptyset$ より無限の枝をもつ。
$w\in S$ について、$S_w$ を $w$ と比較可能な節の全体とする。$S_w$ の特性関数の番号は s-m-n の定理で $w$ から計算できる。よって「$S_w$ が無限の枝をもつ」かどうかは $\mathrm{WF}$ を神託として決定できる。
根(空列)を $w_0$ とし、$w_i$ の子 $c$ で $S_c$ が無限の枝をもつもののうち番号の最小のものを $w_{i+1}$ とする。$S_{w_i}$ が無限の枝をもつので、このような子は存在する。$(w_i)_i$ は $\mathrm{WF}$ に Turing 還元可能で、$S$ の枝である(最左枝)。その第 1 成分 $\alpha$ は $Q$ に属し、$\mathrm{WF}$ に Turing 還元可能である。$\square$

これは Mos09 4E.8(p. 180)である。同所の図 4E.2 が同じ最左枝を描いている。$\mathrm{WF}$ は算術的でなく $\Delta^1_1$ にも入らないので、この基底は $\Delta^1_1$ より真に上にある。そして基底を $\Delta^1_1$ に下げることはできない(下の反例の表)。

射影階層との対応

射影階層 の太字の $\boldsymbol\Sigma^1_1$ は閉集合の射影であり、$\boldsymbol\Pi^1_n$ はその補集合、$\boldsymbol\Sigma^1_{n+1}$ は $\boldsymbol\Pi^1_n$ の射影である。

太字の階層は細字の和

$\mathcal{N}^l$($l\ge1$)の部分集合のクラスとして、$\boldsymbol\Sigma^1_n=\bigcup_{a\in\mathcal{N}}\Sigma^1_n(a)$ である。$\boldsymbol\Pi^1_n$ についても同じである。

パラメータで開集合を符号化する

$n=1$ を示す。$\Sigma^0_1(a)$ の集合は基本開集合 $\{\vec\alpha:\bar\alpha_i(t)=s_i\}$ の和なので開集合である。逆に開集合 $O$ は、基本開集合の符号の集合の特性関数 $a$ を使って $\vec\alpha\in O\iff\exists t\ a(\langle\bar\alpha_1(t),\dots,\bar\alpha_l(t)\rangle)=1$ と書ける。よって閉集合は $\Pi^0_1(a)$ の集合と一致する。射影をとると $n=1$ を得る。
補集合と射影は左右で対応するので、帰納法で一般の $n$ を得る。複数のパラメータは $\langle a,b\rangle$ で 1 つにまとめる。$\square$

Mos09 3E.4(p. 120)は、同じ主張を一般の積空間で述べる。
さらに進んだ結果. 階層の中の構造は段によって異なる。$\Pi^1_1$ と $\Sigma^1_2$ は一様化の性質をもつ(Novikov–近藤基吉–Addison の一様化定理。Mos09 4E.4、p. 178)。その帰結として $\Delta^1_2$ は $\Sigma^1_2$ の基底である(同 4E.5、p. 179)。$\Sigma^1_3$ より上の段の構造は ZFC だけからは定まらず、追加の公理に依存する(Mos09 第 5 章・第 6 章)。

反例:条件を外すと成り立たないこと

外す条件例成り立たなくなること確かめ
量化域が $\mathcal{N}$$\mathcal{N}$ を Cantor空間 $2^{\mathbb{N}}$ に替えるthm-anh-hierarchy:$\exists\alpha$ で算術的の外に出ること弱Kőnigの補題 により $\exists\alpha\in2^{\mathbb{N}}\forall t\ D(x,\bar\alpha(t))\iff\forall m\ \exists s\in2^m\ \forall k\le m\ D(x,\bar s(k))$ で、右辺は $\Pi^0_1$
関数の量化自然数の量化だけの算術的な関係に限る$\Delta^1_1$ の全体を尽くすこと$\mathrm{Tr}$ は $\Delta^1_1$ で算術的でない(prop-anh-truth)
基底の列が $\mathrm{WF}$ まで使えること基底を $\Delta^1_1$ の列に下げるthm-anh-basis空でない $\Pi^0_1$ の部分集合 $A\subset\mathcal{N}$ で $\Delta^1_1$ の元を含まないものがある(Mos09 4D.10、p. 170)
パラメータ$\{a\}\subset\mathcal{N}$($a$ は解析的でない自然数の集合の特性関数)prop-anh-bold:$\boldsymbol\Sigma^1_1$ が細字のクラスに入ること解析的な集合は可算個なので $a$ がある。$\{a\}$ は閉集合だが、$\{a\}$ が解析的なら $n\in a\iff\exists\alpha(\alpha\in\{a\}\land\alpha(n)=1)$ で $a$ が解析的になる

関連項目

参考文献

[1]
Yiannis N. Moschovakis, Descriptive Set Theory, 2nd ed., American Mathematical Society, 2009, Introduction p. 5、3E p. 118、3E.4 p. 120、3F.7 p. 130、4A.1 pp. 145–146、4A.3 p. 147、4A.4 p. 149、4D.10 p. 170、4E.4 p. 178、4E.5 p. 179、4E.8 p. 180、7B.6 p. 307

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する