[過去ﾛｸﾞ] 純粋・応用数学 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
112(1): 現代数学の系譜 雑談 ◆e.a0E5TtKE 2020/05/09(土)13:13 ID:Mxr6sv2r(2/5) AAS
メモ
外部ﾘﾝｸ:ja.wikipedia.org
カット除去定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ナビゲーションに移動検索に移動
カット除去定理（カットじょきょていり、英: Cut-elimination theorem）は、シークエント計算の手法の重要性を示す、数理論理学の主要な結果のひとつである。
（数理論理学の）基本定理と呼ぶこともある。ゲルハルト・ゲンツェンが1934年に書いた記念碑的論文 "Investigations into Logical Deduction" で、古典論理と直観論理の体系をそれぞれ形式化したシークエント計算の形式的体系 LK 及び LJ において、最初に証明が与えられた。
カット除去定理は、シークエント計算の推論規則であるカット規則を用いて証明可能な式には、カット規則を用いない証明図もまた必ず存在することを示したものである。
目次
1 シークエント
省6
116(1): 2020/05/13(水)10:04 ID:YxiDM0Si(1/2) AAS
>>112
カットを除去するのは、証明の効率とか見やすさとは無関係
ざっくりいえば、
「カットのない証明ばかりなら理論は無矛盾」だから
「どんな証明もカットなしにできる」と云えれば
理論が無矛盾だといえる
ただし肝心のカット除去の手続きは元の理論の枠内でできない
（ペアノ算術のカット除去がε0の超限帰納法を必要とするのは有名だが
より弱い算術でもカット除去に必要な順序数の超限帰納法は
その理論で許される帰納法の範囲を超えている）
省2
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.037s