15/03/01 07:56:35.86 NplpTsbd.net
対角線論法５
URLﾘﾝｸ(ja.wikipedia.org)
カントールの定理
証明
2 つの集合が等濃（英語版）である（同じ濃度を持つ）こととそれらの間に一対一対応が存在することは同値である。
カントールの定理を証明するには任意の与えられた集合 A に対して、A から A の冪集合へのどんな関数 f も全射になりえないことを示せば十分である。
すなわち f のもとでの A の像の元でない A の少なくとも 1 つの部分集合の存在を示せば十分である。
そのような部分集合は次の構成によって与えられる：B=\left\{\,x\in A : x\not\in f(x)\,\right\}.
これが意味するのは定義によってすべての x ∈ A に対して x ∈ B ⇔ x ∉ f(x) ということである。
すべての x に対して集合 B と f(x) は同じにはなり得ない、なぜならば B は（f による）像が自信を含まないような A の元から構成されていたからである。
より具体的には、任意の x ∈ A を考えると、x ∈ f(x) かまたは x ∉ f(x) である。前者の場合には f(x) は B に等しくなれない、なぜなら仮定により x ∈ f(x) であり B の構成から x ∉ B だからである。
後者の場合には f(x) は B に等しくなれない、なぜなら仮定により x ∉ f(x) であり B の構成により x ∈ B だからである。
したがって f(x) = B なる x は存在しない； 言い換えると B は f の像に入っていない。
B は A の冪集合に入っているから、A の冪集合は A 自身よりも