カントールの定理 – 日本語百科事典辞書

Cantor’s_theorem

カントールの名前を持つ他の定理にカントールの定理を参照して
数学的集合論では、カントールの定理は基本的な結果であり、任意の集合についてあ { A}
、のすべてのサブセットのセット
あ { A，}
のパワーセット
あ { A，}
より厳密に高いカーディナリティを持つあ { A}
自体。
セット { x ， y ， z }のカーディナリティ
は 3 ですが、そのパワーセットには 8 つの要素 (3 < 2
3 = 8) があり、ここで
は包含順に並べられて
います。
には特殊文字が含まれています。適切な
レンダリングサポートがない場合、
クエスチョンマーク、ボックス、またはその他の記号が表示されることが
有限集合の場合、カントールの定理は部分集合の数を単純に列挙することによって真であることがわかります。空集合を部分集合、 n { n}
要素の合計は2 n
{ 2^{n}}
部分集合であり、定理が成立する理由は2 n> n
{ 2^{n}>n}
すべての非負の整数に対して。
さらに重要なのは、任意の集合に適用できる議論をカントールが発見したことであり、その定理が無限集合にも当てはまることを示しています。結果として、実数のカーディナリティ (整数のベキ集合のカーディナリティと同じ) は、整数のカーディナリティより厳密に大きくなります。詳細については、連続体のカーディナリティを参照して
この定理は、19 世紀末に初めて述べ、証明したドイツの数学者 Georg Cantorにちなんで名付けられました。カントールの定理は、数学の哲学に即座に重要な結果をもたらしました。たとえば、反復的に無限集合のベキ集合を取得し、カントールの定理を適用することによって、無限の基数の無限の階層が得られ、それぞれがその前の基数よりも厳密に大きくなります。したがって、定理は最大の基数がないことを意味します (口語的には、「最大の無限大はありません」)。

コンテンツ
1 証拠
2 Aが可算無限大のとき
3 関連するパラドックス
4 歴史
5 一般化
6 こちらもご覧ください
7 参考文献
8 外部リンク

証拠
カントールの議論はエレガントで驚くほど単純です。完全な証明は以下に示され、詳細な説明が続きます。
定理 (カントール) — しましょうへ { f}
$f""$
セットからのマップであるあ { A}

そのパワーセットに P ( あ ) { {mathcal {P}}(A)}

. それでへ : あ P( あ ) { f:Ato {mathcal {P}}(A)}

