ゲーデルの加速定理
具体的な例を見るために、最短の形式的証明がとてつもなく長大となる文を構成しよう。形式化された対角線論法によって
φ「この文は高々グーゴルプレックス個の記号からなる(ペアノ算術からの)形式的証明を持たない」
なる内容的意味を持つ文を構成する。(ここで「グーゴルプレックス個の記号からなる」という部分を取り除くと不完全性定理の決定不能な文が得られる。)コーディングを工夫すれば φ がΣ1論理式となるようにできる。φ はペアノ算術から証明可能である:もし証明不能なら「高々グーゴルプレックス個の記号からなる(ペアノ算術からの)形式的証明を持たない」が標準模型で真なので、Σ1完全性より φ は証明可能である。これは不合理。したがって φ は証明可能である。するとΣ1健全性より φ は標準模型で真である。つまり「φ は高々グーゴルプレックス個の記号からなる(ペアノ算術からの)形式的証明を持たない」から、φ の形式的証明はグーゴルプレックス個よりも多くの記号から構成される。
φはより強い体系ではもっと短い形式的証明を持つ:例えばペアノ算術に自身の無矛盾性を表す公理 Con(PA) を追加した体系を用いればよい。(追加された公理は不完全性定理よりペアノ算術からは証明不能である。)すると、上の背理法による議論を体系内で実行することができ、より短い形式的証明が得られる: ¬φ と仮定する。
ゲーデルの加速定理(ゲーデルのかそくていり、英: Gödel's speedup theorem)は、クルト・ゲーデルにより証明された、数理論理学における定理である。この定理によれば、弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する、というような文が存在する。より正確にいえば、それはn階算術の体系で証明可能な命題であって、n+1階算術ではより短い証明を持つものが存在するというものである。