カントールの定理

集合 テンプレート:Math の濃度は 3 であり、一方その冪集合には 8 つの元が存在し、包含によってテンプレート:仮リンク。(3 < 2³=8)

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

内容

任意の集合 テンプレート:Mvar に対して、テンプレート:Mvar のすべての部分集合の集合（ テンプレート:Mvar の冪集合）は テンプレート:Mvar 自身よりも真に大きい濃度を持つ。

証明

有限集合に対して定理が成立するのは明らかである。テンプレート:Mvar 個の要素からなる集合に対して、空部分集合、ただ 1 つの要素を持つ テンプレート:Mvar の部分集合、等々……と数えると、 テンプレート:Math 個の部分集合があり、部分集合の濃度は明らかに大きい（テンプレート:Math） 。以下の証明は無限集合に対するものである。

2 つの集合が等濃である（同じ濃度を持つ）こととそれらの間に一対一対応が存在することは同値である。カントールの定理を証明するには、任意の与えられた集合 テンプレート:Mvar に対して、テンプレート:Mvar から テンプレート:Mvar の冪集合へのどんな関数 テンプレート:Mvar も全射になりえないことを示せば十分である。すなわち、 テンプレート:Mvar による テンプレート:Mvar の像の元でない、 テンプレート:Mvar の少なくとも 1 つの部分集合の存在を示せば十分である。そのような部分集合は次の構成によって与えられる：

$B=\{x\in A:x\in ̸f(x)\}.$

これが意味するのは、定義によってすべての テンプレート:Math に対して テンプレート:Math ということである。すべての テンプレート:Mvar に対して集合 テンプレート:Mvar と テンプレート:Math は同じにはなり得ない、なぜならば テンプレート:Mvar は（ テンプレート:Mvar による）像が自身を含まないような テンプレート:Mvar の元から構成されていたからである。より具体的には以下のとおりである。任意の テンプレート:Math を考えると、 テンプレート:Math かまたは テンプレート:Math である。前者の場合には、 テンプレート:Math である一方 テンプレート:Mvar の構成から テンプレート:Math であるため、 テンプレート:Math と テンプレート:Mvar は等しくない。後者の場合には、 テンプレート:Math である一方 テンプレート:Mvar の構成から テンプレート:Math であるため、やはり テンプレート:Math と テンプレート:Mvar は等しくない。

したがって テンプレート:Math なる テンプレート:Mvar は存在しない。言い換えると テンプレート:Mvar は テンプレート:Mvar の像に含まれない。テンプレート:Mvar は テンプレート:Mvar の冪集合に含まれるから、テンプレート:Mvar の冪集合は テンプレート:Mvar 自身よりも大きい濃度を持つ。

別の証明方法としては、 テンプレート:Mvar が空集合であるかどうかにかかわらず、つねに テンプレート:Mvar の冪集合に含まれることを用いる。テンプレート:Mvar が全射であるためには、 テンプレート:Mvar のある元は テンプレート:Mvar に写らなければならないが、これは矛盾であることを示す。 テンプレート:Mvar の構成より、テンプレート:Mvar のどの元も テンプレート:Mvar に写らない。したがって テンプレート:Mvar に写る元は テンプレート:Mvar の元ではない。しかしこれは テンプレート:Mvar の構成における元の判定条件を満たし、矛盾。したがって テンプレート:Mvar のある元が テンプレート:Mvar に写るという仮定は誤りである。したがって テンプレート:Mvar は全射ではない。

式 "テンプレート:Math" において テンプレート:Mvar が 2 回出現するため、これは対角線論法である。

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

証明を理解するために、元の集合が可算無限集合 テンプレート:Mvar である場合を考えよう。一般性を失うことなく テンプレート:Math （自然数の集合）ととれる。

テンプレート:Mathbf とその冪集合 テンプレート:Math は等濃と仮定する。テンプレート:Math の具体的な例を見よう：

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

テンプレート:Math は、すべての偶数の集合 {2, 4, 6,...} や空集合など、テンプレート:Mathbf の無限個の部分集合を含む。

