# Probability/Set Theory
## Introduction

The overview of set theory contained herein adopts a naive point of view. A rigorous analysis of the concept belongs to the foundations of mathematics and mathematical logic. Although we shall not initiate a study of these fields, the rules we follow in dealing with sets are derived from them.

## Sets

Definition. (Set) A set is a well-defined collection of distinct object(s), which are called element(s).
Remark.
* If $x$ belongs to (or is contained in) a set $S$ , we write $x\in S$.
* If $x$ does not belong to the set $S$ , we write $x\notin S$.
* When $x$ and $y$ are equal, denoted by $x=y$, $x$ and $y$ are different symbols denoting the same object(s). (When $x$ and $y$ are not equal, we write $x\neq y$, and they are different things.)
* Because of the vagueness of the term "well-defined", some may not accept this "definition" as a definition of set. Sometimes, a set may be left as a primitive notion, i.e., an undefined term.
Example. (Collection that is not "well-defined")
* The collection of easy school subjects is not a set, since "easy" is not well-defined.
We have different ways to describe a set, e.g.
* word description: e.g., a set $S$ is the set containing the 12 months in a year;
* listing: elements in a set are listed within a pair of braces, e.g., $S{\overset {\text{ def }}{=}}\{{\text{January, }}{\color {darkgreen}{\text{March, February, }}}{\text{April, May, June, July, August, September, October, November, December}}\}$;
    the ordering of the elements is not important, i.e. even if the elements are listed in different order, the set is still the same. E.g., $\{{\text{January, }}{\color {darkgreen}{\text{February, March, }}}{\text{April, May, June, July, August, September, October, November, December}}\}$ is still referring to the same set.
* set-builder notation:$\underbrace {\ _{{\text{The set of}}\;}\underbrace {x} _{{\text{all elements }}x\;}\underbrace {:} _{\text{such that }}\underbrace {P(x)} _{{\text{the property }}P(x){\text{ holds}}}\}$
    (the closing brace must also be written.)
    For example, $S{\overset {\text{ def }}{=}}\{x:x{\text{ is a month in a year}}\}$.
Example. (Empty set) The set $\{\}$ is called an empty set, and it contains no element. It is commonly denoted by $\varnothing$ also.
Exercise.
Example.
* ${\text{apple}}\in \{{\text{apple, orange, banana}}\}$;
* $\varnothing \in \{\varnothing \}$;
* $\varnothing \notin \varnothing$.
Exercise.
Example.
* Let $S_{1}$ be the set containing all outcomes from rolling a six-faced dice. Then, we can express the set $S_{1}$ as $\{1,2,3,4,5,6\}$.
* Let $S_{2}$ be the set containing all outcomes from tossing a coin. Then, we can express the set $S_{2}$ as $\{H,T\}$ where $H$ stands for "heads" and $T$ stands for "tails".
Exercise. Amy participates in a lucky draw where the grand prize is a car. Suppose we say that the outcome is 1 if Amy gets the grand prize, and 0 otherwise, what is the set containing all outcomes?
The set is $\{0,1\}$.
Definition. (Set equality) When two sets are equal, they contain the same elements.
Remark.
* Equivalently, two sets $A$ and $B$ are equal if each element of $A$ is also element of $B$ and each element of $B$ is also element of $A$.
* We use $A=B$ to denote sets $A$ and $B$ are equal ($A\neq B$ is used to denote $A$ and $B$ are not equal).
Example.
* $\{\varnothing \}=\{x:x{\text{ is a empty set}}\}$.
* $\varnothing =\{\}\neq {\big \\{\}{\big \}}=\{\varnothing \}$.
* $\{2,3,5\}=\{x:x{\text{ is a prime number that is not greater than }}5\}$
Example. Let $S_{1}$ be the set containing all odd outcomes from rolling a six-faced dice. Also, let $S_{2}$ be the set containing all outcomes that are not even from rolling a six-faced dice. Then, $S_{1}=S_{2}=\{1,3,5\}$.
Definition. (Universal set) Universal set, denoted by $U$, is the set that contains all objects being considered in a particular context.
Remark.
* In the context of probability, a universal set, which is usually denoted by $\Omega$ instead, is the set containing all outcomes of a particular random experiment, and is also called a sample space.
Example. The sample space of rolling a six-faced dice is $\Omega =\{1,2,3,4,5,6\}$.
Exercise. What is the sample space of tossing a coin? (Use $H$ to stand for the outcome "heads" and $T$ to stand for the outcome "tails".)
The sample space is $\Omega =\{H,T\}$.
Definition. (Cardinality) Cardinality of a finite set is the number of its elements.
Remark.
* A set is said to be finite if it is empty set or it contains $n\in \mathbb {N}$ elements ($\mathbb {N}$ is the set containing all positive integers).
* Cardinality of set $S$ can be denoted by $\#(S)$ (or $|S|$).
* Infinite set is a set containing infinite number of elements.
   * We will leave the cardinality of infinite set undefined in this book, but it can be defined, in a more complicated way.
Example.
* $\#({\big \\{1\},2,3{\big \}})=3$.
* $\#(\varnothing )=0$.
* $\mathbb {N}$ (the set containing each positive integer) is an infinite set.
Exercise.
Example. Let $\Omega$ be the sample space of rolling a six-faced dice and $S$ be the set containing all odd outcomes from rolling a six-faced dice. Then, $\#(S)=3$ and $\#(\Omega )=6$.
Exercise. A student is asked to show that two sets $A$ and $B$ are equal in a question of his assignment. In that question, one of the given condition is that $\#(A)=\#(B)$. The student then makes the following argument:
    Since $\#(A)=\#(B)$, it follows that $A=B$.
Is his argument correct? If not, provides an example of sets $A$ and $B$ such that $\#(A)=\#(B)$ but $A\neq B$.
The argument is wrong. We can take, for example, $A=\{1\}$ and $B=\{2\}$. Then, $\#(A)=\#(B)=1$ but $\{1\}\neq \{2\}$.

## Subsets

We introduce a relationship between sets in this section.
Definition. (Subset) $A$ is a subset of $B$, denoted by $A\subseteq B$ if each element of set $A$ is an element of set $B$.
Remark.
* If $A$ is not a subset of $B$, then we write $A\not \subseteq B$.
* By referring to the definitions of subsets and set equality, we can see that $A=B$ is equivalent to (or if and only if) $A\subseteq B$ and $B\subseteq A$.
* The notation $A\supseteq B$ means that $A$ is a superset of $B$, which means that $B$ is a subset of $A$.
   * This notation and terminology are seldom used.
Definition. (Venn diagram) A Venn diagram is a diagram that shows all possible logical relations between finitely many sets.
Remark.
* It is quite useful for illustrating some simple relationships between sets, and making the relationships clear.
* We may also add various annotations in the Venn digram, e.g. cardinality of each set, and the element(s) contained by each set.
Illustration of subset by Venn diagram:
Example.
* $\{1,3\}\subseteq \{1,2,3\}$.
Venn digram:
* $\{\{1\}\}\not \subseteq \{1,2,3\}$ ($\{1\}\notin \{1,2,3\}$).
* It can be proved that $\varnothing \subseteq S$ for each set $S$.
Example. Let $\Omega$ be the sample space of rolling a six-faced dice and $S$ be the set containing all odd outcomes from rolling a six-faced dice. Then, $S\subseteq \Omega$.
Exercise. Let $P$ be the set containing all prime outcomes from rolling a six-faced dice. Is $P$ a subset of $S$?
No, since $2\in P$ but $2\notin S$.
Example. (Intervals) Intervals are commonly encountered subsets of $\mathbb {R}$. If $a$ and $b$ are real numbers such that $a<b$, then ${\begin{aligned}{\color {Maroon}a,b{\color {Maroon})}&{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\;{\color {Maroon}<}\;x\;{\color {Maroon}<}\;b\};\\{\color {darkgreen}a,b{\color {Maroon})}&{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\;{\color {darkgreen}\leq }\;x\;{\color {Maroon}<}\;b\};\\{\color {Maroon}a,b{\color {darkgreen}]}&{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\;{\color {Maroon}<}\;x\;{\color {darkgreen}\leq }\;b\};\\{\color {darkgreen}a,b{\color {darkgreen}]}&{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\;{\color {darkgreen}\leq }\;x\;{\color {darkgreen}\leq }\;b\}.\\\end{aligned}}$ In particular, $(-\infty ,\infty )=\mathbb {R}$.
We also have $[-\infty ,\infty ]$, which is the set containing all extended real numbers, i.e., $[-\infty ,\infty ]=(-\infty ,\infty )\cup \{-\infty ,\infty \}$. Such notation is occasionally used. (Extended real number system is obtained by adding $\infty$ and $-\infty$ to the real number system.)
Definition. (Proper subset) A set $A$ is a proper subset of set $B$ if $A\subseteq B$ and $A\neq B$;. We write $A\subsetneq B$ in this case.
Remark.
* If a set $A$ is not a proper subset of $B$, then we write $A\not \subsetneq B$ (but we rarely write this).
* The notation $A\supsetneq B$ means that $A$ is a proper superset of $B$, which means that $B$ is a proper subset of $A$.
   * This notation and terminology are seldom used.
Example.
* The set $\{1,2\}$ is not a proper subset of itself, i.e., $\{1,2\}\not \subsetneq \{1,2\}$.
* $\{1\}\subsetneq \{1,2\}$.
Definition. (Complement) Let $A$ be a subset of universal set $U$. The (absolute) complement of $A$, denoted by $A^{c}$, is the set $\{x\in U:x\notin A\}$.
Example. If $A=\{1,2,3\}$ and $U=\{1,2,3,4,5\}$, then $A^{c}=\{4,5\}$.
Venn diagram:
Exercise.

## Set operations

Probability theory makes extensive use of some set operations, and we will discuss them in this section.
Definition. (Union of sets) The union of set $A$ and set $B$, denoted by $A\cup B$, is the set $\{x:x\in A{\text{ or }}x\in B\}$.
Remark.
* $A\cup B$ is read 'A cup B'.
Example.
* $\{{\text{apple}},{\text{orange}}\}\cup \{{\text{orange}},{\text{red}}\}=\{{\text{apple}},{\text{orange}},{\text{red}}\}$.
Venn diagram:
In the following, some basic properties possessed by the union operation: commutative law and associative law, are introduced.
Proposition. (Properties of union of sets) Let $A,B$ and $C$ be sets. Then, we have
    (a) $A\cup B=B\cup A$ (commutative law);
    (b) $A\cup (B\cup C)=(A\cup B)\cup C$ (associative law).
Remark.
* Because of the associative law, we can write the union of three or more sets without ambiguity. For instance, we can write $A\cup B\cup C$ directly, since $A\cup (B\cup C)=(A\cup B)\cup C$.
Example. Let $A_{1}=\{1,2\},A_{2}=\{3,4,5\}$ and $A_{3}=\{6,7\}$. Then,
* $\bigcup _{i=1}^{3}A_{i}=A_{1}\cup A_{2}\cup A_{3}=\{1,2,3,4,5,6,7\}$
* $\bigcup _{i=2}^{3}A_{i}=A_{2}\cup A_{3}=\{3,4,5,6,7\}$
* $A_{1}\cup A_{3}=\{1,2,6,7\}$.
($\bigcup _{i=m}^{n}A_{i}$ means $A_{m}\cup A_{m+1}\cup \dotsb \cup A_{n}$ ($n>m$), and $\bigcup _{i=m}^{\infty }A_{i}$ means $A_{m}\cup A_{m+1}\cup \dotsb$.)
Definition. (Intersection of sets) The intersection of set $A$ and set $B$, denoted by $A\cap B$, is the set $\{x:x\in A{\text{ and }}x\in B\}$.
Remark.
* $A\cap B$ is read 'A cap B'.
Example.
* $\{1,2,3\}\cap \{2,3,4\}=\{2,3\}$.
* $\{1,2,3\}\cap \{4,5,6\}=\varnothing$.
Definition. (Disjoint sets) Sets $A$ and $B$ are disjoint (or mutually exclusive) if $A\cap B=\varnothing$.
Example. The sets $\{1,2,3\}$ and $\{4,5,6\}$ are disjoint.
Remark.
* I.e., $A$ and $B$ are disjoint if they have no element in common.
* More than two sets are said to be disjoint if they are pairwise disjoint.
Venn diagram
Proposition. (Properties of intersection of sets) Let $A$,$B$ and $C$ be sets. Then, we have
    (a) $A\cap B=B\cap A$ (commutative law);
    (b) $A\cap (B\cap C)=(A\cap B)\cap C$ (associative law);
Remark.
* Likewise, we denote $A_{m}\cap A_{m+1}\cap \dotsb \cap A_{n}$ by $\bigcap _{i=m}^{n}A_{i}$ ($n>m$).
* Also, we denote $A_{m}\cap A_{m+1}\cap \dotsb$ (never ends) by $\bigcap _{i=m}^{\infty }A_{i}$.
* For (a), the equation can be interpreted as "distributing" $A\cup$ into the bracket.
* For (b), the equation can be interpreted as "distributing" $A\cap$ into the bracket.
Example. For every positive integer $j$, defines $A_{j}=\{n\in \mathbb {N} :n\geq j\}$. Then, $\bigcap _{i=1}^{10}A_{i}=\{1,2,3,\dotsc \}\cap \{2,3,4,\dotsc \}\cap \dotsb \cap \{10,11,12,\dotsc \}=\{10,11,12,\dotsc \}=\{n\in \mathbb {N} :n\geq 10\}=A_{10}.$
The following result combines the union operation and intersection operation.
Proposition. (Distributive law) Let $A$,$B$ and $C$ be sets. Then, the following statements hold.
    (a) $A\cap ({\color {darkgreen}B}\cup {\color {maroon}C})=(A\cap {\color {darkgreen}B})\cup (A\cap {\color {maroon}C})$;
    (b) $A\cup ({\color {darkgreen}B}\cap {\color {maroon}C})=(A\cup {\color {darkgreen}B})\cap (A\cup {\color {maroon}C})$.
Example. Let $A=\{1,2,3\},B=\{2,3,4\}$ and $C=\{1,5,6\}$. Verify that the distributive law (a) holds for these three sets, i.e., show that $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ for these three sets $A,B,C$.
Solution. First, $A\cap (B\cup C)=A\cap \{1,2,3,4,5,6\}=\{1,2,3\}$. On the other hand, $(A\cap B)\cup (A\cap C)=\{2,3\}\cup \{1\}=\{1,2,3\}$.
Exercise. Verify that the distributive law (b) holds for these three sets.
First, $A\cup (B\cap C)=A\cup \varnothing =A=\{1,2,3\}$. On the other hand, $(A\cup B)\cap (A\cup C)=\{1,2,3,4\}\cap \{1,2,3,5,6\}=\{1,2,3\}$.
Definition. (Relative complement) The relative complement of set $A$ in set $B$, denoted by $B\setminus A$, is the set $\{x:x\in B{\text{ and }}x\notin A\}$.
Remark.
* If $U$ is the universal set and $A$ is a subset of $U$, then $A^{c}=U\setminus A$.
* $B\setminus A$ is read 'B take away A'.
Example.
* $\{1,2,3\}\setminus \{1,2\}=\{3\}$;
* $\{1,2,3\}\setminus \{1,2,3\}=\varnothing$;
* $\{1,2,3\}\setminus \{4,5,6\}=\{1,2,3\}$.
Theorem. (De Morgan's laws) Let $B,A_{1},A_{2},\dotsc$ be sets. Then, $B\setminus (A_{1}\cup A_{2}\cup \dotsb )=(B\setminus A_{1})\cap (B\setminus A_{2})\cap \dotsb {\text{ and }}B\setminus (A_{1}\cap A_{2}\cap \dotsb )=(B\setminus A_{1})\cup (B\setminus A_{2})\cup \dotsb$
Remark.
* Special case: If $B=U$, then the equations become $(A_{1}\cup A_{2}\cup \dotsb )^{c}=A_{1}^{c}\cap A_{2}^{c}\cap \dotsb {\text{ and }}(A_{1}\cap A_{2}\cap \dotsb )^{c}=A_{1}^{c}\cup A_{2}^{c}\cup \dotsb$.
Example. Let $A=\{1,2,3\},B=\{1,3\},C=\{1,2,3,4\}$, and let the universal set be $U=\{1,2,3,4,5\}$. For these three sets $A,B,C$,
(a) Verify that $A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$.
(b) Verify that $C\setminus (A\cup B)=(C\setminus A)\cup (C\setminus B)$.
Solution.
(a) First, $A\setminus (B\cup C)=A\setminus \{1,2,3,4\}=\varnothing$. On the other hand, $(A\setminus B)\cap (A\setminus C)=\{2\}\cap \varnothing =\varnothing$. So, we have the desired equality.
(b) First, $C\setminus (A\cup B)=C\setminus \{1,2,3\}=\{4\}$. On the other hand, $(C\setminus A)\cup (C\setminus B)=\{4\}\cap \{2,4\}=\{4\}$.
Exercise. Verify that $(A\cup B\cup C)^{c}=A^{c}\cap B^{c}\cap C^{c}$ for these three sets $A,B,C$.
First, $(A\cup B\cup C)^{c}=(\{1,2,3,4\})^{c}=\{5\}$. On the other hand, $A^{c}\cap B^{c}\cap C^{c}=\{4,5\}\cap \{2,4,5\}\cap \{5\}=\{5\}$.
Definition. (Power set) The power set of a set $A$, denoted by ${\mathcal {P}}(A)$, is the set of all subsets of $A$, i.e., $\{S:S\subseteq A\}$.
Example.
* ${\mathcal {P}}(\{1,2\})=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$;
* ${\mathcal {P}}(\varnothing )=\{\varnothing \}$ (power set of an empty set is not an empty set).
Remark.
* Power set of a set containing $n$ elements contains $2^{n}$ elements.
   * See the chapter about combinatorics for a proof of this statement.
Example. Let $\Omega =\{H,T\}$ be the sample space of tossing a coin ($H$ and $T$ stand for "heads" and "tails" respectively). Then, ${\mathcal {P}}(\Omega )=\{\varnothing ,\{H\},\{T\},\{H,T\}\}.$
Exercise. Suppose we toss a coin twice. Then, the sample space of this random experiment is $\Omega =\{HH,HT,TH,TT\}$ where $HH$ means "heads" followed by "heads", $HT$ means "heads" followed by "tails", etc. Notice that the order matters, and hence $HT$ is different from $TH$.
(a) Find the power set ${\mathcal {P}}(\Omega )$. (Suggestion: check whether your power set contains $2^{4}=16$ elements.)
(b) Define the set $S$ to be the set containing subsets of $\Omega$ that includes the outcome $HH$. That is, $S=\{X\subseteq \Omega :HH\in X\}$. Find $\#(S)$.
(a) The power set is ${\begin{aligned}{\mathcal {P}}(\Omega )={\bigg \&\varnothing ,{\color {darkgreen}\{HH\}},\{HT\},\{TH\},\{TT\},\\&{\color {darkgreen}\{HH,HT\},\{HH,TH\},\{HH,TT\}},\{HT,TH\},\{HT,TT\},\{TH,TT\},\\&{\color {darkgreen}\{HH,HT,TH\},\{HH,HT,TT\},\{HH,TH,TT\}},\{HT,TH,TT\},{\color {darkgreen}\{HH,HT,TH,TT\}}{\bigg \}}\end{aligned}}$ (b) By observing the power set in (a), we can see that 8 subsets (green one) of $\Omega$ contains the outcome $HH$. So, $\#(S)=8$.
Definition. ($n$-ary Cartesian product) The $n$-ary Cartesian product over $n$ sets $S_{1},\dotsc ,S_{n}$, denoted by $S_{1}\times \dotsb \times S_{n}$, is
${\big \(s_{1},\dotsc ,s_{n}):s_{i}\in S_{i}{\text{ for each }}i\in \{1,\dotsc ,n\}{\big \}}.$
Remark.
* It can be proved that $\#(S_{1}\times \dotsb \times S_{n})=\#(S_{1})\times \dotsb \times \#(S_{n})$.
* $(s_{1},\dotsc ,s_{n})$ is ordered, i.e., the order matters for the things inside it.
* When $n=2$, $(s_{1},s_{2})$ is called an ordered pair.
* It is common to use $\mathbb {R} ^{n}$ to denote $\underbrace {\mathbb {R} \times \mathbb {R} \times \dotsb \times \mathbb {R} } _{n{\text{ times}}}$.
Example. Let $A=\{1,2\},B=\{2,3\}$ and $C=\{3,4\}$. Then,
* $A\times B=\{(1,2),(1,3),(2,2),(2,3)\}$.
* $B\times C=\{(2,3),(2,4),(3,3),(3,4)\}$.
* $A\times B\times C=\{(1,2,3),(1,2,4),(1,3,3),(1,3,4),(2,2,3),(2,2,4),(2,3,3),(2,3,4)\}$.
Exercise. A restaurant offers a set lunch where the customer can choose one food/drink from each of group A,B,C:
* group A: egg, beacon
* group B: steak, salmon
* group C: tea, milk, water
We define the sets $A,B,C$, corresponding to these three groups A,B,C:
* $A=\{{\text{egg}},{\text{beacon}}\}$
* $B=\{{\text{steak}},{\text{salmon}}\}$
* $C=\{{\text{tea}},{\text{milk}},{\text{water}}\}$
(a) Find the set $A\times B\times C$, which contains every possible combination of choices made by the customer.
(b) Suppose the tea in the restaurant is out of stock, so the customer cannot choose tea in group C now. Suppose the set $A\times B\times C^{*}$ now contains every possible combination of choices made by the customer. What should be the set $C^{*}$? What is the cardinality of the set $A\times B\times C^{*}$?
(a) The set $A\times B\times C$ is given by ${\begin{aligned}A\times B\times C={\bigg \&({\text{egg}},{\text{steak}},{\text{tea}}),({\text{egg}},{\text{steak}},{\text{milk}}),({\text{egg}},{\text{steak}},{\text{water}}),\\&({\text{egg}},{\text{salmon}},{\text{tea}}),({\text{egg}},{\text{salmon}},{\text{milk}}),({\text{egg}},{\text{salmon}},{\text{water}}),\\&({\text{beacon}},{\text{steak}},{\text{tea}}),({\text{beacon}},{\text{steak}},{\text{milk}}),({\text{beacon}},{\text{steak}},{\text{water}}),\\&({\text{beacon}},{\text{salmon}},{\text{tea}}),({\text{beacon}},{\text{salmon}},{\text{milk}}),({\text{beacon}},{\text{salmon}},{\text{water}}){\bigg \}}\end{aligned}}$ (b) The set $C^{*}$ should be $\{{\text{milk}},{\text{water}}\}$. The cardinality of the set $A\times B\times C^{*}$ is $2\times 2\times 2=8$.