>>253

つづき

https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%87%E3%83%AB%E3%81%AE%E5%8A%A0%E9%80%9F%E5%AE%9A%E7%90%86
ゲーデルの加速定理

この定理によれば、弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する、というような文が存在する。

クルト・ゲーデルはそのような性質を持つ文を具体的に構成した。それはn階算術の体系で証明可能な命題であってn+1階算術ではより短い証明を持つものが存在するというものである。類似の例として最短の形式的証明がとてつもなく長大となる文を構成しよう。形式化された対角線論法によって

φ「この文は高々グーゴルプレックス個の記号からなる（ペアノ算術からの）形式的証明を持たない」
なる内容的意味を持つ文を構成する。（ここで「グーゴルプレックス個の記号からなる」という部分を取り除くと不完全性定理の決定不能な文が得られる。）コーディングを工夫すれば φ がΣ1論理式となるようにできる。
(引用終り)
以上