Skip to main content

Discrete Mathematics: An Active Approach to Mathematical Reasoning

Jennifer Firkins Nordstrom

Section 6.2 Properties of Sets

Now that we have defined operations on sets such as union and intersection, we can look at various properties of these operations. In the last section we saw that intersection involves an “and” statement, while union involves an “or.” As we work with these properties we will be able to see connections between properties of sets and the logical connectives we saw in Chapter 2.
One of our goals in this section is to learn how to prove properties such as the following subset relations.

Subset Relations.

  1. \(A\cap B\subseteq A\text{;}\) \(A\cap B\subseteq B\text{.}\)
  2. \(A\subseteq A\cup B\text{;}\) \(B\subseteq A\cup B\text{.}\)
  3. Transitivity.
    If \(A\subseteq B\) and \(B\subseteq C\) then \(A\subseteq C\text{.}\)
Recall from Definition 6.1.1, we can think of the statement \(X\subseteq Y\) as the conditional statement, if \(x\in X\) then \(x\in Y\text{.}\)

Proving Subset.

To prove \(X\subseteq Y\text{:}\)
  • Assume \(x\in X\text{.}\)
  • Show \(x\in Y\text{.}\)
Based in their definitions from Section 6.1, we can translate other sets into logical statements, as well. These translations are how we will prove properites of sets using elements.

Translating Set Statements to Logical Statements.

  • \(x \in X\cup Y\) if and only if \(x\in X\) or \(x\in Y\)
  • \(x \in X\cap Y\) if and only if \(x\in X\) and \(x\in Y\)
  • \(x \in X-Y\) if and only if \(x\in X\) and \(x\notin Y\)
  • \(x \in X^C\) if and only if \(x\notin X\)
  • \((x, y) \in X\times Y\) if and only if \(x\in X\) and \(y\in Y\)

Example 6.2.1. Proving a Subset Property.

Prove \(A\cap B\subseteq A\text{.}\)

Proof.

Let \(x\in A\cap B\text{.}\) Then \(x\in A\) and \(x\in B\text{.}\) Thus, \(x\in A\text{.}\)
Therefore, \(A\cap B\subseteq A\text{.}\)

Activity 6.2.1.

Prove \(A\cap B\subseteq B\text{.}\) Be sure to write what you want to assume and what you want to show.

Activity 6.2.2.

Prove \(B\subseteq A\cup B\text{.}\) Be sure to write what you want to assume and what you want to show.

Activity 6.2.3.

Prove if \(A\subseteq B\) and \(B\subseteq C\) then \(A\subseteq C\text{.}\) Be sure to write what you want to assume and what you want to show.

Proving Set Equality.

To prove \(X=Y\) show
  1. \(X\subseteq Y\text{,}\) ie, show if \(x \in X\) then \(x \in Y\text{,}\) and
  2. \(Y\subseteq X\text{,}\) ie, show if \(x \in Y\) then \(x \in X\text{.}\)

Example 6.2.2. Proving Two Sets are Equal.

Prove \(A\cup(B\cap C)=(A\cup B)\cap (A\cup C)\text{.}\)

Proof.

