eBook › Chapter 2 · Probability

Section 2.1

Set Theory

2.1.1Why study set theory?

In mathematics, we are often interested in describing a collection of numbers, for example, a positive interval $[a,b]$ on the real line or the ordered pairs of numbers that define a circle on a graph with two axes. These collections of numbers can be abstractly defined as sets. In a nutshell, a set is simply a collection of things. These things can be numbers, but they can also be alphabets, objects, or anything. Set theory is a mathematical tool that defines operations on sets. It provides the basic arithmetic for us to combine, separate, and decompose sets.

Why do we start the chapter by describing set theory? Because probability is a measure of the size of a set. Yes, probability is not just a number telling us the relative frequency of events; it is an operator that takes a set and tells us how large the set is. Using the example we showed in the prelude, the event “even number” of a die is a set containing numbers $\{\mydice{2}, \mydice{4}, \mydice{6}\}$. When we apply probability to this set, we obtain the number $\frac{3}{6}$, as shown in Figure 2.1. Thus sets are the foundation of the study of probability.

**Figure 2.1.** Probability is a measure of the size of a set. Whenever we talk about probability, it has to be the probability of a set.

2.1.2Basic concepts of a set

Definition 2.1 (Set)

A set is a collection of elements. We denote

A = \{\xi_1,\xi_2,\ldots,\xi_n\}

as a set, where $\xi_i$ is the $i$th element in the set.

In this definition, $A$ is called a set. It is nothing but a collection of elements $\xi_1,\ldots,\xi_n$. What are these $\xi_i$'s? They can be anything. Let's see a few examples below.

Example 2.1

Example 2.1(a). $A = \{\text{apple}, \text{orange}, \text{pear}\}$ is a finite set.

Example 2.1(b). $A = \{1, 2, 3, 4, 5, 6\}$ is a finite set.

Example 2.1(c). $A = \{2,4,6,8,\ldots\}$ is a countable but infinite set.

Example 2.1(d). $A = \{x \;|\; 0 < x < 1\}$ is an uncountable set.

To say that an element $\xi$ is drawn from $A$, we write $\xi \in A$. For example, the number $1$ is an element in the set $\{1,2,3\}$. We write $1 \in \{1,2,3\}$. There are a few common sets that we will encounter. For example,

Example 2.2

Example 2.2(a). $\R$ is the set of all real numbers.

Example 2.2(b). $\R^2$ is the set of ordered pairs of real numbers.

Example 2.2(c). $[a,b] = \{x \,|\, a \le x \le b\}$ is a closed interval on $\R$.

Example 2.2(d). $(a,b) = \{x \,|\, a < x < b\}$ is an open interval on $\R$.

Example 2.2(e). $(a,b] = \{x \,|\, a < x \le b\}$ is a semi-closed interval on $\R$.

**Figure 2.2.** From left to right: a closed interval, a semi-closed (or semi-open) interval, and an open interval.

Sets are not limited to numbers. A set can be used to describe a collection of functions.

Example 2.3

$A = \{f:\R \rightarrow \R \;|\; f(x) = ax+b, \; a, b \in \R\}$. This is the set of all straight lines in 2D. The notation $f : \R \rightarrow \R$ means that the function $f$ takes an argument from $\R$ and sends it to another real number in $\R$. The definition $f(x) = ax+b$ says that $f$ is taking the specific form of $ax+b$. Since the constants $a$ and $b$ can be any real number, the equation $f(x) = ax+b$ enumerates all possible straight lines in 2D. See Figure 2.3(a).

Example 2.4

$A = \{f : \R \rightarrow [-1,1] \;|\; f(t) = \cos(\omega_0 t + \theta), \; \theta \in [0,2\pi]\}$. This is the set of all cosine functions of a fixed carrier frequency $\omega_0$. The phase $\theta$, however, is changing. Therefore, the equation $f(t) = \cos(\omega_0 t + \theta)$ says that the set $A$ is the collection of all possible cosines with different phases. See Figure 2.3(b).