さて テンプレート:Math の具体的な元がわかっているから、これらの無限集合が等濃であることを示すために、テンプレート:Mathbf と テンプレート:Math のそれぞれの元をペアにしてみよう。言い換えると、テンプレート:Mathbf の各元が無限集合 テンプレート:Math の元とペアになるようにして、どちらの無限集合の元もペアにならないまま残ることがないようにする。このように元をペアにすると以下のようになるだろう：

$\mathbb{N}\left\{\begin{array}{ccc}1& ⟷& \{4,5\}\\ 2& ⟷& \{1,2,3\}\\ 3& ⟷& \{4,5,6\}\\ 4& ⟷& \{1,3,5\}\\ ⋮& ⋮& ⋮\end{array}\right\}P(\mathbb{N}).$

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

この考え方を用いて、自然数のある特別な集合を作ろう。この集合は求めるべき矛盾を導く。テンプレート:Mvar をすべての非利己的な自然数の集合とする。定義によって冪集合 テンプレート:Math は自然数からなるすべての集合を含み、したがってこの集合 テンプレート:Mvar を元として含む。写像が全単射であれば、テンプレート:Mvar は対応するある自然数 テンプレート:Mvar とペアになっていなければならない。しかしこれは問題を起こす。テンプレート:Mvar が テンプレート:Mvar に含まれれば、 テンプレート:Mvar が対応する集合に含まれるから テンプレート:Mvar は利己的であるが、これは テンプレート:Mvar の定義に矛盾する。 テンプレート:Mvar が テンプレート:Mvar に含まれなければ、 テンプレート:Mvar は非利己的である一方で テンプレート:Mvar の元でなければならない。したがって テンプレート:Mvar に写るような元 テンプレート:Mvar は存在しない。

テンプレート:Mvar とペアにできる自然数は存在しないから、もとの仮定「 テンプレート:Mathbf と テンプレート:Math の間に全単射が存在すること」に矛盾する。

集合 テンプレート:Mvar は空かもしれないことに注意しよう。これはすべての自然数 テンプレート:Mvar は テンプレート:Mvar を含む自然数の集合に写ることを意味する。すると、すべての自然数は空でない集合に写り、どんな数も空集合に写らない。しかし空集合は テンプレート:Math の元であるので、写像は全射にならない。

この背理法を通して、 テンプレート:Mathbf と テンプレート:Math の濃度が等しくないことが示された。また、 テンプレート:Math の濃度が テンプレート:Mathbf の濃度よりも小さくないこともわかる。なぜならば テンプレート:Math は定義によってすべての一元集合を含み、これらの一元集合は テンプレート:Math の中で テンプレート:Mathbf の「コピー」となるからである。したがって、 テンプレート:Math の濃度は テンプレート:Mathbf の濃度よりも真に大きく、カントールの定理が証明された。

定理に基づく結果

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

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

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

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

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

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

歴史

カントールは 1891 年に出版された論文 Über eine elementare Frage der Mannigfaltigkeitslehre （多様体論の初等的問題に関して）においてこの証明を本質的に与えた。この論文では実数の非可算性のための対角線論法もまた初めて現れる（なお、カントールはテンプレート:仮リンク）。この論文における証明は、集合の部分集合ではなく集合上の指示関数の言葉で表現された。カントールは、 テンプレート:Mvar を テンプレート:Mvar 上で定義された テンプレート:Mvar の 2-値関数とすると 2-値関数 テンプレート:Math は テンプレート:Mvar の値域に含まれないことを示した。

バートランド・ラッセルは Principles of Mathematics (1903, section 348) において非常によく似た証明をしており、彼は対象よりも命題関数の方がたくさんあることを示した。「すべての対象といくつかの命題関数の相関関係が影響を受けると仮定し、テンプレート:Math を テンプレート:Math の相関とする。すると "not テンプレート:Math" すなわち "テンプレート:Math が テンプレート:Math について成り立たない" はこの相関に含まれない命題関数となる。 テンプレート:Math の真偽と テンプレート:Math の真偽が反転するからである。したがって、これはどの テンプレート:Math の値についても テンプレート:Math と異なる。」ラッセルの証明の考え方はカントールのものに基づく。

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

カントールの定理に基づく結果は、ベート数も参照せよ。

関連項目

• カントール・ベルンシュタイン・シュレーダーの定理 (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).
• テンプレート:Citation

外部リンク

• テンプレート:SpringerEOM
• テンプレート:MathWorld