電源セット

数学では、集合Sの冪集合(または冪集合)は、空集合とS自体を含むSのすべての部分集合の集合です。 ^{[ 1 ]}公理的集合論(例えばZFC公理で展開されているように)では、任意の集合の冪集合の存在は冪集合の公理によって仮定されています。^{[ 2 ]} S の冪集合は、 P ( S )、𝒫 ( S )、P ( S )などと様々に表記されます。${\displaystyle \mathbb {P} (S)}$、または2 ^S。^{[ a ]} P ( S ) の任意の部分集合は、 S上の集合の族と呼ばれます。

Sが集合{ x , y , z }である場合、 Sのすべての部分集合は次のようになります。

• {} (空集合、または表記される)${\displaystyle \varnothing }$または${\displaystyle \emptyset }$）
• { x }
• { y }
• { z }
• { x , y }
• { x , z }
• { y , z }
• { x , y , z }

したがって、 Sの冪集合は{{}, { x }, { y }, { z }, { x , y }, { x , z }, { y , z }, { x , y , z }}である。^{[ 3 ]}

S が要素数| S | = nの有限集合である場合(つまり、集合Sのすべての要素の数がnである場合)、 Sのすべての部分集合の数は| P ( S ) | = 2n^となります。この事実、および2S^が冪集合P ( S )を表す理由については、以下で説明します。

集合Sの要素数| S | = nの部分集合Aの指示関数または特性関数は、 Sから2 要素集合{0, 1}への関数であり、I _A : S → {0, 1}と表記され、 Sの要素がAに属するかどうかを示します。Sのx がAに属する場合、I _A ( x ) = 1となり、そうでない場合は0 となります。Sの各部分集合Aは指示関数I Aによって識別されるか、または同等であり、{0,1} ^SはSから{0, 1}へのすべての関数の集合として、_Sのすべての部分集合のすべての指示関数から構成されます。言い換えれば、{0, 1} ^Sは冪集合P ( S )と同等または全単射です。Sの各要素は、 {0, 1} ^Sの任意の関数の下で0または1に対応するため、 {0, 1} ^Sのすべての関数の数は2 ⁿです。数2 は{0, 1}と定義できるため(例えば、フォン・ノイマン順序数を参照)、P ( S )は2 ^Sとも表記されます。明らかに| 2 ^S | = 2 ^{| S |}が成り立ちます。一般に、X ^YはYからXへのすべての関数の集合であり、| X ^Y | = | X | ^{| Y |}です。 

カントールの対角線論法は、集合（無限集合か否かを問わず）の冪集合の濃度は常に元の集合よりも厳密に高い（あるいは非公式に言えば、冪集合は元の集合よりも大きい）ことを示している。特に、カントールの定理は、可算無限集合の冪集合は非可算無限であることを示している。自然数の集合の冪集合は、実数の集合と1対1に対応させることができる（連続体の濃度を参照）。

集合Sの冪集合は、和集合、積集合、補集合の演算とともに、S上のσ 代数であり、ブール代数の典型的な例と見なすことができます。実際、任意の有限ブール代数は、有限集合の冪集合のブール代数と同型であることが示せます。無限ブール代数の場合、これはもはや成り立ちませんが、すべての無限ブール代数は、冪集合ブール代数の部分代数として表現できます (ストーンの表現定理を参照)。

集合Sの冪集合は、対称差演算(空集合を単位元とし、各集合を自身の逆元とする)で考えるとアーベル群を形成し、積演算 (集合S全体を単位元とする) で考えると可換モノイドを形成します。したがって、分配法則を証明することにより、これら 2 つの演算で考えられた冪集合がブール環を形成することが示されます。

集合論において、XY^はYからXへのすべての関数の集合を表す表記です。「2 」は{0, 1}と定義できるため(例えば、フォン・ノイマン順序数を参照)、2S (すなわち、{0, 1} ^{S )は}Sから{0, 1}へのすべての関数の集合です。上記のように、2Sと^Sの冪集合P ( S )は、集合論的には同一とみなされます。