**Figure 2.3.** (a) The set of straight lines $A = \{f:\R \rightarrow \R \;|\; f(x) = ax+b, \; a, b \in \R\}$. (b) The set of phase-shifted cosines $A = \{f : \R \rightarrow [-1,1] \;|\; f(t) = \cos(\omega_0 t + \theta), \; \theta \in [0,2\pi]\}$.

A set can also be used to describe a collection of sets. Let $A$ and $B$ be two sets. Then $\calC = \{A, B\}$ is a set of sets.

Example 2.5

Let $A = \{1,2\}$ and $B = \{\text{apple}, \text{orange}\}$. Then $$\calC = \{A,B\} = \{ \{1,2\}, \{\text{apple}, \text{orange}\}\}$$ is a collection of sets. Note that here we are not saying $\calC$ is the union of two sets. We are only saying that $\calC$ is a collection of two sets. See the next example.

Example 2.6

Let $A = \{1,2\}$ and $B = \{3\}$, then $\calC = \{A,B\}$ means that $$\calC = \{\{1,2\}, \{3\}\}.$$ Therefore $\calC$ contains only two elements. One is the set $\{1,2\}$ and the other is the set $\{3\}$. Note that $\{\{1,2\}, \{3\}\} \not= \{1,2,3\}$. The former is a set of two sets. The latter is a set of three elements.

2.1.3Subsets

Given a set, we often want to specify a portion of the set, which is called a subset.

Definition 2.2 (Subset)

$B$ is a subset of $A$ if for any $\xi \in B$, $\xi$ is also in $A$. To denote that $B$ is a subset of $A$, we write

B \subseteq A.

$B$ is called a proper subset of $A$ if $B$ is a subset of $A$ and $B \not= A$. We denote a proper subset as $B \subset A$. Two sets $A$ and $B$ are equal if and only if $A \subseteq B$ and $B \subseteq A$.

Example 2.7

sep0ex
If $A = \{1,2,3,4,5,6\}$, then $B = \{1,3,5\}$ is a proper subset of $A$.
If $A = \{1,2\}$, then $B = \{1,2\}$ is an improper subset of $A$.
If $A = \{t \;|\; t \ge 0\}$, then $B = \{t \;|\; t > 0\}$ is a proper subset of $A$.

Practice Exercise 2.1

Let $A = \{1,2,3\}$. List all the subsets of $A$.

Solution

The subsets of $A$ are:

\begin{aligned} \calA = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}. \end{aligned}

Practice Exercise 2.2

Prove that two sets $A$ and $B$ are equal if and only if $A \subseteq B$ and $B \subseteq A$.

Solution

Suppose $A \subseteq B$ and $B \subseteq A$. Assume by contradiction that $A \not= B$. Then necessarily there must exist an $x$ such that $x \in A$ but $x\not\in B$ (or vice versa). But $A \subseteq B$ means that $x \in A$ will necessarily be in $B$. So it is impossible to have $x\not\in B$. Conversely, suppose that $A = B$. Then any $x \in A$ will necessarily be in $B$. Therefore, we have $A \subseteq B$. Similarly, if $A = B$ then any $x \in B$ will be in $A$, and so $B \subseteq A$.

2.1.4Empty set and universal set

Definition 2.3 (Empty Set)

A set is empty if it contains no element. We denote an empty set as

A = \emptyset.

A set containing an element $0$ is not an empty set. It is a set of one element, $\{0\}$. The number of elements of the empty set is 0. The empty set is a subset of any set, i.e., $\emptyset \subseteq A$ for any $A$. We use $\subseteq$ because $A$ could also be an empty set.

Example 2.8

Example 2.8(a). The set $A = \{x \,|\, \sin x > 1\}$ is empty because no $x \in \R$ can make $\sin x > 1$.

Example 2.8(b). The set $A = \{x \,|\, x > 5 \text{ and } x < 1\}$ is empty because the two conditions $x > 5$ and $x < 1$ are contradictory.

