9.4: Complement, union, and intersection

First, it is often convenient to restrict the scope of the discussion.

Definition: Universal set

a set that contains all objects currently under consideration

We will consider all of the following set operations to be performed within a universal set $U\text{.}$ In particular, suppose $A,B\subseteq U\text{.}$

9.4.1: Universal and relative complement

Definition: Complement

the set of elements of $U$ which are not in $A$

Definition: $A^{C}$

the complement of $A$ (in $U$), so that

$$\begin{equation*} A^{C} = \{ x \in U \vert x \notin A \} \end{equation*}$$

Definition: Relative complement

if $A,B \subseteq U\text{,}$ the complement of $A$ in $B$ is the set of elements of $B$ which are not in $A$

Definition: $B \setminus A$

the complement of $A$ in $B\text{,}$ so that

$$\begin{equation*} B \setminus A = \{ x \in B \vert x \notin A \} \end{equation*}$$

Figure $\PageIndex{1}$: Venn diagrams of universal and relative set complements.

 

 

Note $\PageIndex{1}$

Another common notation for relative complement is $B - A\text{.}$ However, this conflicts with the notation for the algebraic operation of subtraction in certain contexts, so we will prefer the notation $B \setminus A\text{.}$

Example $\PageIndex{1}$: Some examples of relative complement involving number sets

• Suppose $B = \{ 1, 2, 3, 4, 5, 6 \}$ and $A = \{ 1, 3, 5 \}\text{.}$ Then $B \setminus A = \{ 2, 4, 6 \}\text{.}$
• The complement of the set of rational numbers $\mathbb{Q}$ inside the set of real numbers $\mathbb{R}$ is called the set of irrational numbers, and we write $\mathbb{I} = \mathbb{R} \setminus \mathbb{Q}$ for this set. If you are thinking of real numbers in terms of their decimal expanions, the irrational numbers are precisely those that have nonterminating, nonrepeating decimal expansions.

9.4.2: Union, intersection, and disjoint sets

Definition: Union

the combined collection of all elements in a pair of sets

Definition: $A \cup B$

the union of sets $A$ and $B\text{,}$ so that

$$\begin{equation*} A \cup B = \{ x\in U \vert x\in A \text{ or } x\in B \text{ (or both)}\} \end{equation*}$$

Definition: Intersection

the collection of only those elements common to a pair of sets

Definition: $A \cap B$

the intersection of $A$ and $B\text{,}$ so that

$$\begin{equation*} A \cap B = \{x\in U \vert x\in A \text{ and } x\in B \} \end{equation*}$$

Figure $\PageIndex{1}$: Venn diagrams of set union and intersection.

Note $\PageIndex{2}$

A union contains every element from both sets, so it contains both sets as subsets:

$$\begin{equation*} A, B \subseteq A \cup B \text{.} \end{equation*}$$

On the other hand, every element in an intersection is in both sets, so the intersection is a subset of both sets:

$$\begin{equation*} A \cap B \subseteq A, B \text{.} \end{equation*}$$

Example $\PageIndex{2}$

For subsets $A = \{1,2,3,4\}$ and $B = \{3,4,5,6\}$ of $\mathbb{N}\text{,}$ we have

$$\begin{align*} A \cup B & = \{1,2,3,4,5,6\}, & A \cap B & = \{3,4\}. \end{align*}$$

Example $\PageIndex{3}$

Consider the following subsets of $\mathbb{N}\text{.}$

$$\begin{align*} \scr{E} & = \{ n\in\mathbb{N} \vert n\text{ even}\} & \scr{P} & = \{n\in\mathbb{N} \vert n\text{ prime, } n\mathbb{N}e 0\} \\ \scr{O} & = \{ n\in\mathbb{N} \vert n\text{ odd} \} & \scr{T} & = \{3n \vert n\in\mathbb{N} \} = \{ 0,\, 3,\, 6,\, 9,\, \ldots \} \end{align*}$$
Then,

$$\begin{align*} \scr{E} \cup\scr{O} & = \mathbb{N}, & \scr{E} \cap \scr{P} & = \{2\}, & \scr{E} \cap \scr{T} & = \{6n \vert n\in\mathbb{N} \}, \\ \scr{E} \cap \scr{O} & = \emptyset, & \scr{O} \cap \scr{P} & = \scr{P} \setminus \{2\}, & \scr{O} \cap \scr{T} & = \{6n+3 \vert n\in\mathbb{N}\}. \end{align*}$$

Definition: Disjoint Sets

sets that have no elements in common, i.e. sets $A,B$ such that $A\cap B = \emptyset$

Definition: Disjoint Union

a union $A \cup B$ where $A$ and $B$ are disjoint

Definition: $A \sqcup B$

the disjoint union of sets $A$ and $B$

Figure $\PageIndex{2}$: A Venn diagram of a disjoint set union.

Example $\PageIndex{4}$

Sets $\scr{E},\scr{O}$ from Example $\PageIndex{3}$ are disjoint, and $\mathbb{N} = \scr{E} \sqcup \scr{O}\text{.}$

Remark $\PageIndex{1}$

If $A \subseteq U\text{,}$ then we can express $U$ as a disjoint union $U = A \sqcup A^{C}\text{.}$ Similarly, if $U = A \sqcup B\text{,}$ then we must have $B = A^{C}\text{.}$

9.4.3: Rules for set operations

Proposition $\PageIndex{1}$: Rules for Operations on Sets

Suppose $A,B,C$ are subsets of a universal set $U\text{.}$ Then the following set equalities hold.

1. Properties of the universal set.
   1. $\displaystyle A \cup U = U$
   2. $\displaystyle A \cap U = A$
2. Properties of the empty set.
   1. $\displaystyle A \cup \emptyset = A$
   2. $\displaystyle A \cap \emptyset = \emptyset$
3. Duality of universal and empty sets.
   1. $\displaystyle U^{C} = \emptyset$
   2. $\displaystyle \emptyset ^{C} = U$
4. $\displaystyle (A^{C})^C = A$
5. Idempotence.
   1. $\displaystyle A \cup A = A$
   2. $\displaystyle A \cap A = A$
6. Commutativity.
   1. $\displaystyle A \cup B = B \cup A$
   2. $\displaystyle A \cap B = B \cap A$
7. Associativity.
   1. $\displaystyle (A \cup B) \cup C = A \cup (B \cup C)$
   2. $\displaystyle (A \cap B) \cap C = A \cap (B \cap C)$
8. Distributivity.
   1. $\displaystyle A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
   2. $\displaystyle A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
   3. $\displaystyle (A \cup B) \cap C = (A \cap C) \cup (B \cap C)$
   4. $\displaystyle (A \cap B) \cup C = (A \cup C) \cap (B \cup C)$
9. DeMorgan's Laws.
   1. $\displaystyle (A \cup B)^C = A^{C} \cap B^C$
   2. $\displaystyle (A \cap B)^C = A^{C} \cup B^C$

 

Proof of Rule 9.a.

Recall that to prove this set equality, we need to show both

$$\begin{align*} (A \cup B)^C & \subseteq A^{C} \cap B^C \text{,} & A^{C} \cap B^C & \subseteq (A \cup B)^C \text{.} \end{align*}$$

Show $(A \cup B)^C \subseteq A^{C} \cap B^C$.
We need to show

$$\begin{equation*} x \in (A \cup B)^C \Rightarrow x \in A^{C} \cap B^C \text{.} \end{equation*}$$

If $x \in (A \cup B)^C$ then by definition of complement, $x\in U$ but $x \notin A \cup B\text{.}$ Then $x \notin A$ must be true, since if $x$ were in $A$ then it would also be in $A \cup B\text{.}$ Similarly, $x \notin B$ must also be true. So $x \in A^{C}$ and $x\in B^C\text{;}$ i.e. $x\in A^{C} \cap B^C\text{.}$

Show $A^{C} \cap B^C \subseteq (A \cup B)^C$. We need to show

$$\begin{equation*} x \in A^{C} \cap B^C \Rightarrow x \in (A \cup B)^C \text{.} \end{equation*}$$

If $x \in A^{C} \cap B^C$ then by definition of intersection, both $x \in A^{C}$ and $x \in B^C$ are true.; i.e. $x \notin A$ and $x \notin B\text{.}$ Since $A \cup B$ is all elements of $U$ which are in one (or both) of $A,B\text{,}$ we must have $x \notin A \cup B\text{.}$ Thus $x \in (A \cup B)^C\text{.}$

Proofs of the other rules.

These are left to you, the reader, in the Exercise 9.9.1.

 

Remark $\PageIndex{2}$

Compare the set operation rules of the proposition above with the Rules of Propositional Calculus.