算術還元性と次数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 04:36 UTC 版)
算術還元性は、チューリング還元性と超算術還元性の中間の概念である。 ある集合が算術的であるとは、それがペアノ算術の言語で書かれた式で定義されることを意味する。これと等価的に X が算術的であるとは、X が何らかの整数 n の Σ n 0 {\displaystyle \Sigma _{n}^{0}} または Π n 0 {\displaystyle \Pi _{n}^{0}} に属することを意味する。集合 X が集合 Y において算術的であるということを X ≤ A Y {\displaystyle X\leq _{A}Y} で表し、Y についてのメンバーシップ述語で拡張されたペアノ算術の言語で書かれた式で X を定義可能であることを意味する。これと等価的に X が Y において算術的であるとは、ある整数 n に対し X が Σ n 0 , Y {\displaystyle \Sigma _{n}^{0,Y}} または Π n 0 , Y {\displaystyle \Pi _{n}^{0,Y}} に属することを意味する。 X ≤ A Y {\displaystyle X\leq _{A}Y} は、X が Y に算術還元可能であることを意味する。 X ≤ A Y {\displaystyle X\leq _{A}Y} は反射関係かつ推移関係であり、したがって ≡ A {\displaystyle \equiv _{A}} という関係を次のように定義すると、これは同値関係となる。 X ≡ A Y ⇔ X ≤ A Y ∧ Y ≤ A X {\displaystyle X\equiv _{A}Y\Leftrightarrow X\leq _{A}Y\land Y\leq _{A}X} この関係における同値類を算術次数（arithmetic degrees）と呼ぶ。これらは ≤ A {\displaystyle \leq _{A}} のもとで半順序的である。
※この「算術還元性と次数」の解説は、「算術的階層」の解説の一部です。
「算術還元性と次数」を含む「算術的階層」の記事については、「算術的階層」の概要を参照ください。
- 算術還元性と次数のページへのリンク