Definition 2.4 (Universal Set)

The universal set is the set containing all elements under consideration. We denote a universal set as

A = \Omega.

The universal set $\Omega$ contains itself, i.e., $\Omega \subseteq \Omega$. The universal set is a relative concept. Usually, we first define a universal set $\Omega$ before referring to subsets of $\Omega$. For example, we can define $\Omega = \R$ and refer to intervals in $\R$. We can also define $\Omega = [0,1]$ and refer to subintervals inside $[0,1]$.

2.1.5Union

We now discuss basic set operations. By operations, we mean functions of two or more sets whose output value is a set. We use these operations to combine and separate sets. Let us first consider the union of two sets. See Figure 2.4 for a graphical depiction.

**Figure 2.4.** The union of two sets contains elements that are either in $A$ or $B$ or both.

Definition 2.5 (Finite Union)

The union of two sets $A$ and $B$ contains all elements in $A$ or in $B$. That is,

A \cup B = \{ \xi \;|\; \xi \in A \;\text{\keyword{or}}\; \xi \in B\}.

As the definition suggests, the union of two sets uses the logical operator “or”. Thus, the union of two sets is always larger than or equal to the individual sets.

Example 2.9

Example 2.9(a). If $A = \{1,2\}$, $B = \{1,5\}$, then $A \cup B = \{1,2,5\}$. The overlapping element $1$ is absorbed. Also, note that $A \cup B \not= \{\{1,2\},\{1,5\}\}$. The latter is a set of sets.

Example 2.9(b). If $A = (3,4]$, $B = (3.5,\infty)$, then $A \cup B = (3,\infty)$.

Example 2.9(c). If $A = \{f:\R \rightarrow \R \,|\, f(x) = ax\}$ and $B = \{f:\R \rightarrow \R \,|\, f(x) = b\}$, then $A \cup B$ = a set of sloped lines with a slope $a$ plus a set of constant lines with height $b$. Note that $A \cup B \not = \{f:\R \rightarrow \R \,|\, f(x) = ax + b\}$ because the latter is a set of sloped lines with arbitrary $y$-intercept.

Example 2.9(d). If $A = \{1,2\}$ and $B = \emptyset$, then $A \cup B = \{1,2\}$.

Example 2.9(e). If $A = \{1,2\}$ and $B = \Omega$, then $A \cup B = \Omega$.

The previous example can be generalized in the following exercise. What it says is that if $A$ is a subset of another set $B$, then the union of $A$ and $B$ is just $B$. Intuitively, this should be straightforward because whatever you have in $A$ is already in $B$, so the union will just be $B$. Below is a formal proof that illustrates how to state the arguments clearly. You may like to draw a picture to convince yourself that the proof is correct.

Practice Exercise 2.3

Prove that if $A \subseteq B$, then $A \cup B = B$.

Solution

: We will show that $A \cup B \subseteq B$ and $B \subseteq A \cup B$. Let $\xi \in A \cup B$. Then $\xi$ must be inside either $A$ or $B$ (or both). In any case, since we know that $A \subseteq B$, it holds that if $\xi \in A$ then $\xi$ must also be in $B$. Therefore, for any $\xi \in A\cup B$ we have $\xi \in B$. This shows $A \cup B \subseteq B$. Conversely, if $\xi \in B$, then $\xi$ must be inside $A \cup B$ because $A \cup B$ is a larger set than $B$. So if $\xi \in B$ then $\xi \in A\cup B$ and hence $B \subseteq A \cup B$. Since $A \cup B$ is a subset of $B$ or equal to $B$, and $B$ is a subset of $A \cup B$ or equal to $A \cup B$, it follows that $A \cup B = B$.

What should we do if we want to take the union of an infinite number of sets? First, we need to define the concept of an infinite union.

Definition 2.6 (Infinite Union)

For an infinite sequence of sets $A_1,A_2,\ldots$, the infinite union is defined as

