カントールの定理
初等的な集合論において、カントールの定理 (Cantor's theorem) は次のように述べている。任意の集合 A に対して、A のすべての部分集合の集合（ A の冪集合）は A 自身よりも真に大きい濃度を持つ。有限集合に対して、カントールの定理は下に与えられる証明よりもはるかにシンプルな証明によって正しいと確かめることができる。n 個の要素からなる集合に対して、空部分集合、ただ 1 つの要素を持つ A の部分集合、etc. を数えて、 2ⁿ 個の部分集合があり、部分集合の集合の濃度は明らかに大きい。n < 2ⁿ 。しかし定理は無限集合にも正しい。特に、可算無限集合の冪集合は非可算無限である。定理はドイツ人数学者ゲオルク・カントール (Georg Cantor) にちなんで名づけられている。彼が最初にそれを述べ証明した。
歴史
カントールは 1891 年に出版された論文 Über eine elementare Frage der Mannigfaltigkeitslehre （多様体論の初等的問題に関して）においてこの証明を本質的に与えた。そこでは実数の非可算性のための対角線論法もまた初めて現れる（彼は以前に他の手法によって実数の非可算性を証明していた）。その論文で彼が与えたこの議論のバージョンは集合の部分集合よりもむしろ集合上の指示関数の言葉で表現された。彼は f が X 上値が 2-値関数である X 上定義された関数であれば 2-値関数 G (x) = 1 − f (x)(x) は f の値域に入らないことを示した。
バートランド・ラッセル (Bertrand Russell) は 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 つの結果は、ベート数を参照。