19/04/11 07:27:17.60 SCIZmoFu.net
>>428
>ゲーデルの加速定理は圏とも高階論理とも無関係
(>>184より)
URLﾘﾝｸ(ja.wikipedia.org)
ゲーデルの加速定理
ゲーデルの加速定理（ゲーデルのかそくていり、英: Godel's speedup theorem）は Godel (1936)で証明された。この定理によれば、弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する、というような文が存在する。
クルト・ゲーデルはそのような性質を持つ文を具体的に構成した。それはn階算術の体系で証明可能な命題であってn+1階算術ではより短い証明を持つものが存在するというものである。
(引用終り)
ゲーデルの加速定理
↓
クルト・ゲーデルはそのような性質を持つ文を具体的に構成した。それはn階算術の体系で証明可能な命題であってn+1階算術ではより短い証明を持つものが存在するというものである。
↓
高階論理
↓
圏論