\bigcup_{n=1}^{\infty} A_n = \left\{ \xi \;\;|\;\; \xi \in A_n \mbox{ for \keyword{at least one} } n \mbox{ that is finite.} \right\}.

An infinite union is a natural extension of a finite union. It is not difficult to see that

\xi \in A \;\; \text{\keyword{or}} \;\; \xi \in B \;\;\; \Longleftrightarrow \;\;\; \xi \;\; \text{is in \keyword{at least one of}} \;\; A \; \text{and} \; B.

Similarly, an infinite union means that

\xi \in A_1 \;\; \text{\keyword{or}} \;\; \xi \in A_2 \;\; \text{\keyword{or}} \;\; \xi \in A_3 \ldots \;\;\; \Longleftrightarrow \;\;\; \xi \;\; \text{is in \keyword{at least one of}} \;\; A_1, \; A_2, \; A_3, \; \ldots.

The finite $n$ requirement says that we only evaluate the sets for a finite number of $n$'s. This $n$ can be arbitrarily large, but it is finite. Why are we able to do this? Because the concept of an infinite union is to determine $A_{\infty}$, which is the limit of a sequence. Like any sequence of real numbers, the limit of a sequence of sets has to be defined by evaluating the instances of all possible finite cases.

Consider a sequence of sets $A_n = \left[-1,1-\frac{1}{n}\right]$, for $n = 1,2,\ldots$. For example, $A_1 = \left[-1,0\right]$, $A_2 = \left[-1,\frac{1}{2}\right]$, $A_3 = \left[-1,\frac{2}{3}\right]$, $A_4 = \left[-1,\frac{3}{4}\right]$, etc.

**Figure 2.5.** The infinite union of $\bigcup_{n=1}^{\infty}\left[-1,1-\frac{1}{n}\right]$. No matter how large $n$ gets, the point $1$ is never included. So the infinite union is $[-1,1)$.

To take the infinite union, we know that the set $[-1,1)$ is always included, because the right-hand limit $1-\frac{1}{n}$ approaches $1$ as $n$ approaches $\infty$. So the only question concerns the number 1. Should 1 be included? According to the definition above, we ask: Is 1 an element of at least one of the sets $A_1$, $A_2$, …, $A_n$? Clearly it is not: $1 \not\in A_1$, $1 \not\in A_2$, $\ldots$. In fact, $1 \not\in A_n$ for any finite $n$. Therefore 1 is not an element of the infinite union, and we conclude that $$\bigcup_{n=1}^{\infty} A_n = \bigcup_{n=1}^{\infty}\left[-1,1-\frac{1}{n}\right] = [-1,1).$$

Practice Exercise 2.4

Find the infinite union of the sequences where (a) $A_n = \big[-1,1-\frac{1}{n}\big)$, (b) $A_n = \big(-1,1-\frac{1}{n}\big]$.

Solution

(a) $\bigcup_{n=1}^{\infty} A_n = [-1,1)$. (b) $\bigcup_{n=1}^{\infty} A_n = (-1,1)$.

2.1.6Intersection

The union of two sets is based on the logical operator or. If we use the logical operator and, then the result is the intersection of two sets.

Definition 2.7 (Finite Intersection)

The intersection of two sets $A$ and $B$ contains all elements in $A$ and in $B$. That is,

A \cap B = \{ \xi \;|\; \xi \in A \;\;\mbox{and}\;\; \xi \in B\}.

Figure 2.6 portrays intersection graphically. Intersection finds the common elements of the two sets. It is not difficult to show that $A \cap B \subseteq A$ and $A \cap B \subseteq B$.

Example 2.10

Example 2.10(a). If $A = \{1,2,3,4\}$, $B = \{1,5,6\}$, then $A \cap B = \{1\}$.

Example 2.10(b). If $A = \{1,2\}$, $B = \{5,6\}$, then $A \cap B = \emptyset$.

