Set Theory

2.1. Set Theory#

2.1.1. Set theory basics#

To start our coverage here, we need to know some elementary basics about sets. I am assuming you are already relatively familiar with sets, so this should be largely review:

Definition 2.1 (Set union)

Suppose that $A, B$ are sets. The union of $A$ and $B$ is the set:

\[ A \cup B \triangleq \left\{\omega : \omega \in A\text{ or }\omega \in B\right\}.\]

Definition 2.2 (Set intersection)

Suppose that $A, B$ are sets. The intersection of $A$ and $B$ is the set:

\[ A \cap B \triangleq \left\{\omega : \omega \in A\text{ and }\omega \in B\right\}.\]

Definition 2.3 (Subset)

Suppose that $\Omega$ is a set. $A$ is a subset of $\Omega$ if for every $\omega \in A$, then $\omega \in \Omega$. We denote this as $A \subseteq \Omega$.

This definition is what is usually used for subsets, but it turns out this is actually called an improper subset. The distinction is extremely small, but notice here that $A \subseteq A$ (a set is a subset of itself). For this reason, we have a further term, a proper subset:

Definition 2.4 (Proper subset)

Suppose that $\Omega$ is a set. $A$ is a proper subset of $\Omega$ if for every $\omega \in A$, then $\omega \in \Omega$, but $A \neq \Omega$. We denote this as $A \subset \Omega$.

So, in the proper subset definition here, $\Omega$ necessarily contains elements $\omega \in \Omega$ where $\omega \not \in A$. Further, we can flip these two definitions around, and obtain their equivalent superset definitions: $\Omega \supseteq A$ and $\Omega \supset A$, respectively.

We can use this to define the set complement:

Definition 2.5 (Set complement)

Suppose that $A \subseteq \Omega$. The complement of $A$ in $\Omega$ is:

\[ A^c(\Omega) \triangleq \{\omega \in \Omega : \omega \not \in A\}.\]

Definition 2.6 (Set difference)

Suppose that $A, B \in \Omega$, and $A \subseteq B$. The set difference $B \setminus A$ is:

\[ B \setminus A \triangleq \{\omega \in B : \omega \not \in A\}.\]

This can get extremely cumbersome, and when we are talking about sets, the it’s usually really clear what the superset is, so we’ll generally abbreviate this $A^c$.

Definition 2.7 (Disjoint sets)

Suppose that $A, B$ are sets. $A$ and $B$ are called disjoint if $A \cap B = \varnothing$. If $A$ and $B$ are disjoint, their union $A \cup B$ is abbreviated $A \sqcup B$, to emphasize that it is a disjoint union.

So the idea here is that $A$ and $B$ simply contain nothing in common, and $A \sqcup B$ is just notation which emphasizes that it is a union of disjoint sets. Sometimes we’ll be explicit when we’re talking about disjoint sets, and other times we’ll use the abbreviated version above ($A \cap B = \varnothing$).

All of these terms can be extended to countable (or uncountable) sequences of sets, too:

Definition 2.8 (Arbitrary union)

Suppose that $(A_i)_{i \in \mathcal I}$ are a sequence of sets. Their union is:

\[ \bigcup_{i \in \mathcal I}A_i \triangleq \left\{\omega : \text{there exists } i\text{ where }\omega \in A_i\right\}.\]

Basically, the union is the set that contains all of the elements of the arbitrary sequence of sets. Likewise, we can define an arbitrary intersection:

Definition 2.9 (Arbitrary union)

Suppose that $A, B$ are sets. The union of $A$ and $B$ is the set:

\[ \bigcap_{i \in \mathcal I}A_i \triangleq \left\{\omega : \omega \in A_i\text{ for all }i \in \mathcal I\right\}.\]

Here, the union is the set that contains the elements which are common to all of the arbitrary sequence of sets. We can use this to obtain arbitrary sequences of mutually disjoint sets, too:

Definition 2.10 (Mutually disjoint sets)

Suppose that $(A_i)_{i \in \mathcal I}$ are a sequence of sets, where $\mathcal I$ is an indexing set (countable or uncountable). $(A_i)_{i \in \mathcal I}$ are called mutually disjoint if for all $i, j \in \mathcal I$, $A_i \cap A_j = \varnothing$.

A lot of times when you’re proving things about sets, it can really help intuitively to set the proof up first using pictures. For the basic set operations, these pictures would look like this:

