科学哲学科学史 (演習) 論理学

京都大学文学部の「科学哲学科学史 (演習) 論理学」(毎週火曜日16:45〜18:15)の授業Blogです。

前期授業第14回(7/21)

前期の授業も、いよいよ最終回になりました。今回は前期の総まとめとして、これまで積み上げてきた「良い証明=良い言語」の条件を物差しにして、いま話題の大規模言語モデル(LLM)の「ハルシネーション(もっともらしい嘘)」を診断してみます。

今回の目次は、次のとおりです。まず前回の宿題の答え合わせから始めて、LLM が文章をどう作るのかを概説します。そのうえで「LLM は意味を分布意味論で近似している」という見方を立て、それが意味の全体論の一種であること、そして本物の意味(分子論)とのズレこそがハルシネーションであることを見ます。最後に、そのズレを前期に完成させた三層ハーモニー(局所・中間・大域)で分類し、対策も同じ枠で読み替えます。

大きな結論を先に言ってしまうと、''「計算している」ことは「証明している」ことを含意しない''、ということです。LLM は確かに計算していますが、論理が要求する三つの条件をどれも保証してくれません。前期にやってきた「走って・止まって・積み上がる」という三つの物差しは、そのまま AI を測る物差しでもあった、というのが最終回のメッセージです。

授業日時

7月21日(火)16:45〜18:15
文学部第4講義室

授業内容

  • 前回のおさらい(宿題の答え合わせ:次数・tonk・否定の略記)
  • LLM は文章をどう作るのか(一語ずつ・確率・尤度)
  • 分布意味論——意味を「使われ方」で近似する
  • 分子論は「全体論の決定可能な断片」——カノニカルフォーム
  • 近似だから差分が出る=それがハルシネーション
  • 三層診断:局所(詰まらなさの偽装)/中間(止まるが証明でない)/大域(積み上がる保証がない)
  • 処方を三層で読み替える(RAG・棄権・自己検証)
  • オチ:LLM の中に「システム2」を=それが論理
  • 演習(身近なハルシネーションを三層で診断せよ)

https://speakerdeck.com/player/PRESENTATION_ID speakerdeck.com

解説

前回の宿題の答え合わせ

最終回は、前回(7/14)の宿題の答え合わせから始めました。

問1は、遠回りを一つ含む証明を描き、β簡約すると次数が下がることを確かめる問題でした。→I(ならばの導入)の直後に →E(ならばの除去)が来ると、そこに「峰」として命題 A→B が立ちます。この遠回りを消す(A の証明を仮定 [A] に代入する)と、峰の A→B が消えて B の直接証明になります。残る遠回りは A や B についてのものだけで、必ず次数が小さくなります。だから証明はいつか正規形にたどり着く(弱正規化)、というのが答えです。

問2は、tonk という結合子を足すと保存拡大が壊れることを示す問題でした。tonk は導入で A ⊢ A tonk B、除去で A tonk B ⊢ B とすると、この二つをつなぐだけで A ⊢ B が任意の B について導けてしまいます。つまり、どんな前提からどんな結論も出る「爆発」が起き、古い語彙のままで新しい定理を無限に増やしてしまいます。これが「保存拡大が壊れる」ということでした。

エクストラ問は、否定を ¬A ≔ A→⊥ という「略記」として足すのは良い定義か、というものでした。答えは「はい、保存拡大です」。¬ はあくまで略記なので、いつでも A→⊥ に展開して消すことができます。だから ¬ を使った証明はすべて ¬ なしに書き直せて、⊥(¬)を含まない古い定理は一つも増えません。tonk が「展開して消せない=密輸をする」のと対照的です。''良い定義とは、略記であり、保存拡大である''。これは第10回でやったことの回収でした。

LLM は文章をどう作るのか

さて本題です。まず、今日の主役である LLM が何をしているのかを、素直に確認しました。

LLM(大規模言語モデル)は、大量のテキストで訓練された巨大なニューラルネットワークです。やっていることは、入力に続く文章を''一語ずつ''作ることです。「ここまで来たら次に何が来そうか」を予測し、一語選んで末尾に足し、それをまた入力に戻して次の語……を、止めどきまで繰り返します(自己回帰)。

次の一語は、確率で選ばれます。モデルは候補の語それぞれに点数をつけ、それを合計1の確率に変換して(softmax)、確率にしたがって一語を選びます。「京都は日本の___」なら、古都・都市・首都……に確率が割り振られます。ここで大事なのは、''必ずどれかの語に正の確率が付く''ということです。つまり LLM は「黙る」ことができません。この含意は、あとで効いてきます。

そして学習の目的は「もっともらしさ」です。訓練とは、人間が書いた大量のテキストをうまく再現できるように内部の数値を調整すること(尤度を上げる、最尤推定)です。最適化されるのは、真理性ではなく、もっともらしさです。

分布意味論——意味を「使われ方」で近似する

この仕組みを「意味の理論」として読み直すと、LLM は語の意味を「その語がどんな語と一緒に現れるか(使われ方の分布)」で捉えている、と言えます。これは''分布意味論''と呼ばれる立場で、「語は、そのつきあう仲間で分かる」(ファース)という分布仮説に基づきます。意味を「事実との対応」ではなく「言語内の使われ方」で捉えるわけです。

LLM が見ている「分布」は、ウェブ規模のコーパス(人間が書いた大量テキスト)での共起です。だから LLM が捉えるのは「その語のまわりに何が来やすいか」=コーパスでのもっともらしさであって、世界の事実でも証明でもありません。要するに、''LLM は意味を「分布」で近似している''のです。

分子論は「全体論の決定可能な断片」

分布意味論は、実は「意味の全体論」(意味は言語全体の使われ方に溶けている、クワイン)の一バリエーションです。これに対して、この授業でやってきたのは''分子論''(ダメット)でした。分子論では、一つの語の意味は、その語の「使い方の規則」=導入規則と除去規則だけで決まり、言語全体を見る必要がありません。

面白いのは、分子論は全体論の反対というより、''全体論のうち「決定可能な断片」を取り出したもの''だ、という点です。全体論のまま(言語全体)だと、意味は見渡せず、決定できず、学べません。分子論は、使い方を「見渡せる・決定可能な断片」に限ることで、「意味=使い方」という長所は保ったまま、決定可能性・学習可能性・合成性を手に入れます。いわば「いいとこどり」です。そして前期にやった三層ハーモニー(詰まらない・止まる・積み上がる)は、まさにこの「決定可能な断片」を切り出すための条件でした。

具体例で言うと、「A ∧ B」(A かつ B)のカノニカルな証明(標準的な作り方)は、「A の証明と B の証明を組にしたもの」=ペアです。たとえば「雨が降っている ∧ 風が吹いている」の標準証明は〈雨の証拠, 風の証拠〉というペアで、確かめるのに要るのは「雨」と「風」の意味だけ、言語全体は要りません。しかも正規化定理によって、どんな回り道をした証明も、正規形(カノニカルフォーム)に直せばこのペアに戻ります。だから「A ∧ B が分かる」とは「A と B さえ分かればよい」ということなのです。これが「分子」の正体でした。

近似だから、差分が出る=それがハルシネーション

ここで背骨がつながります。LLM は意味を''全体論の網ごと''近似しています。分子論のように「決定可能な断片(ペアやカノニカルフォーム)」に収める保証がありません。だから、本物(証明の資格ある意味)との間に、断片からはみ出す「差分」が必ず残ります。

''この差分こそが、ハルシネーションです''。「幻覚」という言い方は、じつは誤称です(LLM は感覚を持ちませんし、誤りはデータと目的関数から生じます)。この授業の言葉に直すと、ハルシネーションとは「証明の資格のない項を、全域性を装って差し出す構造的性質」=〈近似〉と〈本物〉のズレなのです。では、そのズレはどう現れるか。前期に完成させた三つのハーモニーが、差分を分類する物差しになります。

三層診断

''局所(詰まらない)の破れ''。論理の「詰まらない」は、根拠(簡約規則)があるから進めることでした。ところが LLM の softmax はいつでも次の語を出せます。これは「詰まらなさの偽装」です。根拠がなくても前に進めてしまう=根拠なき前進。ソース参照乖離(主張がソースに依拠しない)が典型で、意味の分子構造がないために「この主張の根拠」を部品として取り出せないのです。

''中間(止まる=全域性)の破れ''。ここが今日の心臓です。論理の中間は「止まって、証明の資格ある値を返す(全域性)」でした。LLM は生成を止めて答えを差し出しますが、その値は証明の資格を持ちません=「差し出したふり」=永遠に履行されない約束手形です。ではどうやって止まっているのか。証明の正規化のように内側から保証されて止まるのではなく、外から課された「打ち切り」(トークン予算・時間・学習した終了傾向)で止まっています。しかも重要なのは、''推論そのものの正規化と、出力(文章)の正規化が分離している''ことです。内部推論は正規化しないことがあっても、「したがって」で文章を閉じることは学習済みなので、''LLM は証明を正規化できなくても、証明「らしい文書」を正規化して出せる''のです。だから、詰まったときほど最後だけ堂々とした誤答が出ます。理論的にも、Kalai らは「ハルシネーションは二値分類の誤りであり、学習データが誤りゼロでも、生成の誤り率は識別の誤り率のおよそ2倍を下回れない」と示しています。さらに、多くの評価が「わからない」と言う棄権を罰するので、当てずっぽうが最適になり、全域性が偽装されるのです。