\((\subseteq)\text{:}\) Let \(x\in A\cup(B\cap C)\text{.}\) Then \(x\in A\) or \(x\in B\cap C\text{.}\)
Case 1: \(x\in A\text{.}\) Then \(x\in A\cup B\) by the second subset relation. Similarly, \(x\in A\cup C\text{.}\) Thus, \(x\in A\cup B\) and \(x\in A\cup C\text{.}\)
Therefore, \(x\in (A\cup B) \cap (A\cup C)\text{.}\)
Case 2: \(x\in B\cap C\text{.}\) Then \(x\in B\) and \(x\in C\text{.}\) Then \(x\in A\cup B\) and \(x\in A\cup C\) by the second subset relation. Thus, \(x\in A\cup B\) and \(x\in A\cup C\text{.}\)
Therefore, \(x\in (A\cup B) \cap (A\cup C)\text{.}\)
\((\supseteq)\text{:}\) Let \(x\in (A\cup B)\cap (A\cup C)\text{.}\) Then \(x\in A\cup B\) and \(x\in A\cup C\text{.}\)
Case 1: \(x\in A\text{.}\) Then \(x\in A\cup (B\cap C)\) by the second subset relation (since we can do the union with any set).
Case 2: \(x\notin A\text{.}\) Since \(x\in A\cup B\) by assumption, \(x\in A\) or \(x\in B\text{.}\) Since \(x\notin A\text{,}\) \(x\in B\text{.}\)
Similarly, since \(x\in A\cup C\text{,}\) and \(x\notin A\text{,}\) \(x\in C\text{.}\) Thus, \(x\in B\cap C\text{.}\)
Therefore, \(x\in A\cup (B\cap C)\) (again by the second subset relation).
The proofs in Example 6.2.1 and Example 6.2.2 are called element arguments. This type of proof uses elements and the definitions of sets and subsets. You start with \(x\) being an element of the set of interest, use what you know about the set to then get \(x\) as an element of another set. This technique generalizes to sets in all different mathematical contexts.
The next theorem shows that the empty set is a subset of every set.

Proof.

By contradiction, assume there exists a set \(A\) such that \(\emptyset\nsubseteq A\text{.}\)
This means there exists \(x\in \emptyset\) such that \(x\notin A\text{.}\) But we cannot have \(x\in \emptyset\text{.}\) Hence, we have a contradiction. Therefore, \(\emptyset\subseteq A\text{.}\)
There are many times in mathematics that we need to prove that a set is empty. We might need do do this if we need sets to be disjoint, or if we need to prove that there are no elements with a particular property. The common method for proving a set is empty is to use contradiction. Note, usually if we want to prove \(A=B\text{,}\) we show both subsets (\(A\subseteq B\text{,}\) \(B\subseteq A\)), but we just showed \(\emptyset\subseteq A\text{,}\) always. So we just need to show \(A\subseteq \emptyset\text{.}\) We do this by contradiction.

Proving a Set is Empty.

To show \(A=\emptyset\text{:}\)
  • Assume \(x\in A\text{.}\)
  • Reach a contradiction.

Example 6.2.4. Proving a Set is Empty.

Prove \(U^{C}=\emptyset\text{,}\) where \(U\) is the universal set.

Proof.

Let \(x\in U^{C}\text{.}\) Then \(x\notin U\text{.}\) But since \(U\) contains everything, \(x\in U\text{,}\) which is a contradiction. Therefore, \(U^{C}=\emptyset\text{.}\)

Activity 6.2.4.

Prove \(A\cap A^C=\emptyset\text{.}\) Be sure to write what you want to assume and what you want to show.

Activity 6.2.5.

Prove if \(A\subseteq B\) then \(A\cup C\subseteq B\cup C\text{.}\) Note, you need to show \(A\cup C\subseteq B\cup C\text{.}\) So how do you show a subset? What set should you assume \(x\) is in?

Summary of Set Identities.

Let \(U\) be the universal set, and \(A, B\text{,}\) and \(C\) subsets of the universal set.
  1. Commutative Laws.
    \(A\cup B=B\cup A; \ \ A\cap B=B\cap A\)
  2. Associative Laws.
    \((A\cup B)\cup C=A\cup(B\cup C);\ \ (A\cap B)\cap C=A\cap(B\cap C)\)
  3. Distributive Laws.
    \(A\cup(B\cap C)=(A\cup B)\cap (A\cup C);\) \(A\cap(B\cup C)=(A\cap B)\cup (A\cap C)\)
  4. Identity Laws.
    \(A\cup \emptyset=A;\ \ A\cap U=A\)
  5. Complement Laws.
    \(A\cup A^C=U;\ \ A\cap A^C=\emptyset\)
  6. Double Complement Law.
    \((A^C)^C=A\)
  7. Idempotent Laws.
    \(A\cup A=A;\ \ A\cap A=A\)
  8. Universal Bound Laws.
    \(A\cup U=U;\ \ A\cap \emptyset=\emptyset\)
  9. DeMorgan’s Laws.
    \((A\cup B)^C=A^C\cap B^C;\ \ (A\cap B)^C=A^C\cup B^C\)
  10. Absorption Laws.
    \(A\cup(A\cap B)=A;\ \ A\cap(A\cup B)=A\)
  11. Complements.
    \(U^C=\emptyset;\ \ \emptyset^C=U\)
  12. Set Difference Law.
    \(A-B=A\cap B^C\)