は全射ではありません。結果として、
カード( あ) <
カード ( P ( あ) )
{ operatorname {card} (A)
どのセットにも当てはまりますあ { A}
. 証拠
セットを考えるB = {X ε あ
∣X∉ へ (X ) }
{ B={xin Amid xnotin f(x)}}

. 逆にへ { f}

全射です。それから存在しますξ ε あ
{ xi in A}

そのようなへ ( ξ) = B
{ f(xi )=B}

. しかし、構造上、ξ ε B ⟺ ξ∉ へ( ξ) = B
{ xi in Biff xi notin f(xi )=B}

. これは矛盾です。したがって、へ { f}

全射はできません。一方で、g : あ P( あ ) { g:Ato {mathcal {P}}(A)}

によって定義されますX↦ {X }
{ xmapsto {x}}

は単射写像です。したがって、私たちは持っている必要があります
カード( あ) <
カード ( P ( あ) )
{ operatorname {card} (A) . QED カーディナリティの定義により、
カードX ) <
カード( よ ) { operatorname {card} (X)
任意の 2 セットX
{ X}
とよ
{ Y}

からの単射関数はあるが全単射関数がない場合のみX
{ X}
よ
{ Y}

. からの全射がないことを示すだけで十分です。X
{ X}
よ
{ Y}

. これがカントールの定理の核心です: どの集合にも全射関数はありませんあ { A}

そのパワーセットに。これを確立するには、要素をマップする関数fがないことを示すだけで十分ですあ { A}

のサブセットにあ { A}

可能なすべてのサブセットに到達できます。つまり、サブセットの存在を証明する必要があるだけです。あ { A}

それは等しくないへ (X )
{ f(x)}

任意のX
{ x}
ε あ
{ A}

. (それぞれのことを思い出してへ (X )
{ f(x)}

のサブセットですあ { A}

.) そのような部分集合は、次の構成によって与えられ、カントール対角集合と呼ばれることもへ { f}

: B = {X ε あ
∣X∉ へ (X ) } . { B={xin Amid xnot in f(x)}.}

これは、定義により、すべてのx ∈ Aについて、 x ∉ f ( x ) の場合に限り、x ∈ Bであることを意味します。すべてのxについて、セットBとf ( x ) が同じになることはありません。なぜなら、Bは、( fの下の)イメージがそれ自体を含まないAの要素から構築されたからです。より具体的には、任意のx ∈ Aを考えてから、 x ∈ f ( x ) またはx ∉ f ( x ) のいずれかを考えます。前者の場合、仮定によりx ∈ f ( x ) となり、 Bの構成によりx ∉ Bとなるため、 f ( x ) はBと等しくなりません。後者の場合、仮定によりx ∉ f ( x ) となり、 Bの構成によりx ∈ Bとなるため、 f ( x ) はBと等しくなりません。
同様に、もう少し形式的に言えば、 f (ξ) = Bとなるようなξ ∈ Aの存在が次の矛盾を意味することを証明しました。
ξ ( ξ) ⟺ ξ (の定義により B )
; ⟺ ξ ( ξ)(という仮定でへ ( ξ)= B ) ;
{ {begin{aligned}xi notin f(xi )&iff xi in B&&{text{(定義による}}B{text{)}};\xi in B&iff xi in f(xi )&&{text{(仮定}}f(xi )=B{text{)}};\end{aligned}}}

したがって、reductio ad absurdumにより、この仮定は誤りであるに違いありません。したがって、 f (ξ) = Bとなるようなξ ∈ Aはありません。言い換えると、Bはfのイメージになく、fはAのベキ集合のすべての要素にマッピングされません。つまり、fは全射ではありません。
最後に、証明を完了するために、 Aからそのベキ集合への単射関数を示す必要がそのような関数を見つけるのは簡単です: xをシングルトンセット { x }にマップするだけです。これで議論は完了し、カード ( A ) < カード ( ( A )) である任意のセットAに対して厳密な不等式を確立しました。
証明を考えるもう 1 つの方法は、空または空でないBは常にAのベキ集合にあるということです。fをonにするには、 A の一部の要素をBにマップする必要がしかし、それは矛盾につながります: B の要素はBのメンバーシップの基準と矛盾するため、Bにマップできません。したがって、 Bへの要素のマッピングは、Bのメンバーシップの基準を満たすことを意味するBの要素であってはなりません。もう一つの矛盾。したがって、 Aの要素がBにマップされるという仮定は偽でなければなりません。fは onにできません。
式 “” x ∉ f ( x )”” でxが 2 回出現するため、これは対角引数です。可算 (または有限) セットの場合、上記の証明の議論は、各行がA = { x 1 ， x 2 ， …}からの一意のxでラベル付けされたテーブルを作成することによって説明できます。注文。Aは、そのようなテーブルを構築できるように、線形順序を受け入れると仮定されます。テーブルの各列には、 A のベキ集合から一意の y のラベルが付けられます。列はfへの引数によって順序付けられます。つまり、列ラベルはf ( x 1 )、f ( x 2 )、…、この順序です。各行xと列yの交点は、 x ∈ yかどうかの true/false ビットを記録します。行ラベルと列ラベルに選択された順序が与えられると、このテーブルの主対角線Dは、各x ∈ Aについてx ∈ f ( x ) かどうかを記録します。前の段落で構築された集合Bは、この主対角線D上のエントリのサブセットの行ラベルと一致します。ここで、テーブルはx ∈ f ( x ) が false であることを記録しています。各列には、列に対応するセットの指標関数の値が記録されます。Bの指標関数は、主対角要素の論理的に否定された(「真」と「偽」を入れ替えた) エントリと一致します。したがって、 Bの指標関数は、少なくとも 1 つのエントリのどの列とも一致しません。したがって、Bを表す列はありません。
上記の証明は単純ですが、自動化された定理証明者がそれを作成するのはかなり困難です。主な困難は、カントール対角集合の自動発見にローレンス・ポールソンは 1992 年に、おそらく不正行為と見なされる可能性のある戦術に関してある程度の方向性はあるものの、オッターにはそれができなかったのに対し、イザベルにはできたと述べました。

Aが可算無限大のとき
特定の場合の証明を調べてみましょう。あ { A}

可算無限です。一般性を失うことなく、自然数の集合A = N = {1， 2， 3， …}を取ることができます。
Nがそのベキ集合 ( N ) と同数であると仮定します。 ( N ) がどのように見えるかのサンプルを見てみましょう: P ( N)= {
∅ { 1 2 } {
1 2 3
} { 4 } { 1 5 } {
3 4 6
} {
2 4 6 …
} …} .
{ {mathcal {P}}(mathbb {N} )={varnothing ，{1，2}，{1，2，3}，{4}，{1 ，5}，{3，4，6}，{2，4，6，ドット}，ドット}.}

( N ) にはNの無限の部分集合が含まれます。たとえば、すべての偶数の集合 {2， 4， 6，…} と空の集合です。
( N ) の要素がどのように見えるかがわかったので、 Nの各要素と ( N ) の各要素をペアにして、これらの無限集合が等数であることを示します。言い換えると、Nの各要素を無限集合 ( N ) の要素とペアにして、どちらの無限集合の要素もペアにならないままにしないようにします。要素をペアにする試みは次のようになります。N { 1 ⟷
{4 5 } 2 ⟷ { 1 2 3} 3 ⟷ { 4 5 6} 4 ⟷ { 1 3 5 } ⋮ } 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}}{mathcal {P}}(mathbb {N} ) .}

