5 Set Theory

5.3 Properties of Set Operations

5.3.1 Beginning Activity 1 (Exploring a Relationship between Two Sets)

Let $A$ and $B$ be subsets of some universal set $U$.

1. Draw two general Venn diagrams for the sets $A$ and $B$. On one, shade the region that represents ${(A\cup B)}^c$, and on the other, shade the region that represents $A^c\cap B^c$. Explain carefully how you determined these regions.

2. Based on the Venn diagrams in Part (1), what appears to be the relationship between the sets ${(A\cup B)}^c$ and $A^c\cap B^c$ ?

   Some of the properties of set operations are closely related to some of the logical operators we studied in Section 2.1. This is due to the fact that set intersection is defined using a conjunction (and), and set union is defined using a disjunction (or). For example, if $A$ and $B$ are subsets of some universal set $U$, then an element $x$ is in $A\cup B$ if and only if $x\in A$ or $x\in B$.

3. Use one of De Morgan’s Laws (Theorem 2.8) to explain carefully what it means to say that an element $x$ is not in $A\cup B$.

4. What does it mean to say that an element $x$ is in $A^c$? What does it mean to say that an element $x$ is in $B^c$?

5. Explain carefully what it means to say that an element $x$ is in $A^c\cap B^c$.

6. Compare your response in Part (3) to your response in Part (5). Are they equivalent? Explain.

7. How do you think the sets ${(A\cup B)}^c$ and $A^c\cap B^c$ are related? Is this consistent with the Venn diagrams from Part (1)?

5.3.2 Beginning Activity 2 (Proving that Statements Are Equivalent)

1. Let $X,Y$, and $Z$ be statements. Complete a truth table for $[(X\to Y)\wedge (Y\to Z)]\to (X\to Z)$.

2. Assume that $P,Q$, and $R$ are statements and that we have proven that the following conditional statements are true:

• If $P$ then $Q(P\to Q)$.

• If $R$ then $P(R\to P)$.

• If $Q$ then $R(Q\to R)$.

Explain why each of the following statements is true.

1. $P$ if and only if $Q(P\leftrightarrow Q)$.

2. $Q$ if and only if $R(Q\leftrightarrow R)$.

3. $R$ if and only if $P(R\leftrightarrow P)$.

Remember that $X\leftrightarrow Y$ is logically equivalent to $(X\to Y)\wedge (Y\to X)$.

5.3.3 Algebra of Sets - Part 1

This section contains many results concerning the properties of the set operations. We have already proved some of the results. Others will be proved in this section or in the exercises. The primary purpose of this section is to have in one place many of the properties of set operations that we may use in later proofs. These results are part of what is known as the algebra of sets or as set theory.

Theorem 5.17. Let $A,B$, and $C$ be subsets of some universal set $U$. Then

• $A\cap B\subseteq A$ and $A\subseteq A\cup B$.

• If $A\subseteq B$, then $A\cap C\subseteq B\cap C$ and $A\cup C\subseteq B\cup C$.

Proof. The first part of this theorem was included in Exercise (7) from Section 5.2. The second part of the theorem was Exercise (12) from Section 5.2.

The next theorem provides many of the properties of set operations dealing with intersection and union. Many of these results may be intuitively obvious, but to be complete in the development of set theory, we should prove all of them. We choose to prove only some of them and leave some as exercises.

Theorem 5.18 (Algebra of Set Operations). Let $A,B$, and $C$ be subsets of some universal set $U$. Then all of the following equalities hold.

Properties of the Empty Set	$A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$
and the Universal Set	$A\cup \mathrm{\varnothing }=A$
Idempotent Laws	$A\cap A=A$
Commutative Laws	$A\cap B=B\cap A$
Associative Laws	$(A\cap B)\cap C=A\cap (B\cap C)$
	$(A\cup B)\cup C=A\cup (B\cup C)$
Distributive Laws	$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
	$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

Before proving some of these properties, we note that in Section 5.2, we learned that we can prove that two sets are equal by proving that each one is a subset of the other one. However, we also know that if $S$ and $T$ are both subsets of a universal set $U$, then

