メモ
https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%83%E3%83%88%E9%99%A4%E5%8E%BB%E5%AE%9A%E7%90%86
カット除去定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ナビゲーションに移動検索に移動
カット除去定理（カットじょきょていり、英: Cut-elimination theorem）は、シークエント計算の手法の重要性を示す、数理論理学の主要な結果のひとつである。
（数理論理学の）基本定理と呼ぶこともある。ゲルハルト・ゲンツェンが1934年に書いた記念碑的論文 "Investigations into Logical Deduction" で、古典論理と直観論理の体系をそれぞれ形式化したシークエント計算の形式的体系 LK 及び LJ において、最初に証明が与えられた。
カット除去定理は、シークエント計算の推論規則であるカット規則を用いて証明可能な式には、カット規則を用いない証明図もまた必ず存在することを示したものである。

目次
1 シークエント
2 カット規則
3 カット除去定理

カット除去定理
カット除去定理は、ある論理体系でカット規則を使って証明可能なシークエントは、この規則を使わずとも証明可能であることを示したものである。そのシークエントが定理であるとき、カット除去定理は、単に、その証明の過程で使われた補題 C をインライン化できることを示している。
すなわち、定理の証明が補題 C を使っている場合、その箇所を全て C の証明に置き換えることで、新しい完全な証明図を与えることができるということである。従って、カット規則は許容できる規則 (admissible rule) である。

シークエント計算で形式化される体系では、カット規則を使わない証明を「解析的証明; analytic proof」と呼ぶ。そのような証明は必ず長くなるというわけではないが、一般的には長くなる。George Boolos の論文 "Don't Eliminate Cut!" では、カット規則を使えば1ページで表せる証明（導出）があったとき、その解析的証明が完了するまでに宇宙の寿命より長くなる例が示されている。