対角線論法
定理 (Cantor):
X を集合, P(X) をその冪集合とする. このとき f: X → P(X) で全単射となるものは存在しない.
証明 :
f が全射でないことを示せば十分. Y := { x ∈ X | x ∉ f(x) } とする. Y は定義より X の部分集合となるから Y ∈ P(X).
また, 任意の x ∈ X に対し,
・x ∈ f(x) のとき x ∉ Y
・x ∉ f(x) のとき x ∈ Y
であるから, f(x) ≠ Y. 従って Y ∉ f"X.
示すだけであれば上の通り短くシンプルですが, 無駄を削って洗練されている分, "何故この証明が出てきたか" が把握しづらいかもしれません. じっくりと状況を整理することで, この証明が "必然的" であることを確認しましょう.
まず単射性でなく全射性を否定する点ですが, 詳しくは次回以降話していくつもりですが, f: X → Y があったとき,
f が単射のとき X の要素の個数は Y の要素の個数以下 (#X ≦ #Y)
f が全射のとき X の要素の個数は Y の要素の個数以上 (#X ≧ #Y)
が成立します.
f(x) := {x} ∈ P(X) で単射な例を簡単に作れることや, X が有限集合で要素が n 個のとき, P(X) が 2^n 個の要素を持ち n < 2^n であることから全射にならないことを示そうという方針が決まります.
すると任意にとった f: X → P(X) に対し, f"X に含まれない Y ∈ P(X) を構成したいことになります.
Y が f"X に含まれないとは, 全ての x ∈ X に対し f(x) ≠ Y となることです. f(x) も Y も X の部分集合ですから, f(x) ≠ Y とはある要素 z ∈ X で "z ∈ f(x) かどうか" と "z ∈ Y かどうか" が一致しないことにほかなりません.
いま Y を構成しようとしているので, z が Y に属するかどうかが f(x) と逆になるように Y を決めてしまえばよいでしょう.
・z ∈ f(x) のとき z ∉ Y
・z ∉ f(x) のとき z ∈ Y
とすれば Y は f(x) と異なる集合となることが保障されます.
これを全ての x ∈ X に対して行えば, Y は "全ての x ∈ X に対し f(x) ≠ Y" を満たします.
ところでここで注意が必要です. 上の議論の z は, 異なる x ∈ X に対して同じ z がとられてしまうと困ったことになるのです.
x_0 ∈ X と x_1 ∈ X を異なる要素とし, x_0 と x_1 で上の議論の z を同じものとしてとったとします. ここで例えば z ∈ f(x_0) であり z ∉ f(x_1) であったとしましょう.すると z ∈ Y と決めても z ∉ Y と決めても f(x_0) と f(x_1) のどちらかとは "異なることが保障されない" わけです.
すると上の議論の z は, x ∈ X 毎に異なるものをとらないと面倒です. 逆に x ∈ X 毎に異なるものさえとってしまえば, "全ての x ∈ X に対し f(x) ≠ Y" は満たされます.
z ∈ X は x ∈ X 毎に決まりますから x を変数とする関数 z: X → X と思えます. x ∈ X 毎に異なる z(x) となるということは, z が単射であることにほかなりません.
問題を整理することで, 次のようなものが見つかれば定理が証明できることがわかりました.
z: X → X で単射であるものを見つけよ.
そしてこれは trivial に存在します. id: X → X (id(x) = x) とすればよいわけです. そうして Y も具体的に定まります.
任意の x ∈ X に対し, Y は f(x) と x で異なるように定めと, そうして出来た Y が上の証明で定義されている { x ∈ X | x ∉ f(x) } となることを確かめてください.
この定理の証明法は対角線論法と呼ばれ, ゲオルグ・カントール (Georg Cantor) が発見したものです.