../../_images/basic_ops.png — Fig. 2.1 Here, the blue circle represents the space $\Omega$ upon which three sets $A$, $B$, and $C$ are defined. In this setup, notice that $C \subset B$. **(B)** shows the set union of $A$ with $B$, **(C)** shows the set intersection of $A$ with $B$, **(D)** shows the complement of $A$, and **(E)** shows the set difference of $B$ and $C$.#

As a quick primer, take a chance to prove some things about set differences, and prove De Morgan’s laws:

Example 2.1 (Set difference as intersection)

Suppose that $A, B \in \Omega$, and $A \subseteq B$. Show that $B \setminus A \equiv B \cap A^c$.

Hint: reason out using the definitions of the set differences, the set complement, and the set intersection, and first think about it using a picture like Fig. 2.1 above.

Note: this one should be pretty easy, so if you’re struggling, try starting with a book on set theory before tackling this book.

Example 2.2 (De Morgan’s Laws I)

Suppose that $\Omega$ is a set, and $A, B \subseteq \Omega$. Then:

$(A \cup B)^c = A^c \cap B^c$, and
$(A \cap B)^c = A^c \cup B^c$.

Hint: Do this by showing that if an element is in each resulting set on the left, that it follows boolean properties (either $\in$ or $\not\in$) $A$ and/or $B$, respectively.

When you conceptualize sets, you should know these two properties inside and out! As a quick follow-up exercise, show that these laws extend to finitely many operations, too:

Example 2.3 (De Morgan’s Laws II)

Suppose that $\Omega$ is a set, and $A_m \subseteq \Omega$, for all $m \in \mathbb N$. Then if $n \in \mathbb N$:

$\left(\bigcup_{m \in [n]} A_m\right)^c = \bigcap_{m \in [n]} A_m^c$, and
$\left(\bigcap_{m \in [n]} A_m\right)^c = \bigcup_{m \in [n]} A_m^c$.

Hint: Use De Morgan’s Laws I.

These also extend to arbitrary indexing sets:

Example 2.4 (De Morgan’s Laws III)

Suppose that $\Omega$ is a set, and $A_i \subseteq \Omega$, for all $i \in \mathcal I$, where $\mathcal I$ is an arbitrary indexing set (countable or uncountable). Then:

$\left(\bigcup_{n \in \mathbb N} A_m\right)^c = \bigcap_{m \in [n]} A_m^c$, and
$\left(\bigcap_{n \in \mathbb N} A_m\right)^c = \bigcup_{m \in [n]} A_m^c$.

Hint: Use a similar proofing approach to De Morgan’s Laws I.

2.1.2. Establishing units upon which we can build random variables#

To begin to delineate how we can come to terms with this seeming inconsistency when we handle discrete outcomes (like coin flips) with continuous outcomes (like throwing a ball), we need to create a sort of homologous system on which we can ascribe probabilities, that works whether or not the units are discrete or continous. To do this, we’re going to define families of sets (they are sets that contain sets) with increasing complexity (each family of sets you see below is also described by the subsection that precedes it, but not necessarily the reverse).

2.1.3. $\pi$-systems#

The first, and simplest, family of sets that we’re going to see so far is called a $\pi$-system. A $\pi$-system is defined on a set $\Omega$, which can be anything (such as the real line).

Definition 2.11 ($\pi$-system)

Suppose that $\Omega$ is a set. $\mathcal P$ is called a $\pi$-system on $\Omega$ if it is a non-empty collection of subsets $P$ of $\Omega$, where if $P_1, P_2 \in \mathcal P$, then $P_1 \cap P_2 \in \mathcal P$.

In words, a $\pi$-system is a non-empty family of sets $\mathcal P$ that is closed under finitely many intersections. Here, a set being closed under an operation means that, if you were to consider this operation on elements of that set, the result would still be in the set. That it is closed under finitely many interesections means that if you had sets any collection of $n$-many sets ($n \in \mathbb N$ is finite) where $P_m \in \mathcal P$ for $m \in [n]$ (stated another way, $(P_m)_{m \in [n]} \subseteq \mathcal P$), that $\bigcap_{m \in [n]}P_m \in \mathcal P$, too.

Example 2.5 (Example of a simple $\pi$-system)

Let $\Omega = \{1, 2, 3\}$. Show that a $\pi$-system on $\Omega$ is $\mathcal P = \{\varnothing, \{1\}, \{1, 2\}, \{1, 3\}\}$ is a $\pi$-system.

