power set

Definition If $X$ is a set, then the power set of $X$ , denoted by $\powset{X}$ , is the set whose elements are the subsets of $X$ .

Properties

1. If $X$ is finite, then $|\powset{X}|=2^{|X|}$ .
2. The above property also holds when $X$ is not finite. For a set $X$ , let $|X|$ be the cardinality of $X$ . Then $|\powset{X}|=2^{|X|}=|2^X|$ , where $2^X$ is the set of all functions from $X$ to $\{0,1\}$ .
3. For an arbitrary set $X$ , Cantor's theorem states: a) there is no bijection between $X$ and $\powset{X}$ , and b) the cardinality of $\powset{X}$ is greater than the cardinality of $X$ .

Example

Suppose $S=\{a,b\}$ . Then $\powset{S}=\{\emptyset, \{a\}, \{b\}, S\}$ . In particular, $|\powset{S}|=2^{|S|}=4$ .

Related definition

If $X$ is a set, then the finite power set of $X$ , denoted by $\mathcal{F}(X)$ , is the set whose elements are the finite subsets of $X$ .

Remark

Due to the canonical correspondence between elements of $\powset{X}$ and elements of $2^X$ , the power set is sometimes also denoted by $2^X$ .