ゲーデルの加速定理
エーレンフォイヒト(英語版)とミッシェルスキー(英語版)は計算可能性理論を用いて次の加速定理を証明した:
任意の計算可能関数 r {\displaystyle r} に対して、 T {\displaystyle T} で証明可能な文 ψ {\displaystyle \psi } が存在して r ( ‖ ψ ‖ T + φ ) ≤ ‖ ψ ‖ T {\displaystyle r(\Vert \psi \Vert _{T+\varphi })\leq \Vert \psi \Vert _{T}} が成り立つ。
例えば r ( x ) = 2 x {\displaystyle r(x)=2x} とすると 2 ‖ ψ ‖ T + φ ≤ ‖ ψ ‖ T {\displaystyle 2\Vert \psi \Vert _{T+\varphi }\leq \Vert \psi \Vert _{T}} より ‖ ψ ‖ T + φ ≤ ‖ ψ ‖ T / 2 {\displaystyle \Vert \psi \Vert _{T+\varphi }\leq \Vert \psi \Vert _{T}/2} となる。つまり証明のサイズが半分に落ちる。同様に、 r {\displaystyle r} を指数関数とすれば、後式の右辺は対数関数となる。このように、増加の激しい関数 r {\displaystyle r} を取る毎に、その逆関数(これは増加が緩やかとなる)に対応した証明の短縮(加速)が起こる。
帰納的理論 T {\displaystyle T} と文 φ {\displaystyle \varphi } について T + ¬ φ {\displaystyle T+\neg \varphi } は決定不可能であると仮定する。したがってとくに φ {\displaystyle \varphi } は T {\displaystyle T} で証明できない。この条件を満たす例としては、ロビンソン算術と加法や乗法の交換法則、ペアノ算術とグッドスタインの定理やパリス・ハーリントンの定理(英語版)、ZFと選択公理や決定性公理、ZFCと連続体仮説や巨大基数公理などがある。
T {\displaystyle T} における証明と T + φ {\displaystyle T+\varphi } における証明の複雑性を比較したい。ただし証明の複雑性を測る関数 | ⋅ | {\displaystyle |\cdot |} は静的複雑性測度の条件を満たすものとする。すなわち、証明の複雑さの上限を固定する毎に、その複雑さ未満の証明は有限個に限られ、かつそのような証明全体の成す有限集合を(与えられた上限から)計算できるものとする。理論 T ′ {\displaystyle T'} における文 ψ {\displaystyle \psi } の証明の複雑さの最小値を ‖ ψ ‖ T ′ {\displaystyle \Vert \psi \Vert _{T'}} と書くことにする。この証明の最小の複雑さを与える関数は(証明可能な文全体を定義域とする)計算可能関数である。
とだけ書かれた証明を持つ。(厳密には「 T ′ {\displaystyle T'} における証明」の形式化の仕方に依存するが、以下の議論は、適当な修正のもとで、どんなリーズナブルな形式化にも通用する。)一般に ψ {\displaystyle \psi } とだけ書かれた(ベースとなる論理における)推論の複雑さを f ( ψ ) {\displaystyle f(\psi )} と定義する。すると ‖ ψ ‖ T ′ ≤ f ( ψ ) {\displaystyle \Vert \psi \Vert _{T'}\leq f(\psi )} が成り立つ。いま g ( x ) {\displaystyle g(x)} を「 x {\displaystyle x} 以下の複雑さの推論の末尾(帰結)に現れる論理式 ψ {\displaystyle \psi } に対する f ( ψ ) {\displaystyle f(\psi )} の総和」と定める。すると g ( ‖ ψ ‖ T ′ + φ ) ≥ f ( ψ ) ≥ ‖ ψ ‖ T ′ {\displaystyle g(\Vert \psi \Vert _{T'+\varphi })\geq f(\psi )\geq \Vert \psi \Vert _{T'}} となる。
証明の複雑さの尺度として、証明に現れる論理式の個数や、推論規則の適用回数を採用した場合にも、やはり反例が存在する。
↑ もっとも、この場合は文そのものにとてつもなく長大な数字(グーゴルプレックス)が埋め込まれているかもしれず、それが原因で証明が長くなってしまっている可能性を排除できない。この可能性を排除する為には、次のようにすればよい。論理式 π ( x , y ) {\displaystyle \pi (x,y)} を「 x {\displaystyle x} (をコードとして持つ論理式)は高々 y {\displaystyle y} 個の記号からなる形式的証明を持たない」という論理式とする。この論理式は Δ 1 ( P A ) {\displaystyle \Delta _{1}(PA)} で書ける。グーゴルプレックスを(ペアノ算術において)定義する短い Δ 1 ( P A ) {\displaystyle \Delta _{1}(PA)} -論理式 ψ ( x ) {\displaystyle \psi (x)} を見出す。