Power Set
Consider the set {1,2}. Let us write down all the subsets of the set {1,2}. We know that Ø is a subset of every set . So, Ø is a subset of {1,2}. We see that {1} and {2}are also subsets of {1,2}. Also,we know that every set is a subset of itself. So, {1,2} is a subset of {1,2}. Thus,the set {1,2} has,in all,four subsets,viz. Ø, {1}, {2} and {1,2}. The set of all these subsets is called the power set of {1,2}.

[Definition] The collection of all subsets of a set A is called the power set of A. It is denoted by þ(A). In þ(A), every element is a set.
Thus, as in above, if B={1,2}, then

In general, if A is a set with n(A)=m, then it can be shown that n[þ(A)]=2^m.

The collection of all subsets of a set A is called the power set of A. It is denoted by þ(A). If the number of elements in A is equal to n, i.e., n(A)=n, then the number of elements in þ(A)=2ⁿ.

⛲ Example 1. Find all possible subsets of each set.
(a) {7, 8}
By trial and error, the set {7, 8} has four subsets:

In Example 1, the subsets of {7, 8} and the subsets of {a, b, c} were found by trial and error. An alternative method involves drawing a tree diagram, a systematic way of listing all the subsets of a given set. Figures 1(a) and (b) show tree diagrams for {7, 8} and {a, b, c}.

In Example 1, we determined the number of subsets of a given set by making a list of all such subsets and then counting them. The tree diagram method also pro- duced a list of all possible subsets. In many applications, we don’t need to display all the subsets but simply determine how many there are. Furthermore, the trial and error method and the tree diagram method would both involve far too much work if the original set had a very large number of elements. For these reasons, it is desir- able to have a formula for the number of subsets. To obtain such a formula, we use inductive reasoning. That is, we observe particular cases to try to discover a general pattern.

Begin with the set containing the least number of elements possible—the empty set. This set, Ø, has only one subset, Ø itself. Next, a set with one element has only two subsets, itself and Ø. These facts, together with those obtained above for sets with two and three elements, are summarized here.

This chart suggests that as the number of elements of the set increases by one, the number of subsets doubles. This suggests that the number of subsets in each case might be a power of 2. Every number in the second row of the chart is indeed a power of 2. Add this information to the chart.

This chart shows that the number of elements in each case is the same as the exponent on the 2. Inductive reasoning gives the following generalization.

Number of Subsets
The number of subsets of a set with n elements is 2ⁿ.

Since the value 2ⁿ includes the set itself, we must subtract 1 from this value to obtain the number of proper subsets of a set containing n elements.

Number of Proper Subsets
The number of proper subsets of a set with n elements is 2ⁿ-1.

As shown in the chapter on problem solving, although inductive reasoning is a good way of discovering principles or arriving at a conjecture, it does not provide a proof that the conjecture is true in general. A proof must be provided by other means. The two formulas above are true, by observation, for n= 0, 1, 2, or 3.

⛲ Ex2. Find the number of subsets and the number of proper subsets of each set.
(a) {3,4,5,6,7}
This set has 5 elements and 2⁵=2⋅2⋅2⋅2⋅2=32 subsets. Of these, 2⁵-1=32-1=31 are proper subsets.
(b) {1,2,3,4,5,9,12,14}
This set has 8 elements. There are 2⁸=256 subsets and 255 proper subsets.

Number of Subsets

How many distinct subsets can be made from a given set? The empty set has no ele- ments and has exactly one subset, the empty set. A set with one element has two subsets. A set with two elements has four subsets. A set with three elements has eight subsets. This infonnation is illustrated in Table 3.
Table 3. Number of Subsets

By continuing this table with larger and larger sets. we can develop a general expression for finding the number of distinct subsets that can be made from any given set.

Number of Distinct Subsets
The number of distinct subsets of a finite set A is 2ⁿ, where n is the number of elements in set A.

Every set is a subset of itself. but no set is a proper subset of itself. Thus. the number of proper subsets will always be one less than the number of subsets that can be made from any given set. We summarize this concept in the following expression.

Number of Distinct Proper Subsets
The number of distinct proper subsets of a finite sent is 2ⁿ-1, where n is the number of elements in set A.

⛲ Question 1. Brigette Martineau is ordering a new car. She can order some. all, or none of the following options: power windows, MP3 player port, leather interior. alarm system, sun roof, and navigation system. How many different variations of the set of options are possible?
✍ Solution:
Brigette can order the car with no options, any one option, any two options, any three options, and so on, up to six options. One technique used in problem solving is to consider similar problems that you have solved previously. If you think about this problem, you will realize that it is the same as asking how many distinct subsets can be made from a set with six elements. The number of different variations of the set of options is the same as the number of possible subsets of a set that has six elements. There are 2⁶, or 64. possible subsets of a set with six elements. Thus, there are 64 possible variations of the set of options for the car.

⛲ Q2. How many elements has þ(C), if C=Ø?
✍ Solution:
We know that if A is a set with m elements i.e., n(A)=m, then n[þ(A)]=2^m.
If C= Ø, then n(C)=0.
∴ n[þ(C)]=2⁰=1
Hence, þ(C) has one element.

⛲ Ex3. Let D be the set of letters in the word, ‘seed’. Find:
(i) D (ii) n(D) (iii) Number of subsets of D (iv) Number of proper subsets
✍ Solution:
(i) D={s,e,d} (ii) n(D)=number of elements=3
(iii) Number of subsets of D=2³=8