算術的階層（さんじゅつてきかいそう、）は、数理論理学において、集合を定義する式の複雑さに基づいて、その集合を分類した階層である。クリーネ階層（Kleene hierarchy）とも。このような分類が可能な集合は算術的である。算術的階層は、再帰理論やペアノ算術のような形式理論の研究で重要である。算術的階層での式や集合の分類の拡張として、超算術的階層や解析的階層がある。算術的階層では、ペアノ算術の言語で書かれた式を分類する。階層は自然数 "n" を使って、formula_1 および formula_2 と記される。ここでのギリシア文字は細活字(lightface)であり、式に集合パラメータが含まれないことを示している。式 formula_3 が有界量化子しか含まない式と論理的に等価であれば、formula_3 は階層 formula_5 と formula_6 に相当する。階層 formula_1 と formula_2 は、全ての自然数 "n" について以下のように帰納的に定義される。あらゆる式は等価な冠頭標準形に変換できるため、集合量化子のないあらゆる式は少なくとも1つの階層に分類される。意味のない量化子を式に追加することが可能なため、formula_1 または formula_2 に分類された式は、"n" より大きいあらゆる "m" について formula_21 と formula_22 にも分類可能である。従って、最も重要な分類は最小の "n" に対応する階層であり、他の分類はそこから決定可能である。ペアノ算術の言語で書かれた式 φ(n) で、集合 "X" が formula_23 のように定義されるとする。これはつまり、"X" の元が φ を満足する数ということを意味している。集合が一階算術で定義可能であるとは、ペアノ算術の言語で書かれた式で定義されることに他ならない。一階算術で定義可能な自然数の集合 "X" は、formula_24 を自然数としたときの階層 formula_1、formula_2、formula_27 に以下のように分類される。"X" が formula_1 に属する式で定義可能なら、formula_29 は階層 formula_1 に分類される。"X" が formula_2 に属する式で定義可能なら、formula_29 は階層 formula_2 に分類される。formula_29 が formula_1 にも formula_2 にも属するなら、formula_29 は追加の階層 formula_27 に分類される。なお、formula_27 に属する式と言った場合、ほとんど意味をなさない。これはつまり、先頭の量化子が存在量化子か全称量化子の式を意味する。従って formula_27 に属する集合は formula_27 に属する式で定義されるのではなく、formula_1 に属する式と formula_2 に属する式の両方で定義される集合である。自然数の有限な直積集合の算術的階層の定義には並列定義が使われる。1つの自由変項の式の代わりに "k" 個の自由変項の式を使い、"k"-タプルの自然数の集合についての算術的階層を定義する。集合 "X" が 集合 "Y" に対して再帰的相対性を持つということを、"Y" を一種の神託機械として "X" を求められることと定義すると、これを算術的階層全体に拡張し、"Y" に対して "X" が formula_1、formula_27、formula_2 であるということをそれぞれ formula_47、formula_48、formula_49 と記述する。このために、整数の集合"Y" を固定し、ペアノ算術の言語に "Y" のメンバーシップ述語を追加する。"X" が formula_47 に属するとは、この拡張された言語で書かれた formula_1 の式で定義されることを意味する。言い換えれば、"X" が formula_47 に属するとは、その中で"Y" に属するかどうかの質問が許されている formula_53 に属する論理式で定義されることを意味する。例えば、"Y" を整数の集合とする。"X" は、ある "Y" の元で割り切れる数の集合とする。すると "X" は式 formula_54 で定義されるので、"X" は formula_55 に属することになる（実際には、2つの量化子を "n" で制限できるので formula_56 に属する）。算術還元性は、チューリング還元性と超算術還元性の中間の概念である。ある集合が算術的であるとは、それがペアノ算術の言語で書かれた式で定義されることを意味する。これと等価的に "X" が算術的であるとは、"X" が何らかの整数 "n" の formula_1 または formula_2 に属することを意味する。集合 "X" が集合 "Y" において算術的であるということを formula_59 で表し、"Y" についてのメンバーシップ述語で拡張されたペアノ算術の言語で書かれた式で "X" を定義可能であることを意味する。これと等価的に "X" が "Y" において算術的であるとは、ある整数 "n" に対し "X" が formula_47 または formula_49 に属することを意味する。formula_59 は、"X" が "Y" に算術還元可能であることを意味する。formula_59 は反射関係かつ推移関係であり、したがって formula_64 という関係を次のように定義すると、これは同値関係となる。この関係における同値類を算術次数（arithmetic degrees）と呼ぶ。これらは formula_66 のもとで半順序的である。

出典:wikipedia