Power set

Revision as of 12:02, 17 August 2006 by JBL (talk | contribs)

The power set of a given set $S$ is the set $P(S)$ of subsets of that set.

The empty set has only one subset, itself. Thus $P(\emptyset) = \{\emptyset\}$.

A set $\{a\}$ with a single element has two subsets, the empty set and the entire set. Thus $P(\{a\}) = \{\emptyset, \{a\}\}$.

A set $\{a, b\}$ with two elements has four subsets, and $P(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$.

Similarly, for any finite set with $n$ elements, the power set has $2^n$ elements.

Note that for nonnegative integers, $2^n > n$ so the power set of any set is larger than the set itself. An analogous result holds for infinite sets: for any set $S$, there is no bijection between $S$ and $P(S)$ (or equivalently, there is no injection from $P(S)$ to $S$).

Proof

See Also

This article is a stub. Help us out by expanding it.