Power Sets

Posted by: Robin Leboe | March 28, 2008

Power Sets

A power set is a set that contains all of the possible subsets of a given set and is denoted by $P\left(S \right)$ or ${2}^{A}$ In other words:

${2}^{A}=\{X:X\subseteq A\}$

In plain English this reads the collection of X such that X is a subset of A.

As an example, the power set of $\{a, b, c\}$ would be:

${S}_{1}=\oslash$	${S}_{4}=\{c\}$	${S}_{7}=\{c, a\}$
${S}_{2}=\{a\}$	${S}_{5}=\{a, b\}$	${S}_{8}=\{a, b, c\}$
${S}_{3}=\{b\}$	${S}_{6}=\{b, c\}$

From this we find that if the original set has n members then the Power Set will have ${2}^{n}$ members. In the case of the preceding example:

$|P\left(S \right)| = {2}^{n} = {2}^{3} = 8$

Note that the number of members in a set is often denoted $|S|$ . In the preceding example $|P\left(S \right)|$ can be translated the number of mebers in the power set of S.

Another interesting way to look at the various subsets within a power set is to relate them to binary digits like so:

${S}_{1}=\oslash$	$000$
${S}_{2}=\{c\}$	$001$
${S}_{3}=\{b\}$	$010$
${S}_{4}=\{b, c\}$	$011$
${S}_{5}=\{a\}$	$100$
${S}_{6}=\{a, c\}$	$101$
${S}_{7}=\{a, b\}$	$110$
${S}_{8}=\{a, b, c\}$	$111$