カントールの定理のソースを表示

{{脚注の不足|date=2022年2月}}
[[Image:Hasse diagram of powerset of 3.svg|right|thumb|250px|集合 {{math|{{mset|{{mvar|x}}, ''y'', ''z''}}}} の濃度は 3 であり、一方その冪集合には 8 つの元が存在し、[[包含 (集合論)|包含]]によって{{仮リンク|順序論|label=順序付けられている|en|Order theory}}。(3 < 2<sup>3</sup>=8)]]

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

==内容==
任意の[[集合]] {{mvar|A}} に対して、{{mvar|A}} のすべての[[部分集合]]の集合（ {{mvar|A}} の[[冪集合]]）は {{mvar|A}} 自身よりも真に大きい[[濃度 (数学)|濃度]]を持つ。

==証明==
有限集合に対して定理が成立するのは明らかである。{{mvar|n}} 個の要素からなる集合に対して、空部分集合、ただ 1 つの要素を持つ {{mvar|A}} の部分集合、等々……と数えると、 {{math|2<sup>''n''</sup>}} 個の部分集合があり、部分集合の濃度は明らかに大きい（{{math|''n'' < 2<sup>''n''</sup>}}） 。以下の証明は[[無限集合]]に対するものである。

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

:<math>B=\left\{\,x\in A : x\not\in f(x)\,\right\}.</math>

これが意味するのは、定義によってすべての {{math|''x'' &isin; ''A''}} に対して {{math|''x'' &isin; ''B'' &hArr; ''x'' &notin; ''f''&thinsp;(''x'')}} ということである。すべての {{mvar|x}} に対して集合 {{mvar|B}} と {{math|''f''&thinsp;(''x'')}} は同じにはなり得ない、なぜならば {{mvar|B}} は（ {{mvar|f}} による）像が自身を含まないような {{mvar|A}} の元から構成されていたからである。より具体的には以下のとおりである。任意の {{math|''x'' &isin; ''A''}} を考えると、 {{math|''x'' &isin; ''f''&thinsp;(''x'')}} かまたは {{math|''x'' &notin; ''f''&thinsp;(''x'')}} である。前者の場合には、 {{math|''x'' &isin; ''f''&thinsp;(''x'')}} である一方 {{mvar|B}} の構成から {{math|''x'' &notin; ''B''}} であるため、 {{math|''f''&thinsp;(''x'')}} と {{mvar|B}} は等しくない。後者の場合には、 {{math|''x'' &notin; ''f''&thinsp;(''x'')}} である一方 {{mvar|B}} の構成から {{math|''x'' &isin; ''B''}} であるため、やはり {{math|''f''&thinsp;(''x'')}} と {{mvar|B}} は等しくない。

したがって {{math|''f''&thinsp;(''x''){{=}}''B''}} なる {{mvar|x}} は存在しない。言い換えると {{mvar|B}} は {{mvar|f}} の像に含まれない。{{mvar|B}} は {{mvar|A}} の冪集合に含まれるから、{{mvar|A}} の冪集合は {{mvar|A}} 自身よりも大きい濃度を持つ。

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

式 "{{math|''x'' &notin; ''f''&thinsp;(''x'')}}" において {{mvar|x}} が 2 回出現するため、これは[[対角線論法]]である。

==具体例：可算無限集合の場合==
証明を理解するために、元の集合が[[可算集合|可算無限集合]] {{mvar|X}} である場合を考えよう。[[一般性を失わない|一般性を失うことなく]] {{math|''X'' {{=}} {{mathbf|N}} {{=}} {{mset|1, 2, 3,...}}}} （[[自然数]]の集合）ととれる。

{{mathbf|N}} とその[[冪集合]] {{math|''P''({{mathbf|N}})}} は[[等濃]]と仮定する。{{math|''P''({{mathbf|N}})}} の具体的な例を見よう：

:<math>P(\mathbb{N})=\{\varnothing,\{1, 2\}, \{1, 2, 3\}, \{4\}, \{1, 5\}, \{3, 4, 6\}, \{2, 4, 6,\dots\},\dots\}.</math>

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

さて {{math|''P''({{mathbf|N}})}} の具体的な元がわかっているから、これらの無限集合が等濃であることを示すために、{{mathbf|N}} と {{math|''P''({{mathbf|N}})}} のそれぞれの元をペアにしてみよう。言い換えると、{{mathbf|N}} の各元が無限集合 {{math|''P''({{mathbf|N}})}} の元とペアになるようにして、どちらの無限集合の元もペアにならないまま残ることがないようにする。このように元をペアにすると以下のようになるだろう：

:<math>\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}).</math>

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

