# 対角線論法 ## 定義 対角線論法(diagonal argument)とは、可算な列挙のリストが与えられたとき、そのリストのどの要素とも異なる新たな要素を、リスト自身の対角成分を反転させることで構成し、リストが対象全体を尽くしていないことを示す証明技法である。Cantorの定理(定理7.1.11: 任意の集合Aについて A strict pow(A))の証明が原型で、AからpowAへの任意の関数gに対し Ag := {a ∈ A | a ∉ g(a)} を構成すると、Ag = g(a₀) と仮定した場合 a₀ ∈ g(a₀) iff a₀ ∉ g(a₀) という矛盾が生じ、gが全射でないことが示される。この証明を「NとAを対応づける仮想的な無限正方配列(第n行がAnのビット列)」として視覚化すると、対角成分(n行n列目のビット)をすべて反転させた列Cがどの行Anとも少なくとも1ビット異なることになり、これが「対角線」論法という名前の由来である。本書はこの技法を集合論の文脈(Cantorの定理)だけでなく計算可能性理論の文脈(定理7.2.2: 停止性問題の非認識可能性、関数 f(s) := {t | Ps がtで停止する} と No-halt := {s | s ∉ f(s)} を用いる)にもほぼ同型の構造で転用しており、この転用自体が第7章が7.1節から7.2節へ進む構成上の要点になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 7 Infinite Sets]] ch.7 §7.1.3〜§7.1.4, §7.2) ## 横断的知見 (この concept は本 ingest が初出のため、複数ソースの突き合わせによる横断的知見はまだない。他章・他ソースが対角線論法に触れた際にここへ追記する。) ## 未解決の問い - 対角線論法はCantorの定理・停止性問題以外にも、Gödelの不完全性定理(第7章§7.4で言及されるが証明は示されない)や停止性問題以外の決定不能問題の証明にも使われることが知られている。本書の後続章(数論・計算理論に近い章)でさらなる応用が出てくるか。 - 対角線論法は「リストが与えられれば必ず漏れが作れる」という否定的(不可能性)の証明にもっぱら使われている。この技法が構成的(何かを作る)側の証明に使われる例が本書中にあるか。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 7 Infinite Sets]] - 概念: [[濃度]] —— 対角線論法はCantorの定理(A strict pow(A))の証明技法であり、濃度の無限集合への拡張を支える。 / [[停止性問題]] —— 同じ対角線論法が停止性問題の非認識可能性の証明に転用される。 - 実体: [[Georg Cantor]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 7, §7.1.3〜§7.1.4, §7.2.