ゲーデルの加速定理
いま T + φ {\displaystyle T+\varphi } で証明できて T {\displaystyle T} で証明できない文(つまり「新しい定理」)の全体を D {\displaystyle D} とおく。この集合の計算論的な複雑さを解析することで定理が証明される。この集合は次のように性質を持つ:
φ ∨ ψ ∈ D ⟺ T ⊬ φ ∨ ψ ⟺ T + ¬ φ ⊬ ψ . {\displaystyle \varphi \vee \psi \in D\iff T\not \vdash \varphi \vee \psi \iff T+\neg \varphi \not \vdash \psi .}
したがって D {\displaystyle D} は帰納的可算でない。ただしd-帰納的可算ではある。
いま加速定理の主張が成立しないと仮定してみよう。つまり、 T + φ {\displaystyle T+\varphi } で証明可能な任意の文 ψ {\displaystyle \psi } に対して、
T ⊢ ψ {\displaystyle T\vdash \psi } ならば r ( ‖ ψ ‖ T + φ ) > ‖ ψ ‖ T {\displaystyle r(\Vert \psi \Vert _{T+\varphi })>\Vert \psi \Vert _{T}}
が成り立つ。