---

The union of two sets is a set containing all elements that are in $A$ or in $B$ (possibly both). For example, $\{1,2\}\cup\{2,3\}=\{1,2,3\}$. Thus, we can write $x\in(A\cup B)$ if and only if $(x\in A)$ or $(x\in B)$. Note that $A \cup B=B \cup A$. In Figure 1.4, the union of sets $A$ and $B$ is shown by the shaded area in the Venn diagram.

Similarly we can define the union of three or more sets. In particular, if $A_1, A_2, A_3,\cdots, A_n$ are $n$ sets, their union $A_1 \cup A_2 \cup A_3 \cdots \cup A_n$ is a set containing all elements that are in at least one of the sets. We can write this union more compactly by $$\bigcup_{i=1}^{n} A_i.$$ For example, if $A_1=\{a,b,c\}, A_2=\{c,h\}, A_3=\{a,d\}$, then $\bigcup_{i} A_i=A_1 \cup A_2 \cup A_3=\{a,b,c,h,d\}$. We can similarly define the union of infinitely many sets $A_1 \cup A_2 \cup A_3 \cup\cdots$.

The intersection of two sets $A$ and $B$, denoted by $A \cap B$, consists of all elements that are both in $A$ $\underline{\textrm{and}}$ $B$. For example, $\{1,2\}\cap\{2,3\}=\{2\}$. In Figure 1.5, the intersection of sets $A$ and $B$ is shown by the shaded area using a Venn diagram.

More generally, for sets $A_1,A_2,A_3,\cdots$, their intersection $\bigcap_i A_i$ is defined as the set consisting of the elements that are in all $A_i$'s. Figure 1.6 shows the intersection of three sets.

The complement of a set $A$, denoted by $A^c$ or $\bar{A}$, is the set of all elements that are in the universal set $S$ but are not in $A$. In Figure 1.7, $\bar{A}$ is shown by the shaded area using a Venn diagram.

The difference (subtraction) is defined as follows. The set $A-B$ consists of elements that are in $A$ but not in $B$. For example if $A=\{1,2,3\}$ and $B=\{3,5\}$, then $A-B=\{1,2\}$. In Figure 1.8, $A-B$ is shown by the shaded area using a Venn diagram. Note that $A-B=A \cap B^c$.

Two sets $A$ and $B$ are mutually exclusive or disjoint if they do not have any shared elements; i.e., their intersection is the empty set, $A \cap B=\emptyset$. More generally, several sets are called disjoint if they are pairwise disjoint, i.e., no two of them share a common element. Figure 1.9 shows three disjoint sets.

If the earth's surface is our sample space, we might want to partition it to the different continents. Similarly, a country can be partitioned to different provinces. In general, a collection of nonempty sets $A_1, A_2,\cdots$ is a partition of a set $A$ if they are disjoint and their union is $A$. In Figure 1.10, the sets $A_1, A_2, A_3$ and $A_4$ form a partition of the universal set $S$.

Here are some rules that are often useful when working with sets. We will see examples of their usage shortly.

---

Theorem : De Morgan's law

For any sets $A_1$, $A_2$, $\cdots$, $A_n$, we have

• $(A_1 \cup A_2 \cup A_3 \cup \cdots A_n)^c=A_1^c \cap A_2^c \cap A_3^c\cdots \cap A_n^c$;
• $(A_1 \cap A_2 \cap A_3 \cap \cdots A_n)^c=A_1^c \cup A_2^c \cup A_3^c\cdots \cup A_n^c$.

---

Theorem : Distributive law

For any sets $A$, $B$, and $C$ we have

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

---

Example

If the universal set is given by $S=\{1,2,3,4,5,6\}$, and $A=\{1,2\}$, $B=\{2,4,5\}, C=\{1,5,6\} $ are three sets, find the following sets:

1. $A \cup B$
2. $A \cap B$
3. $\overline{A}$
4. $\overline{B}$
5. Check De Morgan's law by finding $(A \cup B)^c$ and $A^c \cap B^c$.
6. Check the distributive law by finding $A \cap (B \cup C)$ and $(A \cap B) \cup (A\cap C)$.

---

A Cartesian product of two sets $A$ and $B$, written as $A\times B$, is the set containing ordered pairs from $A$ and $B$. That is, if $C=A \times B$, then each element of $C$ is of the form $(x,y)$, where $x \in A$ and $y \in B$: $$A \times B = \{(x,y) | x \in A \textrm{ and } y \in B \}.$$ For example, if $A=\{1,2,3\}$ and $B=\{H,T\}$, then $$A \times B=\{(1,H),(1,T),(2,H),(2,T),(3,H),(3,T)\}.$$ Note that here the pairs are ordered, so for example, $(1,H)\neq (H,1)$. Thus $A \times B$ is not the same as $B \times A$.

If you have two finite sets $A$ and $B$, where $A$ has $M$ elements and $B$ has $N$ elements, then $A \times B$ has $M \times N$ elements. This rule is called the multiplication principle and is very useful in counting the numbers of elements in sets. The number of elements in a set is denoted by $|A|$, so here we write $|A|=M, |B|=N$, and $|A \times B|=MN$. In the above example, $|A|=3, |B|=2$, thus $|A \times B|=3 \times 2 = 6$. We can similarly define the Cartesian product of $n$ sets $A_1, A_2, \cdots, A_n$ as $$A_1 \times A_2 \times A_3 \times \cdots \times A_n = \{(x_1, x_2, \cdots, x_n) | x_1 \in A_1 \textrm{ and } x_2 \in A_2 \textrm{ and }\cdots x_n \in A_n \}.$$ The multiplication principle states that for finite sets $A_1, A_2, \cdots, A_n$, if $$|A_1|=M_1, |A_2|=M_2, \cdots, |A_n|=M_n,$$ then $$\mid A_1 \times A_2 \times A_3 \times \cdots \times A_n \mid=M_1 \times M_2 \times M_3 \times \cdots \times M_n.$$

An important example of sets obtained using a Cartesian product is $\mathbb{R}^n$, where $n$ is a natural number. For $n=2$, we have

$\mathbb{R}^2$	$= \mathbb{R}\times \mathbb{R}$
	$= \{(x,y) | x \in \mathbb{R}, y \in \mathbb{R} \}$.

Thus, $\mathbb{R}^2$ is the set consisting of all points in the two-dimensional plane. Similarly, $\mathbb{R}^3=\mathbb{R}\times \mathbb{R} \times \mathbb{R}$ and so on.

---