In this section we introduce set theory with the aim of defining sample spaces and events.

Sets and Subsets

A set is a collection of objects. For example, the set $\{1,2,3\}$ is a set of the numbers 1, 2, and 3 and $\{a\}$ is the set containing a single element $a$. For a set $A$, we denote $a\in A$ (read, $a$ in $A$) to mean that $a$ is an element of the set $A$. We denote $a\notin A$ (read, $a$ not in $A$) to mean that $a$ is not an element of $A$.

Ordering and repetition doesn’t matter for sets. So $\{a,b,c\}=\{a,c,b\}$ and $\{a,a,b\}=\{a,b\}$

If a set is empty, we call this the null or empty set and denote it as $\mathrm{\varnothing }$ or $\{\}$.

Let $A$ and $B$ be sets. Then if for each $x\in A$ we have that $x\in B$, then we say that $A$ is a subset of $B.$ We also say that $A$ is contained in $B$ which we write as $A\subset B$ (or that $B$ contains $A$ which is denoted as $B\supset A$).

By definition, $A$ is always a subset of itself. Additionally, the empty set is always a subset of $A$.

Two sets are equal if and only if both $A\subset B$ and $B\subset A$ are true. This is typically how we prove equality of sets.

You have certainly encountered subsets of the real numbers (We denote the set of real numbers to be $\mathbb{R}$). For any pair of real numbers $a$ and $b$ such that $a<b$, the set of all real numbers $x$ such that $a\le x\le b$ is called the closed interval from $a$ to $b$ and denoted as $[a,b]$. Similarly, for $a<x<b$, we denote the set as $(a,b)$ and call it the open interval from $a$ to $b$. $a<x\le b$ and $a\le x<b$ are half-open intervals and denoted as $(a,b]$ and $[a,b)$ respectively. Note that $(a,b)\subset [a,b]\subset \mathbb{R}$.

Additionally, sets can contain other sets. For example, the set $\{\{a,b\},\{1,2\}\}$ is a set that contains 2 objects, 1 of which is a set that contains $a$ and $b$ and the other is a set that contains the numbers 1 and 2.

Let $A$ be any set. The set of all possible subsets of $A$ is called the power set and is denoted as $2^A$. That is, $B\in 2^A⟺B\subset A$.

Set Operations: Union, Intersection, and Complement

Let $A$ and $B$ be sets. The union of the sets $A$ and $B$ is the set of all elements $x$ such that $x\in A$ or $x\in B$ (“or” in mathematics is inclusive) which we denote $$A\cup B=\{x:x\in A\text{ or }x\in B\}.$$ The intersection of $A$ and $B$ is the set of all elements $x$ such that $x\in A$ and $x\in B$ which we denote $$A\cap B=\{x:x\in A\text{ and }x\in B\}.$$

Let $A\subset S$. The complement of $A$ in $S$ is the set of all elements in $S$ but not in $A$ which we denote by $C_S(A)$ or $A^c$ if we assume to be in $S$. $$A^c=\{x:x\notin A\}$$

Proof of (a): Suppose $x\in (A\cup B{)}^c.$ Then $x\in S$ and $x\notin A\cup B.$ Thus, $x\notin A$ and $x\notin B,$ which is the same as $x\in A^c$ and $x\in B^c.$ Therefore, $x\in A^c\cap B^c.$ This shows that $$(A\cup B{)}^c\subset A^c\cap B^c.$$ Conversely, suppose $x\in A^c\cap B^c.$ Then $x\in S$ and $x\in A^c$ and $x\in B^c.$ Thus, $x\notin A$ and $x\notin B$ and therefore $x\notin A\cup B.$ It follows that $x\in (A\cup B{)}^c$ and thus $$A^c\cap B^c\subset (A\cup B{)}^c.$$ Hence, we have shown that $A^C\cap B^c=(A\cup B{)}^c.$

The proof of (b) follows similarly.

Indexed Families of Sets

Let $I$ be a set, not necessarily countable. For each $\alpha \in I,$ let $A_{\alpha }$ be a subset of a given set $S.$ We call $I$ an indexing set and the collection of the subsets of $S$ indexed by the elements of $I$ an indexed family of subsets of $S.$ We denote this indexed family of subsets of $S$ by $\{A_{\alpha }{\}}_{\alpha \in I}$ (read, “A sub-alpha, alpha in $I$”).

Let $\{A_{\alpha }{\}}_{\alpha \in I}$ be an indexed family of subsets of a set $S.$ The union of this indexed family, written ${\cup }_{\alpha \in I}{A}_{\alpha },$ (read "union over $\alpha$ in $I$ of $A_{\alpha }$") is the set of all elements $x\in S$ such that $x\in A_{\beta }$ for at least one index $\beta \in I.$ The intersection of this indexed family, written ${\cap }_{\alpha \in I}{A}_{\alpha }$ (read "intersection over $\alpha$ in $I$ of $A_{\alpha }$") is the set of all elements $x\in S$ such that $x\in A_{\beta }$ for each $\beta \in I.$

For example, let $A_1,A_2,A_3,A_4$ be respectively the set of freshmen, sophomores, juniors, and seniors at UCSD. Here, we have $I=\{1,2,3,4\}$ as an indexing set, and ${\cup }_{\alpha \in I}{A}_{\alpha }$ is the set of undergraduates while ${\cap }_{\alpha \in I}{A}_{\alpha }=\mathrm{\varnothing }.$

If $I=\mathrm{\varnothing },$ then $${\cup }_{\alpha \in \mathrm{\varnothing }}{A}_{\alpha }=\mathrm{\varnothing }$$ $${\cap }_{\alpha \in \mathrm{\varnothing }}{A}_{\alpha }=S.$$

Products of Sets

Let $x$ and $y$ be objects. Then the ordered pair $(x,y)$ is a sequence of two objects. Note that unlike sets, where ordering doesn’t matter, if $x\ne y,$ then $(x,y)\ne (y,x).$

Let $A$ and $B$ be sets. The Cartesian product of $A$ and $B$, written $A\times B,$ (read “$A$ cross $B$”) is the set whose elements are all ordered pairs $(x,y)$ such that $x\in A$ and $y\in B.$

For example, $\{a,b\}\times \{1,2\}=\{(a,1),(a,2),(b,1),(b,2)\}.$ Also, the familiar 2d coordinate plane is the Cartesian product of $\mathbb{R}$ and $\mathbb{R}$, denoted $\mathbb{R}\times \mathbb{R}$ or ${\mathbb{R}}^2.$

Unless $A=B,$ then $A\times B$ and $B\times A$ are distinct.

Let $A_1,A_2,\dots ,A_n$ be a finite sequence of sets, indexed by $\{1,2,\dots ,n\}.$ The direct product of $A_1,A_2,\dots ,A_n$, written $$\prod _{i=1}^n{A}_i$$ is the set consisting of all sequences $(a_1,a_2,\dots ,a_n)$ such that $a_1\in A_1,a_2\in A_2,\dots ,a_n\in A_n.$

The set of points of Euclidean $n$-space is an example of a direct product of sets. $${\mathbb{R}}^n=\prod _{i=1}^n{A}_i$$

An element $x\in {\mathbb{R}}^n$ is a sequence $x=(x_1,\dots ,x_n)$ of real numbers. In general, if the sets $A_1,\dots ,A_n$ are all equal to the same set $A$, we write $$A^n=\prod _{i=1}^n{A}_i$$ and call an element $a=(a_1,a_2,\dots ,A_n)\in A^n$ an $n$-tuple.