再帰理論
逆数学のプログラムは、二階算術の中の部分体系において、ある定理を証明するのにどの程度の集合存在公理が必要かを問うものである。この研究は Harvey Friedman が創始し、Stephen Simpson らが進めた。Simpson(1999)で、これに関する詳細が議論されている。対象となる集合存在公理は、自然数のべき集合が様々な還元可能性の概念の下で閉じていることを言う公理群とほぼ対応している。逆数学で研究されているそのような公理の中で最も弱いものは「再帰的内包公理; Recursive Comprehension Axiom」であり、これは自然数のべき集合はチューリング還元可能性の下で閉じているとするものである。
ポストの問題は優先度法という技法を用いて解決された。この技法を用いる証明は優先度論法と呼ばれる。これは第一義的には特別な性質を備えた帰納的可算集合を構成することを目的とする。やり方としては、まずその帰納的可算集合が備えるべき性質を無限個の「要件」に分解し、全ての要件を満足すれば目的の集合は自ずと所期の性質を獲得する、という形を作る。個々の要件には優先度を表す自然数を付与しておく。0 を付与された要件が最優先で、以下 1、2 ...という具合である。以後、目的の集合を「段階」を踏んで構築して行く。個々の段階は、一つ以上の要件を満たすように、目的の集合に対して数を追加または削除することから成る。一つの要件を満たすと他の要件に反してしまう場合が有り得るが、その際は優先度を参照して処理方法を決定する。
これまで優先度論法を用いて再帰理論の様々な問題が解決されてきており、それらは複雑さの観点から階層状に分類されている(Soare 1987)。複雑な優先度論法はテクニカルかつ難解になりがちなので、伝統的に出来れば優先度論法は使わずに証明することが望ましいとされ、また優先度論法を用いた証明があればそれ抜きの別証明が模索されてきた。例えば Kummer は Friedberg ナンバリングの存在証明について優先度法を用いない証明を発表した(Kummer 1989, 1990)。