Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 9.4 Complement, union, and intersection

First, it is often convenient to restrict the scope of the discussion.
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{.}\)

Subsection 9.4.1 Universal and relative complement

complement
the set of elements of \(U\) which are not in \(A\)
\(\cmplmnt{A}\)
the complement of \(A\) (in \(U\)), so that
\begin{equation*} \cmplmnt{A} = \setdef{ x \in U }{ x \notin A } \end{equation*}
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\)
\(B \relcmplmnt A\)
the complement of \(A\) in \(B\text{,}\) so that
\begin{equation*} B \relcmplmnt A = \setdef{ x \in B }{ x \notin A } \end{equation*}
A Venn diagram of a (universal) set complement.
A Venn diagram of a relative set complement.
Figure 9.4.1. Venn diagrams of universal and relative set complements.

Note 9.4.2.

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 \relcmplmnt A\text{.}\)

Example 9.4.3. Some examples of relative complement involving number sets.

  • Suppose \(B = \{ 1, 2, 3, 4, 5, 6 \}\) and \(A = \{ 1, 3, 5 \}\text{.}\) Then \(B \relcmplmnt A = \{ 2, 4, 6 \}\text{.}\)
  • The complement of the set of rational numbers \(\Q\) inside the set of real numbers \(\R\) is called the set of irrational numbers, and we write \(\I = \R \relcmplmnt \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.

Subsection 9.4.2 Union, intersection, and disjoint sets

union
the combined collection of all elements in a pair of sets
\(A \union B\)
the union of sets \(A\) and \(B\text{,}\) so that
\begin{equation*} A \union B = \setdef{x\in U}{x\in A \text{ or } x\in B \text{ (or both)}} \end{equation*}
intersection
the collection of only those elements common to a pair of sets
\(A \intersection B\)
the intersection of \(A\) and \(B\text{,}\) so that
\begin{equation*} A \intersection B = \setdef{x\in U}{x\in A \text{ and } x\in B} \end{equation*}
A Venn diagram of a set union.
A Venn diagram of a set intersection.
Figure 9.4.4. Venn diagrams of set union and intersection.

Note 9.4.5.

A union contains every element from both sets, so it contains both sets as subsets:
\begin{equation*} A, B \subseteq A \union 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 \intersection B \subseteq A, B \text{.} \end{equation*}

Example 9.4.6.

For subsets \(A = \{1,2,3,4\}\) and \(B = \{3,4,5,6\}\) of \(\N\text{,}\) we have
\begin{align*} A \union B \amp = \{1,2,3,4,5,6\}, \amp A \intersection B \amp = \{3,4\}. \end{align*}

Example 9.4.7.

Consider the following subsets of \(\N\text{.}\)
\begin{align*} \mathscr{E} \amp = \setdef{n\in\N}{n\text{ even}} \amp \mathscr{P} \amp = \setdef{n\in\N}{n\text{ prime, } n\ne 0} \\ \mathscr{O} \amp = \setdef{n\in\N}{n\text{ odd}} \amp \mathscr{T} \amp = \setdef{3n}{n\in\N} = \{ 0,\, 3,\, 6,\, 9,\, \dotsc \} \end{align*}
Then,
\begin{align*} \mathscr{E} \union\mathscr{O} \amp = \N, \amp \mathscr{E} \intersection \mathscr{P} \amp = \{2\}, \amp \mathscr{E} \intersection \mathscr{T} \amp = \setdef{6n}{n\in\N}, \\ \mathscr{E} \intersection \mathscr{O} \amp = \emptyset, \amp \mathscr{O} \intersection \mathscr{P} \amp = \mathscr{P} \relcmplmnt \{2\}, \amp \mathscr{O} \intersection \mathscr{T} \amp = \setdef{6n+3}{n\in\N}. \end{align*}
disjoint sets
sets that have no elements in common, i.e. sets \(A,B\) such that \(A\intersection B = \emptyset\)
disjoint union
a union \(A \union B\) where \(A\) and \(B\) are disjoint
\(A \disjunion B\)
the disjoint union of sets \(A\) and \(B\)
A Venn diagram of a disjoint set union.
Figure 9.4.8. A Venn diagram of a disjoint set union.

Example 9.4.9.

Sets \(\mathscr{E},\mathscr{O}\) from Example 9.4.7 are disjoint, and \(\N = \mathscr{E} \disjunion \mathscr{O}\text{.}\)

Remark 9.4.10.

If \(A \subseteq U\text{,}\) then we can express \(U\) as a disjoint union \(U = A \disjunion \cmplmnt{A}\text{.}\) Similarly, if \(U = A \disjunion B\text{,}\) then we must have \(B = \cmplmnt{A}\text{.}\)

Subsection 9.4.3 Rules for set operations

Recall that to prove this set equality, we need to show both
\begin{align*} \cmplmnt{(A \union B)} \amp \subseteq \cmplmnt{A} \intersection \cmplmnt{B} \text{,} \amp \cmplmnt{A} \intersection \cmplmnt{B} \amp \subseteq \cmplmnt{(A \union B)} \text{.} \end{align*}
Show \(\cmplmnt{(A \union B)} \subseteq \cmplmnt{A} \intersection \cmplmnt{B}\).
We need to show
\begin{equation*} x \in \cmplmnt{(A \union B)} \lgcimplies x \in \cmplmnt{A} \intersection \cmplmnt{B} \text{.} \end{equation*}
If \(x \in \cmplmnt{(A \union B)}\) then by definition of complement, \(x\in U\) but \(x \notin A \union B\text{.}\) Then \(x \notin A\) must be true, since if \(x\) were in \(A\) then it would also be in \(A \union B\text{.}\) Similarly, \(x \notin B\) must also be true. So \(x \in \cmplmnt{A}\) and \(x\in\cmplmnt{B}\text{;}\) i.e. \(x\in \cmplmnt{A} \intersection \cmplmnt{B}\text{.}\)
Show \(\cmplmnt{A} \intersection \cmplmnt{B} \subseteq \cmplmnt{(A \union B)} \).
We need to show
\begin{equation*} x \in \cmplmnt{A} \intersection \cmplmnt{B} \lgcimplies x \in \cmplmnt{(A \union B)} \text{.} \end{equation*}
If \(x \in \cmplmnt{A} \intersection \cmplmnt{B}\) then by definition of intersection, both \(x \in \cmplmnt{A}\) and \(x \in \cmplmnt{B}\) are true.; i.e. \(x \notin A\) and \(x \notin B\text{.}\) Since \(A \union B\) is all elements of \(U\) which are in one (or both) of \(A,B\text{,}\) we must have \(x \notin A \union B\text{.}\) Thus \(x \in \cmplmnt{(A \union B)}\text{.}\)
<Prev^TopNext>