完全集合
Perfect set
算術的階層の各領域の中で最も計算不可能性の度合いが高い集合 ポストの問題により、各領域は1つではなく複数の同値類に分けられることが示されたが、 その中でも「最も計算不可能性の高い」ものが各領域に存在する、という主張
序列があるということかmrsekut.icon
定義
$ \Sigma_n完全集合
自然数の集合$ \varphiが、以下の2条件を満たすとき、$ \varphiが$ \Sigma_n完全集合である
任意の$ \Sigma_n集合$ \alphaに対して、$ \alpha\le_m\varphiが成り立つ
$ \Pi_n完全集合
自然数の集合$ \varphiが、以下の2条件を満たすとき、$ \varphiが$ \Pi_n完全集合である
任意の$ \Pi_n集合$ \alphaに対して、$ \alpha\le_m\varphiが成り立つ
補足
定理
各$ \Sigma_n,\Pi_n集合に関して、それぞれ完全集合が存在する $ n=1,2,3,\cdots
しかも無限個存在する
証明
1変数用の$ \Sigma_n万能述語$ E^{\Sigma_n}_1を用いて、自然数の集合$ \varphiを以下のように定義する ①$ x\in\varphi\iff E^{\Sigma_n}_1(\mathrm{left}(x),\mathrm{right}(x))
この$ \varphiが$ \Sigma_n完全集合になっている
なぜなら、任意の$ \Sigma_n集合$ \alphaに対して以下が成り立つから
$ x\in\alpha\iff E^{\Sigma_n}_1(p,x)
∵万能述語の性質により$ xに対して、$ pが存在する $ \iff E^{\Sigma_n}_1\left(\mathrm{left}(\mathrm{pair}(p,x), \mathrm{right}(\mathrm{pair}(p,x)))\right)
∵ left, right, pairの定義より
$ \iff \mathrm{pair}(p,x)\in\varphi
∵ 上の①の$ xを$ \mathrm{pair}(p,x)に置き換える
この最初と最後を見比べると$ x\in\alpha\iff\mathrm{pair}(p,x)\in\varphi
これは多対一還元の定義であるmrsekut.icon $ f(x)=\mathrm{pair}(p,x)を帰着関数としている $ \Pi_nも同様