カントールの対角線論法
カントールの定理において、Xとして自然数の集合Nを考える。この冪集合の濃度2 は連続体濃度に等しいことが知られている。では、果たして可算濃度 |N| とその冪集合の濃度 2 の間に濃度が存在するのだろうか。 つまり
|N| < m < 2 なる濃度 m は存在しない
という主張が連続体仮説と呼ばれるものである。これはヒルベルトの23の問題の第1問題として挙げられた。
またこれを一般化して、
無限濃度 n に対して、n < m < 2 なる m は存在しない
というのが、一般連続体仮説である。一般連続体仮説のZFからの無矛盾性をクルト・ゲーデルが、独立性を1963年にポール・コーエンがそれぞれ証明した。
自然数全体の集合 N {\displaystyle \mathbb {N} } から[0, 1]区間(=0以上1以下の実数全体の集合)への全単射が存在しないことを以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。
なお、[0, 1]区間と実数全体の集合 R {\displaystyle \mathbb {R} } は濃度が等しいので、この事実は N {\displaystyle \mathbb {N} } から R {\displaystyle \mathbb {R} } への全単射が存在しないことを含意する。
さて、仮に N {\displaystyle \mathbb {N} } から[0, 1]区間への全単射φが存在したとし、φ(i)をaiと書くことにする。すると[0, 1]区間の各元を a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } と番号づけすることができたことになる。
aiを二進数展開したときの j {\displaystyle j} 桁目をai,jとし、biを¬ai,iとする。
そしてbを小数点展開が0.b1b2...となる実数とする。
以下の補題を使った論法も対角線論法と呼ばれる。後で見るように、実は以下の補題は前節で示した補題と同値である。
X {\displaystyle X} を集合とし、 φ : X × X → { 0 , 1 } {\displaystyle \phi :X\times X\rightarrow \{0,1\}} を写像とする。 φ ( x , y ) {\displaystyle \phi (x,y)} を φ x ( y ) {\displaystyle \phi _{x}(y)} と書くと、各 x ∈ X {\displaystyle x\in X} に対し φ x {\displaystyle \phi _{x}} は X {\displaystyle X} から { 0 , 1 } {\displaystyle \{0,1\}} への写像である。 g : X → { 0 , 1 } {\displaystyle g:X\rightarrow \{0,1\}} を、 g ( x ) = ¬ φ x ( x ) {\displaystyle g(x)=\neg \phi _{x}(x)} により定義する。ここで、「 ¬ {\displaystyle \neg } 」は0と1を反転する写像。