|
|
| 1行目: |
1行目: |
| − | [[Image:Hasse diagram of powerset of 3.svg|right|thumb|250px|集合 {''x'', ''y'', ''z''} の濃度は 3 であり、一方その冪集合には 8 つの元が存在し、[[包含 (集合論)|包含]]によって{{仮リンク|順序論|label=順序付けられている|en|Order theory}}。(3 < 2<sup>3</sup>=8)]]
| + | {{テンプレート:20180815sk}} |
| − | | |
| − | 初等的な[[集合論]]において、'''カントールの定理''' (Cantor's theorem) は次のように述べている。任意の[[集合]] ''A'' に対して、''A'' のすべての[[部分集合]]の集合（''A'' の[[冪集合]]）は ''A'' 自身よりも真に大きい[[濃度 (数学)|濃度]]を持つ。有限集合に対して、カントールの定理は下に与えられる証明よりもはるかにシンプルな証明によって正しいと確かめることができる。''n'' 個の要素からなる集合に対して、空部分集合、ただ 1 つの要素を持つ ''A'' の部分集合、etc. を数えて、{{math|2<sup>''n''</sup>}} 個の部分集合があり、部分集合の集合の濃度は明らかに大きい。{{math|''n'' < 2<sup>''n''</sup>}}。しかし定理は[[無限集合]]にも正しい。特に、[[可算集合|可算無限集合]]の冪集合は[[非可算集合|非可算無限]]である。定理は[[ドイツ]]人[[数学者]][[ゲオルク・カントール]] (Georg Cantor) にちなんで名づけられている。彼が最初にそれを述べ証明した。
| |
| − | | |
| − | ==証明==
| |
| − | 2 つの集合が{{仮リンク|等濃|en|equinumerosity}}である（同じ濃度を持つ）こととそれらの間に[[全単射|一対一対応]]が存在することは同値である。カントールの定理を証明するには任意の与えられた集合 ''A'' に対して、''A'' から ''A'' の[[冪集合]]へのどんな関数 ''f'' も[[全射]]になりえないことを示せば十分である。すなわち ''f'' のもとでの ''A'' の[[像 (数学)|像]]の元でない ''A'' の少なくとも 1 つの部分集合の存在を示せば十分である。そのような部分集合は次の構成によって与えられる：
| |
| − | | |
| − | :<math>B=\left\{\,x\in A : x\not\in f(x)\,\right\}.</math>
| |
| − | | |
| − | これが意味するのは定義によってすべての ''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'' が[[可算無限]]である特別な場合に対して検証しよう。[[一般性を失わない|一般性を失うことなく]] ''X'' = '''N''' = {1, 2, 3,...}, [[自然数]]の集合、ととれる。
| |
| − | | |
| − | '''N''' はその[[冪集合]] '''P'''('''N''') と{{仮リンク|等濃|en|equinumerous}}と仮定する。'''P'''('''''N''''') がどのように見えるか例を見よう：
| |
| − | | |
| − | :<math>P(\mathbb{N})=\{\varnothing,\{1, 2\}, \{1, 2, 3\}, \{4\}, \{1, 5\}, \{3, 4, 6\}, \{2, 4, 6,\dots\},\dots\}.</math>
| |
| − | | |
| − | '''P'''('''N''') は '''N''' の無限個の部分集合を含む、例えばすべての偶数の集合 {2, 4, 6,...}、[[空集合]]。
| |
| − | | |
| − | さて '''P'''('''N''') の元がどのように見えるかのアイデアを持っているから、'''N''' の[[元 (集合論)|元]]を '''P'''('''N''') の各元に、これらの無限集合が等濃であることを示すために、対になるように試みよう。言い換えると、'''N''' の各元が無限集合 '''P'''('''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 は非利己的である。
| |
| − | | |
| − | このアイデアを用いて、自然数のある特別な集合を作ろう。この集合は求める{{仮リンク|矛盾による証明|label=矛盾|en|proof by contradiction}}を提供する。''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''') をカバーしない。
| |
| − | | |
| − | この{{仮リンク|矛盾による証明|en|proof by contradiction}}を通して '''N''' と '''P'''('''N''') の[[濃度 (数学)|濃度]]は等しくはありえないことを示した。'''P'''('''N''') の濃度は '''N''' の濃度よりも小さくなれないことも知っている、なぜならば '''P'''('''N''') は定義によってすべての[[シングルトン]]を含み、これらのシングルトンは '''P'''('''N''') の中で '''N''' の「コピー」をなすからである。したがって、唯一つの可能性が残り、それは、'''P'''('''N''') の濃度は '''N''' の濃度よりも真に大きいことであり、カントールの定理が証明された。
| |
| − | | |
| − | == 歴史 ==
| |
| − | カントールは 1891 年に出版された論文 ''Über eine elementare Frage der Mannigfaltigkeitslehre'' （''多様体論の初等的問題に関して''）においてこの証明を本質的に与えた。そこでは[[実数]]の非可算性のための[[対角線論法]]もまた初めて現れる（彼は{{仮リンク|カントールの第一非可算性証明|label=以前に他の手法によって実数の非可算性を証明していた|en|Cantor's first uncountability proof}}）。その論文で彼が与えたこの議論のバージョンは集合の部分集合よりもむしろ集合上の指示関数の言葉で表現された。彼は ''f'' が ''X'' 上値が 2-値関数である ''X'' 上定義された関数であれば 2-値関数 ''G''(''x'') = 1 − ''f''(''x'')(''x'') は ''f'' の値域に入らないことを示した。
| |
| − | | |
| − | [[バートランド・ラッセル]] (Bertrand Russell) は ''[[:en:Principles of Mathematics|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 つの結果は、[[ベート数]]を参照。
| |
| − | | |
| − | ==関連項目==
| |
| − | * [[ベルンシュタインの定理|カントール・ベルンシュタイン・シュレーダーの定理]] ([[: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}}
| |
| − | | |
| − | == 外部リンク ==
| |
| − | * {{springer|title=Cantor theorem|id=p/c020260}}
| |
| − | * {{MathWorld |title=Cantor's Theorem |id=CantorsTheorem }}
| |
| − | | |
| − | {{Metalogic}}
| |
| − | {{Set theory}}
| |
| − | | |
| − | {{DEFAULTSORT:かんとおるのていり}}
| |
| − | [[Category:集合論]]
| |
| − | [[Category:数学基礎論の定理]]
| |
| − | [[Category:基数]]
| |
| − | [[Category:ゲオルク・カントール]]
| |
| − | [[Category:数学に関する記事]]
| |