One note that is going to be important later on is that a $\pi$-system on $\Omega$ does not, necessarily, contain the entire set $\Omega$ itself.

As we build up, $\pi$-systems are going to be extremely useful because, as you can see above, the statement for a $\pi$-system is pretty easy to wrap your head around: closed under finitely many intersections. When we prove things later on about much, much more complicated families of sets, there will be some extremely nice results about $\pi$-systems that will come in handy. In effect, what we are going to do later on is we are going to make statements that hold on $\pi$-systems, and then use extremely basic extensions about the particularities that differentiate $\pi$-systems from these more complicated families of sets to make much more general statements taht are true about the complicated family of sets. So, for now, you can put $\pi$-systems in the back of your head, but they will come up pretty soon.

Example 2.6 ($\pi$-systems are closed under finitely many intersections)

Show that if $\mathcal P$ is a $\pi$-system on a set $\Omega$, that if $(P_m)_{m \in [n]} \subseteq \mathcal P$, that $\bigcap_{m \in [n]}P_m \in \mathcal P$, too.

2.1.4. Algebras#

The next simplest family of sets are called algebras. An algebra can be thought of as an extension of a $\pi$-system, in that it is also defined on a set $\Omega$, and it includes closure under finitely many intersections like a $\pi$-system, but it adds a few interesting properties:

Definition 2.12 (Algebra)

Suppose that $\Omega$ is a set. $\mathcal A$ is called an algebra on $\Omega$ if it is a non-empty collection of subsets $A \in \mathcal F$, s.t. $A \subseteq \Omega$, where:

Contains the entire set: $\Omega \in \mathcal A$,
Closure under complement: If $A \in \mathcal A$, then $A^c \in \mathcal A$, and
Closure under finitely many unions: If $A_1, A_2 \in \mathcal A$, then $A_1 \cup A_2 \in \mathcal A$.

It isn’t too tough to determine that an algebra is a $\pi$-system, simply by using De’Morgan’s laws. We’ll use this to get your brain in shape for set theory types of proofs, which will grow in difficulty as we go:

Theorem 2.1 (Every algebra is a $\pi$-system)

Suppose the set $\Omega$, where $\mathcal A$ is an algebra on $\Omega$. $\mathcal A$ is also a $\pi$-system on $\Omega$.

Proof. Suppose that $A_1, A_2 \in \mathcal A$.

For $\mathcal A$ to be a $\pi$-system, we need to show that $A_1 \cap A_2 \in \mathcal A$.

Notice that since $\mathcal A$ is closed under complements, that $A_1^c, A_2^c \in \mathcal A$ as well.

Since $\mathcal A$ is closed under finitely many unions, then $A_1^c \cup A_2^c \in \mathcal A$.

Finally, since $\mathcal A$ is closed under complements, then $(A_1^c \cup A_2^c)^c \in \mathcal A$.

By De Morgan’s Law, $(A_1^c \cup A_2^c)^c = A_1 \cap A_2$, so $A_1 \cap A_2 = (A_1^c \cup A_2^c)^c \in \mathcal A$, as desired.

So there’s our first set theory proof. Not bad, right?

In the language we described $\pi$-systems, algebras can be understood similarly: they add that the entire set itself $\Omega$ must be contained, and they also add closure under complement and finitely many unions.

2.1.5. $\sigma$-algebras#

The first ingredient for us to build this homologous system that we’ve been working towards is called a $\sigma$-algebra. A $\sigma$-algebra is defined on a set $\Omega$, which can be anything (such as the real line). $\sigma$-algebras are going to take the property of closure under finitely many unions from algebras, and take it a step further:

Definition 2.13 ($\sigma$-algebra)

Suppose that $\Omega$ is a set. $\mathcal F$ is called a $\sigma$-algebra on $\Omega$ if it is a non-empty collection of events $F \in \mathcal F$, s.t. $F \subseteq \Omega$, where:

Contain event space: $\Omega \in \mathcal F$,
Closure under complement: If $F \in \mathcal F$, then $F^c \in \mathcal F$,
Closure under countable unions: If $\{F_n\}_{n \in \mathbb N} \subseteq \mathcal F$ is a countable sequence of events, then $\bigcup_{n \in \mathbb N}F_n \in \mathcal F$.

