ポストの定理
自然数の集合 A が Σ m 0 {\displaystyle \Sigma _{m}^{0}} であるとは、それを Σ m 0 {\displaystyle \Sigma _{m}^{0}} 論理式で定義できることを意味し、すなわち、 Σ m 0 {\displaystyle \Sigma _{m}^{0}} 論理式 φ ( s ) {\displaystyle \phi (s)} を使って、自然数 n について φ ( n ) {\displaystyle \phi (n)} が成り立つときのみ、その自然数が A に含まれる。ある集合が Σ m 0 {\displaystyle \Sigma _{m}^{0}} であるとき、 n > m {\displaystyle n>m} である任意の n についての Σ n 0 {\displaystyle \Sigma _{n}^{0}} でもある。ただし、個々の m について Σ m 0 {\displaystyle \Sigma _{m}^{0}} ではない Σ m + 1 0 {\displaystyle \Sigma _{m+1}^{0}} 集合が存在する。従って、量化子の交代回数は、集合の複雑さの尺度を定義するのに必要である。
ポストの定理では、上で定義したような絶対的な算術的階層だけでなく、相対化された算術的階層も使う。自然数の集合 A が B に対して相対的に Σ m 0 {\displaystyle \Sigma _{m}^{0}} であることを Σ m 0 , B {\displaystyle \Sigma _{m}^{0,B}} と表記する。これは、B のメンバーシップを表す述語を含めた拡張言語で記述された Σ m 0 {\displaystyle \Sigma _{m}^{0}} 論理式で A を定義可能であることを意味する。