Set Operations | Union | Intersection | Complement | Difference | Mutually Exclusive | Partitions | De Morgan's Law | Distributive Law (2024)

1.2.2 Set Operations

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 arein 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 elementsthat 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 theset 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 arein 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 arein $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 sharedelements; i.e., their intersection is the empty set, $A \cap B=\emptyset$. More generally, several setsare 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 nonemptysets $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 orderedpairs 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 thesame 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 countingthe 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 naturalnumber. For $n=2$, we have

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.