You’ll notice that we called these “subsets” of $\mathcal F$ “events” instead of just subsets (the language we used for $\pi$-systems and algebras): the reason for this will become a little more apparent in a section or two, so just bear with us for a few pages. We’ll often call the entire set $\Omega$ the “event space”, because it is the set in which our “events” $F$ live ($F \subseteq \Omega$). $\mathcal F$ collects these events in a very particular way. It contains the entire “event space” $\Omega$, it is closed under complements, and if a countable set of events are in $\mathcal F$, then the union of these events are also in $\mathcal F$ (closure under countable unions). Using similar insight to the insight you used for algebras in Theorem 2.1, you can also conclude that $\sigma$-algebras are closed under countable intersections, as well, which is a property we’ll use a bit more later on:

Property 2.1 ($\sigma$-algebras are closed under countable intersections)

Suppose that $\Omega$ is a set, and $\mathcal F$ is a $\sigma$-algebra on $\Omega$. Show that if $\{F_i\}_{i \in \mathbb N} \subseteq \mathcal F$ is a countable sequence of events, $\bigcap_{n \in \mathbb N} F_n \in \mathcal F$.

2.1.5.1. Properties of $\sigma$-algebras#

The idea of a $\sigma$-algebra is very simple to conceptualize; a set which contains sets which obey these $3$ rules we described above. However, as we will see here, these $3$ laws imply that $\sigma$-algebras also follow many other critical properties. Together, the properties about $\sigma$-algebras (and tools that we can define on them, such as measures, which we will learn about later), will allow us to define many higher-order operations like integration.

If we have a pair of $\sigma$-algebras (each of which is a collection of subsets of the event space), and we take the subsets of the event space that are in their intersection, what is the result? It turns out that the result is also a $\sigma$-algebra:

Property 2.2 (intersection of $\sigma$-algebras are $\sigma$-algebras)

Let $\{\mathcal F_i\}_{i \in \mathcal I}$ be a collection of $\sigma$-algebras on $\Omega$, where $\mathcal I \neq \varnothing$ is an arbitrary indexing set (which may be countable or uncountable). Then $\bigcap_{i \in \mathcal I} \mathcal F_i$ is a $\sigma$-algebra.

Notice that the indexing set here is, unlike some of the statements we’ve seen so far, potentially uncountable. This means that the family of $\sigma$-algebras are closed under intersections, without any qualifications needed about the number of intersections we might take being finite nor countable. That it is closed under arbitrarily many intersections will be critical for several useful properties about $\sigma$-algebras that you will use later on.

When proving things about $\sigma$-algebras, you always need to show exactly the properties in the definition. This means that every proof where we seek to show something is a $\sigma$-algebra is going to have $3$ parts, one for each delineation in the definition:

Proof. Denote $\mathcal F = \bigcap_{i \in \mathcal I} \mathcal F_i$. To see that it is a $\sigma$-algebra, note:

1. Contains $\Omega$: Note that by definition, since $\mathcal F_i$ are $\sigma$-algebras, then $\Omega \in \mathcal F_i$, for all $i \in \mathcal I$.

Then since $\Omega \in \mathcal F_i$ for all $i \in \mathcal I$, $\Omega \in \mathcal F$.

2. Closed under complement: Let $A_j \in \mathcal F$.

Then by definition of the intersection, $A_j \in \mathcal F_i$, for all $i \in \mathcal I$.

Then since each $\mathcal F_i$ are $\sigma$-algebras, then $A_j^c \in \mathcal F_i$, since $\mathcal F_i$ are closed under intersection.

Then since $A_j^c \in \mathcal F_i$ for all $i \in \mathcal I$, $A_j^c \in \mathcal F$, by definition of the intersection.

3. Closed under countable unions: Let $\{A_n\}_{n \in \mathbb N} \subseteq \mathcal F$ be a countable set of elements of $\mathcal F$.

Then by definition of the intersection, $\{A_n\}_{n \in \mathbb N} \subseteq \mathcal F_i$, for all $i \in \mathcal I$, by definition of the intersection operation.

Then since $\mathcal F_i$ is a $\sigma$-algebra and hence closed under countable unions, $\bigcup_{n \in \mathbb N}A_n \in \mathcal F_i$ for all $i \in \mathcal I$.

Then $\bigcup_{n \in \mathbb N}A_n \in \mathcal F$, by definition of the intersection.

