5
解説大学数学以上
文献あり

Craigの絡繰とその相対化

99
5
$$$$

再帰的可算な理論と初等再帰的な理論が一致するというCraigの絡繰 (Craig's trick) とその算術的階層への一般化を紹介する。以下では言語に指数関数に対する関数記号が含まれていると仮定する。

算術的階層
  • $\Delta^0_0$ を有界論理式全体の集合とする。
  • $\Sigma^0_0:=\Pi^0_0:=\Delta^0_0$ とする。
  • $\Sigma^0_{n+1}$ を、ある $\varphi(x)\in\Pi^0_n$ に対して $\exists x\varphi(x)$ と表せる論理式の集合とする。
  • $\Pi^0_{n+1}$ を、ある $\varphi(x)\in\Sigma^0_n$ に対して $\forall x\varphi(x)$ と表せる論理式の集合とする。
定義可能性

集合$X\subseteq\mathbb{N}^\nu$$\Gamma$-定義可能 ($\Gamma$-definable) であるとは、ある$\varphi\in\Gamma$ が存在し$X=\{\vec{x}\in\mathbb{N}^\nu\mid\mathbb{N}\models\varphi(\vec{x})\}$となることである。
関数$f$$\Gamma$-定義可能であるのはそのグラフが$\Gamma$-定義可能であることとし、理論$T$$\Gamma$-定義可能であるのは$T$に含まれる論理式のコード全体$\{\ulcorner\varphi\urcorner\mid\varphi\in T\}$$\Gamma$-定義可能であることとする。

一般化されたCraigの絡繰

任意の$\Sigma^0_{n+1}$-定義可能な理論$T$に対し、ある$\Pi^0_n$-定義可能な理論$S$が存在し、任意の論理式$\varphi$に対し$$T\vdash\varphi\Longleftrightarrow S\vdash\varphi$$となる。

まず再帰理論の基本的結果、空でない集合$X$$\Sigma^0_{n+1}$-定義可能であることと$X$はある$\Pi^0_n$-定義可能関数の値域となることが同値になることに気をつける。今、理論$T$が空だとするど自明に成立つので空でないとし、$\Pi^0_n$-定義可能な関数$f$$\mathrm{rng}(f)=\{\ulcorner\varphi\urcorner\mid\varphi\in T\}$となるようなものを取る。また論理式$\varphi$に対して$\varphi^n$$\varphi^0:=\top,\varphi^{n+1}:=\varphi^n\land\varphi$と定めて、理論$S$$S:=\{\varphi^{n+1}\mid f(n)=\ulcorner\varphi\urcorner\}$とする。$S$の定義から$$T\vdash\varphi\Longleftrightarrow S\vdash\varphi$$となることは明らか。また$n$$\ulcorner\varphi\urcorner$から$\ulcorner\varphi^n\urcorner$を返す関数、すなわち$g(n,\ulcorner\varphi\urcorner)=\ulcorner\varphi^n\urcorner$を満たす関数$g$は初等再帰的であることから$x\in\{\ulcorner\varphi\urcorner\mid\varphi\in S\}$$(\exists y< x)[x=g(y+1,f(y))]$と同値であり、$\Pi^0_n$-定義可能である。

Craigの絡繰

任意の再帰的可算な理論$T$に対し、ある初等再帰的な理論$S$が存在し、任意の論理式$\varphi$に対し$$T\vdash\varphi\Longleftrightarrow S\vdash\varphi$$となる。

再帰的可算であることと$\Sigma^0_1$-定義可能であることの同値性と初等再帰的であることと$\Pi^0_0$-定義可能であることの同値性による。後者の同値性は関数記号として指数関数を含んでいることによる。

参考文献

[1]
W. Craig, On axiomatizability within a system, The Journal of Symbolic Logic, 1953, 30–32
投稿日:20201112
更新日:2021125

投稿者

@ptykes

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

コメント