このようなペアリングが与えられると、一部の自然数は、まったく同じ数を含むサブセットとペアになります。たとえば、この例では、数値 2 はサブセット {1， 2， 3} とペアになっており、メンバーとして 2 が含まれています。そのような数字をわがままと呼びましょう。他の自然数は、それらを含まないサブセットとペアになっています。たとえば、この例では、数値 1 は、数値 1 を含まないサブセット {4， 5} とペアになっています。これらの数値をnon-selfish と呼びます。同様に、3 と 4 は非利己的です。
この考えを使用して、自然数の特別なセットを構築しましょう。このセットは、私たちが求める矛盾を提供します。Bをすべての非利己的な自然数の集合とします。定義上、冪集合 ( N ) には自然数のすべての集合が含まれるため、この集合Bが要素として含まれます。マッピングが全単射の場合、Bはbなどの自然数とペアにする必要がただし、これにより問題が発生します。bがBにある場合、 bは対応するセットにあるため利己的であり、 Bの定義と矛盾します。bがBにない場合、それは非利己的であり、代わりにBのメンバーであるべきです。したがって、 Bにマップされる要素bは存在しません。
Bと対になる自然数は存在しないため、 Nと ( N )の間に全単射があるという当初の仮定に矛盾が生じました。
セットBは空である場合があることに注意してこれは、すべての自然数xが、 xを含む自然数のサブセットにマップされることを意味します。次に、すべての数値が空でないセットにマップされ、数値が空のセットにマップされません。しかし、空集合は ( N ) のメンバーであるため、マッピングはまだ ( N )をカバーし
この矛盾による証明を通じて、Nと ( N ) の基数が等しくないことが証明されました。また、定義上、 ( N ) にはすべてのシングルトンが含まれており、これらのシングルトンは ( N )内のNの「コピー」を形成するため、 ( N )のカーディナリティはNのカーディナリティよりも小さくならないこともわかっています。したがって、残る可能性は 1 つだけです。つまり、 ( N ) の基数はNの基数より厳密に大きく、カントールの定理が証明されます。

関連するパラドックス
カントールの定理とその証明は、集合論の2 つのパラドックスと密接に関連しています。
カントールのパラドックスは、カントールの定理と、すべての集合を含む集合、普遍集合が存在するという仮定から導かれる矛盾に付けられた名前です。 Ⅴ { V}

. このパラドックスを以下で説明する次のパラドックスと区別するために、この矛盾が何であるかに注意することが重要です。カントールの定理より
| |P X )
| | > | |X
| |
{ |{mathcal {P}}(X)|>|X|}
|X|}””>
どのセットでもX
{ X}

. 一方、のすべての要素 P ( Ⅴ ) { {mathcal {P}}(V)}

はセットであり、したがって、 Ⅴ { V}

、したがって
| | P ( Ⅴ ) | | ≤ | | Ⅴ | |
{ |{mathcal {P}}(V)|leq |V|}

