# Set Operations

## Introduction

Let $U$ be the universal set consisting of all people you know and $A,B \subseteq U$:

$A = \{$people who have brown hair$\}$

$B = \{$ people who have green eyes$\}$

Of course, some people with brown hair also have green eyes. What would be the union of sets $A$ and $B$? Intuitively, it is a set consisting of all elements of both sets. Therefore, the union would be a set of all people with brown hair and people with green eyes (including those who have both). What about the intersection of sets? Intuitively, it is a set consisting of elements that sets $A$ and $B$ have in common. Therefore, the intersection would be a set of all people with brown hair, but those who also have green eyes.

## Definitions and examples

Definition: Let $U$ be the universal set and $A,B$ its subsets.

a) The union of sets $A$ and $B$, denoted by $A \cup B$, is a set

$$A \cup B = \{x \in U: x \in A \lor x \in B\}$$

b) The intersection of sets $A$ and $B$, denoted by $A \cap B$, is a set

$$A \cap B = \{x \in U: x \in A \land x \in B\}$$

c) The difference of sets $A$ and $B$, denoted by $A \setminus B$, is a set

$$A \setminus B = \{x \in U: x \in A \land x \notin B\}$$.

Operations $\cup, \cap, \setminus$ are called Boolean set operations.

In representing sets, it is useful to draw Venn diagrams. In Venn diagram, a circle represents a set and overlapping circles illustrate relations between sets (their union, intersection etc.).

$A \cup B$:                               $A \cap B$:                                             $A \setminus B$:

Example 1: Let $A = \{$x: x is even number $3<x<10$$\} and B = \{x: x is even number 3<x<15$$\}$ be the subsets of $U$. Find:

a) $A \cup B$

b) $A \cap B$

c) $B \setminus A$.

Solution:

$$A = \{4, 6, 8\}, B = \{4, 6, 8, 10, 12, 14\}$$

a) $A \cup B = \{4, 6, 8, 10, 12, 14\} = B$

b) $A \cap B = \{4, 6, 8\} = A$

c) $B \setminus A = \{10, 12, 14\}$

Definition: Let $U$ be the universal set and $A,B$ its subsets.

The symmetric difference of set $A$ with respect to set $B$ is the set of elements which are in either of the sets, but not in their intersection. It is denoted by $A \triangle B$. We also write:

$$A \triangle B = (A\setminus B) \cup (B\setminus A)$$

Definition: Let $U$ be the universal set and $A$ its subset.

The complement of set $A$ is the set of elements which don’t belong to $A$. It is denoted by $A ^\mathsf{c}$.

$$A ^\mathsf{c}= U \setminus A = \{x \in U: x \notin A\}$$

Example 2:  Let $A = \{$x: x is a whole number $-5\leq x \leq 2$$\} and B = \{x: x is a whole number -3 \leq x \leq 3$$\}$ be the subsets of $U = \{x: -8\leq x \leq 4\}$. Find:

a) $A \triangle B$

b) $A ^\mathsf{c}, B ^\mathsf{c}$

Solution:

$A = \{-5,-4, -3, -2, -1, 0, 1, 2\}$, $B = \{-3, -2, -1, 0, 1, 2, 3\}$, $U = \{-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4\}$

a) $A \triangle B = (A\setminus B) \cup (B\setminus A)$

$(A\setminus B) = \{-5, -4\}$, $B\setminus A = \{3\}$

$A \triangle B = \{-5, -4, 3\}$

b) $A ^\mathsf{c} = \{-8, -7, -6, 3, 4\}$, $B^\mathsf{c} = \{-8, -7, -6, -5, -4, 4\}$

Definition: Let $U$ be the universal set and $A,B$ its non – empty subsets.

Sets $A$ and $B$ are said to be disjoint sets if they have no element in common. We write: $A \cap B = \emptyset$.

## Properties of Boolean set operations

Theorem: Let $U$ be the universal set and $A$ its subset.

1) $A \cup A = A$, $A \cap A = A$ (idempotency)

2) $A \cup U = U$, $A \cap U = A$

3) $A \cup \emptyset = A$, $A \cap \emptyset = \emptyset$

4) $A \cup A ^\mathsf{c} = U$, $A \cap A ^\mathsf{c} = \emptyset$

5) $(A ^\mathsf{c})^\mathsf{c}=A$.

Theorem: Let $U$ be the universal set and $A, B$ its subsets.

1) $A \cup B = B \cup A$, $A \cap B = B \cap A$ (commutativity)

2) $(A \cup B)^\mathsf{c} = A^\mathsf{c} \cap B^\mathsf{c}$, $(A \cap B)^\mathsf{c} = A^\mathsf{c} \cup B^\mathsf{c}$ (De Morgan’s laws).

Theorem: Let $U$ be the universal set and $A, B,C$ its subsets.

1) $(A \cup B) \cup C = A \cup (B \cup C)$ (associativity of unions)

2) $(A \cap B) \cap C = A \cap (B \cap C)$ (associativity of intersection)

3) $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ (distributivity for union over intersection)

4) $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ (distributivity for intersection over union).