ゲーデルの加速定理
はペアノ算術において証明可能だが、その最短の証明は少なくとも長さ A ( 1000 ) {\displaystyle A(1000)} を持つ。ここで A ( 0 ) = 1 {\displaystyle A(0)=1} かつ A ( n + 1 ) = 2 A ( n ) {\displaystyle A(n+1)=2^{A(n)}} である。この主張はクラスカルの定理の特別な場合であり、二階算術においてより短い証明を持つ。
ペアノ算術に上記の主張の否定を付け加えたならば、矛盾した理論であって、その最短の矛盾(の証明)が想像を絶するほどに長いものが得られる。上記の主張を φ {\displaystyle \varphi } とおく。いま P A + ¬ φ {\displaystyle PA+\neg \varphi } から矛盾に至る証明が与えられたとする。すると(論理が適切に形式化されている限り)証明の長さを定数倍程度しか増やさない仕方で、 P A {\displaystyle PA} から φ {\displaystyle \varphi } に至る証明が得られる。(例えば、ベースとなる論理体系が帰謬法を推論規則として陽に含む場合、証明の長さは1ステップ分しか増えない。)後者の証明は途轍もなく長いので、前者の証明もまた途轍もなく長い。