Example 2.10(c). If $A = (3,4]$, $B =[3.5,\infty)$, then $A \cap B = [3.5,4]$.

Example 2.10(d). If $A = (3,4]$, $B = \emptyset$, then $A \cap B = \emptyset$.

Example 2.10(e). If $A = (3,4]$, $B = \Omega$, then $A \cap B = (3,4]$.

Example 2.11

If $A = \{f:\R \rightarrow \R \,|\, f(x) = ax\}$ and $B = \{f:\R \rightarrow \R \,|\, f(x) = b\}$, then $A \cap B$ = the intersection of a set of sloped lines with a slope $a$ and a set of constant lines with height $b$. The only line that can satisfy both sets is the line $f(x) = 0$. Therefore, $A \cap B = \{f \,|\, f(x) = 0\}$.

Example 2.12

If $A = \{ \{1\},\{2\}\}$ and $B = \{\{2,3\}, \{4\}\}$, then $A \cap B = \emptyset$. This is because $A$ is a set containing two sets, and $B$ is a set containing two sets. The two sets $\{2\}$ and $\{2,3\}$ are not the same. Thus, $A$ and $B$ have no elements in common, and so $A \cap B = \emptyset$.

Similarly to the infinite union, we can define the concept of infinite intersection.

Definition 2.8 (Infinite Intersection)

For an infinite sequence of sets $A_1,A_2,\ldots$, the infinite intersection is defined as

\bigcap_{n=1}^{\infty}A_n = \left\{\xi \;\; | \;\; \xi \in A_n \mbox{ \keyword{for every} finite }\;n. \right\}

To understand this definition, we note that

\xi \in A \;\; \text{\keyword{and}} \;\; \xi \in B \;\;\; \Longleftrightarrow \;\;\; \xi \;\; \text{is in \keyword{every one} of} \;\; A \; \text{and} \; B.

As a result, it follows that

\xi \in A_1 \;\; \text{\keyword{and}} \;\; \xi \in A_2 \;\; \text{\keyword{and}} \;\; \xi \in A_3 \ldots \;\;\; \Longleftrightarrow \;\;\; \xi \;\; \text{is in \keyword{every one of}} \;\; A_1, \; A_2, \; A_3, \; \ldots.

Since the infinite intersection requires that $\xi$ is in every one of $A_1$, $A_2$, $\ldots$, $A_n$, if there is a set $A_i$ that does not contain $\xi$, the infinite intersection is an empty set.

Consider the problem of finding the infinite intersection of $\bigcap_{n=1}^{\infty} A_n$, where $$A_n = \left[0,1+\frac{1}{n}\right).$$ We note that the sequence of sets is $[0,2)$, $[0,1.5)$, $[0,1.33)$, …. As $n \rightarrow \infty$, we note that the limit is either $[0,1)$ or $[0,1]$. Should the right-hand limit 1 be included in the infinite intersection? According to the definition above, we know that $1 \in A_1$, $1 \in A_2$, …, $1 \in A_n$ for any finite $n$. Therefore, $1$ is included and so $$\bigcap_{n=1}^{\infty}A_n = \bigcap_{n=1}^{\infty}\left[0,1+\frac{1}{n}\right) = [0,1].$$

**Figure 2.7.** The infinite intersection of $\bigcap_{n=1}^{\infty}\big[0,1+\frac{1}{n}\big)$. No matter how large $n$ gets, the point $1$ is always included. So the infinite intersection is $[0,1]$.

Practice Exercise 2.5

Find the infinite intersection of the sequences where (a) $A_n = \big[0,1+\frac{1}{n}\big]$, (b) $A_n = \big(0,1+\frac{1}{n}\big)$, (c) $A_n = \big[0,1-\frac{1}{n}\big)$, (d) $A_n = \big[0,1-\frac{1}{n}\big]$.

Solution

