カントールの定理

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

内容[編集]

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

証明[編集]

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

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

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

これが意味するのは、定義によってすべての $x \in A$ に対して $x \in B \Leftrightarrow x \notin f (x)$ ということである。すべての $x$ に対して集合 $B$ と $f (x)$ は同じにはなり得ない、なぜならば $B$ は（ $f$ による）像が自身を含まないような $A$ の元から構成されていたからである。より具体的には以下のとおりである。任意の $x \in A$ を考えると、 $x \in f (x)$ かまたは $x \notin f (x)$ である。前者の場合には、 $x \in f (x)$ である一方 $B$ の構成から $x \notin B$ であるため、 $f (x)$ と $B$ は等しくない。後者の場合には、 $x \notin f (x)$ である一方 $B$ の構成から $x \in B$ であるため、やはり $f (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 \notin f (x)$ " において $x$ が 2 回出現するため、これは対角線論法である。

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

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

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

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

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

さて $P (N)$ の具体的な元がわかっているから、これらの無限集合が等濃であることを示すために、 $N$ と $P (N)$ のそれぞれの元をペアにしてみよう。言い換えると、 $N$ の各元が無限集合 $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}}P(\mathbb {N} ).

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

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

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

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

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

定理に基づく結果[編集]

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

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

カントールのパラドックス[編集]

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

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

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

歴史[編集]

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

バートランド・ラッセルは Principles of Mathematics (1903, section 348) において非常によく似た証明をしており、彼は対象よりも命題関数の方がたくさんあることを示した。「すべての対象といくつかの命題関数の相関関係が影響を受けると仮定し、 $φx$ を $x$ の相関とする。すると "not $φx (x)$ " すなわち " $φx$ が $x$ について成り立たない" はこの相関に含まれない命題関数となる。 $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

外部リンク[編集]

Hazewinkel, Michiel, ed. (2001), “Cantor theorem”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Weisstein, Eric W. "Cantor's Theorem". mathworld.wolfram.com (英語).