Blogs, Mathematical Reasoning, MR Study Help

Set Equality Proof

In the following posts, we will be looking more at how to prove different theorems. In some of these, we will have to determine if the theorem is true, then prove that our answer is correct. You can find more examples of proof writing in the Study Help category for mathematical reasoning. You can also view the available videos on YouTube.

\(\mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B)\)

We want to determine if for all sets \(A\) and \(B\), we have that \(\mathcal{P}(A) \cap \mathcal{P}(B) =\mathcal{P}(A \cap B)\). We should begin by trying to think about specific sets and what these things would look like.

First example

For a small example, let \(A=\left\{a\right\}\) and \(B=\left\{b\right\}\). We then have

  • \(\mathcal{P}(A)=\left\{ \emptyset, \left\{a\right\}\right\}\).
  • \(\mathcal{P}(B)=\left\{ \emptyset, \left\{b\right\}\right\}\).
  • \(\mathcal{P}(A) \cap \mathcal{P}(B)=\left\{ \emptyset \right\}\).
  • \(\mathcal{P}(A \cap B)=\mathcal{P}(\emptyset)=\left\{\emptyset\right\}\).

In this case, we do indeed have that the two sets are the same. Since we were working with specific examples, this is not a proof of the theorem. Rather we hope that we can see why it worked in this case to try to determine if this will always work, or if we can find a case it won’t work.

In this situation, we should note that there was no intersection between \(A\) and \(B\). With this being the case, we saw that the element of each set resulted in a subgroup. Since there were no elements in both \(A\) and \(B\) to give rise to equivalent sets, there was no resulting intersection, other than the empty set. Before making a general guess, I would suggest trying an example with some intersection.

Second Example

Here we will work with the sets \(A=\left\{a,c\right\}\) and \(B=\left\{b,c\right\}\). We can then find that

  • \(\mathcal{P}(A)=\left\{ \emptyset, \left\{a\right\}, \left\{c\right\}, \left\{a,c\right\}\right\}\).
  • \(\mathcal{P}(B)=\left\{ \emptyset, \left\{b\right\}, \left\{c\right\}, \left\{b,c\right\}\right\}\).
  • \(\mathcal{P}(A) \cap \mathcal{P}(B)=\left\{ \emptyset, \left\{c\right\} \right\}\).
  • \(\mathcal{P}(A \cap B)=\mathcal{P}(\left\{c\right\})=\left\{\emptyset, \left\{c\right\}\right\}\).

Again, we have that the two sets are the same. Since we have some portion that intersects and some portion that doesn’t this gives us hope (though not a proof) that the theorem may be true. At this point, it is time to try to generalize what is happening in these examples so that we can find what happens in general.

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

As we start to generalize, we want to think about what the elements of \(\mathcal{P}(A) \cap \mathcal{P}(B)\) look like. We have that

  • Elements of \(\mathcal{P}(A) \cap \mathcal{P}(B)\) are elements of both \(\mathcal{P}(A)\) and \(\mathcal{P}(B)\)
  • Elements of \(\mathcal{P}(A)\) are subsets of \(A\).
  • Elements of \(\mathcal{P}(B)\) are subsets of \(B\).
  • Hence elements of \(\mathcal{P}(A) \cap \mathcal{P}(B)\) are subsets of both \(A\) and \(B\).

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

We now look at what the elements of \(\mathcal{P}(A \cap B)\) look like. We then get that

  • Elements of \(\mathcal{P}(A \cap B)\) are subsets of \(A \cap B\).
  • A set is a subset of \(A \cap B\) if it is a subset of \(A\) and \(B\).
  • Hence elements of \(\mathcal{P}(A \cap B)\) are subsets of both \(A\) and \(B\).

Note that as we described the elements in each set, we arrive at the same result. In this case, as long as we can put this together formally, this will indeed give us a proof.

\(\mathcal{P}(A) \cap \mathcal{P}(B) \subseteq \mathcal{P}(A \cap B)\)

We can now begin to work on our proof. Recall that in order to show that two sets are equal, we will show that each set is a subset of the other. For the first part we will show that \(\mathcal{P}(A) \cap \mathcal{P}(B) \subseteq \mathcal{P}(A \cap B)\). This means that we will need to show that every element in \(\mathcal{P}(A) \cap \mathcal{P}(B)\) is also an element of \(\mathcal{P}(A \cap B)\).

Proof

Let \(X \in \mathcal{P}(A) \cap \mathcal{P}(B)\). We then have that \(X \in \mathcal{P}(A)\) and \(X \in \mathcal{P}(B)\). Therefore, \(X \subseteq A\) and \(X \subseteq B\). We now have that \(X \subseteq A \cap B\), hence \(X \in \mathcal{P}(A \cap B)\).

\(\mathcal{P}(A \cap B) \subseteq \mathcal{P}(A) \cap \mathcal{P}(B)\)

We now need to show the other direction. That is, we need to show that every element of \(\mathcal{P}(A \cap B)\) is also an element of \(\mathcal{P}(A) \cap \mathcal{P}(B)\).

Proof

Let \(X \in \mathcal{P}(A \cap B)\). Then \(X \subseteq A \cap B\). Therefore, \(X \subseteq A\) and \(X \subseteq B\). We now have that \(X \in \mathcal{P}(A)\) and \(X \in \mathcal{P}(B)\). Hence, \(X \in \mathcal{P}(A) \cap \mathcal{P}(B)\).

Conclusion

We began by looking at some examples to try to determine whehter or not this theorem was true. Because the examples worked out for the different things we tried, we thought that the theorem would work in general. After this, we were able to look at the defining properties of each of these sets and compare them. After this, we were indeed able to show that the two sets must contain exactly the same elements.

For more help with proofs, make sure to continue working on the other problems we have posted solutions for in Study Help. If you find these helpful, make sure to let other people know about them so that they can get help as well.

We'd love to hear your thoughts!

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