.
関数fを恒等関数でインスタンス化することにより、カントールの定理の証明から別のパラドックスを導き出すことができます。これは、カントールの対角集合を、与えられた集合Aのラッセル集合と呼ばれることもあるに変えます。R あ = {X εあ :X
∉X
{ R_{A}=left{，xin A:xnot in x，right}.}
カントールの定理の証明は、すべての集合の集合Uが存在すると仮定すると、そのラッセル集合R Uを考慮すると、矛盾が生じることを示すように単純に適応されます。R う ε R う
⟺R う ∉ R う . { R_{U}in R_{U}iff R_{U}notin R_{U}.}
この議論は、ラッセルのパラドックスとして知られています。微妙な点として、ここで示したラッセルのパラドックスのバージョンは、実際にはゼルメロの定理です。得られた矛盾から、R U ∈ Uという仮説を棄却しなければならないと結論付けることができ、したがって、すべてのセットを含むセットの存在が反証されます。これが可能だったのは、上記のR Aの定義で( ZFCで取り上げられているように)制限された内包表記を使用したためです。R う ε R う ⟺ ( Rう ε う ∧ R
う∉ R う ) .
{ R_{U}in R_{U}iff (R_{U}in Uwedge R_{U}notin R_{U}).}
ラッセル集合を単純にR = {X :X ∉X } { R=left{，x:xnot in x，right}}

、その場合、公理システム自体が矛盾を伴い、それ以上の仮説は必要ありません.
ラッセル集合 (どちらのバリアントでも) とカントール対角集合の間の構文上の類似性にもかかわらず、アロンゾチャーチは、ラッセルのパラドックスは、カーディナリティの考慮事項や、1 対 1 対応などのその根底にある概念とは無関係であることを強調しました。

歴史
カントールは、1891 年に発表された論文「Über eine elementare Frage der Mannigfaltigkeitslehre」で本質的にこの証明を行いました。ここで、実数の不可算性に対する対角線の議論も最初に現れます (彼は以前に他の方法で実数の不可算性を証明していました) 。 . 彼がその論文で示したこの議論のバージョンは、セットのサブセットではなく、セットの指標関数の観点から表現されていました。彼は、fがX上の 2 値関数であるXで定義された関数である場合、2 値関数G ( x ) = 1 − f ( x )( x ) はfの範囲にないことを示しました。
バートランド・ラッセルはPrinciples of Mathematics (1903， section 348) で非常によく似た証明をしており、オブジェクトよりも多くの命題関数があることを示しています。「すべてのオブジェクトといくつかの命題関数の相関関係が影響を受けたと仮定し、ファイxをxの相関とする。すると、「非ファイx ( x )」、つまり「ファイxはxを保持しない」 “” はこの相関関係に含まれていない命題関数です。なぜなら、φ- x が x の偽または真であるように、それは x の真または偽であり、したがってxのすべての値に対してphi- xとは異なるからです。”” 彼は証明の背後にあるアイデアをカントールに帰しています。
Ernst Zermeloは、1908 年に出版された現代集合論の基礎となった論文 (「Untersuchungen über die Grundlagen der Mengenlehre I」) の上記の形式と同一の定理 (彼は「カントールの定理」と呼んでいます) を持っています。Zermelo を参照してセット理論。

一般化
カントールの定理は、積を持つ任意のカテゴリに一般化されています。

こちらもご覧ください
シュレーダー・バーンスタインの定理
カントールの最初の不可算証明.
カントールの理論に関する論争

参考文献
^ Abhijit Dasgupta （2013). 集合論: 実点集合の紹介付き. スプリンガーサイエンス & ビジネスメディア. pp.362–363。ISBN 978-1-4614-8854-5.
^ ローレンス・ポールソン (1992)。Theory を Computational Logic (PDF)として設定します。ケンブリッジ大学コンピューター研究所。p。14.
^ グラハム・プリースト（2002)。思考の限界を超えて。オックスフォード大学出版局。pp.118–119。ISBN 978-0-19-925405-7.
^ ハインツ・ディーター・エビングハウス（2007)。Ernst Zermelo：彼の人生と仕事へのアプローチ。スプリンガーサイエンス & ビジネスメディア。86 ～87ページ。ISBN 978-3-540-49553-6. ^ Church， A. 「普遍集合による集合論」。Tarski シンポジウムの議事録。Pure Mathematics XXV のシンポジウム議事録、編。L. Henkin、プロビデンス RI、1979 年追加の第 2 刷、pp. 297-308。
ISBN 978-0-8218-7360-1 . International Logic Review 15 pp. 11-23にも掲載されています。
^Cantor， Georg (1891)， “”Über eine elementare Frage der Mannigfaltigskeitslehre” ， Jahresbericht der Deutschen Mathematiker-Vereinigung (ドイツ語)， 1 : 75–78、Georg Cantor、Gesammelte Abhandlungen mathematischen und philosophischen Inhalts、E. Zermelo、1932年にも
^ F. ウィリアムロービア; スティーブン H. シャヌエル（2009)。概念数学: カテゴリの最初の紹介. ケンブリッジ大学出版局。セッション 29. ISBN 978-0-521-89485-2.
ハルモス、ポール、単純集合論。Princeton， NJ: D. Van Nostrand Company， 1960. Springer-Verlagにより転載，ニューヨーク， 1974.
ISBN 0-387-90092-6 (Springer-Verlag 版)。マルティーノファインブックス、2011 年に再版。
ISBN 978-1-61427-131-4 (ペーパーバック版)。
Jech， Thomas （2002)， Set Theory ， Springer Monographs in Mathematics (3rd millennium ed.)， Springer， ISBN 3-540-44085-2

外部リンク
「カントールの定理」、数学百科事典、EMS プレス、2001
Weisstein、Eric W. 「カントールの定理」。マスワールド.”