SUBSET
- Thread starter Samin
- Start date
Harry_the_cat
Elite Member
- Joined
- Mar 16, 2016
- Messages
- 3,693
Yes there are 8 subsets.
Thank
Thanks
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
In general if a set has n members then it has \(\displaystyle 2^n\) subsets. \(\displaystyle 2^3= 8\).
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
You can prove that by induction on the number of members.
Every set has at least the empty set and the entire set as subsets. If n= 0 the entire set is the empty set so the empty set has 1 subset. \(\displaystyle 2^0= 1\).
If a set has exactly one member, {x}, then its subsets are precisely the empty set, { }, and the entire set, {x}, so has 2 subsets. \(\displaystyle 2^1= 2\).
Suppose that any set with k members, k> 0, has \(\displaystyle 2^k\) subsets. Let X be a set with k+ 1 members. Since k> 1, we can select a member of the set, x, and X- {x} is one of two kinds- either it contains x or it doesn't. All subsets that do not contain x are subsets of X-{x} and there are \(\displaystyle 2^k\) of them. All subsets that do contain x are precisely a subset that does not contain x union {x} so there are also \(\displaystyle 2^k\) of them. There are \(\displaystyle 2^k+ 2^k= 2(2^k)= 2^{k+ 1}\).
For example, consider the set {a, b, c}. Select the member "c" and remove it. That leave {a, b} which has \(\displaystyle 2^2= 4\) subsets: { }, {a}, {b}, and {a, b}. Those are all also subsets of {a, b, c}. Adding "c" to each of those gives {c}, {a, c}, {b, c}, and {a, b, c}, the other four subsets of {a, b, c} for a total of \(\displaystyle 2^3= 8\) subsets.
Every set has at least the empty set and the entire set as subsets. If n= 0 the entire set is the empty set so the empty set has 1 subset. \(\displaystyle 2^0= 1\).
If a set has exactly one member, {x}, then its subsets are precisely the empty set, { }, and the entire set, {x}, so has 2 subsets. \(\displaystyle 2^1= 2\).
Suppose that any set with k members, k> 0, has \(\displaystyle 2^k\) subsets. Let X be a set with k+ 1 members. Since k> 1, we can select a member of the set, x, and X- {x} is one of two kinds- either it contains x or it doesn't. All subsets that do not contain x are subsets of X-{x} and there are \(\displaystyle 2^k\) of them. All subsets that do contain x are precisely a subset that does not contain x union {x} so there are also \(\displaystyle 2^k\) of them. There are \(\displaystyle 2^k+ 2^k= 2(2^k)= 2^{k+ 1}\).
For example, consider the set {a, b, c}. Select the member "c" and remove it. That leave {a, b} which has \(\displaystyle 2^2= 4\) subsets: { }, {a}, {b}, and {a, b}. Those are all also subsets of {a, b, c}. Adding "c" to each of those gives {c}, {a, c}, {b, c}, and {a, b, c}, the other four subsets of {a, b, c} for a total of \(\displaystyle 2^3= 8\) subsets.