この考え方を用いて、自然数のある特別な集合を作ろう。この集合は求めるべき[[背理法|矛盾]]を導く。{{mvar|D}} を''すべての''非利己的な自然数の集合とする。定義によって冪集合 {{math|''P''({{mathbf|N}})}} は自然数からなるすべての集合を含み、したがってこの集合 {{mvar|D}} を元として含む。写像が全単射であれば、{{mvar|D}} は対応するある自然数 {{mvar|d}} とペアになっていなければならない。しかしこれは問題を起こす。{{mvar|d}} が {{mvar|D}} に含まれれば、 {{mvar|d}} が対応する集合に含まれるから {{mvar|d}} は利己的であるが、これは {{mvar|D}} の定義に矛盾する。 {{mvar|d}} が {{mvar|D}} に含まれなければ、 {{mvar|d}} は非利己的である一方で {{mvar|D}} の元でなければならない。したがって {{mvar|D}} に写るような元 {{mvar|d}} は存在しない。

{{mvar|D}} とペアにできる自然数は存在しないから、もとの仮定「 {{mathbf|N}} と {{math|''P''({{mathbf|N}})}} の間に[[全単射]]が存在すること」に矛盾する。

集合 {{mvar|D}} は空かもしれないことに注意しよう。これはすべての自然数 {{mvar|x}} は {{mvar|x}} を含む自然数の集合に写ることを意味する。すると、すべての自然数は空でない集合に写り、どんな数も空集合に写らない。しかし空集合は {{math|''P''({{mathbf|N}})}} の元であるので、写像は全射にならない。

この[[背理法]]を通して、 {{mathbf|N}} と {{math|''P''({{mathbf|N}})}} の[[濃度 (数学)|濃度]]が等しくないことが示された。また、 {{math|''P''({{mathbf|N}})}} の濃度が {{mathbf|N}} の濃度よりも小さくないこともわかる。なぜならば {{math|''P''({{mathbf|N}})}} は定義によってすべての[[単集合|一元集合]]を含み、これらの一元集合は {{math|''P''({{mathbf|N}})}} の中で {{mathbf|N}} の「コピー」となるからである。したがって、 {{math|''P''({{mathbf|N}})}} の濃度は {{mathbf|N}} の濃度よりも真に大きく、カントールの定理が証明された。
== 定理に基づく結果 ==
カントールの定理は「いかなる無限集合を考えたとしても、それより大きな濃度を持つ無限集合が存在する」ことを示す。特に、[[可算集合|可算無限集合]]の冪集合は[[非可算集合|非可算無限]]である。

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

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

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

歴史上、この結果は[[型理論]]や[[公理的集合論]]の成立を促した。現在の集合論では「全ての集合の集合」は公理から構成不可能であるためパラドックスが回避されており、 {{mvar|X}} のような集合の集まりは[[クラス (集合論)|真のクラス]]と呼ばれる。
== 歴史 ==
カントールは 1891 年に出版された論文 ''Über eine elementare Frage der Mannigfaltigkeitslehre'' （''多様体論の初等的問題に関して''）においてこの証明を本質的に与えた。この論文では[[実数]]の非可算性のための[[対角線論法]]もまた初めて現れる（なお、カントールは{{仮リンク|カントールの最初の非可算性の証明|label=以前に他の手法によって実数の非可算性を証明していた|en|Cantor's first uncountability proof}}）。この論文における証明は、集合の部分集合ではなく集合上の指示関数の言葉で表現された。カントールは、 {{mvar|f}} を {{mvar|X}} 上で定義された {{mvar|X}} の 2-値関数とすると 2-値関数 {{math|''G''&thinsp;(''x'') {{=}} 1 &minus; ''f''&thinsp;(''x'')(''x'')}} は {{mvar|f}} の値域に含まれないことを示した。

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

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

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

==関連項目==
* [[ベルンシュタインの定理|カントール・ベルンシュタイン・シュレーダーの定理]] ([[:en:Cantor–Bernstein–Schroeder theorem|Cantor–Bernstein–Schroeder theorem]])
* [[カントールの最初の非可算性の証明]] ([[:en:Cantor's first uncountability proof|Cantor's first uncountability proof]])
* [[カントールの理論の論争]] ([[:en:Controversy over Cantor's theory|Controversy over Cantor's theory]])

== 参考文献 ==
*[[Paul Halmos|Halmos, Paul]], ''[[Naive Set Theory (book)|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|last=Jech|first=Thomas|authorlink=Thomas Jech|year=2002|title=Set Theory|edition=3rd millennium|series=Springer Monographs in Mathematics|publisher=Springer|isbn=3-540-44085-2}}

== 外部リンク ==
* {{SpringerEOM|title=Cantor theorem|urlname=Cantor_theorem}}
* {{MathWorld |title=Cantor's Theorem |id=CantorsTheorem }}

{{Metalogic}}
{{Set theory}}

{{DEFAULTSORT:かんとおるのていり}}
[[Category:集合論]]
[[Category:数学基礎論の定理]]
[[Category:基数]]
[[Category:ゲオルク・カントール]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]