NUMBER OF SUBSETS

If every element of a set B is also a member of a set A, then we say B is a subset of A. We use the symbol ⊂ to mean “is a subset of” and the symbol ⊄ to mean “is not a subset of”.

Example:
A = {1, 3, 5}, B = {1, 2, 3, 4, 5}

So,  A ⊂  B because every element in A is also in B.

X = {1, 3, 5}, Y = {2, 3, 4, 5, 6}.

X ⊄  Y  because 1 is in X  but not in Y.

Note:

  • Every set is a subset of itself i.e. for any set A, A ⊂  A
  • The empty set is a subset of any set A i.e. Ø ⊂  A
  • For any two sets A and B, if A ⊂  B and B ⊂  A then A = B

 

Example:


List all the subsets of the set Q = {x, y, z}

Solution:
The subsets of Q are { }, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}and {x, y, z}

a set of n elements is given by the 

 sum_(k=0)^n(n; k)=2^n.

For sets of n=1, 2, ... elements, the numbers of subsets are therefore 2, 4, 8, 16, 32, 64, ...

A set is a collection of objects.

A set is definite if all its members are known. There are a lot of sets: a set of letters, a set of numbers....

letters = {a, b, c, ...x, y z}

numbers = {0, 1, 2, 3, ...}

Three points ... have the same meaning as etc. We use the symbol = and brackets {,} to denote the fact that specific elements belong to a set.

We denote sets with uppercase letters, for example: A, B, C, S, X, Y,…

The elements of sets are denoted by lowercase letters: a, b, c, x, y,….

The relation that an element x belongs to the set S is denoted by x S (we read it: “x is an element of S”).

If the element y is not a member of the set S, we write y S (we read it: “y is not an element of S”).

 

Find the number of subsets of the set.?

Find the number of subsets of the set.

{mom, dad, son, daughter}

a. 8

b. 16

c. 14

d. 12

Solution:

Well let's see if we can brute force it

1. { } empty set is a subset of every set
2. {mom, dad, son, daughter}
3. {mom}
4. {dad}
5. {son}
6. {daughter}
7. {mom, dad}
8. {mom, son}
9. {mom, daughter}
10. {dad, son}
11. {dad, daughter}
12. {son, daughter}
13. {mom, dad, son}
14, {mom, dad, daughter}
15. {mom, son, daughter}
16. {dad, son, daughter}

 

And that's it. 16 subsets.

Another way to determine this is 2^n where n is the number of elements in the set.

For this problem we had 4 elements so we have 2^4 subsets and 2^4 is 16.