Set Operations

# Set Operations

We are now ready to look at some operations between two sets $A$ and $B$.

## The Intersection of Sets

 Definition: The Intersection of the sets $A$ and $B$ denoted $A \cap B$ is the set of elements $x$ such that $x \in A$ and $x \in B$.

Using set-builder notation, we have that the intersection of $A$ and $B$ is given by:

(1)
\begin{align} \quad A \cap B = \{ x : x \in A \: \mathrm{and} \: x \in B \} \end{align}

For example, consider the sets $A = \{ 1, 2, 3, 4, 5 \}$ and $B = \{ 2, 4, 6, 8, 10 \}$. We have that the intersection of $A$ and $B$ is $A \cap B = \{ 2, 4 \}$.

Of course, it is possible that the intersection of two sets contains no elements in common.

 Definition: If the intersection of the sets $A$ and $B$ contains no elements, that is $A \cap B = \emptyset$ then $A$ and $B$ are said to be Disjoint sets from one another.

For example, the set of all even integers $E = \{ x \in \mathbb{Z} : x \: \mathrm{is \: even} \}$ and the set of all odd integers $O = \{ x \in \mathbb{Z} : x \: \mathrm{is \: odd} \}$ are disjoint, i.e, $E \cap O = \emptyset$ because there exists no integer that is both even and odd.

If we have a finite number of sets, $A_1, A_2, ..., A_n$ then the intersection between all of these sets is defined in set-builder notation as:

(2)
\begin{align} \quad \bigcap_{i=1}^{n} A_i = \{ x : x \in A_1, x \in A_2, ..., x \in A_n \} \end{align}

Of course, this definition can be extended as expected if we want to determine the intersection of an infinite number of sets.

## The Union of Two Sets

 Definition: The Union of the sets $A$ and $B$ denoted $A \cup B$ is defined to be the set of elements $x$ such that $x \in A$ or $x \in B$ or $x \in A \cap B$.

The definition above uses the "inclusive" or - that is $A \cup B$ is the set of elements $x$ such that $x$ must be in at least one of $A$ or $B$.

In set-builder notation we can define the union between two sets to be:

(3)
\begin{align} \quad A \cup B = \{ x : x \in A \: \mathrm{or} \: x \in B \} \end{align}

For example, consider the sets $A = \{ 1, 2, 3 \}$ and $B = \{2, 3, 4 \}$. Then $A \cup B = \{1, 2, 3, 4 \}$.

Once again, if $A_1, A_2, ..., A_n$ are a finite number of sets then the union between these sets in set-builder notation is:

(4)
\begin{align} \quad \bigcup_{i=1}^{n} A_i = \{ x : x \in A_1, \: \mathrm{or} \: x \in A_2 \:, ..., \: \mathrm{or} \: x \in A_n \} \end{align}

## The Symmetric Difference of Two Sets

 Definition: The Symmetric Difference of the sets $A$ and $B$ denoted $A \oplus B$ is the set of elements $x$ such that $x \in A$ or $x \in B$ and $x \not \in A \cap B$.

Notice that the symmetric difference of two sets is similar to the union of two sets however elements that are in both $A$ and $B$ are no longer included. For example, consider the sets $A = \{ 1, 2, 3 \}$ and $B = \{2, 3, 4 \}$ from above. Then $A \oplus B = \{1, 4 \}$.

With the definitions above, we can now prove a somewhat useful result regarding the equality of the union and symmetric difference between two sets.

 Theorem 1: Let $A$ and $B$ be sets. Then $A \cup B = A \oplus B$ if and only if $A$ and $B$ are disjoint.
• Proof: $\Rightarrow$ Suppose that $A \cup B = A \oplus B$ and assume that $A$ and $B$ are not disjoint. Then there exists an element $x \in A \cap B$. If $x \in A \cap B$ then $x \in A \cup B$ and $x \not \in A \oplus B$. But $A \cup B = A \oplus B$, so we have a contradiction and our assumption that $A$ and $B$ are not disjoint was false. Therefore $A \cap B = \emptyset$.
• $\Leftarrow$ Suppose that $A$ and $B$ are disjoint. Then $A \cap B = \emptyset$. To show that $A \cup B = A \oplus B$ we must show that $A \cup B \subset A \oplus B$ and that $A \oplus B \subseteq A \cup B$.
• Let $x \in A \cup B$. Then $x \in A$ or $x \in B$, however, $x \not \in A \cap B$ since $A \cap B = \emptyset$. Therefore $x \in A$ or $x \in B$ and $x \not \in A \cap B$, i.e, $x \in A \oplus B$.
• Now let $x \in A \oplus B$. Then $x \in A$ or $x \in B$ and $x \not \in A \cap B$. Since $A \cap B = \emptyset$, we have that $x \not \in A \cap B$ is given so $x \in A \cup B$. $\blacksquare$

Like before - we can define the symmetric difference of a finite number of sets $A_1, A_2, ..., A_n$ as:

(5)
\begin{align} \quad \bigoplus_{i=1}^{n} A_i = \{ x : x \: \mathrm{is \: in \: only \: one \: A_j \: for} \: j = 1, 2, ..., n \} \end{align}

## The Set-Theoretic Difference of Sets

 Definition: The Set-Theoretic Difference of the set $A$ to $B$ denoted $A \setminus B$ is the set of elements $x$ such that $x \in A$ and $x \not \in B$.

The term "Relative Complement of $B$ to $A$" is also sometimes used to mean the same thing.

In terms of set-builder notation we have that:

(6)
\begin{align} \quad A \setminus B = \{ x : x \in A \quad \mathrm{and} \: x \not \in B \} \end{align}

For example, if $A = \{1, 3, 5\}$ and $B = \{3, 5, 7 \}$ then $A \setminus B = \{ 1 \}$.