''大域(積み上がる=保存拡大)の破れ''。論理の大域は「増築しても既存が壊れない(保存拡大・モジュラリティ)」でした。LLM の再学習では、破滅的忘却——新しく学ぶと既習の性能が急落しうる現象——が起きえます。ここは精度が大事で、破滅的忘却は「必ず起きる」わけではありません(EWC やリプレイなどで大きく緩和できます)。しかし、どの手法も「非忘却」を保証しません。論理は保存拡大を内在的に「保証」するのに対し、LLM の再学習にはその保証がない——だから「積み上がる」と言い切れないのです。追従(sycophancy、話者に迎合して結論が動く)も、同じく非保存的な症状です。

三つの破れは、根が一つでした。''意味の分子構造の欠如''です。分子がないから、(局所)根拠に結べず、(中間)値を検証できず、(大域)部品を足せない。これは前期の「有限性の三つの顔」のちょうど裏返しになっています。

処方を三層で読み替える

対策も、同じ三層で「どの層の要求を補強するか」で読めます。局所を補強するのが RAG(検索で主張を根拠に結ぶ)や記号的検証。中間を補強するのが棄権(わからないと言う訓練)・評価改革・自己検証(SelfCheckGPT)・DoLa。大域を補強するのが RAG(知識の外部化=非破壊的更新)や継続学習です。どれも「システム1の上に、あとから足場を組む」試みだと見ることができます。

オチ:LLM の中に「システム2」を=それが論理

最後のオチです。第2回で、人間の脳は速くて直感的な「システム1」の上に、ゆっくり規則にしたがう「システム2」を育てた、という話をしました。システム2は脳の上の仮想計算機で、その起源は社会的・言語的実践にあり、プログラマブル(学べる・直せる)でした。LLM は、このシステム1(もっともらしさの模倣)に当たります。足りないのは''システム2=証明を走らせる仮想計算機''=今日の三層ハーモニーです。今日見た処方は、どれも「システム1の上にシステム2を後付けする」試みでした。だとすれば、''論理こそ、その「システム2」の仕様書''なのです。速度の代償はあります(システム2は遅くて高価です)。でも、証明の資格は、そこにしかありません。

前期の一行にまとめれば、''「計算している」ことは「証明している」ことを含意しない''。LLM は走ります(むしろ走りすぎます)。けれど、止まって証明を差し出すことも、壊れずに積み上がることも、保証してくれません。論理とは、走って・止まって・積み上がる営みです。その三層の物差しは、AI を測る物差しでもありました。半年間、おつかれさまでした。

今回のキーワード

分布意味論, 意味の使用説, 分布仮説, 意味の全体論, 分子論(ダメット), カノニカルフォーム, 正規化, 全域性, 保存拡大, モジュラリティ, ハルシネーション, 二値分類の誤り, 破滅的忘却, 継続学習, RAG, 棄権, システム1/システム2, 仮想計算機, カリー・ハワード対応

前期授業第13回(7/14)

第13回は、これまで積み上げてきた「論理の良さ」の話と「計算」の話を、一本につなぐ回でした。合言葉は「走って、止まって、積み上がる」です。今回の目次は、(1) なぜ証明は必ず止まるのか、(2) 局所の関門=詰まらない(反転原理=β変換=計算が走る根幹)、(3) 大域の関門=モジュラリティ(保存拡大=社会的分業=知識が積み上がる)、(4) 統合と総括、の四本です。

前回(第12回)で、証明とはプログラムであり、正規化とはそのプログラムの実行である、というカリー・ハワード対応を紹介しました。今回はその見方を土台にして、第11回でやった三層ハーモニー(局所の反転原理・中間の正規化・大域の保存拡大)を、まるごと計算の言葉に翻訳します。三つの層は、計算で言えば「詰まらない・止まる・壊さず増築できる」の三つになります。

とくに時間をかけたのが「なぜ証明は必ず止まるのか」です。前回は時間切れで言えなかった一番大事なところで、じつは階乗の計算が必ず止まるのと同じ理由です。命題(型)は帰納的に、有限に組み立てられるので、それを崩していく還元は必ず有限で終わります。この「有限型の正規化可能性」については、証明そのものを参考資料として二種類配布しました(詳しくは後述します)。次回は最終回で、この道具立てを使ってLLMのハルシネーションを計算の言葉で特徴づけます。

授業日時

7月14日(火)16:45〜18:15
文学部第4講義室

授業内容

  • 前回のおさらい(証明はプログラム、正規化はその実行)
  • 宿題の答え合わせ(弱化の匂いのする A→B→A、怪物ρで矛盾を導くエクストラ問)
  • なぜ止まるのか(有限型のλ項は次数が下がるから必ず止まる。階乗と同じ)
  • カリーのパラドックス=自明化、不動点コンビネータ、Ω(止まらないもの)、一般再帰fix
  • 局所の関門=詰まらない(反転原理=β変換=計算が走る根幹)
  • 大域の関門=モジュラリティ(仮想機械の合成=社会的分業=借り物を一本道に直せる=知識が積み上がる)
  • 統合と総括(型安全性、ライプニッツの夢、意味の有限主義、ふたたびLLMへ)
  • 演習・次回予告(最終回はハルシネーションの計算的特徴づけ)

https://speakerdeck.com/player/PRESENTATION_ID speakerdeck.com

解説

まず前回の復習からです。証明木に項(λ項)を注釈すると、証明はλ計算のプログラムになります。導入の直後に除去がくる「遠回り」は、項では (λx.M)N という形(β基)になり、これを消すことが計算を一歩実行すること(β変換)でした。遠回り=β基、カット&ペースト=代入、正規化=プログラムの実行、という辞書です。

今回の一番大事なところは「なぜ証明は必ず止まるのか」です。ここは言葉で「型が停止を守る」と書くだけでは伝わりません。イメージは階乗です。fact(3) = 3・fact(2) = 3・2・fact(1) = 3・2・1・fact(0) = 6 のように、引数を一つずつ減らして 0(底)で必ず止まります。証明の書き換えもこれと同じで、命題(型)が帰納的に有限に組み立てられるので、それを崩していく作業は必ず有限で底を打ちます。より具体的には「次数」で測れます。次数とは遠回りの峰にある論理式の複雑さ(結合子の数)で、たとえば p は 0、p→q は 1、(p→q)→r は 2 です。A→B の遠回りを消すと、より小さい部分 A・B の遠回りに変わる(次数が下がる)。一番高い峰から消していけば必ず正規形に至ります。第9回のヒドラゲームで見た、あの「次数の辞書式が減る」話がそのまま効いています。逆に自己言及の文 ρ ⟺ (ρ→C) は、ほどいても自分自身が出てくるので次数が下がらず、Ω や fix は永遠に回ります。ここが「止まる/止まらない」の分かれ目です。

その怪物の正体も答え合わせしました。エクストラ問の ρ に項をつけると、Ω = (λx.xx)(λx.xx) になり、β簡約すると自分自身に戻って止まりません。一般化すると、自己言及する ρ からは任意の C が「証明」できてしまう。これがカリーのパラドックスで、tonk と同じ「自明化」の仲間です(矛盾律を経由せず、直接どんな結論も出てしまう)。その証明項は不動点コンビネータ Y でした。犯人は縮約(自己言及の仮定を二回使うこと)で、嘘つきのパラドックスはその C=⊥ の特殊ケースです。縮約のないアフィン論理(第8・9回)では xx が作れないので、これらは矛盾を起こしません。

次に、局所の関門を計算の言葉にしました。反転原理(導入と除去が釣り合う=どの遠回りにも簡約規則がある)は、計算で言えば「β変換ができること」そのものです。遠回りを消すこと=計算を一歩実行すること。つまり反転原理が計算の実行を保証しているのです。tonk のように簡約規則が書けないと、計算は詰まって走りません。ここが本質で、「推論とは計算である」とカリー・ハワード的に言えるのは、反転原理があって初めてなのです。

そして大域の関門=モジュラリティです。ここは今回いちばん膨らませたところです。仮想計算機(第2回、デネット)は言語共同体で共有・同期されるので、私たちは他人の議論を借りられます。カリー・ハワードで見ると、その仮想機械は一つの証明そのもので、実行が正規化です。ここで、A→B を証明した機械と A を証明した機械を→除去(適用)でつなぐと、より大きな一つの機械(B の証明)になります。これが社会的分業です。つないだ継ぎ目が遠回り(β基)で、正規化すると二つの機械が融合して、一つの根拠から結論への一本道になります。借り物の議論でも一本道に直せるということは、借りた補題は原理的に自分で展開できた(新しいことを密輸していない)ということで、これが保存拡大=モジュラリティです。良い定義とは「略記」で保守的に足せるもの(たとえば ¬A ≔ A→⊥)で、第10回でやったとおり、tonk やボッシュのような悪い定義は非保存的で、既存の言語を汚染してしまう「借りてはいけない議論」です。技術的には、正規化(カット除去)が部分論理式性を与え、それが保存拡大を保証します(中間が大域を支える)。そしてこのモジュラリティのおかげで、社会的分業が成立し、各人・各世代が別々に証明した部品を持ち寄れて、ローカルな知識が壊れずに世代を超えて積み上がっていきます。これが合言葉「積み上がる」の意味です。