この等価性は、上記の例（ S = { x , y , z }）に適用して、 0 から2 ⁿ − 1までの数の二進表現との同型性を得ることができます。ここで、nは集合Sの要素の数、つまり| S | = nです。まず、列挙された集合{ ( x , 1), ( y , 2), ( z , 3) }が定義されます。各順序対の数値は、 { x , y } = 011 ₍₂₎のような二進数のシーケンスにおけるSのペアの要素の位置を表します。Sのxはこのシーケンスの右から 1 番目に位置し、yは右から 2 番目に位置します。シーケンスの 1 は、シーケンス内のその位置に対応するSの要素がシーケンスのSの部分集合に存在することを意味し、0 は存在しないことを意味します。

Sの冪集合全体について、次の式が得られます。

P ( S )から整数へのこのような単射写像は任意であるため、 Sのすべての部分集合のこの表現は一意ではありませんが、列挙された集合の順序は濃度を変えません。（例えば、{( y , 1), ( z , 2), ( x , 3)}を使用して、 1対1対応の数を変えることなく、 P ( S )から整数への別の単射写像を構築できます。）

しかし、このような有限の二進数表現は、S を列挙できる場合にのみ可能です。（この例では、x、y、zはそれぞれ二進数列の位置として1、2、3で列挙されます。） Sの濃度が無限（つまり、 Sの要素数が無限）であっても、例えば整数や有理数の集合のように列挙は可能ですが、例えばS が実数の集合である場合は不可能です。この場合、すべての無理数を列挙することはできません。

二項定理は冪集合と密接に関係しています。ある集合からのk個の要素の組み合わせは、 k個の要素からなる部分集合の別名です。したがって、組み合わせの数C( n , k ) (二項係数とも呼ばれる) は、 n個の要素を持つ集合におけるk個の要素を持つ部分集合の数です。言い換えれば、n個の要素を持つ集合の冪集合の要素であるk個の要素を持つ集合の数です。

例えば、3つの要素を持つ集合の冪集合は次のようになります。

• C(3, 0) =要素が0個の部分集合(空の部分集合)、
• C(3, 1) = 1つの要素を持つ3つの部分集合（単一要素部分集合）、
• C(3, 2) = 2つの要素を持つ3つの部分集合（単一要素部分集合の補集合）、
• C(3, 3) = 3つの要素を持つ1つの部分集合（元の集合自体）。

この関係式を用いると、 | 2S |^を次の式で計算できます。 $$\displaystyle \left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}}$$

したがって、 | S | = nと仮定すると、次の恒等式を導き出すことができる。 $${\displaystyle \left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}}$$

Sが有限集合である場合、P ( S )の再帰的定義は次のように進められます。

• S = {}の場合、P ( S ) = { {} }となります。
• それ以外の場合は、e ∈ SおよびT = S ∖ { e }とします。このとき、P ( S ) = P ( T ) ∪ { t ∪ { e }  : t ∈ P ( T )}となります。

言葉で表すと：

• 空集合の冪集合は、唯一の要素が空集合である単集合である。
• 空でない集合Sに対して、${\displaystyle e}$を集合の任意の要素とし、Tをその相対補集合とすると、 Sの冪集合は、Tの冪集合と、各要素がe要素で拡張されたTの冪集合の和集合となる。

Sの部分集合のうち、濃度がκ以下のものは、 P _κ ( S )または[ S ] ^κと表記されることがあり、濃度がκより厳密に小さい部分集合は、P _{< κ} ( S )または[ S ] ^{< κ}と表記されることがあります。同様に、 Sの空でない部分集合の集合は、P _≥1 ( S )またはP ⁺ ( S )と表記されることがあります。

集合は、非自明な演算や定義方程式を持たない代数とみなすことができる。この観点から、 Xのすべての部分集合の集合としてのXの冪集合の概念は、代数構造または代数のすべての部分代数の集合に自然に一般化される。^{[ 4 ] [ 5 ]}

包含関係によって順序付けられた集合の冪集合は、常に完全な原子ブール代数であり、すべての完全な原子ブール代数は、ある集合のすべての部分集合の束として生じます。任意の代数への一般化は、再び包含関係によって順序付けられた代数の部分代数の集合は常に代数束であり、すべての代数束はある代数の部分代数の束として生じます。^{[ 6 ]}したがって、その点において、部分代数は部分集合と類似した振る舞いをします。

しかし、部分集合には、一般に部分代数には当てはまらない重要な性質が2つあります。まず、集合の部分集合は集合（および束）を形成しますが、一部のクラスでは、代数の部分代数をそのクラスの代数として整理することができない場合があります。ただし、部分代数は常に束として整理することができます。次に、集合の部分集合は、その集合から集合{0, 1} = 2への関数と一対一ですが、代数のクラスに、このように2の役割を果たすことができる代数が含まれているという保証はありません。

