冪集

维基百科,自由的百科全书
跳转至: 导航搜索

數學上,給定集合S,其冪集\mathcal{P}(S)(或作2^S)是以S的全部子集為元素的集合。以符號表示即為

\mathcal{P}(S) := \{U | U \subseteq S\}

公理集合論(例如ZFC集合論)中,冪集公理假定了任何集合的冪集均存在。

\mathcal{P}(S)的任何子集F稱為S上的集族

例子[编辑]

S是集合\{a, b, c\},則S的全部子集如下:

因此S的冪集為

\mathcal{P}(S) = \{\varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}\,\!

性質[编辑]

S是有限集,有|S|=n個元素,那麼S的冪集有|\mathcal{P}(S)| = 2^n個元素。(其實可以——事實上電腦就是這樣做的——將\mathcal{P}(S)的元素表示為n位二進制數;第n位表示包含或不含S的第n個元素。這樣的數總共有2^n個。)

我們也可以考慮無窮集的冪集。以对角论证法可證明一個集合(不論是否無窮)的冪集的基數總是大於原來集合的基數(粗略的說,集合的冪集必然大於原來集合)。例如正整數集的冪集可以一一對應實數集(把一個無窮0-1序列對應於那些包含有1出現的指數的集合。例如,\{1,3\}對應於序列(1,0,1,0,0,0,\ldots)\{2,4,6,8,\ldots\}對應於序列(0,1,0,1,0,1,0,1,\ldots) )。

集合S的冪集,加上併、交和補運算,就得出布爾代數的原始例子。事實上,我們可以證明所有有限布爾代數都是同構於某有限集的冪集的布爾代數。這結果雖然對無窮布爾代數不成立,但是所有無窮布爾代數都是某個冪集布爾代數的子代數。

集合S的冪集與對稱差運算構成一個阿貝爾群(其中空集為幺元,每個集合的逆元為其本身),與交運算一起則構成交換半群。因此這兩個運算跟冪集(透過證明分配律)一起構成一個交換

2S的記法[编辑]

集合論中,X^Y是由所有從YX的函數構成的集合。因為2可以定義為\{0,1\}(見自然數),2^S這集合包含了所有從S\{0,1\}的函數。把2^S內的函數對應於由這函數給出的1原像,可看出在2^S\mathcal{P}(S)之間存在雙射,其中每個函數是\mathcal{P}(S)中這函數所對應的子集的特徵函數。所以就集合論來說2^S\mathcal{P}(S)是相同的。