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

Advertisements

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 :/

    Thanks for your time

    • Hi Chris! First of all I’m very sorry for my comically late reply! And second of all these are not confusing questions at all, but are indeed very good ones! Let’s look at your first questions. The element {4} is indeed an element of {1,2,3,{4}}, however it is not an element of {{1,2},{{4}}}. Namely, the set {{1,2},{{4}}} contains two elements: one element that it contains is the set {1,2}, and another element it contains is the set {{4}}. Note that neither of these elements is {4}. That said, the element {{4}} is itself a set and this set has one element, and this one element is {4}. Thus, {4} is not an element of {{1,2},{{4}}}, but it is an element of a set that is contained as an element of {{1,2},{{4}}}. Does that make sense?

      Similarly, the set {{1,2,3,{4}}} has only one element in it! That one element is the set {1,2,3,{4}}, and this set is a set with four elements in it: 1, 2, 3, and {4}. Thus, three elements of the set {1,2,3,{4}} are numbers and one element is a set, a set with one number as its element. But it is important to remember that the initial set {{1,2,3,{4}}} has only one element in it.

      Finally, the set {empty set, 1, {empty set}} works the same way. Namely, this set has 3 elements in it. One element is the number one, one element is the set “the empty set,” and one element is the set that contains only the empty set as its element. Now, it is very important to understand that the empty set is a subset of the set nonetheless {empty set, 1, {empty set}}. Namely, it is the subset of {empty set, 1, {empty set}} that contains no elements! In particular, one subset of {empty set, 1, {empty set}} is the set {empty set}, which only contains the element “empty set,” and another subset of the set {empty set, 1, {empty set}} is the set {{empty set}}, which only contains the element that is a set with only the empty set as its subset. However, the empty set is still a subset of {empty set, 1, {empty set}}—it is is the subset with no elements!

      Did this clear things up? If not let me know because these are great questions and I’m happy to help. Judging by your flawless use of nested brackets it’s clear that you are understanding things very well. Don’t hesitate to ask more questions 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s