Cantorの対角線論法
概要
Cantorの対角線論法（Cantor's diagonal argument）とは、一覧表の $n$ 番目の項目と $n$ 番目の箇所で食い違うものを作り、それが一覧表に載っていないことを示す証明の方法である。一般には、写像 $f\colon X\to Y^X$ と不動点のない写像 $\sigma\colon Y\to Y$ から $d(x)=\sigma(f(x)(x))$ を作ると $d$ は $f$ の像に属さず、$Y$ が 2 個以上の元をもてば $X$ から $Y^X$ への全射は存在しない。とくに集合 $X$ から冪集合 $\mathcal{P}(X)$ への全射はなく（Cantor の定理）、$0,1$ の無限列の全体や実数全体は可算でない。実数に使うときは $0.0999\cdots=0.1$ のような表示の重複に注意する。Russell の逆理や停止問題も同じ型である。
定義
$0$ と $1$ の無限列を 4 本、上から順に並べてみる。
$$
\begin{array}{c|ccccc}
& 0 & 1 & 2 & 3 & \cdots\\\hline
s_0 & \mathbf{0} & 1 & 1 & 0 & \cdots\\
s_1 & 1 & \mathbf{1} & 0 & 1 & \cdots\\
s_2 & 0 & 0 & \mathbf{0} & 1 & \cdots\\
s_3 & 1 & 0 & 1 & \mathbf{1} & \cdots
\end{array}
$$
太字の対角線上の数字 $0,1,0,1$ を読み、それぞれを反転した列 $t=1,0,1,0,\dots$ を作る。$t$ は $0$ 番目の項で $s_0$ と違い、$1$ 番目の項で $s_1$ と違い、一般に $n$ 番目の項で $s_n$ と違う。したがって、列を何本並べても（無限に $s_0,s_1,s_2,\dots$ と並べても）、そのどれとも一致しない列 $t$ が作れる。これが Cantor の対角線論法であり、$0$ と $1$ の無限列の全体に番号を付けて並べ尽くすことはできない、すなわちこの集合が非可算集合であることを示す。同じ考えで、どんな集合 $X$ についても、$X$ の部分集合の全体 $\mathcal{P}(X)$ は $X$ より真に大きいことが示される（cor-cda-power-set）。
一般の形では、表の行は集合 $X$ の元 $x$ で番号付けられ、各行は $X$ から集合 $Y$ への写像であり、「反転」は $Y$ から $Y$ への写像で与えられる。$X$ から $Y$ への写像全体の集合を $Y^X$ と書く。
$X,Y$ を集合とし、写像 $f\colon X\to Y^X$ と、不動点をもたない写像 $\sigma\colon Y\to Y$（すべての $y\in Y$ で $\sigma(y)\neq y$）が与えられたとする。$x\in X$ に対し $f_x:=f(x)\colon X\to Y$ と書き、写像 $d\colon X\to Y$ を
$$
d(x):=\sigma\bigl(f_x(x)\bigr)\qquad(x\in X)
$$
で定める。$d$ を $f$ と $\sigma$ から作った 対角線の元 という。$d$ を作って「$d$ は $f$ の像に属さない」と結論する議論を 対角線論法（diagonal argument）といい、とくに Cantor に由来するものを Cantor の対角線論法（Cantor's diagonal argument）という。
冒頭の表は $X=\mathbb{N}$（自然数全体）、$Y=\{0,1\}$、$f_n=s_n$、$\sigma(0)=1$、$\sigma(1)=0$ の場合であり、$d=t$ である。「$f_x(x)$」は表の $x$ 行 $x$ 列の成分、つまり対角線上の成分であり、$\sigma$ でそれを変えることで、$d$ は $x$ 行目の写像 $f_x$ と $x$ 番目の値で必ず異なる。
直感
対角線論法は「どんな一覧表にも載っていないものを、その表自身を材料に作る」方法である。一覧表の $x$ 番目の項目と $x$ 番目の箇所で食い違うように作るので、作ったものは一覧のどの項目とも一致しない。一覧表がどう与えられても作れるので、「すべてを載せた一覧表は存在しない」という否定的な結論が得られる。
この論法の要点は 2 つある。1 つは、表の行と列を同じ集合 $X$ で番号付けること（だから対角線が意味をもつ）、もう 1 つは、値を必ず変える写像 $\sigma$ があること（$Y$ が 2 個以上の元をもつこと）である。後者が欠けると論法は成り立たない（ex-cda-fixed-point）。また、作った元 $d$ が考えている集合に属することを別に確かめる必要がある（ex-cda-rationals、ex-cda-decimal）。
例と反例
$X=\{a,b,c\}$ とし、写像 $f\colon X\to\mathcal{P}(X)$ を $f(a)=\{a,b\}$、$f(b)=\emptyset$、$f(c)=\{a,c\}$ で定める。対角線の集合 $D:=\{x\in X\mid x\notin f(x)\}$ を計算すると、$a\in f(a)$、$b\notin f(b)$、$c\in f(c)$ なので $D=\{b\}$ である。$D$ は $f(a),f(b),f(c)$ のどれとも異なり、実際 $D$ は $a$ を含まない点で $f(a)$ と、$b$ を含む点で $f(b)$ と、$c$ を含まない点で $f(c)$ と異なる。$X$ の部分集合は $2^3=8$ 個あり、$X$ の元は $3$ 個なので、どんな $f$ も全射にはなりえないが、対角線論法は数えずに取りこぼしを具体的に示す。
自然数から自然数への写像の列 $f_0,f_1,f_2,\dots$ が与えられたとき、$g(n):=f_n(n)+1$ と定めると、$g(n)\neq f_n(n)$ なので $g$ はどの $f_n$ とも異なる（$Y=\mathbb{N}$、$\sigma(y)=y+1$）。したがって自然数から自然数への写像全体 $\mathbb{N}^{\mathbb{N}}$ は可算でない。
同じ考えで、増え方についての主張も得られる。$h(n):=\max\{f_0(n),f_1(n),\dots,f_n(n)\}+1$ とおくと、各 $k$ について $n\ge k$ なら $h(n)>f_k(n)$ である。すなわち、写像の列がどう与えられても、そのどれよりも最終的には大きくなる写像が作れる。
$Y=\{0\}$ が 1 元集合なら、$Y^X$ はただ 1 つの写像（定数写像 $0$）からなり、$X\neq\emptyset$ ならば $X\to Y^X$ の定数写像は全射である。このとき $Y\to Y$ の写像は恒等写像しかなく、それは不動点をもつので、対角線の元が作れない。満たさない性質：不動点をもたない $\sigma\colon Y\to Y$ が存在する。破る含意：「どんな集合 $X,Y$ についても $X\to Y^X$ は全射でない」は成り立たない。$Y$ が 2 個以上の元をもてば、異なる 2 元 $y_0,y_1$ を入れ替え他を $y_0$ に送る写像が不動点をもたないので、この問題は起きない。
$0$ と $1$ の間の有理数全体は可算なので、それらを $r_0,r_1,r_2,\dots$ と並べることができる（可算集合 の記事の例「有理数全体の可算性」）。各 $r_n$ の小数第 $n+1$ 位を見て、それが $1$ なら $2$、そうでなければ $1$ を第 $n+1$ 位の数字とする小数 $x$ を作ると、$x$ はどの $r_n$ とも異なる。しかしこれは矛盾ではない。$x$ は有理数ではない（有理数なら一覧のどれかに等しいはずである）ので、一覧の外にあってよい。満たす性質：$x$ は一覧のどの項とも異なる。満たさない性質：$x$ が一覧の対象の集合（ここでは有理数全体）に属する。破る含意：「対角線で作った元が一覧に載っていない」ことだけからは、その集合が非可算であるとは結論できない。非可算性を示すには、作った元が考えている集合に属することが必要である。
$[0,1)$ の実数の列 $x_n$ の小数第 $n+1$ 位の数字 $\delta_n$ に対し、「$\delta_n\ge1$ なら $\delta_n-1$、$\delta_n=0$ なら $9$」を新しい小数の第 $n+1$ 位とする規則を考える。$x_0=0.1000\cdots$、$x_n=0$（$n\ge1$）とすると、新しい小数は $0.0999\cdots$ となる。この数字の列は $x_0$ の数字の列 $0.1000\cdots$ と第 1 位で異なるが、実数としては $0.0999\cdots=0.1=x_0$ であり、一覧に載っている。満たさない性質：数字の列が異なれば実数として異なる。破る含意：「小数の数字の列を対角線で変えれば、一覧に載っていない実数が得られる」は、数字 $0$ と $9$ を使うと成り立たない。可算集合 の記事の定理「実数全体の非可算性」の証明は、新しい数字を $1$ と $2$ から選ぶことでこれを避けている。
性質
基本の形
$X,Y$ を集合、$f\colon X\to Y^X$ を写像、$\sigma\colon Y\to Y$ を不動点をもたない写像とし、$d$ を $f$ と $\sigma$ から作った対角線の元とする。このとき $d$ は $f$ の像に属さない。とくに、$Y$ が 2 個以上の元をもつならば、$X$ から $Y^X$ への全射は存在しない。
ある $x_0\in X$ について $d=f_{x_0}$ であったとする。両辺の $x_0$ での値を比べると $d(x_0)=f_{x_0}(x_0)$ である。一方、定義から $d(x_0)=\sigma(f_{x_0}(x_0))$ であり、$\sigma$ は不動点をもたないので $d(x_0)\neq f_{x_0}(x_0)$ である。これは矛盾なので、$d$ は $f$ の像に属さない。
$Y$ が相異なる元 $y_0,y_1$ をもつとき、$\sigma(y_0):=y_1$、$y\neq y_0$ なら $\sigma(y):=y_0$ と定めると、$\sigma$ は不動点をもたない。よってどんな $f\colon X\to Y^X$ についても対角線の元が像から漏れ、$f$ は全射でない。$\square$
証明は $d$ と $f_{x_0}$ を $X$ のただ 1 点 $x_0$ で比べるだけであり、$X$ や $Y$ が有限か無限かによらない。選択公理も使わない。
対偶をとると次の形になる。
$X$ から $Y^X$ への全射が存在するならば、$Y$ から $Y$ へのすべての写像は不動点をもつ。
不動点をもたない $\sigma\colon Y\to Y$ があれば、thm-cda-main により $X\to Y^X$ のどの写像も全射でない。$\square$
$Y$ が 2 個以上の元をもてば不動点のない写像があるので、この系の仮定は $Y$ が高々 1 個の元をもつときにしか満たされない。系の形は、対角線論法を「全射があれば不動点がある」という不動点定理として読むものである。
冪集合の定理
冪集合 $\mathcal{P}(X)$ と $\{0,1\}^X$ は、部分集合 $A\subset X$ にその特性関数(集合) $\chi_A$（$x\in A$ なら $1$、そうでなければ $0$）を対応させることで一対一に対応する。逆の対応は $s\mapsto\{x\in X\mid s(x)=1\}$ である。
任意の集合 $X$ について、$X$ から $\mathcal{P}(X)$ への全射は存在しない。より具体的に、写像 $F\colon X\to\mathcal{P}(X)$ に対し
$$
D:=\{x\in X\mid x\notin F(x)\}
$$
は $F$ の像に属さない。一方 $x\mapsto\{x\}$ は $X$ から $\mathcal{P}(X)$ への単射である。したがって濃度について $|X|<|\mathcal{P}(X)|$ である。
$Y=\{0,1\}$、$\sigma(0)=1$、$\sigma(1)=0$ とし、$f_x:=\chi_{F(x)}$ とおく。対角線の元は $d(x)=1-\chi_{F(x)}(x)$ であり、$d(x)=1$ となるのは $x\notin F(x)$ のとき、すなわち $x\in D$ のときなので、$d=\chi_D$ である。thm-cda-main により $\chi_D$ はどの $\chi_{F(x)}$ とも異なり、特性関数の対応は一対一なので、$D$ はどの $F(x)$ とも異なる。
直接確かめることもできる。$D=F(x_0)$ とすると、$x_0\in D$ なら $D$ の定義から $x_0\notin F(x_0)=D$、$x_0\notin D$ なら $x_0\notin F(x_0)$ なので $x_0\in D$ となり、どちらでも矛盾する。
$\{x\}=\{x'\}$ なら $x=x'$ なので $x\mapsto\{x\}$ は単射である。単射 $X\to\mathcal{P}(X)$ があって全単射がないことが $|X|<|\mathcal{P}(X)|$ の意味である。$\square$
これは Cantor の定理と呼ばれる結果で、冪集合 の記事の定理「Cantorの定理」、可算集合 の記事の定理「冪集合への全射の不存在」、基数 の記事の定理「Cantor の定理：冪集合は真に大きい」にも同じ証明がある（Ham 定理 14.7、pp. 281–282）。有限集合では $n<2^n$ という当たり前の不等式であるが、無限集合にも同じ形で成り立ち、$|\mathbb{N}|<|\mathcal{P}(\mathbb{N})|<|\mathcal{P}(\mathcal{P}(\mathbb{N}))|<\cdots$ と、いくらでも大きい無限が存在することが分かる。
数列の集合と実数
$0$ と $1$ の無限列の全体 $\{0,1\}^{\mathbb{N}}$、および自然数の無限列の全体 $\mathbb{N}^{\mathbb{N}}$ は非可算である。より強く、無限列の任意の列 $s_0,s_1,s_2,\dots$ に対し、そのどれとも異なる $0$ と $1$ の無限列 $t$ が $t(n):=1-s_n(n)$ で得られる。
$X=\mathbb{N}$、$Y=\{0,1\}$、$\sigma(y)=1-y$、$f_n=s_n$ として thm-cda-main を使うと、$t=d$ はどの $s_n$ とも異なる。したがって $\mathbb{N}$ から $\{0,1\}^{\mathbb{N}}$ への全射は存在せず、$\{0,1\}^{\mathbb{N}}$ は空でないので可算でない（可算集合 の記事の命題「単射・全射による特徴づけ」）。$\mathbb{N}^{\mathbb{N}}$ は $\{0,1\}^{\mathbb{N}}$ を部分集合として含むので、やはり非可算である（非可算集合 の記事の命題「上位集合と可算集合の除去」）。$\square$
実数全体 $\mathbb{R}$ の非可算性も同じ論法で示される。ただし実数を小数の数字の列で表すと $0.0999\cdots=0.1$ のような表し方の重複があるので（ex-cda-decimal）、新しい小数の数字を $1$ と $2$ から選び、数字の列から実数への対応が一対一になる範囲で対角線をとる。この証明は 可算集合 の記事の補題「小数の桁の読み取り」と定理「実数全体の非可算性」に完全な形で書かれている（Ham 定理 14.2、pp. 271–272 は数字 $0$ と $1$ を使う版を与えている）。区間を 3 等分していく別の証明は 非可算集合 の記事の定理「区間の非可算性」にある。
論法の広がり
対角線論法は集合の大きさの比較以外にも現れる。
- Russell の逆理：「自分自身を元として含まない集合全体」$R=\{x\mid x\notin x\}$ を集合として認めると、$R\in R$ でも $R\notin R$ でも矛盾する（Ham §1.10、pp. 32–33）。これは cor-cda-power-set の集合 $D$ で、$F(x)=x$ とした形である。現在の集合論では、このような集合の作り方は分出公理で制限されている。
- 停止問題：どんなプログラムと入力についても「そのプログラムがその入力で停止するか」を判定するプログラムは存在しない（Turing、Tur36）。判定するプログラム $H$ があったとすると、「プログラム $P$ を受け取り、$H$ が『$P$ に $P$ 自身を入力すると停止する』と答えれば無限に動き続け、そうでなければ停止する」プログラム $Q$ が作れ、$Q$ に $Q$ 自身を入力すると矛盾する。プログラムを行と列の両方の番号に使い、対角線上の振る舞いを反転している。
どちらも本記事では言及にとどめ、厳密な定式化はそれぞれの主題に譲る。
「対角線」の名が付く議論には、本記事の論法と別のものもある。$\mathbb{N}\times\mathbb{N}$ や有理数全体に番号を付けるときに、表を斜めの線に沿って数えていく方法（可算集合 の記事の命題「自然数の対の番号付け」）は、可算であることを示す議論であり、本記事の論法とは結論の向きが逆である。また解析学では、関数の列の列から、各列について収束する共通の部分列を「対角線に沿って」取り出す議論（対角線部分列の方法）が使われる。これも行と列を同じ番号で走らせる点は共通するが、何かが一覧に載らないことを示すものではない。
Cantor は 1874 年に、区間の入れ子を使う別の議論で実数全体が可算でないことを示した（Can74）。対角線論法は 1891 年の論文で導入され、2 種類の記号からなる無限列の全体が非可算であることがこの論法で示された（Can91）。本記事冒頭の表はこの論法を $0$ と $1$ の列で書いたものである。冪集合の定理や上の Russell の逆理・停止問題の議論も、thm-cda-main と同じ型をしている。
関連項目
- 前提: 集合, 写像, 全射, 冪集合, 可算集合
- 比較: 非可算集合, 基数, Cantor–Bernsteinの定理
- 直後に読む: 連続体仮説, 濃度
- 発展: 停止問題, Russellのパラドックス, Gödelの不完全性定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
