この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "冪集合"
冪集合(べきしゅうごう、英: power set)とは、数学において、与えられた集合から、その部分集合の全体として新たに作り出される集合のことである。べきは冪乗の冪(べき)と同じもので、冪集合と書くのが正確だが、一部分をとった略字として巾集合とも書かれる。
集合と呼ぶべき対象を公理的にかつ構成的に与える公理的集合論では、新たに作られた原体の冪集合もしくはそれに準ずる複数の冪集合が、それぞれの連続性に関わらず集合と呼ばれるべきもののうちにあることを公理の一つ(冪集合公理)としてしばしば提示する。 集合 S {\displaystyle S} の冪集合は、冪を表す power からとって、通常は P ( S ) , P ( S ) , p o w ( S ) , P o w e r ( S ) , Π ( S ) , P ( S ) {\displaystyle {\mathfrak {P}}(S),\ {\mathcal {P}}(S),\ {\mathfrak {pow}}(S),\ \mathrm {Power} (S),\ \Pi (S),\;\mathbb {P} (S)} , ℘(S), 2S などのように記される。2S という表記は、一般に XY が Y から X への写像全体の集合を表すことによる(後述)。 集合 S が与えられたとき、S のすべての部分集合からなる集合 P ( S ) := { A : a set ∣ A ⊆ S } {\displaystyle {\mathfrak {P}}(S):=\{A\colon {\mbox{a set}}\mid A\subseteq S\}} を S の冪集合と呼ぶ。例えば などとなる。空集合の冪集合は空集合を唯一つの元として持つ一元集合であり、空集合とは別のものである。 なおこの定義から明らかに A ∈ P ( S ) ⟺ A ⊂ S {\displaystyle A\in {\mathfrak {P}}(S)\iff A\subset S} である。 冪集合は包含関係を順序として順序集合になる。冪集合を底となる集合、包含関係を順序とする順序集合 ( P ( S ) , ⊂ ) {\displaystyle ({\mathcal {P}}(S),\subset )} (ここでの ⊂ {\displaystyle \subset } は集合が一致する場合も含む)に順序同型な順序集合は単体様半順序集合 (simplex-like Poset) と呼ばれ、単体の一つの組合せ論的な特徴づけを与える(底となる P ( S ) {\displaystyle {\mathcal {P}}(S)} から空集合を抜いた順序集合を指すこともある)。また、冪集合 P ( S ) {\displaystyle {\mathcal {P}}(S)} に包含関係と逆の順序 ⊂ o p p {\displaystyle \subset ^{\mathrm {opp} }} A ⊂ o p p B ⟺ A ⊃ B {\displaystyle A\subset ^{\mathrm {opp} }B\iff A\supset B} を与えた順序集合 ( P ( S ) , ⊂ o p p ) {\displaystyle ({\mathcal {P}}(S),\subset ^{\mathrm {opp} })} は、もとの順序集合 ( P ( S ) , ⊂ ) {\displaystyle ({\mathcal {P}}(S),\subset )} に順序同型で、その対応は補集合をとる操作 ( P ( S ) , ⊂ o p p ) ∋ A ⟼ ≃ A c = S ∖ A ∈ ( P ( S ) , ⊂ ) {\displaystyle ({\mathcal {P}}(S),\subset ^{\mathrm {opp} })\ni A\ {\stackrel {\simeq }{\longmapsto }}\ A^{c}=S\smallsetminus A\in ({\mathcal {P}}(S),\subset )} によって与えられる。またこの対応で、集合の結びと交わりが互いに入れ替わる(双対性:ド・モルガンの法則)、対称差は不変(自己双対性)などを見て取ることができる。 順序集合 ( P ( S ) , ⊂ ) {\displaystyle ({\mathcal {P}}(S),\subset )} の部分集合である集合族 M ⊂ P ( S ) {\displaystyle {\mathfrak {M}}\subset {\mathcal {P}}(S)} が与えられたとき、集合族の結びや交わりをとる操作 sup ( M ) = ⋃ M = ⋃ m ∈ M m , inf ( M ) = ⋂ M = ⋂ m ∈ M m {\displaystyle \sup({\mathfrak {M}})=\bigcup {\mathfrak {M}}=\bigcup _{m\in {\mathfrak {M}}}m,\quad \inf({\mathfrak {M}})=\bigcap {\mathfrak {M}}=\bigcap _{m\in {\mathfrak {M}}}m} は、この集合族に対して包含関係による順序に関する上限と下限を与える。とくに、 S {\displaystyle S} の二つの部分集合 A , B {\displaystyle A,B} について A ∨ B := sup { A , B } = A ∪ B {\displaystyle A\vee B:=\sup\{A,B\}=A\cup B} A ∧ B := inf { A , B } = A ∩ B {\displaystyle A\wedge B:=\inf\{A,B\}=A\cap B} を考えることにより、組 ( P ( S ) , ∧ , ∨ ) {\displaystyle ({\mathcal {P}}(S),\land ,\lor )} は完備束となる。完備束の条件は空で無い部分集合族に対する上限・下限の存在を要求するものであるが、冪集合の束では集合族 M ⊂ P ( S ) {\displaystyle {\mathfrak {M}}\subset {\mathcal {P}}(S)} が空集合であるときにも sup ( ∅ ) = ∅ , inf ( ∅ ) = S {\displaystyle \sup(\varnothing )=\varnothing ,\quad \inf(\varnothing )=S} が冪集合 P ( S ) {\displaystyle {\mathcal {P}}(S)} の中に存在する。
記法
定義
P ( ∅ ) = { ∅ } {\displaystyle {\mathfrak {P}}(\varnothing )=\{\varnothing \}}
P ( { a } ) = { ∅ , { a } } {\displaystyle {\mathfrak {P}}(\{a\})=\{\varnothing ,\{a\}\}}
P ( { x , y } ) = { ∅ , { x } , { y } , { x , y } } {\displaystyle {\mathfrak {P}}(\{x,y\})=\{\varnothing ,\{x\},\{y\},\{x,y\}\}}
P ( { 1 , 2 , 3 } ) = { ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } {\displaystyle {\mathfrak {P}}(\{1,2,3\})=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}}
構造
包含関係による順序
Size:31 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef