# Lesson 4 Solutions

Exercise 1) Let $A=\{1,2,3,4,5\}$ and let $B=\{\{1,2\},\{3,4\},\{5\}\}$.  How many elements does A have?  How many elements does B have?  Does A=B?

Solution: A has 5 elements, and B has 3!  The result for A should be clear, but the result for B follows because the elements in B are $\{1, 2\}, \{3,4\}, \mathrm{\ and\ } \{5\}$, where $\{1, 2\} \mathrm{\ and\ } \{3, 4\}$ are single elements—they’re sets in their own right, but when viewed in B they are single elements!  Accordingly, A and B are not equal as sets.  We can see this many ways.  First of all, a set with 3 elements can never be equal to a set with 5 elements.  More concretely, we see that the element 1 is not in B, nor is the element 2, or 3, or 4.  Conversely, the element $\{1, 2\}$ is not in A, nor is the element $\{3, 4\}$.  When viewed in this way, it becomes clear that these sets are not equal.

Exercise 2) Knowing that a set with $N$ elements has a power set with $2^N$ elements, how many elements does the power set of the power set have?  In the notation of letting $P(A)$ denote the power set of $A$, the question is to find the number of elements in $P(P(A))$.  (hint: what if $N=2^M$ where M is some other number?)

Solution:  Suppose A has N elements.  Then from this lesson we know that $P(A)$ has $2^N$ elements.  Now we ask how many elements the power set of $P(A)$ has.  Well, we simply apply this logic again to the set $P(A)$.  Namely, we can let $M=2^N$, and then we’re just asking what the power set of a set with $M$ elements is.  We already know this answer: it’s $2^M$.  But, recalling how we defined M, we see that $P(P(A))$ has $2^{2^N}$ elements.  For example, if A has 2 elements, then $P(P(A))$ has $2^{2^2}=2^4=2\times 2\times 2\times 2=16$ elements.  If A has 3 elements, then $P(P(A))$ has $2^{2^3}=2^8=256$ elements.  Clearly, the size of $P(P(A))$ grows extremely fast as the size of A grows!

Back to lesson 4

On to lesson 5

### 4 Responses to Lesson 4 Solutions

1. Anonymous says:

Are you sure about the solution of lesson 4’s exercise 2 solution. Because initially, we take set which doesn’t contain an empty element but by taking power set we include null set as a subset now again when we take power set of a power set we cannot take null set again and again so it should not be equal to “two to the power two to the power n”.It should be less.

• Great question! And yes, the solution is correct, but it is confusing. The important thing to note is the distinction between when the empty set is viewed as a SET, and when it’s viewed as an ELEMENT. Namely, we already know that entire sets can be single elements of a set, and this distinction is important here. For example, the SUBSETS of the set {a} are the set {a} itself and the empty set. Thus, the set of all subsets of this set is {{a}, empty set}. Namely, the empty set is an ELEMENT of the set of all subsets of {a}. Now, if we want to consider the set of all subsets of THIS set, namely of the set {{a}, empty set}, then we need to consider the set itself {{a},empty set}, the set {a}, the set whose single element is the empty set {empty set}, AND the empty set itself. Namely, the empty set is a subset of every set, so it is a subset of the set {{a}, empty set}, but the set whose single element in “empty set” is also a subset of this set. I.e., the set {empty set} is NOT the empty set, it is a set with one element, and that one element is the empty set itself. Thus, the set of all subsets of {{a},empty set} is {{{a},empty set}, {a}, {empty set}, empty set}. Does that make sense?

2. Chris Philp says:

Hi, I really liked the lesson but I was wondering about some other examples:

Say if you had a Set A which contained {1, 2, 3, {4}} and a set B which contained {{1, 2}, {{4}}}, is {4} an element of B? And if you had a set C = {{1, 2, 3, {4}}}, is A an element of C?

If i’m not making myself clear, say if you had the set A = { empty set, 1, {empty set}} and then say B = {A}, why isn’t A an element of B and why is A a subset of B? Sorry if i’ve been confusing