$$S=T\text{ if and only if for each }x\in U,x\in S\text{ if and only if }x\in T.$$

We can use this to prove that two sets are equal by choosing an element from one set and chasing the element to the other set through a sequence of "if and only if" statements. We now use this idea to prove one of the commutative laws.

5.3.4 Proof of One of the Commutative Laws in Theorem 5.18

Proof. We will prove that $A\cap B=B\cap A$. Let $x\in U$. Then

$$x\in A\cap B\text{ if and only if }x\in A\text{ and }x\in B.$$ (1)

However, we know that if $P$ and $Q$ are statements, then $P\wedge Q$ is logically equivalent to $Q\wedge P$. Consequently, we can conclude that

$$x\in A\text{ and }x\in B\text{ if and only if }x\in B\text{ and }x\in A.$$ (2)

Now we know that

$$x\in B\text{ and }x\in A\text{ if and only if }x\in B\cap A.$$ (3)

This means that we can use (1), (2), and (3) to conclude that

$$x\in A\cap B\text{ if and only if }x\in B\cap A,$$

and, hence, we have proved that $A\cap B=B\cap A$.

5.3.5 Progress Check 5.19 (Exploring a Distributive Property)

We can use Venn diagrams to explore the more complicated properties in Theorem 5.18, such as the associative and distributive laws. To that end, let $A,B$, and $C$ be subsets of some universal set $U$.

1. Draw two general Venn diagrams for the sets $A,B$, and $C$. On one, shade the region that represents $A\cup (B\cap C)$, and on the other, shade the region that represents $(A\cup B)\cap (A\cup C)$. Explain carefully how you determined these regions.

2. Based on the Venn diagrams in Part (1), what appears to be the relationship between the sets $A\cup (B\cap C)$ and $(A\cup B)\cap (A\cup C)$ ?

5.3.6 Proof of One of the Distributive Laws in Theorem 5.18

We will now prove the distributive law explored in Progress Check 5.19. Notice that we will prove two subset relations, and that for each subset relation, we will begin by choosing an arbitrary element from a set. Also notice how nicely a proof dealing with the union of two sets can be broken into cases.

Proof. Let $A,B$, and $C$ be subsets of some universal set $U$. We will prove that $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$ by proving that each set is a subset of the other set.

We will first prove that $A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$. We let $x\in A\cup (B\cap C)$. Then $x\in A$ or $x\in B\cap C$.

So in one case, if $x\in A$, then $x\in A\cup B$ and $x\in A\cup C$. This means that $x\in (A\cup B)\cap (A\cup C)$.

On the other hand, if $x\in B\cap C$, then $x\in B$ and $x\in C$. But $x\in B$ implies that $x\in A\cup B$, and $x\in C$ implies that $x\in A\cup C$. Since $x$ is in both sets, we conclude that $x\in (A\cup B)\cap (A\cup C)$. So in both cases, we see that $x\in (A\cup B)\cap (A\cup C)$, and this proves that $A\cup (B\cap C)\subseteq (A\cup B)\cap (A\cup C)$.