sep0ex
(a) $\bigcap_{n=1}^{\infty} A_n = [0,1]$.
(b) $\bigcap_{n=1}^{\infty} A_n = (0,1]$.
(c) $\bigcap_{n=1}^{\infty} A_n = [0,0) = \emptyset$.
(d) $\bigcap_{n=1}^{\infty} A_n = [0,0] = \{0\}$.

2.1.7Complement and difference

Besides union and intersection, there is a third basic operation on sets known as the complement.

Definition 2.9 (Complement)

The complement of a set $A$ is the set containing all elements that are in $\Omega$ but not in $A$. That is,

A^c = \{ \xi \;|\; \xi \in \Omega \;\mbox{and}\; \xi \not\in A\}.

Figure 2.8[Left] graphically portrays the idea of a complement. The complement is a set that contains everything in the universal set that is not in $A$. Thus the complement of a set is always relative to a specified universal set.

**Figure 2.8.** [Left] The complement of a set $A$ contains all elements that are not in $A$. [Right] The difference $A \backslash B$ contains elements that are in $A$ but not in $B$.

Example 2.13

Example 2.13(a). Let $A = \{\mbox{1,2,3}\}$ and $\Omega = \{\mbox{1,2,3,4,5,6}\}$. Then $A^c = \{\mbox{4,5,6}\}$.

Example 2.13(b). Let $A = \{\mbox{even integers}\}$ and $\Omega = \{\mbox{integers}\}$. Then $A^c =$ {odd integers}.

Example 2.13(c). Let $A = \{\mbox{integers}\}$ and $\Omega = \R$. Then $A^c =${any real number that is not an integer}.

Example 2.13(d). Let $A = [0,5)$ and $\Omega = \R$. Then $A^c = (-\infty,0) \cup [5,\infty)$.

Example 2.13(e). Let $A = \R$ and $\Omega = \R$. Then $A^c = \emptyset$.

The concept of the complement will help us understand the concept of difference.

Definition 2.10 (Difference)

The difference $A \backslash B$ is the set containing all elements in $A$ but not in $B$.

A \backslash B = \{ \xi \;|\; \xi \in A \;\mbox{and}\; \xi \not\in B\}.

Figure 2.8[Right] portrays the concept of difference graphically. Note that $A \backslash B \not= B \backslash A$. The former removes the elements in $B$ whereas the latter removes the elements in $A$.

Example 2.14

Example 2.14(a). Let $A = \{1,3,5,6\}$ and $B = \{2,3,4\}$. Then $A \backslash B = \{1,5,6\}$ and $B \backslash A = \{2,4\}$.

Example 2.14(b). Let $A = [0,1]$, $B = [2,3]$, then $A \backslash B = [0,1]$, and $B \backslash A = [2,3]$. This example shows that if the two sets do not overlap, there is nothing to subtract.

Example 2.14(c). Let $A = [0,1]$, $B = \R$, then $A \backslash B = \emptyset$, and $B \backslash A = (-\infty,0)\cup(1,\infty)$. This example shows that if one of the sets is the universal set, then the difference will either return the empty set or the complement.

Practice Exercise 2.6

Show that for any two sets $A$ and $B$, the differences $A \backslash B$ and $B \backslash A$ never overlap, i.e., $(A \backslash B) \cap (B \backslash A) = \emptyset$.

Solution

Suppose, by contradiction, that the intersection is not empty so that there exists an $\xi \in (A \backslash B) \cap (B \backslash A)$. Then, by the definition of intersection, $\xi$ is an element of $(A \backslash B)$ and $(B \backslash A)$. But if $\xi$ is an element of $(A \backslash B)$, it cannot be an element of $B$. This implies that $\xi$ cannot be an element of $(B \backslash A)$ since it is a subset of $B$. This is a contradiction because we just assumed that the $\xi$ can live in both $(A \backslash B)$ and $(B \backslash A)$.

Difference can be defined in terms of intersection and complement:

Theorem 2.1

Let $A$ and $B$ be two sets. Then

A \backslash B = A \cap B^c

