Sales Toll Free No: 1-855-666-7446

# Power Set

Top
 Sub Topics The Set is the basic concept of all mathematics and mathematics application. We deal with different kinds of set in our daily life. For example collection of students, number of player in Indian hockey team etc. A set is nothing but a well-defined object. A famous mathematician Georg Cantor who created set theory it to give the concept of transfinite number with cardinal and ordinal number clasess.

## Definition

In math context, a set is defined as a well-defined collection or a group of items.  The items contained in the set are called as the elements. Some of the elements in that set can form a set by themselves; each of such sets is called as a subset. The number of all such possible sets is called power set of the main set.

## Power Set of a Set

Suppose we describe a set of colors red, yellow, blue and green as $\{R, Y, B]$ and ask someone his or her likeness on these colors. It may be possible that the person likes any one of the three, any two of the three or all the three colors. It is also possible that the person may not like any of these three colors! In each case, the set of colors liked is a subset of the main set $\{R, Y, B\}$. The subsets are $\{R\},\ \{Y\},\ \{B\},\ \{R, Y\},\ \{Y, B\},\ \{B, R\},\ \{R, Y, B\}$ and for none of the three colors the set is empty and denoted as $\{\ \}$. Thus we find there are $8$ subsets for the main set of $3$ items. In short we say $8$ is the power set a set consisting $3$ items. So the definition of power set of a set is the number of all possible subsets of the main set.

## Formula

In the previous section we were analyzing the possible formations of subsets for a main set of $3$ elements. If we keenly observe, we have been using the principle of combination.  We first found the number of subsets containing only one element. That is nothing but combinations of $3$ elements with $1$ element taken at a time, which is denoted as $^3C_1$ and which equals to $3$. It is exactly the same number found by counting principle. Similarly the number of subsets we found with $2$ elements was $3$ which is same as $^3C_2$ in combination language.  We found that only one subset was possible with all the three elements (the main set itself) and that is same as $^3C_3$. The remaining one set which is a null set can also be explained as $^3C_0$ which is also equal to $1$. Hence the power set of $8$ for a set of $3$ elements can be expressed as $P(3)$ = $^3C_0\ +\ ^3C_1\ +\ ^3C_2\ +\ ^3C_3$  = $8$

The above concept can be extended to a main set with any number of elements and thus we can express a formula

$P(n)$ = $^nC_0\ +\ ^nC_1\ +\ ^nC_2\ +……\ +\ ^nC_n$

## Functions

We arrived at a formula for power set as, $P(n)$ = $^nC_0\ +\ ^nC_1\ +\ ^nC_2\ +……\ +\ ^nC_n$

Let us find the power sets of a few sets and make a table.

Main Set Elements (n) Power Set P(n)
1 2
2 4
3 8
4 16

We notice a very interesting fact. The values of $P(n)$ are all powers of $2$ and the power is same as the number of elements in the corresponding main set. Therefore, we can express a power set as an exponential function of the number of elements. That is,

$P(n)$ = $2^n$.

This is one of the important formulas for a power set and it is extremely useful in higher topics of probability.

## Properties

Another interesting property is the connection between power set and binary numbers. Binary number system is based on powers of $2$ and uses only the digits $0$ and $1$ The powers of $2$ starts from $0$ at right most place exactly the same as the powers of $10$ in a normal decimal system.  So, for example, the binary number $101$ represents the decimal number $5$, figured out like $1 \times 22\ +\ 0 \times 21\ +\ 1 \times 20$ = $4 + 0 + 1$ = $5$.

Now let us get back to the same example that we discussed in the beginning. We concluded that a set $\{a. b, c\}$ has a power set of $8$. The first subset numbered as $1$. That number $1$ in binary is written as $001$. Taking $a, b$ and $c$ in the same order of the binary $001$ we can write the first subset as $[$zero '$a$', zero '$b$', one '$c$' $\}$ = $\{ c \}$. The second subset is number as $2$ which is equivalent to $010$ in binary and forms the second subset is formed as $\{$zero '$a$', one '$b$', zero '$c$' $\}$ = $\{b\}$.  Thus, if we know the power set (the actual number of subsets, we can list out all the subsets), with the aid of binary numbers. Later we will work out an example to completely understand the process.

## Power Set of Null Set

A null set is a set in which no element is present. There is general misconception that a set described as $\{0 \}$ is a null set. Actually it is a set with a single element of $0$. Hence a null set is denoted only as $\{ \}$. Now what is the power set of null set? We can approach in two different ways to answer this question.  The subsets of any set are sets with all possible combinations of the elements in the set. But in case of a null set there all possible combinations only lead to the same set $\{ \}$. Thus, the power set of a null set is $1$. The same conclusion can be arrived in an easier way by realizing that $P(0)$ = $20$ = $1$, since $n$ = $0$ in case of a null set.

## Examples

Example 1:

Sam is on a tour to California and he intends to visit three of his friends Aaron, Bob, Charles and David at different places, subject to time constraints. What is the probability that he visits only Aaron and Charles?

Solution:

Since there is a time constraint for Sam, he may not visit any of the friends, any one of the four friends, any two of the four friends, any three of the four friends or he might visit all the four friends. Hence the total possible number of visits is the power set of the set of his four friends {Aaron, Bob, Charles, David}. The power set of a set of $4$ elements is $24$ = $16$ and that is the number of all possible friends’ visits.

Therefore, the probability of visiting only Aaron and Charles is $\frac{1}{16}$.
Example 2:

In a library newspapers are available in three languages English, French and German. List the possible newspapers a visitor could read?

Solution:

The different ways that the visitor could read the newspapers is a power set of the $3$ elements set {English, French, German}, which is $23$ = $8$. The list can be prepared using the concept of binary numbers shown as below. The order in the digits of binary numbers is same the order $E$ for English, $F$ for French and $G$ for German.

Subset Number Binary Number of Subset Actual Subset
0 0 { }
1 1 {G}
2 10 {F}
3 11 {F, G}
4 100 (E}
5 101 {E, G}
6 110 (E, F}
7 111 {E, F, G}

Rearranging the last column the list of possible newspapers a visitor could read is, $\{ \}$ (none), {English}, {French}, {German}, {English, French}, {French, German}, {English, German},  {English, French, German}.