ゲーデルの加速定理
この定理は同じ言語で書かれたふたつの理論の間の加速可能性しか教えてくれない。理論 T {\displaystyle T} が言語 L {\displaystyle L} で書かれ、理論 T ′ ⊋ T {\displaystyle T'\supsetneq T} が言語 L ′ ⊋ L {\displaystyle L'\supsetneq L} で書かれている場合、この定理は加速可能な L ′ {\displaystyle L'} -文の存在は教えてくれるが、加速可能な L {\displaystyle L} -文の存在は教えてくれない。例えば、二階算術の部分体系ACA0とその超準的な拡大理論との間には、多項式増大度を越える加速定理が成立しないことが知られている。すなわち言語の拡大を伴う場合には反例が存在する。
また T {\displaystyle T} が帰納的でない場合にも反例が存在する。例えば T , φ {\displaystyle T,\varphi } を定理の条件を満たすペアとする。 T {\displaystyle T} で証明可能な文全体(演繹閉包) T ′ {\displaystyle T'} と φ {\displaystyle \varphi } は帰納性の条件を除いて定理の条件を満たす。 T ′ {\displaystyle T'} で証明可能な任意の文 ψ {\displaystyle \psi } は
ψ {\displaystyle \psi }
すると P A ⊢ ∀ y ( ψ ( y ) → π ( x , y ) ) ≡ ∃ y ( ψ ( y ) ∧ π ( x , y ) ) {\displaystyle PA\vdash \forall y(\psi (y)\to \pi (x,y))\equiv \exists y(\psi (y)\land \pi (x,y))} であるから、この同値な Δ 1 ( P A ) {\displaystyle \Delta _{1}(PA)} -論理式を π ( x ) {\displaystyle \pi (x)} とおく。形式化された対角線論法によって P A ⊢ φ ≡ π ( ⌈ φ ⌉ ) {\displaystyle PA\vdash \varphi \equiv \pi (\lceil \varphi \rceil )} を満たす φ {\displaystyle \varphi } が得られる。この φ {\displaystyle \varphi } は前述の文と同じ内容を持つが、その長さはグーゴルプレックスより遥かに短い。