最後に統合と総括です。ミルナーの「型のついたプログラムは間違えない(well-typed programs don't go wrong)」は、まさに三層ハーモニーの計算版でした。ライプニッツが夢見た「推論は計算である」は、350年後にカリー・ハワード対応として定理になりました。ただしライプニッツも知っていたように、人間にとって証明の資格を持つのは「止まる(全域的な)」計算だけです(意味の有限主義)。そして次回の頭出しとして、ふたたびLLMに戻りました。LLMは計算はしているけれども、中間の要求(全域性=止まって証明の資格ある値を返す)も、大域の要求(モジュラリティ=追加学習が保存拡大にならない、破滅的忘却)も、欠いているかもしれない。その答えは最終回で、というところで切りました。

今回のキーワード

カリー・ハワード対応, 証明はプログラム, 正規化はその実行, 反転原理, β変換, 詰まらない, 正規化, 止まる, 全域性, 次数, 部分論理式性, カット除去, 保存拡大, モジュラリティ, 社会的分業, 仮想計算機, カリーのパラドックス, 自明化, 不動点コンビネータ, 縮約, 一般再帰fix, 強正規化, 弱正規化, 意味の有限主義, ハルシネーション

配布した参考資料(有限型の正規化可能性の証明)

「なぜ有限型の証明は必ず止まるのか」を、証明そのものとして二種類配布しました。どちらも→断片で、証明の各ステップが「証明の正規化」のどこに当たるかをカリー・ハワードで一対一に対応づけています。

  • 強正規化を「可約性」で読む(Taitの方法):型ごとに「良い(正規化する)項」の集まりを命題の複雑さに関する帰納で構成し、すべての項がそれに入ることを示します。単純型が整礎に並ぶ(帰納的に構成される)ことが、この構成を回す土台です。
  • 弱正規化を「次数」で読む:型の次数が停止の測度そのものになる版です。一番高い峰から遠回りを消すと、次数の(最大値・本数)が必ず減って正規形に至ります。第9回のヒドラゲームが、縮約のないアフィン論理でこれを目に見える形で示したものです。

興味のある人は、授業本編の「なぜ止まるのか」の厳密版として読んでみてください。

宿題

  • 問1(中間):遠回りを一つ含む証明を描き、β簡約すると峰の命題 A→B が消えて次数が下がることを確かめよ。
  • 問2(大域):tonk 規則(A ⊢ A tonk B / A tonk B ⊢ B)を足すと、任意の A ⊢ B が導けること(=保存拡大が壊れること)を証明図で示せ。
  • エクストラ問(任意):否定を ¬A ≔ A→⊥ の略記として足すのは「良い定義(保存拡大)」か。論じよ。ヒント:⊥ を含まない古い定理が、¬ を足したことで新しく増えるか。

提出方法・期限はKULMSの指示に従ってください。

前期授業第12回(7/7)

前回(第11回)は、調和(ハーモニー)を三層モデル(ミクロ=反転原理/中間=正規化/大域=保存拡大)として定式化しました。今回(第12回)は「証明を走らせる」と題して、その中間層=正規化を、計算の言葉で読み替えます。鍵になるのはカリー・ハワード対応、すなわち「命題は型、証明はプログラム」という発見です。

今回のいちばんのメッセージは、新しく覚える記法はλ(ラムダ)ひとつだけで、あとはすべて既習概念の読み替えだ、ということです。証明木に項(λ項)を注釈すると、それがそのままλ計算になります。すると「遠回り(detour)」はβ基に、「正規化」はβ簡約=プログラムの実行になり、正規化定理は「このプログラムは必ず止まる」という停止性の保証になります。

さらに、宿題・問2で作ってもらった「壊れた結合子」を怪物図鑑として整理し、三層のどこで壊れるかを診断しました。最後に登場する怪物ρはカリー文(ρ ⟺ (ρ→⊥))で、局所診断を通り抜けるのに簡約が止まらない、いちばん陰湿な相手です。ダメットの「真正のハーモニー」を計算モデルの性質として捉え直し、「意味の有限主義」まで話を進めました。次回(第13回・7/14)は、証明から「取り出す」——A∨B の証明からAかBかが実効的に取り出せる、という∨の話に進みます。

授業日時

7月7日(火)16:45〜18:15
文学部第4講義室

授業内容

  • 前回のおさらい:三つのハーモニー概念と三層モデル
  • 宿題・問2の解説:壊れた結合子の「怪物図鑑」(打ち出の小槌/tonk/古典論理/逆張りknot/怪物ρ)
  • 証明を一次元の記号列でコードする(動機)
  • 準備:λ記法——関数の入力変数を明示する
  • 証明木に名前をつける:→導入=λ抽象、→除去=適用
  • 種明かし:この記法はChurchのλ計算だった
  • β変換:計算とはλ項の書き換え((λx.M)N →β M[x:=N])
  • カリー・ハワード対応の辞書(遠回り=β基、正規化=β簡約=プログラムの実行)
  • なぜ対応するのか:命題=証明のデータ型(propositions as types)
  • 目玉:宿題・問1の答え合わせをλで再演(カット&ペースト=代入)
  • 正規化定理の計算版=「プログラムは必ず止まる」
  • 止まらない項Ωと、型が停止を守るという教訓
  • ダメットの回収:真正のハーモニーは計算モデルの性質/意味の有限主義
  • ふたたびLLMへ/まとめ/演習・次回予告
  • 付録:カリーのパラドックスと「嘘つき」、犯人は縮約

https://speakerdeck.com/player/PRESENTATION_ID speakerdeck.com

解説

新記法はλひとつ、あとは全部「再読」

今回のねらいは、正規化を計算の言葉に翻訳することです。本講義は第1回からずっと、推論を「記号列の規則に則った変換」として見る計算的な論理観で進めてきました。命題は第3回で一次元の記号列として帰納的に定義しましたし、規則は構成子・解体子として見てきました。ところが、証明そのものだけは、まだ二次元の木の図のままでした。今日やることは、この証明を一次元の記号列でコードすることです。コードしてしまえば、証明の書き換え(正規化)も「記号列の規則に則った変換」として、本講義の推論観そのままの姿で表現できます。

証明木に名前をつける

出発点は、実はもう始まっていた作業です。みなさんは第2回から仮定に名前をつけて [v : A] と書いてきました。これは「vという名前のAの証明があると仮定する」と読めます。今日はこの名前を、仮定だけでなく証明全体に拡張します。

やり方はたった二つの規則です。まず→導入。AからAを導く証明で仮定vをキャンセルすると、A→A が得られます。これに名前をつけると λv.v になります。仮定vをキャンセルするとは、入力vを待つ関数を作ることで、これがλ抽象です。λv.v は恒等関数idですから、「証明A→Aの正体は恒等関数だった」わけです。次に→除去。A→Bの証明hにAの証明fを渡すと、hf という B の証明になります。これは関数に引数を渡す適用(application)です。この二つの注釈規則だけで、今学期書いてきた→の証明はすべて一行の式になります。

種明かし:これはλ計算だった

ここで種明かしです。いまみなさんが「発明」した記法は、アロンゾ・チャーチが1930年代に作ったλ計算そのものです。λ計算は証明論とは独立に、「計算とは何か」への一つの答えとして生まれました(チューリング機械と同値です)。論理の側(ゲンツェン1934の自然演繹)と計算の側(チャーチのλ計算)が、互いを知らずに同じものを作っていた——これがカリー・ハワード対応の驚きです。

計算の一歩はβ変換です。関数のいちばん基本的な操作は、入力を本体に代入することでした。λ項でも同じで、(λx.M)N →β M[x:=N] と書きます。左辺の (λx.M)N の形をβ基(β-redex)と呼びます。計算とは、λ項の中のβ基を見つけて書き換えていくことで、もうβ基がない項が値(正規形)です。第3回で 2+2 を eval して + が消えていったのと同じ発想です。

カリー・ハワードの辞書

こうして対応表(辞書)ができます。命題は型、証明は項(プログラム)、仮定は変数、→導入はλ抽象、→除去は適用、カノニカルな証明は値(正規形)。そして今日の目玉は下二行です。''遠回りはβ基''、''正規化はβ簡約=プログラムの実行''。なぜ辞書が成り立つかというと、命題をその証明の集まり=データ型と同一視するからです(propositions as types)。第3回で作った自然数もどき(Z, Succ(Z), …)が、実はデータ型だったのと同じ見方です。

宿題・問1の A→((A→B)→B) で確かめました。遠回りのある証明に項を注釈すると、遠回りの箇所がちょうどβ基になっています。そしてβ簡約を実行すると、余計なβ基が消えて短い項になります。「カット&ペーストとは、代入のことだった」というわけです。

証明は走る。そして止まる

正規化定理を計算の言葉で言うと、型付け可能なλ項はすべて有限ステップで正規形に到達する、となります。つまり「このプログラムは必ず止まる」という停止性の保証です。証明の正規化は、プログラムの実行だったのです。

では、止まらないものはないのでしょうか。あります。Ω=(λx.xx)(λx.xx) は、一ステップ簡約しても元に戻る永久ループです。ところがΩには単純型がつきません。xが関数であると同時にその引数でもなければならず、型として矛盾するからです。教訓は「型(=命題)が停止を守っている」。停止性は非自明で面倒で、項が有限だから止まるのではなく、減少する測度を見つけるのが本当の仕事でした(第9回のヒドラと同じ構図です)。

怪物図鑑と、いちばん陰湿な怪物ρ

宿題・問2の「壊れた結合子」を、三層診断で図鑑にしました。打ち出の小槌(前提なしで何でも作る)とtonkは局所(反転原理)で捕まります。古典論理は排中律を前提なしで鋳造するので局所と大域が死に、中間だけ生き残ります。逆張りknotは三層すべて通ってしまいますが、遠回りが二通りに潰せて答えが一意でない(合流性の破れ)という欠陥を持ちます。そして怪物ρは、ρ ⟺ (ρ→⊥) というカリー文で、カリーのパラドックスの結合子版です。導入と除去は釣り合って見えるので局所診断を通り抜けますが、潰した遠回りが自分自身を再生産して簡約が止まりません。ρは中間(停止性)で捕まる怪物で、その「証明」の正体は、まさにΩのような止まらないプログラムです。

ダメットの回収と意味の有限主義

哲学的な回収をします。ダメットが「真正のハーモニー」と呼んだ正規化可能性は、保存拡大性や反転原理とは性格が違い、言語行為論の枠内の概念ではなく、計算モデルの性質として捉え直す必要があります。カリー・ハワード対応がその翻訳装置です。なぜ「止まる」ことを要求するのか——ここで意味の有限主義に触れました。人間は有限な生き物です。有限性は二枚あり、証明が有限の対象であること(構文からタダで手に入る)と、それを走らせた過程が有限であること(正規化定理が要る)です。有限な存在者に意味が現れるためには後者こそが必要で、止まって値を返す計算(全域的な計算)だけが、証明の資格を持つのです。

ふたたびLLMへ

「証明=プログラム」なら、根拠のある主張とは実行可能なプログラムを添えた主張です。では根拠のない主張(ハルシネーション)は、計算の言葉で何にあたるのか。Ωのような型のつかない項なのか、そもそも項のない主張なのか。この問いの答えは、最終回(7/21)に回します。

付録では、学生が混同しがちなカリーのパラドックスと「嘘つき」の関係を整理しました。嘘つき文 λ ⟺ ¬λ は、¬λ を λ→⊥ と書けば λ ⟺ (λ→⊥) となり、カリー文の C=⊥ の場合です。つまり嘘つきはカリーの特殊ケースです。そして犯人はどちらも縮約(contraction)=自己言及の仮定を二回使うことで、項でいえばΩの xx がそれです。縮約があれば両方とも自明化しますが、縮約を落としたアフィン論理(第8・9回)では xx が作れず、Ωも組めず、どちらも矛盾を起こしません。第8・9回で縮約を落とすと正規化が戻ったのは偶然ではなく、縮約こそが中間層(停止性)を壊す張本人だったのです。

今回のキーワード

カリー・ハワード対応、命題は型・証明はプログラム、λ計算、チャーチ、λ抽象、適用、β変換、β簡約、β基、正規形、正規化定理、型付きλ計算、停止性、propositions as types、データ型、Ω、型が停止を守る、怪物図鑑、打ち出の小槌、tonk、古典論理、逆張りknot、怪物ρ、カリー文、カリーのパラドックス、不動点コンビネータ、意味の有限主義、全域的な計算、縮約(contraction)、アフィン論理、嘘つきのパラドックス

宿題

当日の演習問題です。

''問1'':A→B→A の証明を描き、各行に項を注釈せよ(弱化の匂いがする例。答えは λv.λw.v)。

''問2'':(λx.M)N の形のλ項を一つ自作し、対応する遠回り証明を証明図で描け。β簡約と証明図の還元が対応することを確認せよ。

''エクストラ問(任意・提出歓迎)'':怪物ρの規則で⊥を導く証明を描き、今日の注釈法でλ項を付けてみよ。得られた項をβ簡約すると何が起きるか。ヒント1:ρとρ→⊥は同一視してよい。ヒント2:今日のあるスライドに、答えの姿がすでに出ている。

(解答にかかった時間も書いてください。)

提出方法・期限はKULMSの指示に従ってください。

      • -

[2026前期火5] 科学哲学科学史(演習) 担当:矢田部俊介(西日本旅客鉄道株式会社)

前期授業第11回(6/30)

第10回では、tonkを作って壊し、「良い定義とは調和した規則のことだ」というところまで来ました。今回(第11回)は、その「調和(ハーモニー)」を、ぼんやりした標語ではなく数学的な条件として展開します。鍵になるのは、調和は一つの現象ではなく、ミクロ・中間・大域という三つのレベルの連鎖だ、という見方です。

三層とは、ミクロ(結合子1個を見る=反転原理)、中間(証明全体を見る=正規化)、大域(言語全体を見る=保存拡大)の三つです。今回はこの三層がどう繋がるか、そしてどこで切れるかを追いました。連鎖は「反転原理(ミクロ)⇒ 正規化(中間)⇒ 保存拡大(大域)」で、tonkは一番下のリンクで切れるので、上の二層もろとも自滅します。

さらに今回は一歩踏み込んで、「三つのハーモニーは、いつも揃って成り立つのか?」という問いを立てました。答えは「いいえ」です。古典論理やCookの体系のように、三層が一致しない例があります。次回(第12回)は、正規化のもう一つの顔として、カット除去と推件計算へ進む予定です。

授業日時

6月30日(火)16:45〜18:15
文学部第4講義室

授業内容

  • 前回の回収:tonkを壊した「正体」を三層モデルとして定式化する
  • 大域のハーモニー=保存拡大性(Belnap 1962)の定義
  • 保存拡大性の落とし穴:正しいが「非操作的」/言語相対性
  • ミクロのハーモニー=反転原理:ローレンツェンの「透明な窓」と許容可能性
  • プラヴィッツの読み替え(1965):除去は導入を「既に含んでいる」
  • ∧のカット&ペースト:1手で「戻せる」=「消せる」(還元前と還元後の証明図)
  • 中間のハーモニー=正規化(真正のハーモニー)が三層を架橋する橋
  • 連鎖まとめ:反転原理 ⇒ 正規化 ⇒ 保存拡大、tonkは最下層で折れる
  • ダメットのハーモニー(1973a)と思想史(Lorenzen→Prawitz→Dummett)
  • 意味の分子論:全体論と原子論の中間
  • 三層は一致するとは限らない①:古典論理(正規化は成立、反転原理・保存拡大は破れる)
  • 三層は一致するとは限らない②:早見表と散布図(古典論理とCookは鏡像)
  • 発展:tonkは本当に死んだか?(Cook 2005)
  • ふたたびLLMへ:ハルシネーションの三層診断/まとめ/演習

speakerdeck.com

解説

「良い規則」とは何か——三層モデルへ

前回(第10回)は、tonkを作って壊し、「良い定義とは調和した規則のことだ」というところまで来ました。今回はその「調和(ハーモニー)」を、数学的な条件として展開します。大事なのは、調和は一つの現象ではなく、ミクロ・中間・大域という三つのレベルの連鎖だ、という見方です。ミクロは結合子1個を見る反転原理、中間は証明全体を見る正規化、大域は言語全体を見る保存拡大です。今日はこの三層がどう繋がり、そしてどこで切れるのかを追いました。

大域のハーモニー:保存拡大性とその落とし穴

まず一番大きなレベル、大域から始めます。ブランダムの「論理は内容を足さない」という要求を数学的に書くと、保存拡大性(conservative extension)になります。体系Sに新しい結合子∘の導入・除去規則を足して S′ にしたとき、∘を含まない古い論理式φについて「S′でφが証明できる ⟺ Sでφが証明できる」が成り立つ、というのが保存拡大の定義です。つまり∘を足しても、∘を含まない命題の証明力は増えない。これはベルナップ(Belnap, 1962)がtonkへの応答として定式化したものです。∧・∨・→は保存拡大を満たし、tonkは満たしません。

ところがこの大域の基準には落とし穴があります。正しいのですが、''非操作的''なのです。「矛盾に陥らないよう何かをすればよい」と言われても、言語全体(可算無限個の命題)について「すべてのφで同値」を直接確かめるのは現実的ではありません。大域要求は目標を与えますが、行動規範(手順)を与えてくれないのです。さらにベルナップが強調したように、何が論理結合子かは''言語相対的''で、同じ規則でも足すベースの体系が違えば結果が変わりえます。

ミクロのハーモニー:反転原理と「透明な窓」

そこで、結合子1個ごとに・一目でチェックできる操作的な基準が欲しくなります。それがミクロのレベルの反転原理です。出発点はローレンツェン(Lorenzen, 1950年代)の許容可能性で、「その規則を足しても原子命題の証明可能な集合が大きくならない」という、保存拡大を原子命題に限定した種子のような条件です。ローレンツェンは論理結合子を''透明なガラス窓''になぞらえました(この比喩は本書のものです)。除去規則は透明で、余計なことをしない。A∨B ⊢ C は「Cの導出にはAとBの二つの前提が要る」以上の意味を持たない、というわけです。

これをプラヴィッツ(Prawitz, 1965)が自然演繹の除去規則に焦点を当てて再定式化したのが反転原理です。除去規則は導入規則の「反転」であり、導入の直後に除去すると元に戻ります。プラヴィッツ自身の言葉でいえば、導入してすぐ除去した証明(還元前)は、除去規則を使わない証明(還元後)を''「既に含んでいる」''のです。実際に∧でやってみましょう。AとBからA∧Bを作り(∧導入)、そこからAを取り出す(∧除去)のは遠回りです。でも左のAの証明を切り取って上に貼り直せば、A∧Bを経由せずにAが得られます。除去で取り出したAは、導入の時点で''もとから手元にあった''のです。この切り取り&貼り付けが効くと、結合子を含まない結論からその結合子を消せます。つまりミクロ(反転原理)が大域(保存拡大)を導きます。

中間のハーモニー:正規化という橋

ミクロと大域をつなぐのが、中間レベルの正規化です。どんな証明も遠回りを全て消してカノニカルな証明に書き換えられる、という第8・9回の主役です。ダメットはこれを''真正のハーモニー''(intrinsic harmony)と呼び、もっとも本質的な調和としました。正規化は「ただの中間の一段」ではなく、ミクロの局所的な書き換えを証明全体に行き渡らせ、それによって大域の保存拡大を保証する橋なのです。こうして、反転原理(ミクロ)⇒ 正規化(中間)⇒ 保存拡大(大域)という連鎖ができあがります。tonkはこの連鎖の最初のリンク(反転原理)で切れます。tonk除去で取り出すBは、tonk導入の時点では手元になく、復元できないからです。だから中間も大域も総崩れになり、体系ごと自滅します。

統合:三層は一致するとは限らない

ここで一歩踏み込みました。三つのハーモニーは、いつも揃うのでしょうか。まず分子論の話から。ある命題Aの意味が変わったとき、影響が及ぶのはAを部分論理式として含む命題の意味だけです。これを意味の分子論(molecularism)と呼びます。全体論(クワインの信念の網:一文の変化が言語全体に波及する)と原子論(各文が独立)の中間で、部分論理式原理(カノニカルな証明には結論の部分論理式しか現れない)が効くからこそ、意味は適切なサイズの文脈で確定します。これは正規化が効くからこそ言えることです。

そして反例です。古典論理は、正規化定理もカット除去定理も成立します(ゲンツェン)。ところが排中律 ¬A∨A は前提なしで証明でき、この∨除去は還元できません。だから反転原理も保存拡大も成り立たない(古典は直観主義の保存拡大ではない)。''正規化は成り立つのに反転原理と保存拡大は破れる''のです。逆向きの例もあります。クック(Cook, 2005)は、推論の推移性(カット)を捨てれば、tonkを足しても自滅しない体系を作れることを示しました。tonkを保存拡大として追加できる代わりに、中間の橋(正規化)を失うのです。古典論理とCookはちょうど鏡像で、片方は正規化を保ち保存拡大を失い、もう片方は正規化を捨て保存拡大を得ます。三層は独立に壊れうる——「ハーモニーの間のハーモニー」は、いつでもあるわけではないのです。

ふたたびLLMへ

最後にLLMへ戻ります。LLMは「根拠なく言わない」という大域要求は(あるべきものとして)持っていても、各推論ステップの局所的な保証機構(反転原理に当たるもの)を持ちません。「矛盾しないよう何かすればよい」という非操作的な要求だけでは、実装は守れない。ハルシネーションを、三層のどこが欠けているかという診断の枠組みで捉え直せないか——これが引き続きの問いです。次回(第12回)は、正規化のもう一つの顔として、カット除去と推件計算に進む予定です。

今回のキーワード

保存拡大性(conservative extension)、ベルナップ(Belnap 1962)、非操作的、言語相対性、反転原理(inversion principle)、ローレンツェン(Lorenzen)、許容可能性(admissibility)、透明なガラス窓、プラヴィッツ(Prawitz 1965)、既に含んでいる、カット&ペースト、正規化、真正のハーモニー(intrinsic harmony)、ダメット(Dummett 1973a)、三層モデル、ミクロ/中間/大域、意味の分子論(molecularism)、部分論理式原理、全体論/原子論、古典論理、排中律、ゲンツェン、カット除去、クック(Cook 2005)、推移性、tonk、自滅化、ハルシネーションの三層診断

宿題

当日の演習問題です。

''問1'': ある論理結合子について、導入規則の直後に除去規則を適用した遠回り(detour)を、カット&ペーストで還元せよ(∧ または → で)。

''問2'': tonkに似た「壊れた結合子」を自作し、それが三層(ミクロ=反転原理/中間=正規化/大域=保存拡大)のどこで、なぜ壊れるかを診断せよ。

(解答にかかった時間も書いてください。)

提出方法・期限はKULMSの指示に従ってください。

      • -

[2026前期火5] 科学哲学科学史(演習) 担当:矢田部俊介(西日本旅客鉄道株式会社)

前期授業第10回(6/23)

第8回・第9回では証明の正規化(detour=遠回りを有限回の書き換えで消し、正規形にすること)を学びました。今回(第10回)は、その重労働が「何のためだったのか」を哲学的に回収する回です。第1回で投げたまま保留していた問い「意味とは何か」に立ち返り、意味の理論を1.0(対応説・真理重視型)と2.0(使用説・推論規則重視型)として整理し直しました。そのうえで2.0の核心を「良い定義とは何か」として展開し、素朴な2.0の危機であるPriorのTonkを提示して終わります。

今回の背骨は次の通りです。意味には二つの道がある(1.0は世界記述の理論で推論は二次的、2.0は使用説)→ 論理結合子の意味は導入規則と除去規則で定まる → ただし良い定義とは「単なる略記」であって現実について言えることを増やしてはならない(保存拡大)→ 悪い定義は結論を密輸する(アンセルム・ボッシュ)→ その論理結合子版がTonk → 体系が崩壊する → だから「調和」が要る(ゲンツェン)→ その調和は第8・9回の正規化で測れた、という伏線回収です。本格的な定式化は次回(第11回)に回します。

次回(第11回)は、今回名前だけ出した「調和」を数学的な条件として展開します。反転原理・正規化・保存拡大という三つのレベルの関係が主題です。

授業日時

6月23日(火)16:45〜18:15
文学部第4講義室

授業内容

  • 導入:正規化は何のためだったのか——第1回の問い「意味とは何か」への回帰
  • LLMのハルシネーションを「意味」の問題として捉え直す
  • 意味の理論1.0=対応説(真理条件)と、その限界(推論の良し悪し・照合すべき外界がない場合)
  • 1.0は「世界記述の理論」であって「推論の理論」ではない(命題が一次的・推論は二次的)
  • ウィトゲンシュタイン『哲学探究』第2節の言語ゲーム(棟梁と見習い)
  • 意味の理論2.0=使用説:「語の意味とは、言語におけるその使われ方である」(探究43節)
  • 論理学版の使用説=証明論的意味論/推論主義(Dummett・Prawitz・Read)
  • ブランダム:論理は推論を「明示化」する(doing → saying)
  • 良い定義=単なる略記、グローバルな要求としての保存拡大
  • 悪い定義①:アンセルムの神の存在証明(結論の密輸)
  • 悪い定義②:ボッシュ(ダメット)——導入と除去が釣り合わない
  • 論理結合子版の悪い定義=Tonk(Prior, 1960)の導入・除去規則
  • Tonkの破綻:任意のAから任意のBが導け、体系が崩壊する
  • 危機の診断=調和(harmony):除去で取り出せるのは導入で入れたものだけ
  • ゲンツェン:導入規則は定義、除去規則はその帰結
  • 伏線回収:調和は第8・9回の正規化で測れる(Tonkは正規化できない)
  • 調和の三つのレベル(反転原理・正規化・保存拡大)——名前と位置づけのみ
  • まとめ:ふたたびLLMへ/演習・次回予告

speakerdeck.com


解説

正規化は何のためだったのか——意味の問いへ戻る

第8回・第9回では、どんな証明も遠回り(detour)を有限回の書き換えで消して正規形にできる、という正規化を苦労して証明しました。今回はまず、その重労働が何のためだったのかを問い直すところから始めました。結論を先取りすれば、正規化は「ある哲学的な問いに答えるための準備」だったのです。その問いとは、第1回で投げたまま保留していた「意味とは何か」です。第1回では、LLMが存在しない論文をもっともらしく引用し、事実と異なることを自信ありげに述べる(ハルシネーション)現象を見ました。これは「嘘」ではありません。嘘をつく意図がそもそもないからです。では、LLM(あるいは私たち)にとって、文の「意味」とは何なのでしょうか。意味を説明する道は、大きく二つあります。

意味の理論1.0=対応説とその限界

意味の理論1.0は、文の意味をその文が真となる条件(真理条件)だと考えます。「雪は白い」の意味は、雪が白いという事実に対応していることです。この立場では、ハルシネーションは外界との対応の失敗であり、診断は文を事実のデータベースと照合することになります。しかし1.0では捉えきれないことがあります。一つは推論そのものの良し悪しです。「雪は白い、ゆえに草は緑である」は、結論はたまたま正しくても推論はおかしいのですが、外界照合だけではこのおかしさを捉えられません。もう一つは、照合すべき外界がない場合です。数学の命題や「もし〜だったら」という反実仮想は、いったい何と照合すればよいのでしょうか。

ここで大事なのは、1.0の目的はそもそも「世界を記述すること」にあるという点です。1.0にとって論理的な推論とは、世界の記述状態(どのモデル)によらず真を保つ推論のこと(タルスキの「すべてのモデルで真」)です。つまり1.0では、命題(真理の担い手)が一次的な基礎概念であり、推論はそこから派生する二次的な概念にすぎません。これは第2回で見た、アリストテレスにおいて「形式」が必然性概念から導かれる二次的概念だった構造と同じです。しかし、論理学で本当に問いたいのは推論そのものではないでしょうか。推論の生成のメカニズム(導入規則と除去規則)や、推論の同値関係や変形(正規化)こそ知りたいのです。そこで、推論を一次的に扱う理論=2.0が必要になります。

意味の理論2.0=使用説:meaning is use

2.0の発想は、後期ウィトゲンシュタイン『哲学探究』にさかのぼります。第2節の言語ゲームでは、棟梁Aと見習いBが登場します。Aが「ブロック」「ピラー」「プレート」「ビーム」と叫ぶと、Bは対応する石材を運びます。この原始的な言語では、語の意味は辞書の定義ではなく、このやりとりのなかでの使われ方に尽きています。これが「意味とは使用である」という発想の出発点です。43節の有名な定式化は「語の意味とは、言語におけるその使われ方である」というものでした。

論理学版の使用説では、論理結合子の「使用」とは数学の証明のなかでの使われ方であり、それは導入規則(どんな根拠でその結合子を使ってよいか)と除去規則(その結合子から何を取り出してよいか)で定まります。この立場を証明論的意味論(proof-theoretic semantics)あるいは推論主義(inferentialism)と呼びます。担い手はDummett・Prawitz・Readです。さらにブランダムは、論理的語彙の役割を「明示化(making it explicit)」として捉えました。推論のなかに暗黙に含まれている各語の役割を、主張の形で明示するのが論理の仕事だ、という見方です。たとえば条件法 A→B は、「AからBを推してよい」という推論のふるまい(doing)を、「A→B」という主張(saying)に変えます。だから論理は内容を「足さない」——すでに行っている推論を明示するだけなのです。

良い定義=略記、悪い定義=密輸

論理結合子を導入規則・除去規則で定めることは、結局その結合子を「定義」することです。では良い定義とは何でしょうか。良い定義とは「単なる略記」です。既知の語を使って新しい語の使い方を定めるだけのもので、導入も除去もスムーズにできます。そしてグローバルな要求として、定義したからといって現実について言えることが増えてはいけません。これが保存拡大(conservative extension)です。定義は言葉だけに関わるべきで、いつのまにか世界について何かを主張してはなりません。

悪い定義は、こっそり結論を密輸します。例の一つはアンセルムの神の存在証明です。神を「肯定的な性質を全て持つもの」と定義し、「存在する」も肯定的な性質だとすれば、定義から「神は存在する」が出てしまいます。言葉の定義のはずが、いつのまにか現実について何かを言ってしまっているのです。もう一つはダメットの挙げる「ボッシュ」です。大戦期、英国人はドイツ人を「ボッシュ」と呼び、言外に「野蛮人」というニュアンスを込めました。導入規則は「xはドイツ人 ⊢ xはボッシュ」、除去規則は「xはボッシュ ⊢ xは野蛮人」です。合成すると「ドイツ人 → ボッシュ → 野蛮人」となり、導入でこっそり入れた「野蛮人」が除去で取り出されてしまいます。元の「ドイツ人」にはなかった含意が出てくる——これは導入と除去が釣り合っていない、つまり保存拡大の破れであり、悪い定義です。

Tonkの破綻と、調和という診断

この自然言語のボッシュと同じことを論理結合子でやったらどうなるか。それがPrior(1960)「The Runabout Inference-Ticket」の出した新しい結合子 tonk です。導入規則は ∨ の導入に似せて「A から A tonk B を導いてよい」、除去規則は ∧ の除去に似せて「A tonk B から B を取り出してよい」とします。この二つを合成すると、A から A tonk B を導入し、そこから B を除去できます。つまり任意のAから任意のBが導けてしまいます。Aが一つでも証明できれば(たとえば A→A)、あとは何でも証明できてしまい、体系は崩壊します。「導入規則と除去規則を勝手に置けば意味が決まる」という素朴な使用説は、このままでは破綻するのです。

なぜtonkはダメなのか。除去で取り出すBが、導入で入れたAと無関係だからです。良い結合子なら、除去で取り出せるのは導入で入れたものだけであるべきです。この導入と除去の釣り合いを調和(harmony)と呼びます。ではなぜ釣り合っている「はず」なのか。その原理的根拠は、自然演繹を作ったゲンツェン(1934)にさかのぼります。ゲンツェンの考えでは、導入規則はその論理結合子の「定義」とみなせ、除去規則は結局その定義からの帰結にすぎません。だとすれば、除去は定義(=導入)で入れた以上のものを取り出せない——導入と除去には釣り合い(調和)があるはずなのです。

伏線回収:調和は正規化で測れる

ゲンツェンは「釣り合うはず」と言いました。では、その「はず」をどう確かめればよいのでしょうか。それがまさに第8・9回でやった正規化です。導入の直後に除去するという遠回り(detour)が必ず書き換えで消せる——これは、除去が導入の裏返しになっていることの証拠であり、調和の一つの測り方です。∧・∨・→・¬ は正規化できました。しかしtonkは正規化できません。遠回りを消す書き換えが存在しないのです。正規化という重労働は、2.0をtonkから救うための技術的な答えだったのです。

なお調和は、実は一つの概念ではなく複数のレベルがあります。ローカル(結合子1個のレベル)の反転原理、中間(証明全体のレベル)の正規化、グローバル(言語全体のレベル)の保存拡大の三つです。今日触れたのは中間の正規化(ダメットの言う「真正な調和」)でした。三者の関係は次回(第11回)で扱います。こうして使用説(2.0)は、「調和した規則に限る」という条件を付けて、はじめて本物の立場になります。最後にふたたびLLMへ。ハルシネーションを、「外界照合の失敗(1.0)」としてだけでなく、「推論規則の不調和/証明の遠回りが解けないこと(2.0)」として診断できないか——これが第11回以降に持ち越す問いです。

今回のキーワード

意味の理論1.0(対応説・真理条件・モデル的意味論)、意味の理論2.0(使用説・証明論的意味論・推論主義/inferentialism)、世界記述の理論、ウィトゲンシュタイン『哲学探究』、言語ゲーム、meaning is use、Dummett、Prawitz、Read、Brandom(明示化/making it explicit)、doing と saying、良い定義=略記、保存拡大(conservative extension)、密輸、アンセルムの神の存在証明、ボッシュ(Boche)、Tonk(Prior, 1960)、体系の崩壊、調和(harmony)、ゲンツェン(1934)、導入規則は定義・除去規則は帰結、反転原理、正規化、真正な調和

宿題

当日口頭で指定した演習問題を提出してください。

''問1'': tonkの導入規則と除去規則を合成し、任意のAから任意のBが導けることを証明木で確かめよ。

''問2'': ボッシュの導入規則「xはドイツ人 ⊢ xはボッシュ」と除去規則「xはボッシュ ⊢ xは野蛮人」から「ドイツ人 ⊢ 野蛮人」が出ることを図示し、どこで釣り合い(調和)が破れているか説明せよ。

''問3'': ∧ の導入直後に除去する遠回り(detour)が、なぜtonkと違って消せるのか説明せよ。

(解答にかかった時間も書いてください。)

提出方法・期限はKULMSの指示に従ってください。

      • -

[2026前期火5] 科学哲学科学史(演習) 担当:矢田部俊介(西日本旅客鉄道株式会社)

前期授業第9回(6/16)

前回(第8回)は正規化定理の証明戦略を立てたが、最終盤(18:13)で「止まる」ことの説明が不完全なまま時間切れとなった。今回(第9回)はその続きとして、なぜ「止まる」証明が難しいかを丁寧に振り返り、「峰の高さ(degree)の多重集合」を計測器に選ぶことの正当性をヒドラゲームという道具を通じて明らかにした。授業の前半は前回の残課題(計測器選び)、後半はヒドラゲームの定式化とスコアベクタによる停止性証明が中心だった。

目次:

  • Section 0:前回のおさらい(detour除去・見敵必殺)
  • 前回で足りなかった説明:「止まる」はなぜ難しいか
  • 第1幕:還元すると何が起きるか(§1.1 具体例)
  • 第2幕:継ぎ目2か所——還元後に新detourが生まれる場所
  • 第2幕:正しい計測器——峰の高さ(degree)
  • 第3幕:抽象化——ヒドラゲームへの翻訳(対応表)
  • 第4幕:ヒドラゲームのルールとプレイ実演
  • 第5幕:スコアベクタと辞書式順序——停止性の証明
  • 縮約がある場合・正規化定理の仲間たち・ジラールの洞察
  • まとめ・演習・次回予告

授業の骨子は「正しい計測器の発見」です。detour数・証明の長さ・詰まりの数という3つの候補がそれぞれ停止の証明に使えない理由を確認し、「峰の高さだけを多重集合にまとめたもの」が正しい計測器であることをヒドラゲームを通じて説明しました。この計測器はヒドラゲームのスコアベクタとして定式化され、辞書式順序で毎手厳密に減少する——だから有限手で必ず終わる、という論法です。

次回(第10回・6/23)は推論主義(inferentialism)とTonkの問題に進みます。正規化定理が「良い論理規則の条件」とどう結びつくかが主題です。

授業日時

6月16日(火)16:45〜18:15
文学部第4講義室

授業内容

  • 前回のおさらい(正規化定理の主張・見敵必殺・→と∧のdetour除去)
  • 前回の宿題(問1・問2)解答配布
  • 前回で足りなかった説明:「止まる」がなぜ難しいか(detour数・長さ・詰まりの3候補の検討)
  • 第1幕:§1.1の具体例で還元を実行——証明が縦に長くなる現象
  • 第2幕:継ぎ目2か所——→還元後に上側・下側の2か所に新detourが生まれる
  • 第2幕:峰の「高さ(degree)」が正しい計測器である理由
  • 第3幕:抽象化——「峰の度数の多重集合」をヒドラゲームに翻訳(対応表)
  • 第4幕:ヒドラゲームのルール(頭を刈ると高さが低い頭が最大2本増える)
  • 第4幕:プレイ実演——{3}スタート最悪ケース(7手で終了)
  • ヒドラ実況①②③:視覚的な進行の確認
  • 第5幕:スコアベクタ(高さdの頭の本数cをならべたベクタ)の定義
  • 第5幕:補題——1手ごとにスコアベクタが辞書式に厳密減少する
  • 第5幕:補題——辞書式順序には無限下降列がない(二重帰納法)
  • 第5幕:定理——アフィン版ヒドラゲームは必ず有限手で終わる
  • 証明論への持ち帰り:正規化定理の停止性証明の完成
  • 縮約がある場合の困難(本家Kirby-Paris問題・超限順序数の必要性)
  • 正規化定理の仲間たち(弱・強正規化、カット除去定理、部分論理式原理)——前回再掲
  • ジラールの洞察(前回再掲)
  • 演習問題(問A・問B・問C、当日指定)
  • 次回予告:第10回(6/23)推論主義とTonk

https://speakerdeck.com/player/PRESENTATION_ID speakerdeck.com

解説

前回の残課題——「止まる」はなぜ難しいか

第8回授業の終盤で、正規化の証明の核心として「1回の還元でdetourが必ず減る」ことを示す必要があると確認したが、その説明が不完全なままになっていた。今回はまずその原因を正面から確認した。

計測器の候補として次の3つが考えられる。

(1) ''detour個数'':1回の還元でdetour個数が増えることがある。→還元を実行すると、元の峰(A→B)は消えるが、代わりに π₁[π₂/u]という証明が合成され、その中に新たな継ぎ目(上側・下側)が現れてdetourになりうる。計測器として不適切。

(2) ''証明の長さ(縦)'':→還元では π₂ を π₁ に代入するため証明が縦に伸びる。前回授業記録(17:51)でこの現象を録音で確認した。長さは増えるので計測器にならない。

(3) ''詰まり(V字)の数'':実は「詰まりは減る」という側面があるが、その一方で証明の長さは増える。この2つは''逆方向に動く''ため、どちらか一方だけでは「全体として終わりに近づいている」と言えない。

    • -

第1幕:還元すると何が起きるか——§1.1 の具体例

具体的な証明図(§1.1)を使い、→還元を実際に実行した。峰の論理式は (A∧B)→A(高さ = degree 2)。

還元前:π₁(仮定[u: A∧B]を使い A を導く)と π₂(A∧B を証明する)が横に並び、→E の横棒がまたいで B を導く。

還元後:π₂ を π₁ の仮定[u: A∧B]に代入した証明 π₁[π₂/u] が縦に続く。A→B という峰は消えるが、証明は縦に延び、新たな峰(∧-detour)が生まれる可能性がある。

この例で「証明の長さは増える」「detour数は変わりうる」ことが具体的に確認できた。

    • -

第2幕:継ぎ目2か所——どこに新detourが生まれるか

→還元 π₁[π₂/u] を詳しく見ると、新しいdetourが生まれる可能性がある箇所は''ちょうど2か所''に限定される(アフィン論理の場合)。

''上側継ぎ目'':π₂ の底(I-規則)と π₁ 内で u の直上にある E-規則が接続される場所。π₂ の結論(A)が π₁ の I-規則の下に来るため、I→E の「V字」ができる可能性がある。

''下側継ぎ目'':π₁[π₂/u] の底(→I)と外側の文脈の E-規則が接続される場所。π₁ が A→B の証明だったなら、→I が下に来て外側の →E と接触する。

どちらの継ぎ目で生まれる新detourも、元の峰(A→B、degree d)より''低い''論理式が峰になる(degree < d)。これが停止性の鍵だ。

''正しい計測器の発見'':個々のdetourの個数ではなく、「峰の高さ(degree)の多重集合」を比較すれば良い。元の峰(degree d)が消え、生まれる新峰は全て degree < d ——つまり多重集合は「高い要素が消えて低い要素が増える」方向に変化する。

    • -

第3幕:抽象化——ヒドラゲームへの翻訳

峰の高さの多重集合という概念を、より直感的なゲームとして定式化する。これが''ヒドラゲーム''である。

対応表をまとめると次のようになる:

証明論 ヒドラゲーム
-------- -------------
証明図 π ヒドラ(怪獣)
detour 1個 頭 1本
峰の degree 頭の高さ(1, 2, 3, ...)
還元 1回 頭を 1本刈る
新しい峰(高さ < d) 高さ < d の頭が高々2本
正規形(detourゼロ) 頭が全部なくなった
正規化の停止性 ゲームは必ず終わる

ヒドラゲームを使うと、論理式の構造という複雑な情報を捨て、「高さだけ」に集中できる。このような抽象化が数学の力だ。

アフィン論理(縮約なし)では、仮定ラベル u がちょうど1か所にしか現れないため、π₂ の代入は1か所のみ。したがって新しく生まれる峰の候補は継ぎ目2か所だけで、どちらも degree < d。これが「高さ < d の頭が''高々2本''」という制約の由来だ。

    • -

第4幕:ヒドラゲームのルールとプレイ実演

アフィン版ヒドラゲームのルール(§4 の形式化):

1. ヒドラは自然数の有限多重集合 H(各要素が「頭の高さ」)
2. 1手ごとに任意の要素 d ∈ H を選んで取り除く(「刈る」)
3. 刈った d に対し、d より低い高さの要素を最大2本まで追加できる
4. H = ∅ になったらゲーム終了(ヘラクレスの勝ち)

§4.2 の実演:{3}(高さ3の頭1本)から最悪ケースをたどる。

  • 手1:高さ3を刈る → {2, 2}(辞書式ベクタ (1,0,0) → (0,2,0) に減少)
  • 手2:高さ2を1本刈る → {2, 1, 1}((0,2,0) → (0,1,2) に減少)
  • 手3:高さ2を刈る → {1,1,1,1}((0,1,2) → (0,0,4) に減少)
  • 手4〜7:高さ1を1本ずつ刈る(4本→3→2→1→0)

計7手で終了。頭の本数は一度4本まで増えるが、ゲームは有限手で必ず終わる。

    • -

第5幕:スコアベクタと辞書式順序——停止性の証明

''スコアベクタ''の定義:初期状態の最大高さを D とする。ヒドラの現在状態を

(c_D, c_{D-1}, ..., c_2, c_1)

というベクタで表す。ここで c_d は高さ d の頭の本数。

''補題(辞書式減少)'':高さ d の頭を1本刈ると、c_d が1減り、c_i(i < d)がいくつか増えうる。辞書式順序では左の桁が優先されるため、c_d の位置(左)が1減れば、右の桁がどれだけ増えてもベクタ全体は辞書式に小さくなる。''→ スコアベクタは毎手厳密に減少する。''

''補題(辞書式整礎性)'':(N^D, 辞書式順序)には無限下降列は存在しない。証明は D についての帰納法:D=1 は自然数の最小原理(N に無限下降列なし)。D → D+1 のステップでは、無限下降列があると仮定すると第1成分が有限回で安定し、その後は第2〜D+1成分が N^D で辞書式無限下降することになるが、これは帰納仮定に矛盾する。□

''定理(アフィン版ヒドラゲームの停止性)'':どのような手順でヒドラを刈っても、アフィン版ヒドラゲームは有限手で必ず終わる。

''証明論への持ち帰り'':証明図の正規化はヒドラゲームの停止性に帰着した。スコアベクタが毎手(=毎回の還元で)辞書式に減少し、辞書式順序には無限下降列がないから、正規化は有限回の還元で完了する。アフィン論理の正規化定理が''完全に証明された''。

''縮約がある場合'':最小命題論理(縮約規則あり)では、仮定ラベル u が複数箇所に現れるため π₂ を k 箇所にコピーする必要がある。コピーの中に新たなdetourが増えうるため「高々2本」という制約が破れる。本家 Kirby-Paris ヒドラ(1982)では「n 本増える」という設定になり、停止性の証明には ω^ω 以上の超限順序数が必要になる。これは''ペアノ算術では証明できない''(Kirby-Paris 定理)という衝撃的な結果につながる(付録A3参照)。

    • -

正規化定理の仲間たち——前回からの再掲

''弱正規化と強正規化'':今回証明したのは弱正規化(少なくとも1つの還元列が正規形に到達する)に相当する。強正規化(どの順番で還元しても必ず終わる)はより強い主張で、最小命題論理でも成立するがより精密な議論が必要。

''カット除去定理(Hauptsatz)'':推件計算における対応物。自然演繹の detour が推件計算ではカット規則に対応する。

''部分論理式原理'':正規な証明では証明に現れる全ての論理式が結論または仮定の部分論理式になる。正規化定理から自動的に導かれる系。

''ジラールの洞察'':正規化定理は技術的便宜ではなく論理にとって本質的。正規な証明こそが「カノニカルな証明」であり、導入規則と除去規則の「調和」が正規化可能性と等価になる。Tonk(Prior, 1960)のような「不調和な」規則が正規化できないのはその帰結である。

今回のキーワード

停止性(termination)、スコアベクタ(score vector)、辞書式順序(lexicographic order)、整礎性(well-foundedness)、ヒドラゲーム(Hydra game)、アフィン版ヒドラ、本家 Kirby-Paris ヒドラ、degree(峰の高さ)、継ぎ目(junction point)、上側継ぎ目・下側継ぎ目、超限順序数(transfinite ordinal)、ω^ω、二重帰納法、弱正規化・強正規化、カット除去定理(Hauptsatz)、部分論理式原理

宿題

当日口頭で指定した演習問題(問A・問B・問C のうち指定したもの)を提出すること。

''問A'': §1.1 とは別の「→還元で新 ∧-detour が生まれる」例を自分で構成し、(a) 還元前のdetourと峰を全て挙げ、(b) →還元を1回実行し、(c) 生まれた新しい峰の論理式と degree を確認せよ。

''問B'': ヒドラ {高さ2の頭2本} = {2, 2} からゲームを始め、各状態のスコアベクタを書き、辞書式に減っていることを確認せよ(最悪ケースと最善ケースの両方を試みよ)。

''問C'': 高さ d の頭1本のアフィン版ヒドラゲームの最悪手数が 2^d − 1 であることを d = 1, 2, 3 で確かめよ(最悪手順を明示すること)。

提出方法・期限はKULMSの指示に従ってください。

前期授業第8回(6/9)

今回は正規化定理の証明を行いました。前回は「正規な証明とは何か」「detourとは何か」という定義と、正規化定理の主張(任意の証明は正規な証明に変換できる)を紹介したが、証明の手順は次回に持ち越しとなっていました。今回はその続きとして、実際に「どうやってdetourを除去するか」「なぜそれが有限回で終わるか」を追います。後半では、この定理がジラールの言葉を借りれば単なる技術的便宜ではなく論理の本質に関わるという話に触れ、次回の論理学の哲学(推論主義・Prior のTonk問題)への橋渡しとします。

目次:

  • Section 0:前回おさらい(証明樹のかたち・V字型・detour)
  • Section 1:アフィン論理で証明する + メタ定理と帰納法 + 見敵必殺戦略
  • Section 2:各結合子のdetour除去(→・∧・∨)
  • Section 3:停止性の証明(アフィン論理版)
  • Section 4:縮約ありの指数的爆発と「隠れた回り道」
  • Section 5:正規化定理の仲間たち(弱・強正規化、カット除去定理、部分論理式原理)
  • ジラールの洞察と次回への橋渡し
  • 演習問題

授業日時

6月9日(火)16:45〜18:15
文学部第4講義室

授業内容

  • 前回のおさらい:証明樹のV字型(上が除去規則・下が導入規則)、detourの定義、正規化定理の主張
  • アフィン論理(縮約なし)での正規化定理の証明
  • 正規化定理はメタ定理であることの確認(detour数への帰納法)
  • 基本戦略:見敵必殺(Search and Destroy)
  • →・∧・∨それぞれのdetour除去操作
  • 停止性の証明(アフィン論理では還元でdetour数が単調に減る)
  • 縮約規則ありの場合の困難(証明の複製・指数的爆発)
  • 「隠れた回り道」問題(∨E 規則固有の問題)
  • 弱正規化と強正規化の違い(前回Q&A Q3の回答)
  • カット除去定理(Hauptsatz)との対応
  • 部分論理式原理との関係
  • ジラールの洞察:正規化定理と論理結合子の「意味」
  • 演習問題:問1〜4(必修)+チャレンジ(∨のdetour除去)

speakerdeck.com

解説

前回からの流れ:正規化定理とは何か**

前回(第7回)は自然演繹の証明がある特定の「きれいな形」を持つことができるという話をしました。証明図には''detour''(回り道)と呼ばれる冗長な部分があり、これは「導入規則で命題を組み立てた直後に、同じ結合子の除去規則でそれを壊す」パターンです。たとえば A と B から ∧I で A∧B を作り、すぐに ∧E_L で A だけ取り出すのはdetourの典型で、最初から A を使えばよいのです。

detourを含まない証明を''正規な証明''と呼びます。正規な証明は「V字型の構造」を持ちます:証明の上半分では除去規則を使って仮定から情報を取り出し、下半分では導入規則を使って結論を組み立てます。前回の第7回で「今日はこの定理の主張のみ」として紹介した正規化定理は次の主張です:

''「最小命題論理の任意の証明は、正規な証明に変換できる。」''

今回はこの定理を実際に証明しました。

アフィン論理での証明:なぜ縮約規則を外すか

証明の出発点として、最小命題論理そのものではなく''アフィン論理''(縮約規則のない体系)を対象に選ぶことを宣言しました。

縮約規則(contraction)とは「同じ前提を複数回使える」というルールです。proof netのY字ノードがこれに対応します。アフィン論理ではこの規則を外し、各前提はちょうど1回しか使えない。

なぜアフィン論理を選ぶか——縮約があると正規化の証明が極めて難しくなるためだ。具体的には、→のdetour除去では「仮定 [u:A] をAの証明で置き換える」という操作を行うが、縮約ありの場合は u が複数箇所に出てくるため、Aの証明を複製しなければならない。この複製の中に新しいdetourが生まれ、「1個消して2個増える」という事態が起きうる。最悪ケースでは証明サイズが指数関数的に膨らむ。アフィン論理なら u は1箇所だけなので複製が不要であり、停止性の議論がシンプルになる。

正規化定理はメタ定理:detour数への帰納法

正規化定理は対象言語(命題A, B, A→B, ...)の定理ではなく、''証明図の構造について語るメタ定理''である。「任意の証明図 π は正規形に変換できる」は、命題論理の命題ではなく、証明図そのものに関する主張だ。

証明の骨格は''detour数に対する帰納法''である。detour数とは証明図に含まれるdetourの個数——たとえば ∧I直後の ∧E が2か所あればdetour数は2。

  • detour数 = 0:すでに正規形(帰納法の基底)
  • detour数 = n+1:1回の還元操作でdetour数を n 以下にする → 帰納法の仮定を適用

アフィン論理では「1回の還元でdetour数が厳密に減る」ことが保証されるため(後述)、この帰納法が完全に機能する。

基本戦略:見敵必殺(Search and Destroy)

detour除去の基本戦略は三段階だ:
1. ''サーチ'':証明図の中をくまなく探し、detour(IノードとEノードの隣接)を見つける
2. ''デストロイ'':見つけたdetourを還元操作で消去する
3. ''繰り返し'':detourが残っていればステップ1に戻る

各結合子について「還元操作」の中身を確認した。

各結合子のdetour除去**

''→の場合'':
→I で A→B を作り、直後に →E で B を取り出す(A→B が「峰」)。
還元後は π_1 中の仮定 [u:A] を π_2(A の証明)で置き換えた証明 π_1[π_2/u] になる。A→B と →I・→E の両ノードが消える。アフィン論理では u が1か所だけなので π_2 の複製は不要。

''∧の場合'':
∧I で A∧B を作り、直後に ∧E_L で A を取り出す(A∧B が「峰」)。
還元後は A の証明 π_1 だけが残る。B の証明 π_2 は「実際には不要だった」ことになり消える(proof net ではBのワイヤがdangling wireになる)。∧E_R の場合は π_2 が残り π_1 が消える。

''∨の場合'':
∨I_L で A∨B を作り、直後に ∨E で場合分けする(A∨B が「峰」)。
∨I_L で「左から来た」という情報が保持されているため、左枝 π_2([u:A] を使う証明)が生き残る。π_2 中の [u:A] を A の証明 π_1 で置き換えた証明になる。右枝 π_3 は消える。∨I_R の場合は右枝が生き残る。

停止性の証明(アフィン論理版)**

アフィン論理版正規化定理の証明の概略:

1. 証明 π に含まれるdetourの総数を n とおく(n は有限:証明図は有限サイズ)
2. アフィン論理では縮約規則がないため、各仮定ラベル u はちょうど1回しか出てこない
3. →の還元で π_1[π_2/u] を作るとき、u が1箇所だけなので π_2 を複製しない
4. したがって1回の還元でdetourの総数が厳密に n-1 以下になる
5. n は有限だから、高々 n 回の還元でdetourがゼロの証明(正規形)に到達する □

縮約ありの場合:指数的爆発と隠れた回り道**

最小命題論理(縮約あり)の場合は上述のように証明の複製が起き、停止性の証明に超限帰納法が必要になる。また証明サイズが 2^n オーダーに膨らみうる。

「隠れた回り道」問題は縮約とは''別の''問題である。∨E 規則は3入力の「大がかりな規則」であり、他の除去規則が ∨E の内外にまたがると、detour が見た目には存在しないにもかかわらず部分論理式原理が破れているケースが生じる。解決策は「順番変更(commuting conversion)」——∨E と他の除去規則の順番を入れ替えて隠れた回り道を顕在化させ、基本戦略で除去する。この問題は自然演繹に固有であり、推件計算では生じない。

正規化定理の仲間たち**

''弱正規化と強正規化'':
今日証明したのは「少なくとも1つの還元列が正規形に到達する(弱正規化)」。強正規化は「どの順番で還元しても必ず正規形に到達する」という強い主張であり、最小命題論理(アフィン論理も含む)でも成立するが証明には精密な議論が必要。これは前回Q&A Q3「スライドの正規化定理がネットで見るものと違う」という疑問への回答でもある。

''カット除去定理(Hauptsatz)'':
推件計算(sequent calculus)での対応物。自然演繹のdetourが推件計算ではカット規則に対応し、「カット規則を使わなくても証明できるものはカットを使っても証明できる」というゲンツェンのカット除去定理(Hauptsatz)が対応する。

''部分論理式原理'':
正規な証明では証明に現れる全ての論理式が結論または仮定の部分論理式になる。今回の証明から自動的に導かれる系である。

ジラールの洞察:正規化定理は論理の本質

Jean-Yves Girard(線形論理の創始者)の観点では、正規化定理は技術的便宜ではなく論理にとって本質的に重要な定理だ。正規な証明こそが論理的推論の「真の姿」——カノニカルな証明——であり、部分論理式原理はその証明が「結論の意味の範囲内で動く」ことを保証する。

ここで重要な観察が生まれる。导入規則は結合子に''意味を与え''、除去規則はその意味を''使う''。detour が除去できること = 導入と除去が「調和している」ということ。逆に言えば、正規化できない規則の組み合わせは「調和していない」——論理結合子として不適格である。

この観察は論理の哲学の核心問題につながる。「論理語の意味は推論規則で決まる」という立場(推論主義・inferentialism)を取るとき、任意の規則が「論理」になれるのか? Arthur Prior(1960)は''Tonk''という接続子を提案し、その導入規則と除去規則を使うと任意の A から任意の B が証明できることを示した——明らかに論理として破綻している。Tonk はまさに正規化できない:Tonk-I の直後の Tonk-E は還元できないdetourである。

今回のキーワード

正規化定理(normalization theorem)、弱正規化(weak normalization)、強正規化(strong normalization)、アフィン論理(affine logic)、縮約規則(contraction rule)、メタ定理(metatheorem)、見敵必殺(Search and Destroy)、還元操作(reduction)、停止性(termination)、カット除去定理(Hauptsatz)、部分論理式原理(subformula property)、カノニカルな証明(canonical proof)、推論主義(inferentialism)、Tonk

宿題

スライドの演習問題(問1〜4・チャレンジ)のうち、授業中に解けなかったものを提出すること。

問1:スライドの問1の証明(∧I直後に∧E_L、∧I直後に∧E_R を含む冗長な証明)を正規化せよ。含まれるdetourを全て挙げること。
問2:スライドの問2の証明((A→B)→(A→B) の非正規な証明)を正規化せよ。
問3:A∧(A→B)→B の正規な証明を逆算法で作れ。
問4:A→A∧A を最小命題論理(縮約規則あり)で証明せよ。
チャレンジ(加点・任意):スライドのチャレンジ問題の証明(∨I_L 直後に ∨E が来ている A→A の証明)を正規化せよ。

提出方法・期限はKULMSの指示に従ってください。