power set

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

Properties

1.

If $X$ is finite, then $|\mathcal{P}(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 $|\mathcal{P}(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 $\mathcal{P}(X)$ , and b) the cardinality of $\mathcal{P}(X)$ is greater than the cardinality of $X$ .

Example

Suppose $S=\{a,b\}$ . Then $\mathcal{P}(S)=\{\emptyset,\{a\},\{b\},S\}$ . In particular, $|\mathcal{P}(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 $\mathcal{P}(X)$ and elements of $2^{X}$ , the power set is sometimes also denoted by $2^{X}$ .

Title	power set
Canonical name	PowerSet
Date of creation	2013-03-22 11:43:46
Last modified on	2013-03-22 11:43:46
Owner	matte (1858)
Last modified by	matte (1858)
Numerical id	23
Author	matte (1858)
Entry type	Definition
Classification	msc 03E99
Classification	msc 03E10
Classification	msc 37-01
Synonym	powerset
Related topic	PowerObject
Related topic	ProofOfGeneralAssociativity
Defines	finite power set
Defines	finite powerset