代数の特定のクラスは、これらの性質の両方を有しています。最初の性質の方が一般的ですが、両方を有するケースは比較的まれです。両方を有するクラスの1つは、多重グラフです。2つの多重グラフGとHが与えられたとき、準同型写像h  : G → Hは、頂点を頂点に写像する関数と、辺を辺に写像する関数の2つから構成されます。GからHへの準同型写像の集合H G^は、その集合に現れる頂点関数と辺関数をそれぞれ頂点と辺とするグラフとして構成できます。さらに、多重グラフGの部分グラフは、2つの頂点（したがって4つの辺、すなわち2つの自己ループとサイクルを形成する2つの辺）上の完全有向グラフに5番目の辺、すなわちいずれかの頂点での2番目の自己ループを追加したグラフΩへのGから多重グラフへのグラフ準同型写像と一対一です。したがって、 Gの部分グラフを多重グラフΩ ^Gとして整理することができ、これはGのパワーオブジェクトと呼ばれます。

多重グラフが代数として特別なのは、その演算が単項であることです。多重グラフは、頂点の集合Vと辺の集合Eを形成する 2 種類の要素を持ち、各辺の始点 (開始) 頂点と終点 (終了) 頂点を与える2 つの単項演算s、t  : E → Vを持ちます。すべての演算が単項である代数を前層と呼びます。前層のクラスには、部分代数に対して2 が部分集合に対して果たす役割を果たす前層Ωが含まれます。このようなクラスは、閉じた(さらにデカルト的に閉じた)圏であり、部分対象分類子と呼ばれる対象Ωを持つ、より一般的な概念である初等トポスの特殊なケースです。「べき対象」という用語は、指数対象Y ^Xと同義語として使用されることがありますが、トポス理論ではY はΩである必要があります。^{[ 7 ]}

共変および反変の冪集合ファンクター、P : Set → SetおよびP : Set ^op → Setが存在する。共変ファンクターは、集合SをP ( S )に、射f : S → T (ここでは集合間の関数) を像射に送るファンクターとして、より簡単に定義される。つまり、A = { x ₁ , x ₂ , ...} ∈ P ( S ) に対して、P f ( A ) = { f ( x ₁ ), f ( x ₂ ), ...} ∈ P ( T )となる。この記事の別の箇所では、冪集合はSから 2 つの要素を持つ集合への関数の集合として定義されている。形式的には、これは自然な同型P ≅ Set(-,2)を定義する。反変冪集合ファンクターは、f を前像射に送る点で共変バージョンとは異なり、 f ( A ) = B ⊆ Tの場合、P f ( B ) = Aとなります。これは、一般ファンクターC(-, c )が射h : a → b をhによる前合成に送るため、関数h *: C( b , c ) → C( a , c )は、 bからcへの射を受け取り、 b を介して hを介してaからcへの射に送るからです。^{[ 8 ]}

圏論および基本トポスの理論では、全称量化子は冪集合間の関手の右随伴、集合間の関数の逆像関手として理解できます。同様に、存在量化子は左随伴です。^{[ 9 ]}

• カントールの定理
• 集合の族
• 集合の体
• 組み合わせ
• クリーネ・スター

• デブリン、キース・J. (1979).現代集合論の基礎. ユニバーシテキスト.シュプリンガー・フェルラーク. ISBN 0-387-90441-7. Zbl 0407.04003 . 
• Halmos, Paul R. (1960).素朴な集合論. 大学学部数学シリーズ. van Nostrand Company. Zbl 0087.04403 . 
• Mac Lane, Saunders ; Moerdijk, Ieke (1992), Sheaves in Geometry and Logic , Springer-Verlag, ISBN 0-387-97710-4
• Puntambekar, AA (2007).オートマタと形式言語の理論. Technical Publications. ISBN 978-81-8431-193-8。
• Weisstein, Eric W. 「Power Set」 . mathworld.wolfram.com . 2023年4月6日時点のオリジナルよりアーカイブ。 2020年9月5日取得。

• PlanetMathで設定されたパワーセット。
• nラボで設定された電力
• n Labのパワーオブジェクト
• C++におけるべき集合アルゴリズム