Proof. Let $x \in A \backslash B$. Then $x \in A$ and $x \not\in B$. Since $x \not\in B$, we have $x \in B^c$. Therefore, $x \in A$ and $x \in B^c$. By the definition of intersection, we have $x \in A \cap B^c$. This shows that $A \backslash B \subseteq A \cap B^c$. Conversely, let $x \in A \cap B^c$. Then, $x \in A$ and $x \in B^c$, which implies that $x \in A$ and $x \not\in B$. By the definition of $A \backslash B$, we have that $x \in A \backslash B$. This shows that $A \cap B^c \subseteq A \backslash B$.

■

2.1.8Disjoint and partition

It is important to be able to quantify situations in which two sets are not overlapping. In this situation, we say that the sets are disjoint.

Definition 2.11 (Disjoint)

Two sets $A$ and $B$ are disjoint if

A \cap B = \emptyset.

For a collection of sets $\{A_1,A_2,\ldots,A_n\}$, we say that the collection is disjoint if, for any pair $i \not= j$,

A_i \cap A_j = \emptyset.

A pictorial interpretation can be found in Figure 2.9.

Example 2.15

Example 2.15(a). Let $A = \{x > 1\}$ and $B = \{x < 0\}$. Then $A$ and $B$ are disjoint.

Example 2.15(b). Let $A = \{1,2,3\}$ and $B = \emptyset$. Then $A$ and $B$ are disjoint.

Example 2.15(c). Let $A = (0,1)$ and $B = [1,2)$. Then $A$ and $B$ are disjoint.

With the definition of disjoint, we can now define the powerful concept of partition.

Definition 2.12 (Partition)

A collection of sets $\{A_1,\ldots,A_n\}$ is a partition of the universal set $\Omega$ if it satisfies the following conditions:

sep0ex
(non-overlap) $\{A_1,\ldots,A_n\}$ is disjoint:
$A_i \cap A_j = \emptyset.$
(decompose) Union of $\{A_1,\ldots,A_n\}$ gives the universal set:
$\bigcup_{i=1}^n A_i = \Omega.$

In plain language, a partition is a collection of non-overlapping subsets whose union is the universal set. Partition is important because it is a decomposition of $\Omega$ into smaller subsets, and since these subsets do not overlap, they can be analyzed separately. Partition is a handy tool for studying probability because it allows us to decouple complex events by treating them as isolated sub-events.

**Figure 2.10.** A partition of $\Omega$ contains disjoint subsets of which the union gives us $\Omega$.

Example 2.16

Example 2.16. Let $\Omega = \{1,2,3,4,5,6\}$. The following sets form a partition: $$A_1 = \{1,2,3\}, \quad A_2 = \{4,5\}, \quad A_3 = \{6\}$$

Example 2.17

Example 2.17. Let $\Omega = \{1,2,3,4,5,6\}$. The collection $$A_1 = \{1,2,3\}, \quad A_2 = \{4,5\}, \quad A_3 = \{5,6\}$$ does not form a partition, because $A_2 \cap A_3 = \{5\}$.

If $\{A_1,A_2,\ldots,A_n\}$ forms a partition of the universal set $\Omega$, then for any $B \subseteq \Omega$, we can decompose $B$ into $n$ disjoint subsets: $B \cap A_1$, $B \cap A_2$, … $B \cap A_n$. Two properties hold:

sep0ex
$B \cap A_i$ and $B \cap A_j$ are disjoint if $i \not= j$.
The union of $B \cap A_1$, $B \cap A_2$, … $B \cap A_n$ is $B$.

Practice Exercise 2.7

Prove the above two statements.

Solution

To prove the first statement, we can pick $\xi \in (B \cap A_i)$. This means that $\xi \in B$ and $\xi \in A_i$. Since $\xi \in A_i$, it cannot be in $A_j$ because $A_i$ and $A_j$ are disjoint. Therefore $\xi$ cannot live in $B \cap A_j$. This completes the proof, because we just showed that any $\xi \in B \cap A_i$ cannot simultaneously live in $B \cap A_j$.

To prove the second statement, we pick $\xi \in \bigcup_{i=1}^n (B \cap A_i)$. Since $\xi$ lives in the union, it has to live in at least one of the $(B \cap A_i)$ for some $i$. Now suppose $\xi \in B \cap A_i$. This means that $\xi$ is in both $B$ and $A_i$, so it must live in $B$. Therefore, $\bigcup_{i=1}^n (B \cap A_i) \subseteq B$. Now, suppose we pick $\xi \in B$. Since $\{A_i\}$ is a partition, $\xi$ must belong to exactly one $A_k$. Therefore $\xi \in B \cap A_k$, which means $\xi \in \bigcup_{i=1}^n (B \cap A_i)$, and so we showed that $B \subseteq \bigcup_{i=1}^n (B \cap A_i)$. Combining the two directions, we conclude that $\bigcup_{i=1}^n (B \cap A_i) = B$.

Example 2.18

Let $\Omega = \{1,2,3,4,5,6\}$ and let a partition of $\Omega$ be $A_1 = \{1,2,3\}$, $A_2 = \{4,5\}$, $A_3 = \{6\}$. Let $B = \{1,3,4\}$. Then, by the result we just proved, $B$ can be decomposed into three subsets:

\begin{aligned} B \cap A_1 = \{1,3\}, \quad B \cap A_2 = \{4\}, \quad B \cap A_3 = \emptyset. \end{aligned}

Thus we can see that $B \cap A_1$, $B \cap A_2$ and $B \cap A_3$ are disjoint. Furthermore, the union of these three sets gives $B$.

2.1.9Set operations

When handling multiple sets, it would be useful to have some basic set operations. There are four basic theorems concerning set operations that you need to know for our purposes in this book:

Theorem 2.2 (Commutative)

(Order does not matter)

A \cap B = B \cap A, \quad\mbox{and}\quad A \cup B = B \cup A.

Theorem 2.3 (Associative)

(How to do multiple union and intersection)

\begin{aligned} A \cup (B \cup C) &= (A \cup B) \cup C, \\ A \cap (B \cap C) &= (A \cap B) \cap C. \end{aligned}

Theorem 2.4 (Distributive)

(How to mix union and intersection)

\begin{aligned} A \cap (B \cup C) &= (A \cap B) \cup (A \cap C), \\ A \cup (B \cap C) &= (A \cup B) \cap (A \cup C). \end{aligned}

Theorem 2.5 (De Morgan's Law)

(How to complement over intersection and union)

\begin{aligned} (A \cap B)^c &= A^c \cup B^c, \\ (A \cup B)^c &= A^c \cap B^c. \end{aligned}

Example 2.19

Consider $[1,4]\cap([0,2]\cup[3,5])$. By the distributive property we can simplify the set as

\begin{aligned} [1,4]\cap([0,2]\cup[3,5]) &= ([1,4] \cap [0,2]) \cup ([1,4] \cap [3,5]) \\ &= [1,2] \cup [3,4]. \end{aligned}

Example 2.20

Consider $([0,1]\cup[2,3])^c$. By De Morgan's Law we can rewrite the set as

([0,1]\cup[2,3])^c = [0,1]^c \cap [2,3]^c.

2.1.10Closing remarks about set theory

It should be apparent why set theory is useful: it shows us how to combine, split, and remove sets. In Figure 2.11 we depict the intersection of two sets $A = \{\text{even number}\}$ and $B = \{\text{less than or equal to 3}\}$. Set theory tells us how to define the intersection so that the probability can be applied to the resulting set.

Universal sets and empty sets are useful too. Universal sets cover all the possible outcomes of an experiment, so we should expect $\Pb[\Omega] = 1$. Empty sets contain nothing, and so we should expect $\Pb[\emptyset] = 0$. These two properties are essential to define a probability because no probability can be greater than 1, and no probability can be less than 0.