If we have an event space $\Omega$, and a collection of sets that we are interested in $\mathcal A$, can we make a $\sigma$-algebra from the collection of sets we are interested in? The answer is yes, and it is called the $\sigma$-generated algebra:

Definition 2.14 ($\sigma$-generated algebra)

Let $\Omega$ be an event space, and let $\mathcal A$ be a collection of sets, where $A \in \mathcal A \Rightarrow A \subseteq \Omega$. Then the smallest $\sigma$-algebra containing $\mathcal A$ is denoted $\sigma(\mathcal A)$, and is defined:

\[\begin{split} \sigma(\mathcal A) = \bigcap_{\mathcal F_i \in \left\{\mathcal F_i : \substack{\mathcal F_i \textrm{ is a $\sigma$-algebra } \\ \textrm{on $\Omega$ and $\mathcal A \subseteq \mathcal F_i$}}\right\}}\mathcal F_i\end{split}\]

Notice that by Property 2.2, that $\sigma(\mathcal A)$ is also a $\sigma$-algebra.

We’ll often want to consider $\sigma$-algebras generated by a particular type of sets, called partitions:

Definition 2.15 (Partition)

Suppose the event space $\Omega$. A family of sets $\mathcal A$ is called a partition if:

It does not contain the empty set: $\varnothing \not\in \mathcal A$,
The sets are disjoint: If $\Omega_i, \Omega_j \in \mathcal A$, then $\Omega_i \cap \Omega_j = \varnothing$, and
The sets in $\mathcal A$ exhaust $\Omega$: $\bigsqcup_{\Omega_n \in \mathcal A}\Omega_i = \Omega$.

Can we describe the $\sigma$-algebra generated by these partitions easily? It turns out, we can:

Lemma 2.1 ($\sigma$-algebra generated by a partition)

Let $\Omega$ be an event space with $\sigma$-algebra $\mathcal F$, where $\{\Omega_i\}_{i \in \mathcal I} \subseteq \mathcal F$ is a partition of $\Omega$. Then:

\[ \sigma\left(\Omega_i : i \in \mathcal I\right) \equiv \mathcal G \triangleq \left\{\bigsqcup_{j \in \mathcal J : \mathcal J \subseteq \mathcal I}\Omega_j\right\}\]

Proof. To start, we need to show that $\mathcal G$ is a $\sigma$-algebra. We can do this in $3$ steps: 1. Contains the event space: Let $\mathcal J = \mathcal I$, so $\bigsqcup_{\Omega_n \in \mathcal A}\Omega_i \in \mathcal G$.

But since $\{\Omega_i\}_{i \in \mathcal I}$ is a partition of $\omega$, $\bigsqcup_{\Omega_n \in \mathcal A}\Omega_i = \Omega \in \mathcal G$.

2. Closed under complements: Suppose that $A \in \mathcal G$.

Then by construction, there exists $\mathcal J \subseteq \mathcal I$ s.t. $A = \bigsqcup_{j \in \mathcal J}\Omega_j$.

Take $\mathcal T = \mathcal I \setminus \mathcal J$. By construction, $\mathcal T \subseteq \mathcal I$, and further, $\mathcal T \cap \mathcal J = \varnothing$.

Define $B = \bigcap_{j \in \mathcal T}\Omega_j$. Since $\mathcal T \subseteq \mathcal I$, then $B \in \mathcal G$.

Notice that $A \cap B = \varnothing$, and $A \cup B = \Omega$, so $B = \Omega \setminus A$, and $B \equiv A^c$.

Then $A^c \in \mathcal G$.

3. Closed under countable unions: Suppose that $A_n \in \mathcal G$, for $n \in \mathbb N$.

Then there exists $\mathcal J_n$, s.t. $A_n = \bigcup_{j \in \mathcal J_n}\Omega_j$, by construction.

Further, note that $\mathcal J' = \bigcup_{n \in \mathbb N}\mathcal J_n \subseteq \mathcal I$.

