# 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.

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

 Yes. No.

Example.

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

Exercise.

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

 $\varnothing$ $\{\varnothing \}$ $\{\varnothing ,\{\varnothing \}\}$ $\{\{\varnothing \}\}$ $\{\{\varnothing ,\{\varnothing \}\}\}$ 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?

Solution

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".)

Solution

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.

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

 0 1 2 3 None of the above.

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

Solution

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:

A ⊆ B (A ≠ B):

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


Example.

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

Venn digram:

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

• $\{\{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$ ?

Solution

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 , 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:

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


Exercise.

Find $\varnothing ^{c}$ .

 $U$ $\{U\}$ $\varnothing$ $\{\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 $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:

*----------------*
|                |
|  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 $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

*-----*       *-----*       *-----*
|     |       |     |       |     |
|  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 $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.

Solution

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\}$ . The relative complement of A {\displaystyle A}   (left) in B {\displaystyle B}   (right) ( B ∖ A {\displaystyle B\setminus A}  ), given by the red region.

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

Solution

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.

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

Solution

(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^{*}$ ?

Solution

(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$ .