Reading Questions Check Your Understanding

Let \(A, B, C\) be sets.

1.

    True or false: \(A\cap C=C\cap A\text{.}\)

  • True.

  • False.

2.

    True or false: \(A\cap(B\cup C)=(A\cap B)\cup (A\cap C)\text{.}\)

  • True.

  • False.

3.

    True or false: \(A\cap(B\cup C)=(A\cap B)\cup C\text{.}\)

  • True.

  • False.

4.

    True or false: \(A\cup \emptyset=\emptyset\text{.}\)

  • True.

  • False.

5.

    True or false: \((A\cup B)^C=A^C\cup B^C\text{.}\)

  • True.

  • False.

6.

    True or false: \(B-A=A-B\text{.}\)

  • True.

  • False.

7.

    Let \(U\) be the universal set. True or false: \(\emptyset\subseteq U\text{.}\)

  • True.

  • False.

8.

    True or false: \(A\subseteq A\cup(B\cap C)\text{.}\)

  • True.

  • False.

9.

    True or false: \(B\subseteq A\cup(B\cap C)\text{.}\)

  • True.

  • False.

Exercises Exercises

1.

Fill in the blanks.
  1. To say that an element is in \(A\cap(B\cup C)\) means that it is in ___ and in ___.
  2. To say that an element is in \((A\cap B)\cup C\) means that it is in ___ or in ___.
  3. To say that an element is in \(A-(B\cap C)\) means that it is in ___ and not in ___.

2.

Illustrate the distributive laws by drawing the Venn diagrams for the given sets.
  1. \(A\cup (B\cap C)\) and \((A\cup B)\cap (A\cup C)\)
  2. \(A\cap (B\cup C)\) and \((A\cap B)\cup (A\cap C)\)

3.

Illustrate DeMorgan’s laws by drawing the Venn diagrams for the given sets.
  1. \((A\cup B)^C\) and \((A^C\cap B^C)\)
  2. \((A\cap B)^C\) and \((A^C\cup B^C)\)

4.

Use an element argument to prove for all sets \(A\) and \(B\text{,}\) \((A\cap B)^C=(A^C\cup B^C)\text{.}\) Be sure to write what you want to assume and what you want to show.

5.

Use an element argument to prove for all sets \(A\) and \(B\text{,}\) \((A\cap B)\cup(A\cap B^C)=A\text{.}\) Be sure to write what you want to assume and what you want to show.

6.

Use an element argument to prove for all sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) if \(A\subseteq B\) then \((A\cap C)\subseteq (B\cap C)\text{.}\) Be sure to write what you want to assume and what you want to show.

7.

Use an element argument to prove for all sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) if \(A\subseteq B\) then \((A\cup C)\subseteq (B\cup C)\text{.}\) Be sure to write what you want to assume and what you want to show.

8.

Use an element argument to prove for all sets \(A\) and \(B\text{,}\) if \(A\subseteq B\) then \(B^C\subseteq A^C\text{.}\) Be sure to write what you want to assume and what you want to show.

9.

Use an element argument to prove for all sets \(A\) and \(B\text{,}\) \((A\cap B)\cap (A\cap B^C)=\emptyset\text{.}\)
Hint.
Proving a set is the empty set often involves a proof by contradiction.

10.

Use an element argument to prove for all sets \(A\) and \(B\text{,}\) if \(A\subseteq B\) then \(A\cap B^C=\emptyset\text{.}\)

11.

Use an element argument to prove for all sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) if \(A\subseteq B\) and \(B\cap C=\emptyset\) then \(A\cap C=\emptyset\text{.}\)
You have attempted of activities on this page.
PrevTopNext