Blogs, Mathematical Reasoning, MR Study Help

Cartesian Product and Power Sets

Yes, it is that time of the semester when all of my classes are having exams.  It seemed that the last posts going over the practice exam problems for Calculus were helpful, so I will continue to make such posts around exam time.  For this series of posts, I will be working through the practice exam for the exam my introduction to proofs class will take later this week.

In this post, we start with two small sets, and build other sets from these using Cartesian products and power sets.

Definitions

In order to build new sets from old, we will be using the definitions we provided in Venn Diagrams.  As we look through solution below, I will refer to this post when we have to find things that would have been shown there.  Additionally, we will also need to define a Cartesian product, a subset and a power set.

First, we define the Cartesian product of two sets, \(A\) and \(B\) as the set of all ordered pairs where the first entry in the ordered pair is in \(A\) and the second is in \(B\).  This will be denoted \[A \times B=\left\{(a,b): a \in A\text{ and } b\in B\right\}.\]

A set \(B\) is a subset of \(A\), if every element in \(B\) is also in \(A\).  That is \(B \subseteq A\) if, for all \(b \in B\) we have that \(b \in A\).  The power set of \(A\), is then the set of all subsets of \(A\).  That is \[\mathcal{P}(A)=\left\{X: X \subseteq A\right\}.\]

Let \(A=\left\{a,b,c\right\}\) and \(B=\left\{b,c,d\right\}\).  Find the following.

\(A \cap B\)

Since we looked at intersections in Venn diagrams, I will refer you to that post for an explanation.  However, we will get that \(A \cap B=\left{b,c\right\}\).

\((A-B) \times B\)

For this problem, we will start by finding \(A-B\).  We are looking for things in \(A\) but not \(B\), so this will give us \(A-B=\left\{a \right\}.\)  In order to find the Cartesian product of this set with \(B\), we will now list all ordered pairs where the first element is in \(A-B\) and the second in \(B\).  When doing this, I try to assign an order to the elements in my mind so that I don’t repeat any.  In this case, I will just use alphabetical order.   \[(A-B) \times B=\left\{(a,b), (a,c), (a,d)\right\}.\]

\(\mathcal{P}(A)\)

When finding the power set of \(A\), we need to find all subsets.  In order to do this, I like to think about all the possible subsets with a specific number of elements in them.  Therefore, we will make a list for this

  • 0 elements in the subset.
    Since the only set without any elements in it is the empty set, \(\emptyset\), this will be the only subset with 0 elements in it.
  • 1 element in the subset.
    Since the elements of \(A\) are \(a,b\) and \(c\), we get that the subsets containing exactly one of these are \(\left\{a\right\}\), \(\left\{b\right\}\) and \(\left\{c\right\}\).
  • 2 elements in the subset.
    Here we look at all ways we can combine two at a time. We then get these possibilities will be \(a\) with \(b\), \(a\) with \(c\) and \(b\) with \(c\). Therefore, the subsets with two elements will be \(\left\{a,b\right\}\), \(\left\{a,c\right\}\) and \(\left\{b,c \right\}\).
  • 3 elements in the subset.
    The only way we can have 3 elements in the subset is if the subset contains all three elements in \(A\). That is, the three element subset is \(\left\{a,b,c\right\}\).
  • 4 or more elements.
    Since there are only 3 elements in \(A\), there is no way to have more than 3 elements and remain a subset.

We can now combine all of these to get that
\begin{align*}
\mathcal{P}(A)&=\{ \emptyset, \\
& \left\{a\right\}, \left\{b\right\}, \left\{c\right\}, \\
& \left\{a,b\right\}, \left\{a,c\right\}, \left\{b,c\right\}, \\
& \left\{a,b,c\right\} \}.
\end{align*}

\(\mathcal{P}(A-B) \times \mathcal{P}(B-A)\)

Here, we will start by finding \(A-B\) and \(B-A\).  Since we already found \(A-B\) in a previous example, so we will use that answer.  In a similar way, we would find the \(B-A=\left\{d\right\}\).

Now, we need to find the power set of each of these sets.  If we follow the process as in the last example, we can find that \(\mathcal{P}(A-B)=\left\{ \emptyset, \left\{ a \right\} \right\}\) and \(\mathcal{P}(B-A)=\left\{ \emptyset, \left\{d\right\}\right\}.\)

Next, we need to take the Cartesian product the same way we did in an earlier example.  We then get that \[\mathcal{P}(A-B) \times \mathcal{P}(B-A)=\left\{ (\emptyset, \emptyset), ( \emptyset, \left\{d \right\}), (\left\{a \right\}, \emptyset), (\left\{a \right\}, \left\{ d \right\})\right\}.\]

Find \(|\mathcal{P}(A) \times B|\)

In order to find this, we will find a few things first.

  • \(C\) is a set, then \(|C|\) is the cardinality of the set \(C\), that is, the number of elements in the set \(C\).
  • The set \(A \times B\) contains all elements of the form \((a,b)\) where \(a \in A\) and \(b \in B\). Therefore, each ordered pair is distinct for each choice of \(a\) and \(b\). Since the number of choices for \(a\) are \(|A|\) and the number of choices for \(b\) are \(|B|\), we find that the total number of choices is \(|A| \times |B|\). Therefore, \(|A \times B| =|A||B|\).
  • If we want to find a subset of a set \(A\), we can decide to either put in or leave out any element of \(A\). Since any of these choices leads to a different set, we will get 2 options for each element. Therefore the total number of choices will be \(2^{|A|}\).

Now we can find the solution to the above question.  Here
\begin{align*}
|\mathcal{P}(A) \times B|&=|\mathcal{P}(A)||B| \\
&=2^{|A|}*|B| \\
&=2^{3}*3 \\
&=24.
\end{align*}

Conclusion

We have now found the sets that result beginning with \(A\) and \(B\) and combining them using Cartesian products and power sets.  We can indeed combine these in many more ways, but, as we saw in the last one, the number of elements of such sets can get large very quickly.  Therefore, listing all such elements would take some time.

If you found the post helpful or entertaining, please like it below and share it with anyone else that may be looking at set theory or logic.  You can also find the rest of the solutions to this practice exam here.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.