It is a set that contains all elements in the universal set that are not in a given set

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 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 elements. 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)$.

• Solution
  • 1. $A \cup B=\{1,2,4,5\}$.
    2. $A \cap B=\{2\}$.
    3. $\overline{A}=\{3,4,5,6\}$ ($\overline{A}$ consists of elements that are in $S$ but not in $A$).
    4. $\overline{B}=\{1,3,6\}$.
    5. We have $$(A \cup B)^c=\{1,2,4,5\}^c=\{3,6\},$$ which is the same as $$A^c \cap B^c=\{3,4,5,6\} \cap \{1,3,6\}=\{3,6\}.$$
    6. We have $$A \cap (B \cup C)=\{1,2\} \cap \{1,2,4,5,6\}=\{1,2\},$$ which is the same as $$(A \cap B) \cup (A\cap C)=\{2\} \cup \{1\}=\{1,2\}.$$

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

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.

The print version of the book is available through Amazon here.

What is the set of all elements in the universal set that is not in set A?

What refers to the set of all elements in the first set that are not in the second set?