The Analysis of Data, volume 1

Set Theory: Limits of Sets

A.4. Limits of Sets

Definition A.4.1. For a sequence of sets $A_n$, $n\in\mathbb{N}$, we define \begin{align*} \inf_{k\geq n} A_k &= \bigcap_{k=n}^{\infty} A_k\\ \sup_{k\geq n} A_k &= \bigcup_{k=n}^{\infty} A_k\\ \liminf_{n\to\infty} A_n &= \bigcup_{n\in\mathbb{N}}\,\, \inf_{k\geq n} A_k = \bigcup_{n\in\mathbb{N}}\,\,\bigcap_{k=n}^{\infty} A_k \\ \limsup_{n\to\infty} A_n &= \bigcap_{n\in\mathbb{N}} \,\,\sup_{k\geq n} A_k = \bigcap_{n\in\mathbb{N}} \,\, \bigcup_{k=n}^{\infty} A_k. \end{align*}

Applying De-Morgan's law (Proposition A.1.1) we have \[\left(\liminf_{n\to\infty} A_n\right)^c = \limsup_{n\to\infty} A_n^c.\]

Definition A.4.2. If for a sequence of sets $A_n$, $n\in\mathbb{N}$, we have $\liminf_{n\to\infty} A_n=\limsup_{n\to\infty} A_n$, we define the limit of $A_n$, $n\in\mathbb{N}$ to be \[ \lim_{n\to\infty} A_n=\liminf_{n\to\infty} A_n=\limsup_{n\to\infty} A_n,\] The notation $A_n\to A$ is equivalent to the notation $\lim_{n\to\infty} A_n=A$.
Example A.4.1. For the sequence of sets $A_k=[0,k/(k+1))$ from Example A.1.6 we have \begin{align*} \inf_{k\geq n} A_k &= [0,n/(n+1))\\ \sup_{k\geq n} A_k &= [0,1) \\ \limsup_{n\to\infty} A_n &= [0,1)\\ \liminf_{n\to\infty} A_n &= [0,1)\\ \lim A_n&=[0,1).\end{align*}

We have the following interpretation for the $\liminf$ and $\limsup$ limits.

Proposition A.4.1. Let $A_n, n\in\mathbb{N}$ be a sequence of subsets of $\Omega$. Then \begin{align*} \limsup_{n\to\infty} A_n &= \left\{\omega\in\Omega\,:\,\sum_{n\in\mathbb{N}} I_{A_n}(\omega)=\infty\right\}\\ \liminf_{n\to\infty} A_n &= \left\{\omega\in\Omega\,:\,\sum_{n\in\mathbb{N}} I_{A_n^c}(\omega)<\infty\right\}. \end{align*} In other words, $\limsup_{n\to\infty} A_n$ is the set of $\omega\in\Omega$ that appear infinitely often (abbreviated i.o.) in the sequence $A_n$, and $\liminf_{n\to\infty} A_n$ is the set of $\omega\in\Omega$ that always appear in the sequence $A_n$ except for a finite number of times.
Proof. We prove the first part. The proof of the second part is similar. If $\omega\in \limsup_{n\to\infty} A_n$ then by definition for all $n$ there exists a $k_n$ such that $\omega\in A_{k_n}$. For that $\omega$ we have $\sum_{n\in\mathbb{N}} I_{A_n}(\omega)=\infty$. Conversely, if $\sum_{n\in\mathbb{N}} I_{A_n}(\omega)=\infty$, there exists a sequence $k_1,k_2,\ldots$ such that $\omega\in A_{k_n}$, implying that for all $n\in\mathbb{N}$, $\omega\in \cup_{i\geq n} A_i$.
Corollary A.4.1. \[\liminf_{n\to\infty} A_n \subset \limsup_{n\to\infty} A_n.\]
Definition A.4.3. A sequence of sets $A_n, n\in\mathbb{N}$ is monotonic non-decreasing if $A_1\subset A_2\subset A_3\subset \cdots$ and monotonic non-increasing if $\cdots \subset A_3 \subset A_2\subset A_1$. We denote this as $A_n\nearrow$ and $A_n\searrow$, respectively. If $\lim A_n=A$, we denote this as $A_n\nearrow A$ and $A_n\searrow A$, respectively.
Proposition A.4.2. If $A_n\nearrow$ then $\lim_{n\to\infty} A_n=\cup_{n\in\mathbb{N}} A_n$ and if $A_n\searrow$ then $\lim_{n\to\infty} A_n=\cap_{n\in\mathbb{N}} A_n$.
Proof. We prove the first statement. The proof of the second statement is similar. We need to show that if $A_n$ is monotonic non-decreasing, then $\limsup A_n=\liminf A_n=\cup_n A_n$. Since $A_i\subset A_{i+1}$, we have $\cap_{k\geq n} A_k=A_n$, and \begin{align*} \liminf_{n\to\infty} A_n &= \bigcup_{n\in\mathbb{N}} \bigcap_{k\geq n} A_k = \bigcup_{n\in\mathbb{N}} A_n\\ \limsup_{n\to\infty} A_n &= \bigcap_{n\in\mathbb{N}} \bigcup_{k\geq n} A_k \subset \bigcup_{k\in\mathbb{N}} A_k = \liminf_{n\to\infty} A_n \subset \limsup_{n\to\infty} A_n. \end{align*}

The following corollary of the above proposition motivates the notations $\liminf$ and $\limsup$.

Corollary A.4.2. Since $B_n=\cup_{k\geq n}A_k$ and $C_n=\cap_{k\geq n}A_k$ are monotonic sequences \begin{align*} \liminf_{n\to\infty} A_n &= \lim_{n\to\infty} \inf_{k\geq n} A_n\\ \limsup_{n\to\infty} A_n &= \lim_{n\to\infty} \sup_{k\geq n} A_n. \end{align*}