3
$\begingroup$

If given the following sets $A = \{1,2,3\}$ and $B = \{3,4,5\}$, the power sets of each are the following: $$\mathfrak P(A) = \{\emptyset,(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)\}\\ \mathfrak P(B) = \{\emptyset, (3),(4),(5),(3,4),(3,5),(4,5),(3,4,5)\}$$

What is

  • $\mathfrak P(A) \cap \mathfrak P(B)$
  • $|\mathfrak P(A \cup B)|$
  • $|\mathfrak P(A) \cup \mathfrak P(B)|$

My guess for the intersection one the first one is just $\{3\}$ and ${\emptyset}$ because it is only used elements in both.
I'm not sure about the next two. I do understand how power sets work but im curious on what the difference is between the $\mathfrak P(A \cup B)$ and $\mathfrak P(A) \cup \mathfrak P(B)$. Is there a difference?
How do we approach these types of problems?

$\endgroup$
4
  • $\begingroup$ If you understand the power set you should be able to write the two sets out and see if there is any difference. $\endgroup$
    – User
    Commented Feb 1, 2015 at 22:01
  • $\begingroup$ Is this thinking right on the subject though? My idea is if you first union both sets then take the power set of that then thats POW(A union B) and the other is just a union of power sets? Also, is my answer correct that {b} and empty set are only intersection elements between both sets? $\endgroup$
    – MD_90
    Commented Feb 1, 2015 at 22:04
  • $\begingroup$ Thank you @AlexR for the edit. I'm gonna learn these ways on how to post the questions :) $\endgroup$
    – MD_90
    Commented Feb 1, 2015 at 22:10
  • $\begingroup$ @MD_90 You're welcome :) For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$
    – AlexR
    Commented Feb 1, 2015 at 22:12

2 Answers 2

3
$\begingroup$

Your assertion is correct since $$\mathfrak P(A) \cap \mathfrak P(B) = \mathfrak P(A\cap B) = \mathfrak P(\{3\}) = \{\emptyset, \{3\}\}$$ Now for the other two since you already wrote down $\mathfrak P(A)$ and $\mathfrak P(B)$, write down $\mathfrak P(A\cup B) = \mathfrak P(\{1,2,3,4,5\})$ and compare to $\mathfrak P(A) \cup \mathfrak P(B)$. What do you notice?

Using inclusion-exclusion we can see that $$\begin{align*} |\mathfrak P(A) \cup \mathfrak P(B)| & = |\mathfrak P(A)| + |\mathfrak P(B)| - |\mathfrak P(A\cap B)| \\ &= 2^{|A|} + 2^{|B|} - 2^{|A\cap B|} \\ & = 2^3 + 2^3 - 2^1 = 8 + 8 - 2 = 14 \end{align*}$$ On the other hand $$|\mathfrak P(A\cup B)| = 2^{|A\cup B|} = 2^5 = 32$$

$\endgroup$
8
  • $\begingroup$ There equal because both can't have duplicates. $\endgroup$
    – MD_90
    Commented Feb 1, 2015 at 22:13
  • $\begingroup$ @MD_90 You'll see that they are in fact not equal. Write it out ;) Hint: Look at $\{1,5\}\in\mathfrak P(A\cup B)$, for example. $\endgroup$
    – AlexR
    Commented Feb 1, 2015 at 22:13
  • $\begingroup$ how would it be different if you had something like this..... |POW(POW(A x B))|? $\endgroup$
    – MD_90
    Commented Feb 1, 2015 at 22:14
  • $\begingroup$ Consolidate the definition of a power set. A frequent excercise first semester students are given is to calculate $$\mathfrak P(\mathfrak P(\mathfrak P(\mathfrak P(\emptyset))))$$ (it's an uglier set than first glance might suggest) $\endgroup$
    – AlexR
    Commented Feb 1, 2015 at 22:15
  • $\begingroup$ I know that Cartesian product is 9 so it would be a POW(POW(2^9))? $\endgroup$
    – MD_90
    Commented Feb 1, 2015 at 22:18
0
$\begingroup$

First of all i would suggest the notation $2^S$ as a notation for "power set of S". Why?

Because the power set of $S$, $2^S$ has $2^{|S|}$ elements.

$2^A \cap 2^B = \{\emptyset,\{3\}\}$ as both elements are included in both $A$ and $B$.

$A \cup B = \{1,2,3,4,5\}$

The powerset of $A \cup B$ must have $2^5 = 32$ elements as there are 5 elements in $A \cup B$:

$2^{A \cup B} = \{\emptyset,\{1\},\{2\},\{3\},\{4\},\{5\},\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\},\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\},\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\{1,3,4,5\},\{2,3,4,5\},\{1,2,3,4,5\}\}$

The power set of $A$ has $2^3 = 8$ elements (same for power set of $B$). The union therefore has a maximum of 16 elements (two less since $\emptyset$ and $\{3\}$ are included in both):

$2^A \cup 2^B = \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\},\{4\},\{5\},\{3,4\},\{3,5\},\{4,5\},\{3,4,5\}\}$

When to include a set to $2^A$?

Whenever all elements of the set are elements of $A$ i.e a subset of $A$.

$\endgroup$
6
  • $\begingroup$ While correct, the notation $2^A$ should be avoided for beginners, I think. Especially since it's motivated from the canonical isomorphism to $\{0,1\}^A = \{f:A\to\{0,1\}\}$ $\endgroup$
    – AlexR
    Commented Feb 1, 2015 at 22:17
  • $\begingroup$ oh okay so what your saying is the power set of following is this in length |POW(A union B)| = 2^5 = 32 elements where as the other |POW(A) union POW(B)| is just 2^3 + 2^3 = 16 $\endgroup$
    – MD_90
    Commented Feb 1, 2015 at 22:20
  • $\begingroup$ The first one is correct, but the second is not 16. Why? the union of two power sets may remove duplicate elements i.e elements included in both power sets. At minimum, the empty set is included in both. $\endgroup$
    – User
    Commented Feb 1, 2015 at 22:22
  • $\begingroup$ @MD_90 Not quite. You are counting duplicates: $\emptyset$ and $\{3\}$ are present in both sets. $\endgroup$
    – AlexR
    Commented Feb 1, 2015 at 22:23
  • $\begingroup$ oh okay! so there's 14 because of the intersection parts? $\endgroup$
    – MD_90
    Commented Feb 1, 2015 at 22:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .