カントールの定理

集合 {x, y, z} の濃度は 3 であり、一方その冪集合には 8 つの元が存在し、包含によって順序付けられている。(3 < 2³=8)

カントールの定理 (Cantor's theorem) は集合論における基本的な定理の一つで、冪集合の濃度について述べたものである。最初にこれを証明したドイツ人数学者ゲオルク・カントール (Georg Cantor) にちなむ。

内容

任意の集合 A に対して、A のすべての部分集合の集合（ A の冪集合）は A 自身よりも真に大きい濃度を持つ。

証明

有限集合に対して定理が成立するのは明らかである。n 個の要素からなる集合に対して、空部分集合、ただ 1 つの要素を持つ A の部分集合、etc. を数えて、 2ⁿ 個の部分集合があり、部分集合の集合の濃度は明らかに大きい（n < 2ⁿ） 。以下の証明は無限集合に対するものである。

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 自身よりも大きい濃度を持っている。

証明について考える別の方法は B は空でも空でなくてもつねに A の冪集合に入っていることである。f が全射であるためには A のある元は B に写らなければならない。しかしそれは矛盾を導く： B のどんな元も B に写れない、なぜならそれは B の元の判定法に矛盾するからで、したがって B に写る元は B の元であってはいけなくて、つまりそれは B の元の判定条件を満たし、別の矛盾。なので A のある元が B に写るという仮定は誤りでなければならない； そして f は全射ではありえない。

式 "x ∉ f (x)" における x の二重の出現のためにこれは対角線論法である。

具体例：可算無限集合の場合

証明を理解するために、元の集合が可算無限集合 X である特別な場合に対して検証しよう。一般性を失うことなく X = N = {1, 2, 3,...} , 自然数の集合、ととれる。

N はその冪集合 P(N) と等濃と仮定する。P(N) がどのように見えるか例を見よう：

$P(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.$

P(N) は、すべての偶数の集合 {2, 4, 6,...} や空集合など、N の無限個の部分集合を含む。

さて P(N) の元がどのように見えるかのアイデアを持っているから、N の元を P(N) の各元に、これらの無限集合が等濃であることを示すために、対になるように試みよう。言い換えると、N の各元が無限集合 P(N) の元と対になるようにしてどちらの無限集合からの元も対にならないまま残ることはないように試みる。元を対にするそのような試みはこのように見えるだろう：

$\mathbb {N} {\begin{Bmatrix}1&\longleftrightarrow &\{4,5\}\\2&\longleftrightarrow &\{1,2,3\}\\3&\longleftrightarrow &\{4,5,6\}\\4&\longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}P(\mathbb {N} ).$

そのようなペアリングが与えられると、ある自然数はまさに同じ数を含む部分集合と対にされる。例えば、我々の例において数 2 は元として 2 を含む部分集合 {1, 2, 3} と対にされている。そのような数を利己的と呼ぶことにしよう。他の自然数はそれを含まない部分集合と対にされる。例えば、我々の例において数 1 は元として 1 を含まない部分集合 {4, 5} と対にされている。このような数を非利己的と呼ぶ。同様に、3 と 4 は非利己的である。

このアイデアを用いて、自然数のある特別な集合を作ろう。この集合は求める矛盾を提供する。D をすべての非利己的な自然数の集合とする。定義によって冪集合 P(N) は自然数からなるすべての集合を含み、したがってこの集合 D を元として含む。写像が全単射であれば、D は対応するある自然数 d と対にされていなければならない。しかしながら、これは問題を起こす。d が D に入っていれば、d は利己的である。なぜならばそれは対応する集合に入っているからで、D の定義に矛盾する。d が D に入っていなければ、それは非利己的であり代わりに D の元でなければならない。したがって D に写るような元 d は存在しえない。

D と対にできる自然数は存在しないから、我々のもとの仮定、 N と P(N) の間に全単射が存在することに矛盾した。

集合 D は空かもしれないことに注意しよう。これはすべての自然数 x は x を含む自然数の集合に写ることを意味する。すると、すべての自然数は空でない集合に写り、どんな数も空集合に写らない。しかし空集合は P(N) の元であるので、写像はなお P(N) をカバーしない。

この矛盾による証明を通して N と　P(N) の濃度は等しくはありえないことを示した。 P(N) の濃度は N の濃度よりも小さくなれないことも知っている、なぜならば P(N) は定義によってすべてのシングルトンを含み、これらのシングルトンは P(N) の中で N の「コピー」をなすからである。したがって、唯一つの可能性が残り、それは、P(N) の濃度は N の濃度よりも真に大きいことであり、カントールの定理が証明された。

定理のもたらしたもの

カントールの定理は「いかなる無限集合を考えたとしても、それより大きな濃度を持つ無限集合が存在する」事を示している。特に、可算無限集合の冪集合は非可算無限である。

次に考えられる疑問は、元の集合の濃度${\mbox{card}}\,A$と冪集合の濃度${\mbox{card}}\,{\mathfrak {P}}(A)$の間に別の濃度が存在するかどうかである。カントールは存在しないと予想し、この問題は連続体仮説と呼ばれる事になった。

カントールのパラドックス

素朴集合論において、カントールの定理はパラドックスを導く。

「全ての集合の集合」Xを考える。カントールの定理より、Xの冪集合${\mathfrak {P}}(X)$はXより真に大きな濃度を持つ。しかしXは全ての集合をその部分集合として持つから、Xは${\mathfrak {P}}(X)$よりも大きな濃度を持つはずである。これは矛盾である。

歴史上、この結果は型理論や公理的集合論の成立を促した。現在の集合論では「全ての集合の集合」は公理から構成不可能であるためパラドックスが回避されており、Xのような集合の集まりは真のクラスと呼ばれる。

歴史

カントールは 1891 年に出版された論文 Über eine elementare Frage der Mannigfaltigkeitslehre （多様体論の初等的問題に関して）においてこの証明を本質的に与えた。そこでは実数の非可算性のための対角線論法もまた初めて現れる（彼は以前に他の手法によって実数の非可算性を証明していた）。その論文で彼が与えたこの議論のバージョンは集合の部分集合よりもむしろ集合上の指示関数の言葉で表現された。彼は f が X 上値が 2-値関数である X 上定義された関数であれば 2-値関数 G (x) = 1 − f (x)(x) は f の値域に入らないことを示した。

バートランド・ラッセル (Bertrand Russell) は Principles of Mathematics (1903, section 348) において非常によく似た証明をしており、そこで彼は対象よりも命題関数の方がたくさんあることを示す。"For suppose a correlation of all objects and some propositional functions to have been affected, and let phi-x be the correlate of x. Then "not-phi-x(x)," i.e. "phi-x does not hold of x" is a propositional function not contained in this correlation; for it is true or false of x according as phi-x is false or true of x, and therefore it differs from phi-x for every value of x." 彼は証明の背後のアイデアをカントールに帰する。

エルンスト・ツェルメロ (Ernst Zermelo) は 1908 年に出版された、現代的集合論の基礎となった論文 ("Untersuchungen über die Grundlagen der Mengenlehre I"（集合論の基礎についての研究 I ）) において、上の形に同一な（彼が「カントールの定理」と呼ぶ）定理を持つ。en:Zermelo set theory を参照。

カントールの定理の 1 つの結果は、ベート数を参照。

関連項目

• カントール・ベルンシュタイン・シュレーダーの定理 (Cantor–Bernstein–Schroeder theorem)
• カントールの最初の非可算性の証明 (Cantor's first uncountability proof)
• カントールの理論の論争 (Controversy over Cantor's theory)

参考文献

• Halmos, Paul, Naive Set Theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition).
• Jech, Thomas (2002), Set Theory, Springer Monographs in Mathematics (3rd millennium ed.), Springer, ISBN 3-540-44085-2 

外部リンク

• Hazewinkel, Michiel, ed. (2001), “Cantor theorem”, Encyclopaedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://eom.springer.de/p/c020260.htm 
• Weisstein, Eric W. "Cantor's Theorem". mathworld.wolfram.com (英語).