この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。(2022年2月)
集合 {x, y, z} の濃度は 3 であり、一方その冪集合には 8 つの元が存在し、包含によって順序付けられている
カントールの定理(カントールのていり、Cantor's theorem)は、集合論における基本的な定理の一つで、冪集合の濃度について述べたものである。最初にこれを証明したドイツ人数学者ゲオルク・カントールにちなむ。 任意の集合 A に対して、A のすべての部分集合の集合( A の冪集合)は A 自身よりも真に大きい濃度を持つ。 有限集合に対して定理が成立するのは明らかである。n 個の要素からなる集合に対して、空部分集合、ただ 1 つの要素を持つ A の部分集合、等々……と数えると、 2n 個の部分集合があり、部分集合の濃度は明らかに大きい(n < 2n) 。以下の証明は無限集合に対するものである。 2 つの集合が等濃である(同じ濃度を持つ)こととそれらの間に一対一対応が存在することは同値である。カントールの定理を証明するには、任意の与えられた集合 A に対して、A から A の冪集合へのどんな関数 f も全射になりえないことを示せば十分である。すなわち、 f による A の像の元でない、 A の少なくとも 1 つの部分集合の存在を示せば十分である。そのような部分集合は次の構成によって与えられる: B = { x ∈ A : x ∉ f ( x ) } . {\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\}.} これが意味するのは、定義によってすべての x ∈ A に対して x ∈ B ⇔ x ∉ f (x) ということである。すべての 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 (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 が 2 回出現するため、これは対角線論法である。 証明を理解するために、元の集合が可算無限集合 X である場合を考えよう。一般性を失うことなく X = N = {1, 2, 3,...} (自然数の集合)ととれる。 N とその冪集合 P(N) は等濃と仮定する。P(N) の具体的な例を見よう: P ( N ) = { ∅ , { 1 , 2 } , { 1 , 2 , 3 } , { 4 } , { 1 , 5 } , { 3 , 4 , 6 } , { 2 , 4 , 6 , … } , … } . {\displaystyle 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) の元とペアになるようにして、どちらの無限集合の元もペアにならないまま残ることがないようにする。このように元をペアにすると以下のようになるだろう: N { 1 ⟷ { 4 , 5 } 2 ⟷ { 1 , 2 , 3 } 3 ⟷ { 4 , 5 , 6 } 4 ⟷ { 1 , 3 , 5 } ⋮ ⋮ ⋮ } P ( N ) . {\displaystyle \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} ).}
内容
証明
具体例:可算無限集合の場合
Size:35 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef