# 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 ${\displaystyle x}$ belongs to (or is contained in) a set ${\displaystyle S}$ , we write ${\displaystyle x\in S}$.
• If ${\displaystyle x}$ does not belong to the set ${\displaystyle S}$ , we write ${\displaystyle x\notin S}$.
• When ${\displaystyle x}$ and ${\displaystyle y}$ are equal, denoted by ${\displaystyle x=y}$, ${\displaystyle x}$ and ${\displaystyle y}$ are different symbols denoting the same object(s). (When ${\displaystyle x}$ and ${\displaystyle y}$ are not equal, we write ${\displaystyle 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 ${\displaystyle 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., ${\displaystyle 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., ${\displaystyle \{{\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:
${\displaystyle \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, ${\displaystyle S{\overset {\text{ def }}{=}}\{x:x{\text{ is a month in a year}}\}}$.

Example. (Empty set) The set ${\displaystyle \{\}}$ is called an empty set, and it contains no element. It is commonly denoted by ${\displaystyle \varnothing }$ also.

Exercise.

Is ${\displaystyle \{\varnothing \}}$ an empty set?

 Yes. No.

Example.

• ${\displaystyle {\text{apple}}\in \{{\text{apple, orange, banana}}\}}$;
• ${\displaystyle \varnothing \in \{\varnothing \}}$;
• ${\displaystyle \varnothing \notin \varnothing }$.

Exercise.

Select all element(s) belonging to the set ${\displaystyle {\big \{}\varnothing ,\{\varnothing \},\{\{\varnothing \}\}{\big \}}}$.

 ${\displaystyle \varnothing }$ ${\displaystyle \{\varnothing \}}$ ${\displaystyle \{\varnothing ,\{\varnothing \}\}}$ ${\displaystyle \{\{\varnothing \}\}}$ ${\displaystyle \{\{\varnothing ,\{\varnothing \}\}\}}$

Example.

• Let ${\displaystyle S_{1}}$ be the set containing all outcomes from rolling a six-faced dice. Then, we can express the set ${\displaystyle S_{1}}$ as ${\displaystyle \{1,2,3,4,5,6\}}$.
• Let ${\displaystyle S_{2}}$ be the set containing all outcomes from tossing a coin. Then, we can express the set ${\displaystyle S_{2}}$ as ${\displaystyle \{H,T\}}$ where ${\displaystyle H}$ stands for "heads" and ${\displaystyle 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?

Solution

The set is ${\displaystyle \{0,1\}}$.

Definition. (Set equality) When two sets are equal, they contain the same elements.

Remark.

• Equivalently, two sets ${\displaystyle A}$ and ${\displaystyle B}$ are equal if each element of ${\displaystyle A}$ is also element of ${\displaystyle B}$ and each element of ${\displaystyle B}$ is also element of ${\displaystyle A}$.
• We use ${\displaystyle A=B}$ to denote sets ${\displaystyle A}$ and ${\displaystyle B}$ are equal (${\displaystyle A\neq B}$ is used to denote ${\displaystyle A}$ and ${\displaystyle B}$ are not equal).

Example.

• ${\displaystyle \{\varnothing \}=\{x:x{\text{ is a empty set}}\}}$.
• ${\displaystyle \varnothing =\{\}\neq {\big \{}\{\}{\big \}}=\{\varnothing \}}$.
• ${\displaystyle \{2,3,5\}=\{x:x{\text{ is a prime number that is not greater than }}5\}}$

Example. Let ${\displaystyle S_{1}}$ be the set containing all odd outcomes from rolling a six-faced dice. Also, let ${\displaystyle S_{2}}$ be the set containing all outcomes that are not even from rolling a six-faced dice. Then, ${\displaystyle S_{1}=S_{2}=\{1,3,5\}}$.

Definition. (Universal set) Universal set, denoted by ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \Omega =\{1,2,3,4,5,6\}}$.

Exercise. What is the sample space of tossing a coin? (Use ${\displaystyle H}$ to stand for the outcome "heads" and ${\displaystyle T}$ to stand for the outcome "tails".)

Solution

The sample space is ${\displaystyle \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 ${\displaystyle n\in \mathbb {N} }$ elements (${\displaystyle \mathbb {N} }$ is the set containing all positive integers).
• Cardinality of set ${\displaystyle S}$ can be denoted by ${\displaystyle \#(S)}$ (or ${\displaystyle |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.

• ${\displaystyle \#({\big \{}\{1\},2,3{\big \}})=3}$.
• ${\displaystyle \#(\varnothing )=0}$.
• ${\displaystyle \mathbb {N} }$ (the set containing each positive integer) is an infinite set.

Exercise.

Calculate ${\displaystyle \#(\{\varnothing ,\{\varnothing \}\})}$.

 0 1 2 3 None of the above.

Example. Let ${\displaystyle \Omega }$ be the sample space of rolling a six-faced dice and ${\displaystyle S}$ be the set containing all odd outcomes from rolling a six-faced dice. Then, ${\displaystyle \#(S)=3}$ and ${\displaystyle \#(\Omega )=6}$.

Exercise. A student is asked to show that two sets ${\displaystyle A}$ and ${\displaystyle B}$ are equal in a question of his assignment. In that question, one of the given condition is that ${\displaystyle \#(A)=\#(B)}$. The student then makes the following argument:

Since ${\displaystyle \#(A)=\#(B)}$, it follows that ${\displaystyle A=B}$.

Is his argument correct? If not, provides an example of sets ${\displaystyle A}$ and ${\displaystyle B}$ such that ${\displaystyle \#(A)=\#(B)}$ but ${\displaystyle A\neq B}$.

Solution

The argument is wrong. We can take, for example, ${\displaystyle A=\{1\}}$ and ${\displaystyle B=\{2\}}$. Then, ${\displaystyle \#(A)=\#(B)=1}$ but ${\displaystyle \{1\}\neq \{2\}}$.

## Subsets

We introduce a relationship between sets in this section.

Definition. (Subset) ${\displaystyle A}$ is a subset of ${\displaystyle B}$, denoted by ${\displaystyle A\subseteq B}$ if each element of set ${\displaystyle A}$ is an element of set ${\displaystyle B}$.

Remark.

• If ${\displaystyle A}$ is not a subset of ${\displaystyle B}$, then we write ${\displaystyle A\not \subseteq B}$.
• By referring to the definitions of subsets and set equality, we can see that ${\displaystyle A=B}$ is equivalent to (or if and only if) ${\displaystyle A\subseteq B}$ and ${\displaystyle B\subseteq A}$.
• The notation ${\displaystyle A\supseteq B}$ means that ${\displaystyle A}$ is a superset of ${\displaystyle B}$, which means that ${\displaystyle B}$ is a subset of ${\displaystyle 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:

A ⊆ B (A ≠ B):

*-----------------------*
|                       |
|                       |
|   *----------*        | <---- B
|   |          |        |
|   |    A     |        |
|   |          |        |
|   *----------*        |
*-----------------------*


Example.

• ${\displaystyle \{1,3\}\subseteq \{1,2,3\}}$.

Venn digram:

*--------------------*
|   *----------*  2  |
|   |    1  3  |     |
|   *----------*     |
*--------------------*

• ${\displaystyle \{\{1\}\}\not \subseteq \{1,2,3\}}$ (${\displaystyle \{1\}\notin \{1,2,3\}}$).
• It can be proved that ${\displaystyle \varnothing \subseteq S}$ for each set ${\displaystyle S}$.

Example. Let ${\displaystyle \Omega }$ be the sample space of rolling a six-faced dice and ${\displaystyle S}$ be the set containing all odd outcomes from rolling a six-faced dice. Then, ${\displaystyle S\subseteq \Omega }$.

Exercise. Let ${\displaystyle P}$ be the set containing all prime outcomes from rolling a six-faced dice. Is ${\displaystyle P}$ a subset of ${\displaystyle S}$?

Solution

No, since ${\displaystyle 2\in P}$ but ${\displaystyle 2\notin S}$.

Example. (Intervals) Intervals are commonly encountered subsets of ${\displaystyle \mathbb {R} }$. If ${\displaystyle a}$ and ${\displaystyle b}$ are real numbers such that ${\displaystyle a, then

{\displaystyle {\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, ${\displaystyle (-\infty ,\infty )=\mathbb {R} }$.

We also have ${\displaystyle [-\infty ,\infty ]}$, which is the set containing all extended real numbers, i.e., ${\displaystyle [-\infty ,\infty ]=(-\infty ,\infty )\cup \{-\infty ,\infty \}}$. Such notation is occasionally used. (Extended real number system is obtained by adding ${\displaystyle \infty }$ and ${\displaystyle -\infty }$ to the real number system.)

Definition. (Proper subset) A set ${\displaystyle A}$ is a proper subset of set ${\displaystyle B}$ if ${\displaystyle A\subseteq B}$ and ${\displaystyle A\neq B}$;. We write ${\displaystyle A\subsetneq B}$ in this case.

Remark.

• If a set ${\displaystyle A}$ is not a proper subset of ${\displaystyle B}$, then we write ${\displaystyle A\not \subsetneq B}$ (but we rarely write this).
• The notation ${\displaystyle A\supsetneq B}$ means that ${\displaystyle A}$ is a proper superset of ${\displaystyle B}$, which means that ${\displaystyle B}$ is a proper subset of ${\displaystyle A}$.
• This notation and terminology are seldom used.

Example.

• The set ${\displaystyle \{1,2\}}$ is not a proper subset of itself, i.e., ${\displaystyle \{1,2\}\not \subsetneq \{1,2\}}$.
• ${\displaystyle \{1\}\subsetneq \{1,2\}}$.

Definition. (Complement) Let ${\displaystyle A}$ be a subset of universal set ${\displaystyle U}$. The (absolute) complement of ${\displaystyle A}$, denoted by ${\displaystyle A^{c}}$, is the set ${\displaystyle \{x\in U:x\notin A\}}$.

Example. If ${\displaystyle A=\{1,2,3\}}$ and ${\displaystyle U=\{1,2,3,4,5\}}$, then ${\displaystyle A^{c}=\{4,5\}}$.

Venn diagram:

*-----------------------*
|                       |
|    A           4  5   |
|   *----------*        |
|   |          |        | <---- U
|   |  1 2  3  |        |
|   |          |        |
|   *----------*        |
*-----------------------*


Exercise.

Find ${\displaystyle \varnothing ^{c}}$.

 ${\displaystyle U}$ ${\displaystyle \{U\}}$ ${\displaystyle \varnothing }$ ${\displaystyle \{\varnothing \}}$ None of the above.

## 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 ${\displaystyle A}$ and set ${\displaystyle B}$, denoted by ${\displaystyle A\cup B}$, is the set ${\displaystyle \{x:x\in A{\text{ or }}x\in B\}}$.

Remark.

• ${\displaystyle A\cup B}$ is read 'A cup B'.

Example.

• ${\displaystyle \{{\text{apple}},{\text{orange}}\}\cup \{{\text{orange}},{\text{red}}\}=\{{\text{apple}},{\text{orange}},{\text{red}}\}}$.

Venn diagram:

*----------------*
|                |
|  red   *-------*--------*
|        | orange|        |
*--------*-------*        |
|       apple    |
*----------------*


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 ${\displaystyle A,B}$ and ${\displaystyle C}$ be sets. Then, we have

(a) ${\displaystyle A\cup B=B\cup A}$ (commutative law);
(b) ${\displaystyle 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 ${\displaystyle A\cup B\cup C}$ directly, since ${\displaystyle A\cup (B\cup C)=(A\cup B)\cup C}$.

Example. Let ${\displaystyle A_{1}=\{1,2\},A_{2}=\{3,4,5\}}$ and ${\displaystyle A_{3}=\{6,7\}}$. Then,

• ${\displaystyle \bigcup _{i=1}^{3}A_{i}=A_{1}\cup A_{2}\cup A_{3}=\{1,2,3,4,5,6,7\}}$
• ${\displaystyle \bigcup _{i=2}^{3}A_{i}=A_{2}\cup A_{3}=\{3,4,5,6,7\}}$
• ${\displaystyle A_{1}\cup A_{3}=\{1,2,6,7\}}$.

(${\displaystyle \bigcup _{i=m}^{n}A_{i}}$ means ${\displaystyle A_{m}\cup A_{m+1}\cup \dotsb \cup A_{n}}$ (${\displaystyle n>m}$), and ${\displaystyle \bigcup _{i=m}^{\infty }A_{i}}$ means ${\displaystyle A_{m}\cup A_{m+1}\cup \dotsb }$.)

Definition. (Intersection of sets) The intersection of set ${\displaystyle A}$ and set ${\displaystyle B}$, denoted by ${\displaystyle A\cap B}$, is the set ${\displaystyle \{x:x\in A{\text{ and }}x\in B\}}$.

Remark.

• ${\displaystyle A\cap B}$ is read 'A cap B'.

Example.

• ${\displaystyle \{1,2,3\}\cap \{2,3,4\}=\{2,3\}}$.
• ${\displaystyle \{1,2,3\}\cap \{4,5,6\}=\varnothing }$.

Definition. (Disjoint sets) Sets ${\displaystyle A}$ and ${\displaystyle B}$ are disjoint (or mutually exclusive) if ${\displaystyle A\cap B=\varnothing }$.

Example. The sets ${\displaystyle \{1,2,3\}}$ and ${\displaystyle \{4,5,6\}}$ are disjoint.

Remark.

• I.e., ${\displaystyle A}$ and ${\displaystyle 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

*-----*       *-----*       *-----*
|     |       |     |       |     |
|  A  |       |  B  |       |  C  |
*-----*       *-----*       *-----*

(A, B and C are disjoint)

*----------------*
|                | <---- D
| *--*   *-------*--------*
| |  |   |       |        |
*-*--*---*-------*        | <--- E
|  |   |                |
*--*   *----------------*
^
|
F

(D, E and F are not disjoint, but E and F are disjoint)


Proposition. (Properties of intersection of sets) Let ${\displaystyle A}$,${\displaystyle B}$ and ${\displaystyle C}$ be sets. Then, we have

(a) ${\displaystyle A\cap B=B\cap A}$ (commutative law);
(b) ${\displaystyle A\cap (B\cap C)=(A\cap B)\cap C}$ (associative law);

Remark.

• Likewise, we denote ${\displaystyle A_{m}\cap A_{m+1}\cap \dotsb \cap A_{n}}$ by ${\displaystyle \bigcap _{i=m}^{n}A_{i}}$ (${\displaystyle n>m}$).
• Also, we denote ${\displaystyle A_{m}\cap A_{m+1}\cap \dotsb }$ (never ends) by ${\displaystyle \bigcap _{i=m}^{\infty }A_{i}}$.
• For (a), the equation can be interpreted as "distributing" ${\displaystyle A\cup }$ into the bracket.
• For (b), the equation can be interpreted as "distributing" ${\displaystyle A\cap }$ into the bracket.

Example. For every positive integer ${\displaystyle j}$, defines ${\displaystyle A_{j}=\{n\in \mathbb {N} :n\geq j\}}$. Then,

${\displaystyle \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 ${\displaystyle A}$,${\displaystyle B}$ and ${\displaystyle C}$ be sets. Then, the following statements hold.

(a) ${\displaystyle A\cap ({\color {darkgreen}B}\cup {\color {maroon}C})=(A\cap {\color {darkgreen}B})\cup (A\cap {\color {maroon}C})}$;
(b) ${\displaystyle A\cup ({\color {darkgreen}B}\cap {\color {maroon}C})=(A\cup {\color {darkgreen}B})\cap (A\cup {\color {maroon}C})}$.

Example. Let ${\displaystyle A=\{1,2,3\},B=\{2,3,4\}}$ and ${\displaystyle C=\{1,5,6\}}$. Verify that the distributive law (a) holds for these three sets, i.e., show that

${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$
for these three sets ${\displaystyle A,B,C}$.

Solution. First, ${\displaystyle A\cap (B\cup C)=A\cap \{1,2,3,4,5,6\}=\{1,2,3\}}$. On the other hand, ${\displaystyle (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.

Solution

First, ${\displaystyle A\cup (B\cap C)=A\cup \varnothing =A=\{1,2,3\}}$. On the other hand, ${\displaystyle (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 ${\displaystyle A}$ in set ${\displaystyle B}$, denoted by ${\displaystyle B\setminus A}$, is the set ${\displaystyle \{x:x\in B{\text{ and }}x\notin A\}}$.

Remark.

• If ${\displaystyle U}$ is the universal set and ${\displaystyle A}$ is a subset of ${\displaystyle U}$, then ${\displaystyle A^{c}=U\setminus A}$.
• ${\displaystyle B\setminus A}$ is read 'B take away A'.

Example.

• ${\displaystyle \{1,2,3\}\setminus \{1,2\}=\{3\}}$;
• ${\displaystyle \{1,2,3\}\setminus \{1,2,3\}=\varnothing }$;
• ${\displaystyle \{1,2,3\}\setminus \{4,5,6\}=\{1,2,3\}}$.

Theorem. (De Morgan's laws) Let ${\displaystyle B,A_{1},A_{2},\dotsc }$ be sets. Then,

${\displaystyle 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 ${\displaystyle B=U}$, then the equations become ${\displaystyle (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 ${\displaystyle A=\{1,2,3\},B=\{1,3\},C=\{1,2,3,4\}}$, and let the universal set be ${\displaystyle U=\{1,2,3,4,5\}}$. For these three sets ${\displaystyle A,B,C}$,

(a) Verify that ${\displaystyle A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)}$.

(b) Verify that ${\displaystyle C\setminus (A\cup B)=(C\setminus A)\cup (C\setminus B)}$.

Solution.

(a) First, ${\displaystyle A\setminus (B\cup C)=A\setminus \{1,2,3,4\}=\varnothing }$. On the other hand, ${\displaystyle (A\setminus B)\cap (A\setminus C)=\{2\}\cap \varnothing =\varnothing }$. So, we have the desired equality.

(b) First, ${\displaystyle C\setminus (A\cup B)=C\setminus \{1,2,3\}=\{4\}}$. On the other hand, ${\displaystyle (C\setminus A)\cup (C\setminus B)=\{4\}\cap \{2,4\}=\{4\}}$.

Exercise. Verify that ${\displaystyle (A\cup B\cup C)^{c}=A^{c}\cap B^{c}\cap C^{c}}$ for these three sets ${\displaystyle A,B,C}$.

Solution

First, ${\displaystyle (A\cup B\cup C)^{c}=(\{1,2,3,4\})^{c}=\{5\}}$. On the other hand, ${\displaystyle 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 ${\displaystyle A}$, denoted by ${\displaystyle {\mathcal {P}}(A)}$, is the set of all subsets of ${\displaystyle A}$, i.e., ${\displaystyle \{S:S\subseteq A\}}$.

Example.

• ${\displaystyle {\mathcal {P}}(\{1,2\})=\{\varnothing ,\{1\},\{2\},\{1,2\}\}}$;
• ${\displaystyle {\mathcal {P}}(\varnothing )=\{\varnothing \}}$ (power set of an empty set is not an empty set).

Remark.

• Power set of a set containing ${\displaystyle n}$ elements contains ${\displaystyle 2^{n}}$ elements.

Example. Let ${\displaystyle \Omega =\{H,T\}}$ be the sample space of tossing a coin (${\displaystyle H}$ and ${\displaystyle T}$ stand for "heads" and "tails" respectively). Then,

${\displaystyle {\mathcal {P}}(\Omega )=\{\varnothing ,\{H\},\{T\},\{H,T\}\}.}$

Exercise. Suppose we toss a coin twice. Then, the sample space of this random experiment is

${\displaystyle \Omega =\{HH,HT,TH,TT\}}$
where ${\displaystyle HH}$ means "heads" followed by "heads", ${\displaystyle HT}$ means "heads" followed by "tails", etc. Notice that the order matters, and hence ${\displaystyle HT}$ is different from ${\displaystyle TH}$.

(a) Find the power set ${\displaystyle {\mathcal {P}}(\Omega )}$. (Suggestion: check whether your power set contains ${\displaystyle 2^{4}=16}$ elements.)

(b) Define the set ${\displaystyle S}$ to be the set containing subsets of ${\displaystyle \Omega }$ that includes the outcome ${\displaystyle HH}$. That is, ${\displaystyle S=\{X\subseteq \Omega :HH\in X\}}$. Find ${\displaystyle \#(S)}$.

Solution

(a) The power set is

{\displaystyle {\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 ${\displaystyle \Omega }$ contains the outcome ${\displaystyle HH}$. So, ${\displaystyle \#(S)=8}$.

Definition. (${\displaystyle n}$-ary Cartesian product) The ${\displaystyle n}$-ary Cartesian product over ${\displaystyle n}$ sets ${\displaystyle S_{1},\dotsc ,S_{n}}$, denoted by ${\displaystyle S_{1}\times \dotsb \times S_{n}}$, is

${\displaystyle {\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 ${\displaystyle \#(S_{1}\times \dotsb \times S_{n})=\#(S_{1})\times \dotsb \times \#(S_{n})}$.
• ${\displaystyle (s_{1},\dotsc ,s_{n})}$ is ordered, i.e., the order matters for the things inside it.
• When ${\displaystyle n=2}$, ${\displaystyle (s_{1},s_{2})}$ is called an ordered pair.
• It is common to use ${\displaystyle \mathbb {R} ^{n}}$ to denote ${\displaystyle \underbrace {\mathbb {R} \times \mathbb {R} \times \dotsb \times \mathbb {R} } _{n{\text{ times}}}}$.

Example. Let ${\displaystyle A=\{1,2\},B=\{2,3\}}$ and ${\displaystyle C=\{3,4\}}$. Then,

• ${\displaystyle A\times B=\{(1,2),(1,3),(2,2),(2,3)\}}$.
• ${\displaystyle B\times C=\{(2,3),(2,4),(3,3),(3,4)\}}$.
• ${\displaystyle 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 ${\displaystyle A,B,C}$, corresponding to these three groups A,B,C:

• ${\displaystyle A=\{{\text{egg}},{\text{beacon}}\}}$
• ${\displaystyle B=\{{\text{steak}},{\text{salmon}}\}}$
• ${\displaystyle C=\{{\text{tea}},{\text{milk}},{\text{water}}\}}$

(a) Find the set ${\displaystyle 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 ${\displaystyle A\times B\times C^{*}}$ now contains every possible combination of choices made by the customer. What should be the set ${\displaystyle C^{*}}$? What is the cardinality of the set ${\displaystyle A\times B\times C^{*}}$?

Solution

(a) The set ${\displaystyle A\times B\times C}$ is given by

{\displaystyle {\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 ${\displaystyle C^{*}}$ should be ${\displaystyle \{{\text{milk}},{\text{water}}\}}$. The cardinality of the set ${\displaystyle A\times B\times C^{*}}$ is ${\displaystyle 2\times 2\times 2=8}$.