算術的階層
算術還元性は、チューリング還元性と超算術還元性の中間の概念である。
ある集合が算術的であるとは、それがペアノ算術の言語で書かれた式で定義されることを意味する。これと等価的に 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}} に属することを意味する。