1 基本概念
対角線論法は、ある対象の一覧を仮定し、その各項目と少なくとも一箇所で異なる新しい対象を作ることで、最初の一覧が完全ではないと示す証明技法である。数学では集合や関数、論理学では命題や形式的記述に対して用いられ、有限・無限を問わず「全てを並べた」という主張を検証する際に重要な役割を果たす。
1.1 定義
この方法では、候補を縦または横に並べ、対角に当たる成分を手掛かりに別の対象を組み立てる。構成された新対象は、列挙された各要素の少なくとも一つの位置で一致しないため、どの候補とも同一にはならない。
1.2 基本的な考え方
発想の核心は、「一覧の各行に対して、必ずそこから外れるような要素を一つずつ作れる」という点にある。個々の候補を順に照合していくと、作り出された対象はどの行にも完全には一致せず、列挙の抜け落ちが明らかになる。
1.3 反証法との関係
対角線論法は、しばしば反証法と結びついて使われる。まず「完全な列挙がある」と仮定し、その仮定から矛盾を導く形を取るためである。ただし、反証法が推論の枠組みであるのに対し、対角線論法は矛盾を生むための具体的な構成手順に重点がある。
2 歴史
対角線論法の起源は19世紀後半の集合論にさかのぼる。以後、この手法は無限集合の大小比較から、計算理論、数理論理学、数学基礎論へと広がり、現代数学の基礎的な道具の一つになった。
2.1 カントールの対角線論法
ゲオルク・カントールは、実数全体が自然数で番号付けできないことを示すためにこの方法を用いた。彼の議論は、無限集合にも異なる大きさがあるという画期的な見方を定着させた。
2.2 数学基礎論への発展
20世紀に入ると、対角線的な発想は集合論だけでなく、証明論や形式体系の研究にも取り入れられた。特に、ある体系が自分自身についてどこまで語れるか、どこで限界が現れるかを調べる際に有効であることが分かった。
2.3 論理学への応用
論理学では、記述可能な性質の全体や、真偽を判定できる文の集合に対して応用される。ここでは、言語が自らの構造を完全には取り込めないことや、意味論と構文論の間に距離があることを示す場面で重要となる。
3 代表的な応用
対角線論法は、単なる一手法にとどまらず、複数の分野で決定的な結論を与える。実数の大きさの比較、アルゴリズムの限界、形式的理論の不完全性など、異なる主題を一つの共通した発想で貫いている。
3.1 実数の非可算性
実数の集合は、自然数で順に並べ尽くすことができない。仮に小数展開を用いて一覧を作っても、対角成分をずらして新しい小数を作れば、その一覧に含まれない実数が得られる。
3.2 集合の濃度比較
この論法は、二つの集合の要素数の比較にも使われる。ある集合から別の集合への全単射が存在しないことを示すことで、前者の方が大きい、あるいは少なくとも同じではないと結論づけられる。
3.3 計算理論
計算理論では、入力に対して出力を返す手続きの全体を考え、その一覧化が可能かを問う。対角線論法を用いると、全ての手続きを網羅する一般的な仕組みには限界があることが分かる。
3.3.1 停止性問題
停止性問題は、任意のプログラムが与えられた入力で停止するかどうかを一般的に判定できるかという問いである。対角線的な構成により、そうした万能判定手続きがあれば自己矛盾が生じることが示され、一般解は存在しないと結論される。
3.3.2 決定不能性
ある問題について、すべての入力に対し正しく「はい」か「いいえ」を返すアルゴリズムが存在しないとき、その問題は決定不能である。対角線論法は、他の全ての手続きと異なる振る舞いをする対象を作ることで、この種の限界を証明する。
3.4 数学基礎論
数学基礎論では、証明体系や公理系そのものの性質が対象となる。対角線論法は、体系内部で扱える文の範囲や、真理と証明の隔たりを明示する道具として機能する。
3.4.1 ゲーデルの不完全性定理
ゲーデルの不完全性定理は、十分に強く一貫した形式体系には、その体系内では証明も反証もできない真なる命題が存在することを示す。ここで対角線的な自己参照の構成が用いられ、体系の自己完結性に限界があることが明らかになる。
3.4.2 タルスキの真理定義不能性
タルスキは、算術の真理をその言語内で完全に定義することはできないと示した。対角線論法は、「この文は偽である」に類する自己言及を扱う際の矛盾を通じて、真理述語の内部定義が不可能であることを支える。
4 典型的な証明の流れ
対角線論法の証明は、概ね一定の順序で進む。列挙を仮定し、対角部分を見て、新しい対象を作り、元の一覧に収まらないことを確認する、という流れが基本である。
4.1 列挙の仮定
まず、対象の全体が番号付きで並べられていると仮定する。これは証明の出発点であり、あえて強い主張を置くことで、その不可能性を後で示す。
4.2 対角成分の抽出
次に、一覧を表の形に整理し、各行の対角に当たる部分を取り出す。ここが変形の起点となり、既存の候補と必ずずれるように調整する。
4.3 新しい対象の構成
対角成分をもとに、各位置で元の要素とは異なる値を選んで対象を作る。数の置換、記号の反転、真偽の切り替えなど、具体的な操作は分野によって異なる。
4.4 矛盾の導出
作られた対象が一覧のどの項目とも一致しないことを示すと、最初の仮定と衝突する。したがって、完全な列挙の存在は否定される。
4.5 結論の整理
最後に、何が否定され、何が残るかを明確にする。結論は、単に「違うものができた」というだけでなく、対象全体の構造や限界についての一般的な性質としてまとめられる。
5 例題と具体例
対角線論法は抽象的に見えるが、具体例に落とし込むと理解しやすい。数列、集合、形式体系の三つは、考え方の共通性を示す代表的な題材である。
5.1 数列による例
二次元の表に数列を並べ、各列の対角項を参照して新しい数列を作ると、元のどの列とも一致しない列が得られる。これは、順番に並べた候補の外側に新しいものが必ずあることを視覚的に示す。
5.2 集合論による例
自然数全体から実数全体への対応を仮定し、その対応表の各行から小数展開を読むと、対角の数字を変更した実数が構成できる。これにより、実数は自然数で完全には番号付けできないと分かる。
5.3 形式体系による例
ある形式体系の証明を列挙し、それぞれに対応する文を作ると、自分自身の証明可能性に関して特別な性質を持つ文が現れる。これが、体系が自らの限界を内部から完全には解消できないことを示す手掛かりとなる。
6 関連概念
対角線論法は単独で現れるだけでなく、近縁の概念群と結びついて理解される。特に、反対角化や自己言及は、その構造を支える重要な要素である。
6.1 反対角化
反対角化は、列挙された各候補と意図的にずれるよう対象を作る一般的な発想を指す。対角線論法の技術的な中核に近く、構成の向きを変えた言い方として理解できる。
6.2 自己言及
自己言及とは、文や式が自分自身について何かを述べる性質である。対角線的構成では、この性質が矛盾や限界の発見に深く関わる。
6.3 カントールの定理
カントールの定理は、任意の集合よりその冪集合の方が高い濃度を持つことを述べる。対角線論法は、この結論を導く典型的な証明手段として現れる。
6.4 ラッセルのパラドックスとの違い
ラッセルのパラドックスは、集合の定義に内在する自己適用の問題から生じる矛盾である。一方、対角線論法は、列挙の不完全性や定義不能性を示すための体系的な証明法であり、パラドックスそのものとは目的が異なる。
7 論理学上の意義
対角線論法は、論理学において「何が表現でき、何が証明でき、何が理論の外に残るか」を考えるための基本的な枠組みを与える。形式体系を閉じた宇宙とみなしたとき、その内部だけでは尽くせない領域があることを示す点に大きな意義がある。
7.1 表現可能性の限界
ある言語や体系が、すべての対象や性質を一様に表せるとは限らない。対角線論法は、どれほど豊かな形式でも、自己を含む全体を完全には写し取れないことを示す。
7.2 証明可能性の限界
証明できることと真であることは一致しない場合がある。対角線的な議論は、体系内で導出できないにもかかわらず意味のある命題が存在することを明らかにし、証明能力の範囲を定量的に意識させる。
7.3 可算性と非可算性の理解
この方法は、無限集合を一つの大きさにまとめて考える直観を修正する。可算な対象と非可算な対象の差を明確にし、無限にも階層があるという現代数学の基本観念を支えている。