カントールの定理とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > カントールの定理の意味・解説 

カントールの定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/12/10 16:21 UTC 版)

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

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

内容

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

証明

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

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

これが意味するのは、定義によってすべての xA に対して xBxf (x) ということである。すべての x に対して集合 Bf (x) は同じにはなり得ない、なぜならば B は( f による)像が自身を含まないような A の元から構成されていたからである。より具体的には以下のとおりである。任意の xA を考えると、 xf (x) かまたは xf (x) である。前者の場合には、 xf (x) である一方 B の構成から xB であるため、 f (x)B は等しくない。後者の場合には、 xf (x) である一方 B の構成から xB であるため、やはり f (x)B は等しくない。

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

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

式 "xf (x)" において x が 2 回出現するため、これは対角線論法である。

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

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

N とその冪集合 P(N)等濃と仮定する。P(N) の具体的な例を見よう:

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

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

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

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

D とペアにできる自然数は存在しないから、もとの仮定「 NP(N) の間に全単射が存在すること」に矛盾する。

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

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

定理に基づく結果

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

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

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

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

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

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

歴史

カントールは 1891 年に出版された論文 Über eine elementare Frage der Mannigfaltigkeitslehre多様体論の初等的問題に関して)においてこの証明を本質的に与えた。この論文では実数の非可算性のための対角線論法もまた初めて現れる(なお、カントールは以前に他の手法によって実数の非可算性を証明していた英語版)。この論文における証明は、集合の部分集合ではなく集合上の指示関数の言葉で表現された。カントールは、 fX 上で定義された X の 2-値関数とすると 2-値関数 G (x) = 1 − f (x)(x)f の値域に含まれないことを示した。

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

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

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

関連項目

参考文献

  • 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 

外部リンク


カントールの定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/01 07:08 UTC 版)

カントールの対角線論法」の記事における「カントールの定理」の解説

詳細は「カントールの定理」を参照 カントールの定理とは次のようなものである定理 Xを任意の集合とするとき、XからXの冪集合2Xへの全射存在しない(従って特に全単射存在しない)。つまり、Xの濃度より2X濃度のほうが真に大きい。 これは以下のように対角線論法用いて次のように示される。 Xから2Xへの全射ψが存在したとする。 Y = { x ∈ X : x ∉ ψ ( x ) } {\displaystyle Y=\{x\in X:x\notin \psi (x)\}} により定義すると、対角線論法より、ψ(x)=Yとなるx∈Xは存在しない。これはψの全射性反する。 上の Y の構成ラッセルのパラドックス用いられる自分自身含まないような集合」と酷似していることに注意されたい。X を「全ての集合を含む集合」として同じことを行うと、2X は X の部分集合ありながらしかも X より濃度大きくなり矛盾生じる(カントールのパラドックス)。したがって、(公理的集合論立場では)「すべての集合を含む集合」は集合ではなくクラスになる。

※この「カントールの定理」の解説は、「カントールの対角線論法」の解説の一部です。
「カントールの定理」を含む「カントールの対角線論法」の記事については、「カントールの対角線論法」の概要を参照ください。

ウィキペディア小見出し辞書の「カントールの定理」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「カントールの定理」の関連用語

カントールの定理のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



カントールの定理のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのカントールの定理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのカントールの対角線論法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS