How to List all the distinct Subsets of a Set?


Representing subsets on a Venn diagram

When we know that S is a subset of T, we place the circle representing S inside the circle representing T. For example, let S={0,1,2}, and T={0,1,2,3,4}. Then S is a subset of T, as illustrated in the Venn diagram below.

venn diagram an

Figure 1. Venn diagram

Make sure that 5, 6, 7, 8, 9 and 10 are placed outside both circles.

⛲ Example 0: Subsets
If A={a,b,c} then A has eight different subsets:

Ø {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}

Notice that AA and in fact each set is a subset of itself. The empty set Ø is a subset of every set.

⛲ Ex1. Write down the subsets of the following sets.
(i) {1,2,3} (ii) Ø

(i) The subsets of {1,2,3} are

Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

(ii) Clearly, {Ø} is the power set of empty set Ø. Now, its subsets are Ø and {Ø}.

⛲ Ex2. Write down all the subsets of the following sets:
(i) {a}
(ii) {a,b}
(iii) {1,2,3}
(iv) Ø

(i) The subsets of {a} are Ø and {a}.
(ii) The subsets of {a, b} are Ø, {a}, {b}, and {a, b}.
(iii) The subsets of {1,2,3} are Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}
(iv) The only subset of Ø is Ø.

⛲ Ex3. List all the subsets of the set {-1,0,1}.
✍ Solution:
Let A={-1,0,1}. The subset of A having no element is the empty set Ø. The subsets of A having one element are {-1}, {0}, {l}. The subsets of A having two elements are {-1,0}, {-1,1}, {0,1}. The subset of A having three elements of A is A itself. So, all the subsets of A are (1), {-1}, {0}, {1}, {-1,0}, {-1,1}, {0,1} and {-1,0,1}.

📌 Exercises (solved)
A. List all the subsets of the following sets.
1. {1,2,3,4}. The subsets of {1,2,3,4} are:
{}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}.
2. {{ℝ}}. The subsets of {{ℝ}} are: {} and {{ℝ}}.
3. {Ø}. The subsets of {Ø} are {} and {Ø}.
4. {ℝ,{ℚ,ℕ}. The subsets of {ℝ,{ℚ,ℕ} are {}, {ℝ}, {{ℚ,ℕ}}, {ℝ,{ℚ,ℕ}}.
B. Write out the following sets by listing their elements between braces.
1. {XX⊆{3,2,a} and |X|=2}={{3,2},{3,a},{2,a}}
2. {XX⊆{3,2,a} and |X|=4}={}=Ø

⛲ Example 5: Distinct Subsets
a) Determine the number of distinct subsets for the set {S,L,E,D}.
b) List all the distinct subsets for the set {S,L,E,D}.
c) How many of the distinct subsets are proper subsets?
✍ Solution:
a) Since the number of elements in the set is 4, the number of distinct subsets is 2=24=2⋅2⋅2⋅2=16.

c) There are 15 proper subsets. Every subset except {S,L,E,D} is a proper subset

This idea of “making” a subset can help us list out all the subsets of a given set B. As an example, let B={a,b,c}. Let’s list all of its subsets.
One way of approaching this is to make a tree-like structure. Begin with the subset {}, which is shown on the left of Figure 2. Considering the element a of B, we have a choice: insert it or not. The lines from {} point to what we get depending whether or not we insert a, either {} or {a}. Now move on to the element b of B. For each of the sets just formed we can either insert or not insert b, and the lines on the diagram point to the resulting sets {}, {b}, {a}, or {a,b}. Finally, to each of these sets, we can either insert c or not insert it, and this gives us, on the far right-hand column, the sets {}, {c}, {b}, {b,c}, {a}, {a,c}, {a,b} and {a,b,c}. These are the eight subsets of B={a,b,c}.


Figure 2. A “tree” for listing subsets

We can see from the way this tree branches out that if it happened that B={a}, then B would have just two subsets, those in the second column of the diagram. If it happened that B={a,b}, then B would have four subsets, those listed in the third column, and so on. At each branching of the tree, the number of subsets doubles. Thus in general, if |B|=n, then B must have 2n subsets.

[Fact] If a finite set has n elements, then it has 2n subsets.

For a slightly more complex example, consider listing the subsets of B={1,2,{1,3}}. This B has just three elements: 1, 2 and {1,3}. At this point you probably don’t even have to draw a tree to list out B’s subsets.
You just make all the possible selections from B and put them between braces to get

{}, {1}, {2}, {{1,3}}, {1,2}, {1,{1,3}}, {2,{1,3}}, {1,2,{1,3}}.

These are the eight subsets of B. Exercises like this help you identify what is and isn’t a subset. You know immediately that a set such as {1,3} is not a subset of B because it can’t be made by selecting elements from B, as the 3 is not an element of B and thus is not a valid selection. Notice that although {1,3}⊄B (read: {1,3} isn’t a proper-subset of B), it is true that {1,3}∈B. Also, {{1,3}}⊂ B (read: {1,3} is a proper-subset of B).

🌈 Element ∊ or Proper Subset ⊂ — True or False Statements