We next prove that $(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$. So let $y\in (A\cup B)\cap (A\cup C)$. Then, $y\in A\cup B$ and $y\in A\cup C$. We must prove that $y\in A\cup (B\cap C)$. We will consider the two cases where $y\in A$ or $y\notin A$. In the case where $y\in A$, we see that $y\in A\cup (B\cap C)$.

So we consider the case that $y\notin A$. It has been established that $y\in A\cup B$ and $y\in A\cup C$. Since $y\notin A$ and $y\in A\cup B,y$ must be an element of $B$. Similarly,
since $y\notin A$ and $y\in A\cup C$, $y$ must be an element of $C$. Thus, $y\in B\cap C$ and, hence, $y\in A\cup (B\cap C)$.

In both cases, we have proved that $y\in A\cup (B\cap C)$. This proves that $(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$. The two subset relations establish the equality of the two sets. Thus, $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$.

5.3.7 Important Properties of Set Complements

The three main set operations are union, intersection, and complementation. Theorems 5.18 and 5.17 deal with properties of unions and intersections. The next theorem states some basic properties of complements and the important relations dealing with complements of unions and complements of intersections. Two relationships in the next theorem are known as De Morgan’s Laws for sets and are closely related to De Morgan’s Laws for statements.

Theorem 5.20. Let $A$ and $B$ be subsets of some universal set $U$. Then the following are true:

Basic Properties	${\left(A^c\right)}^c=A$ $A-B=A\cap B^c$
Empty Set and Universal Set	$A-\mathrm{\varnothing }=A\text{ and }A-U=\mathrm{\varnothing }$ ${\mathrm{\varnothing }}^c=U\text{ and }{U}^c=\mathrm{\varnothing }$
De Morgan’s Laws	${(A\cap B)}^c=A^c\cup B^c$ ${(A\cup B)}^c=A^c\cap B^c$
Subsets and Complements	$A\subseteq B$ if and only if $B^c\subseteq A^c$

Proof. We will only prove one of De Morgan’s Laws, namely, the one that was explored in Beginning Activity 1. The proofs of the other parts are left as exercises. Let $A$ and $B$ be subsets of some universal set $U$. We will prove that ${(A\cup B)}^c=A^c\cap B^c$ by proving that an element is in ${(A\cup B)}^c$ if and only if it is in $A^c\cap B^c$. So let $x$ be in the universal set $U$. Then

$$x\in {(A\cup B)}^c\text{ if and only if }x\notin A\cup B,$$ (1)

and

$$x\notin A\cup B\text{ if and only if }x\notin A\text{ and }x\notin B\text{. }$$ (2)

Combining (1) and (2), we see that

$$x\in {(A\cup B)}^c\text{ if and only if }x\notin A\text{ and }x\notin B\text{. }$$ (3)

In addition, we know that

$$x\notin A\text{ and }x\notin B\text{ if and only if }x\in A^c\text{ and }x\in B^c,$$ (4)

and this is true if and only if $x\in A^c\cap B^c$. So we can use (3) and (4) to conclude that

$$x\in {(A\cup B)}^c\text{ if and only if }x\in A^c\cap B^c,$$

and, hence, that ${(A\cup B)}^c=A^c\cap B^c$.

5.3.8 Progress Check 5.21 (Using the Algebra of Sets)

1. Draw two general Venn diagrams for the sets $A,B$, and $C$. On one, shade the region that represents $(A\cup B)-C$, and on the other, shade the region that represents $(A-C)\cup (B-C)$. Explain carefully how you determined these regions and why they indicate that $(A\cup B)-C=(A-C)\cup (B-C)$.

It is possible to prove the relationship suggested in Part (1) by proving that each set is a subset of the other set. However, the results in Theorems 5.18 and 5.20 can be used to prove other results about set operations. When we do this, we say that we are using the algebra of sets to prove the result. For example, we can start by using one of the basic properties in Theorem 5.20 to write

$$(A\cup B)-C=(A\cup B)\cap C^c.$$

We can then use one of the commutative properties to write

$(A\cup B)-C$ $=(A\cup B)\cap C^c$

$=C^c\cap (A\cup B)$

1. Determine which properties from Theorems 5.18 and 5.20 justify each of the last three steps in the following outline of the proof that $(A\cup B)-C=(A-C)\cup (B-C)$.

   Note: It is sometimes difficult to use the properties in the theorems when the theorems use the same letters to represent the sets as those being used in the current problem. For example, one of the distributive properties from Theorems 5.18 can be written as follows: For all sets $X,Y$, and $Z$ that are subsets of a universal set $U$,

   $$X\cap (Y\cup Z)=(X\cap Y)\cup (X\cap Z).$$

5.3.9 Proving that Statements Are Equivalent

When we have a list of three statements $P,Q$, and $R$ such that each statement in the list is equivalent to the other two statements in the list, we say that the three statements are equivalent. This means that each of the statements in the list implies each of the other statements in the list.

The purpose of Beginning Activity 2 was to provide one way to prove that three (or more) statements are equivalent. The basic idea is to prove a sequence of conditional statements so that there is an unbroken chain of conditional statements from each statement to every other statement. This method of proof will be used in Theorem 5.22.

Theorem 5.22. Let $A$ and $B$ be subsets of some universal set $U$. The following are equivalent:

1. $A\subseteq B$

2. $A\cap B^c=\mathrm{\varnothing }$

3. $A^c\cup B=U$

Proof. To prove that these are equivalent conditions, we will prove that (1) implies (2), that (2) implies (3), and that (3) implies (1).

Let $A$ and $B$ be subsets of some universal set $U$. We have proved that (1) implies (2) in Proposition 5.14.

To prove that (2) implies (3), we will assume that $A\cap B^c=\mathrm{\varnothing }$ and use the fact that ${\mathrm{\varnothing }}^c=U$. We then see that

$${\left(A\cap B^c\right)}^c={\mathrm{\varnothing }}^c.$$

Then, using one of De Morgan’s Laws, we obtain

$A^c\cup {\left(B^c\right)}^c$ $=U$

$A^c\cup B$ $=U.$

This completes the proof that (2) implies (3).
We now need to prove that (3) implies (1). We assume that $A^c\cup B=U$ and will prove that $A\subseteq B$ by proving that every element of $A$ must be in $B$.

So let $x\in A$. Then we know that $x\notin A^c$. However, $x\in U$ and since $A^c\cup B=U$, we can conclude that $x\in A^c\cup B$. Since $x\notin A^c$, we conclude that $x\in B$. This proves that $A\subseteq B$ and hence that (3) implies (1).

Since we have now proved that (1) implies (2), that (2) implies (3), and that (3) implies (1), we have proved that the three conditions are equivalent.

5.3.10 Exercises for Section 5.3

1. Let $A$ be a subset of some universal set $U$. Prove each of the following (from Theorem 5.20):

   1. $(\star )$ ${\left(A^c\right)}^c=A$

   2. $A-\mathrm{\varnothing }=A$

   3. $(\star )$ ${\mathrm{\varnothing }}^c=U$

   4. $U^c=\mathrm{\varnothing }$

2. $(\star )$ Let $A,B$, and $C$ be subsets of some universal set $U$. As part of Theorem 5.18, we proved one of the distributive laws. Prove the other one. That is, prove that

   $$A\cap (B\cup C)=(A\cap B)\cup (A\cap C).$$

3. Let $A,B$, and $C$ be subsets of some universal set $U$. As part of Theorem 5.20, we proved one of De Morgan’s Laws. Prove the other one. That is, prove that

   $${(A\cap B)}^c=A^c\cup B^c$$

4. Let $A,B$, and $C$ be subsets of some universal set $U$.

   1. $(\star )$ Draw two general Venn diagrams for the sets $A,B$, and $C$. On one, shade the region that represents $A-(B\cup C)$, and on the other, shade the region that represents $(A-B)\cap (A-C)$. Based on the Venn diagrams, make a conjecture about the relationship between the sets $A-(B\cup C)$ and $(A-B)\cap (A-C)$.

   2. Use the choose-an-element method to prove the conjecture from Exercise (4a).

   3. $(\star )$ Use the algebra of sets to prove the conjecture from Exercise (4a).

5. Let $A,B$, and $C$ be subsets of some universal set $U$.

   1. Draw two general Venn diagrams for the sets $A,B$, and $C$. On one, shade the region that represents $A-(B\cap C)$, and on the other, shade the region that represents $(A-B)\cup (A-C)$. Based on the Venn diagrams, make a conjecture about the relationship between the sets $A-(B\cap C)$ and $(A-B)\cup (A-C)$.

   2. Use the choose-an-element method to prove the conjecture from Exercise (5a).

   3. Use the algebra of sets to prove the conjecture from Exercise (5a).

6. Let $A,B$, and $C$ be subsets of some universal set $U$. Prove or disprove each of the following:

   1. $(A\cap B)-C=(A-C)\cap (B-C)$

   2. $(A\cup B)-(A\cap B)=(A-B)\cup (B-A)$

7. Let $A,B$, and $C$ be subsets of some universal set $U$.

   1. Draw two general Venn diagrams for the sets $A,B$, and $C$. On one, shade the region that represents $A-(B-C)$, and on the other, shade the region that represents $(A-B)-C$. Based on the Venn diagrams, make a conjecture about the relationship between the sets $A-(B-C)$ and $(A-B)-C$. (Are the two sets equal? If not, is one of the sets a subset of the other set?)

   2. Prove the conjecture from Exercise (7a).

8. Let $A,B$, and $C$ be subsets of some universal set $U$.

   1. Draw two general Venn diagrams for the sets $A,B$, and $C$. On one, shade the region that represents $A-(B-C)$, and on the other, shade the region that represents $(A-B)\cup \left(A-C^c\right)$. Based on the Venn diagrams, make a conjecture about the relationship between the sets $A-(B-C)$ and $(A-B)\cup \left(A-C^c\right)$. (Are the two sets equal? If not, is one of the sets a subset of the other set?)

   2. Prove the conjecture from Exercise (8a).

9. Let $A$ and $B$ be subsets of some universal set $U$.

   1. Prove that $A$ and $B-A$ are disjoint sets.

   2. Prove that $A\cup B=A\cup (B-A)$.

10. Let $A$ and $B$ be subsets of some universal set $U$.

    1. Prove that $A-B$ and $A\cap B$ are disjoint sets.

    2. Prove that $A=(A-B)\cup (A\cap B)$.

11. Let $A$ and $B$ be subsets of some universal set $U$. Prove or disprove each of the following:

    1. $A-\left(A\cap B^c\right)=A\cap B$

    2. ${\left(A^c\cup B\right)}^c\cap A=A-B$

    3. $(A\cup B)-A=B-A$

    4. $(A\cup B)-B=A-(A\cap B)$

12. Evaluation of proofs. See the instructions for Exercise (19) from Section 3.1.

    1. If $A,B$, and $C$ are subsets of some universal set $U$, then $A-(B-C)=A-(B\cup C)$.

       Proof.

       $A-(B-C)$ $=(A-B)-(A-C)$

       $=\left(A\cap B^c\right)\cap \left(A\cap C^c\right)$

       $=A\cap \left(B^c\cap C^c\right)$

       $=A\cap {(B\cup C)}^c$

       $=A-(B\cup C)$

    2. If $A,B$, and $C$ are subsets of some universal set $U$, then $A-(B\cup C)=(A-B)\cap (A-C)$.

       Proof. We first write $A-(B\cup C)=A\cap {(B\cup C)}^c$ and then use one of De Morgan’s Laws to obtain

       $$A-(B\cup C)=A\cap \left(B^c\cap C^c\right).$$

       We now use the fact that $A=A\cap A$ and obtain
       $A-(B\cup C)=A\cap A\cap B^c\cap C^c=\left(A\cap B^c\right)\cap \left(A\cap C^c\right)=(A-B)\cap (A-C)$.

5.3.11 Explorations and Activities

1. (Comparison to Properties of the Real Numbers). The following are some of the basic properties of addition and multiplication of real numbers.

Commutative Laws: $a+b=b+a$, for all $a,b\in ℝ$. $a\cdot b=b\cdot a$, for all $a,b\in ℝ$.

Associative Laws: $(a+b)+c=a+(b+c)$, for all $a,b,c\in ℝ$. $(a\cdot b)\cdot c=a\cdot (b\cdot c)$, for all $a,b,c\in ℝ$.

Distributive Law: $a\cdot (b+c)=a\cdot b+a\cdot c$, for all $a,b,c\in ℝ$.

Additive Identity:   For all $a\in ℝ,a+0=a=0+a$.

Multiplicative Identity: For all $a\in ℝ,a\cdot 1=a=1\cdot a$.

Additive Inverses:   For all $a\in ℝ,a+(-a)=0=(-a)+a$.

Multiplicative Inverses: For all $a\in ℝ$ with $a\ne 0,a\cdot a^{-1}=1=a^{-1}\cdot a$.

Discuss the similarities and differences among the properties of addition and multiplication of real numbers and the properties of union and intersection of sets.