Then $A = \bigcup_{n \in \mathcal J'}A_n$ has an indexing set $\mathcal J' \subseteq \mathcal I$, so $A \in \mathcal I$.

To see that $\sigma(\Omega_i : i \in \mathcal I)$ is equivalent to $\mathcal G$, we can do this in parts:

1. $\mathcal G \supseteq \sigma(\Omega_i : i \in \mathcal I)$: Note that $\mathcal G$ is a $\sigma$-algebra containing each $\Omega_i$, for all $i \in \mathcal I$, by taking $\mathcal J_i = \{i\}$.

Then $\sigma(\Omega_i : i \in \mathcal I) \subseteq \mathcal G$, since $\sigma(\Omega_i : i \in \mathcal I)$ is the intersection of $\sigma$-algebras containing $\Omega_i$s by definition Definition 2.14, and $\mathcal G$ is one such $\sigma$-algebra.

2. $\mathcal G \subseteq \sigma(\Omega_i : i \in \mathcal I)$: Suppose that $A \in \mathcal G$.

Then by construction, there exists $\mathcal J \subseteq \mathcal I$ s.t. $A = \bigcup_{j \in \mathcal J}\Omega_j$.

Then since $\sigma(\Omega_i : i \in \mathcal I)$ is the intersection of all $\sigma$-algebras containing $\{\Omega_i : i \in \mathcal I\}$, $\sigma(\Omega_i : i \in \mathcal I)$ must contain all of the countable unions of elements of $\{\Omega_i : i \in \mathcal I\}$, of which $A$ is one.

Then $A \in \sigma(\Omega_i : i \in \mathcal I)$.

Another interesting property is that $\sigma$-generated algebras preserve the subset operation. While this might seem rather intuitive, it isn’t immediately obvious, but this lemma will be extremely helpful later on:

Lemma 2.2 (Generated algebras preserve subsets)

Let $\Omega$ be an event space, and let $\mathcal C, \mathcal F$ be families of sets on $\Omega$ (for every $C \in \mathcal C$ and $F \in \mathcal F$, $C, F \subseteq \Omega$). If $\mathcal C \subseteq \mathcal F$, then $\sigma(\mathcal C) \subseteq \sigma(\mathcal F)$.

Proof. By definition, $\sigma(\mathcal F)$ is the $\sigma$-algebra at the intersection of all $\sigma$-algebras containing $\mathcal F$.

Since $\mathcal C \subseteq \mathcal F$, then $\mathcal C \subseteq \sigma(\mathcal F)$, since $\sigma(\mathcal F)$ is the intersection of all $\sigma$-algebras containing $\mathcal F$ (and consequently, also contain $\mathcal C$) by definition of $\sigma(\mathcal F)$ Definition 2.14.

Then since $\sigma(\mathcal C)$ is the intersection of every $\sigma$-algebra containing $\mathcal C$, it is the intersection of $\sigma(\mathcal F)$ (since $\mathcal C \in \sigma(\mathcal F)$) with other $\sigma$-algebras that contain $\mathcal C$ but might not contain $\mathcal F$.

Since the intersection operation of a set $\sigma(\mathcal F)$ with other sets will necessarily be at most $\sigma(\mathcal C)$, then $\sigma(\mathcal C) \subseteq \sigma(\mathcal F)$.

2.1.5.2. Borel $\sigma$-algebras#

Next, we have one of the most important results about $\sigma$-algebras that we will use repeatedly throughout this book when looking at probabilities: the Borel $\sigma$-algebra. The Borel $\sigma$-algebra will allow us to break up intervals of the (or the entire) real line into palatable open intervals. When we begin to define probability measures, we will generally define them using Borel $\sigma$-algebras.

Definition 2.16 (Borel $\sigma$-algebra)

Suppose that $\Omega$ is a set. The borel $\sigma$-algebra is defined as:

\[\mathcal B(\Omega) \triangleq \sigma\left(\left\{A \in \Omega : A \text{ is open}\right\}\right)\]

So, the Borel $\sigma$-algebra is the $\sigma$-algebra generated by the family of sets containing all open sets in $\Omega$.

There are a variety of special Borel $\sigma$-algebras that we will deal with in this book, for which we’ll use special notation to simplify things. They are:

Remark 2.1 (Special Borel $\sigma$-algebras)

If $\Omega = \mathbb R$, then $\mathcal R \triangleq \mathcal B(\mathbb R)$,
If $\Omega = \mathbb R^d$, then $\mathcal R^d \triangleq \mathcal B(\mathbb R^d)$,
If $\Omega = [\alpha, \beta]$, is a closed interval s.g. $\Omega \subseteq \mathbb R$, then $\mathcal R[\alpha, \beta] \triangleq \mathcal B([\alpha, \beta])$,
If $\Omega = (\alpha, \beta)$, is a closed interval s.g. $\Omega \subseteq \mathbb R$, then $\mathcal R[\alpha, \beta] \triangleq \mathcal B((\alpha, \beta))$

Next, we’ll introduce some sets which generate $\mathcal R$. These will be fundamental for many proofs you’ll find later on:

Example 2.7 (Generators of $\mathcal R$)

Show that the families of sets $\mathcal P_{\mathbb R} = \{(-\infty, x] : x \in \mathbb R\}$ and $\mathcal P_{\mathbb Q} = \{(-\infty, x) : x \in \mathbb Q\}$ are generators of $\mathcal R$.

Hint: Begin by showing that $\mathcal P_{\mathbb R}$ and $\mathcal P_{\mathbb Q}$ are $\pi$-systems on $\mathbb R$.

Then, show that $\mathcal B(\mathbb R) \subseteq \sigma(\pi(\mathcal P))$ (using that any open subset $G \subseteq \mathbb R$ is in $\sigma(\pi(\mathbb R))$, and $\sigma(\mathcal P) \subseteq \mathcal B(\mathbb R))$ (using that any subset of $\mathcal P$ can be expressed using the closure properties of $\sigma$-algebras on open subsets of $\mathbb R$).

2.1.6. Set-Theoretic Limits and extrema#

Just like we have extrama of sequences, we can conceptualize extrama of sets, too.

Definition 2.17 (Supremum of sets)

Suppose that $\Omega$ is an event space, and $F_n \subseteq \Omega$ for $n \in \mathbb N$ is a sequence of sets. Then:

\[ \sup_{n \in \mathbb N} F_n \triangleq \bigcup_{n \in \mathbb N}F_n.\]

The idea here is that the supremum of a sequence of sets is just the union of the whole sequence of sets. To draw an analogy to the definition of a supremum of a sequence, you can understand this as the supremum of a sequence of sets is the smallest possible set (in terms of the number of elements in it) which contains all of the elements of the entire sequence. Intuitively, this idea is just the union. Likewise, we can conceptualize the infimum:

Definition 2.18 (Infimum of sets)

Suppose that $\Omega$ is an event space, and $F_n \subseteq \Omega$ for $n \in \mathbb N$ is a sequence of sets. Then:

\[ \inf_{n \in \mathbb N}F_n \triangleq \bigcap_{n \in \mathbb N} F_n.\]

Likewise, here the idea is that the infinmum of a sequence of sets is just the intersection of the whole sequence of sets. Extending our analogy, the infimum of a sequence of sets is the largest possible set which contains elements common to the entire sequence of sets. This idea is captured by an intersection. Try to see what happens when, further, the sequence of sets is captured by a $\sigma$-algebra:

Example 2.8 ($\sigma$-algebras are closed under extrema)

Suppose that $\Omega$ is an event space with $\sigma$-algebra $\mathcal F$, and $(F_n)_{n \in \mathbb N} \subseteq \mathcal F$ is a sequence of sets in the $\sigma$-algebra. Show that $\sup_{n \in \mathbb N}F_n$ and $\inf_{n \in \mathbb N} F_n$ are also in the $\sigma$-algebra.

Hint: these proofs should be short and sweet, and borrow from the definition of $\sigma$-algebras and De Morgan’s Law III.

Likewise, we can conceptualize set-theoretic versions of the limits you have come to appreciate in real analysis:

Definition 2.19 (Set-theoretic limits of sets)

Suppose that $\Omega$ is an event space, and $F_n \subseteq \Omega$ for $n \in \mathbb N$ is a sequence of sets. Then:

\[ \liminf_{n \rightarrow \infty} F_n \triangleq \inf_{n \in \mathbb N}\sup_{m \geq n} F_n \equiv \bigcup_{n \in \mathbb N}\bigcap_{m \geq n}F_n, \limsup_{n \rightarrow \infty} F_n \triangleq \inf_{n \in \mathbb N}\sup_{m \geq n} F_n \equiv \bigcap_{n \in \mathbb N}\bigcup_{m \geq n}F_n,\]

and further, if $\limsup_{n \in \mathbb N} F_n = \liminf_{n \in \mathbb N} F_n$, and we say that:

\[ \lim_{n \rightarrow \infty}F_n = \liminf_{n \rightarrow \infty}F_n = \limsup_{n \rightarrow \infty}F_n\]

$\sigma$-algebras are also closed under set-theoretic limits, too:

Example 2.9 ($\sigma$-algebra is closed under set-theoretic limits)

Suppose that $\Omega$ is an event space with $\sigma$-algebra $\mathcal F$, and $\{F_n\}_{n \in \mathbb N} \subseteq \mathcal F$ is a sequence of sets in the $\sigma$-algebra. Show that $\limsup_{n \rightarrow \infty}F_n$ and $\liminf_{n \rightarrow \infty} F_n$ are also in the $\sigma$-algebra.

Hint: use your result from Example 2.8 and borrow from the definition of $\sigma$-algebras.

We can further clarify some special situations where the set-theoretic limit, $\lim$, of a sequence of sets exists, using monotone sequences of sets:

Definition 2.20 (Monotone sequence of sets)

Suppose that $\Omega$ is an event space, and $F_n \subseteq \Omega$ for $n \in \mathbb N$ is a sequence of sets. Then:

$\{F_n\}$ is called monotone non-increasing if for every $n \in \mathbb N$, $F_{n + 1} \subseteq F_n$, and
$\{F_n\}$ is called monotone non-decreasing if for every $n \in \mathbb N$, $F_n \subseteq F_{n + 1}$.

The ideas here are that, like for sequences of numbers, monotonicity here refers to the composition of elements in the sets. Monotone non-increasing sets are those where every sequential set is contained in the preceding set, and monotone non-decreasing sets are those where every sequential set contains the preceding set.

If we have a sequence of sets which is monotone, the set-theoretic limits exist:

Lemma 2.3 (Monotone sequences of sets have limits)

Suppose that $\Omega$ is an event space, and $F_n \subseteq \Omega$ for $n \in \mathbb N$ is a monotone (non-increasing or non-decreasing) sequence of sets. Then:

\[ \lim_{n \rightarrow \infty}F_n = \liminf_{n \rightarrow \infty}F_n = \limsup_{n \rightarrow \infty}F_n.\]

Proof. We have two cases, the case where $\{F_n\}$ is monotone non-increasing or non-decreasing: 1. Monotone non-increasing: If $\{F_n\}$ is monotone non-increasing, then for any $n \in \mathbb N$:

\[\begin{split} \bigcap_{m \in \mathbb N}F_m &= \bigcap_{m \geq n}F_m,\\ F_n &= \bigcup_{m \geq n}F_m,\end{split}\]

by definition of $F_{n + 1} \subseteq F_{n}$. Then:

\[\begin{split} \liminf_{n \rightarrow \infty}F_n &= \sup_{n \in \mathbb N}\inf_{m \geq n}F_m \\ &= \bigcup_{n \in \mathbb N}\bigcap_{m \geq n}F_m \\ &= \bigcap_{n \in \mathbb N}\bigcap_{m \in \mathbb N}F_m,\,\,\,\, \bigcap_{m \in \mathbb N}F_m = \bigcap_{m \geq n}F_m \\ &= \bigcap_{n \in \mathbb N}F_n,\,\,\,\,\text{double $\cap$ is redundant} \\ &= \bigcap_{n \in \mathbb N}\bigcup_{m \geq n}F_m,\,\,\,\,F_n = \bigcup_{m \geq n}F_m \\ &= \inf_{n \in \mathbb N}\sup_{m \geq n}F_m \\ &= \limsup_{n \rightarrow \infty}F_n.\end{split}\]

2. Monotone non-decreasing:

Repeat the same argument, noting that if $\{F_n\}$ is monotone non-increasing, then $F_n \subseteq F_{n + 1}$, so for every $n \in \mathbb N$:

\[\begin{split} F_n &= \bigcap_{m \geq n}F_m,\\ \bigcup_{m \in \mathbb N}F_m &= \bigcup_{m \geq n}F_m.\end{split}\]

Then in both cases, $\liminf_{n \rightarrow \infty}F_n = \limsup_{n \rightarrow \infty}F_n$, and we can define $\lim_{n \rightarrow \infty}F_n$ to be this set.

Set Theory

Contents

2.1. Set Theory#

2.1.1. Set theory basics#

2.1.2. Establishing units upon which we can build random variables#

2.1.3. \(\pi\)-systems#

2.1.4. Algebras#

2.1.5. \(\sigma\)-algebras#

2.1.5.1. Properties of \(\sigma\)-algebras#

2.1.5.2. Borel \(\sigma\)-algebras#

2.1.6. Set-Theoretic Limits and extrema#