# In Borel-Cantelli lemma, what is the limit superior?

In a proof of the Borel-Cantelli lemma in the stochastic process textbook, the author used the following.

$$\limsup_{n\to\infty}A_n=\bigcap_{n\ge1}\bigcup_{k\ge n} A_k$$

Can someone explain why lim sup is intersection and union? Thank you

• Think characteristic functions (indicator functions, if you're probability-minded). We have $\chi_{\limsup A_n} = \limsup \chi_{A_n}$, and analogously for $\liminf$ (and $\lim$ when that exists). – Daniel Fischer Jan 4 '16 at 21:14

I find it very helpful to think of the limit superior and limit inferior of a sequence of real numbers and a sequence of sets as special cases of limit superior and limit inferior in so called complete lattices:

You probably already know the following notions for the special case of the ordered set $(\mathbb{R},\leq)$:

Definition: Let $(S,\leq)$ be a partially ordered set and $A \subseteq S$ a subset. An element $s \in S$ is called an upper bound of $A$ if $a \leq s$ for all $a\ \in A$. An element $t \in S$ is called a lower bound of $A$ if $t \leq a$ for all $a \in A$.

An element $s \in S$ is called supremum of $A$ if $s$ is a least upper bound of $A$, i.e. $s$ is an upper bound of $A$ and for every upper bound $s'$ of $A$ we have $s \leq s'$.

Similarly an element $t \in S$ is called infimum of $A$ if $t$ is a least lower bound of $A$, i.e. $t$ is a lower bound of $A$ and for every lower bound $t'$ of $A$ we have $t' \leq t$.

If $(S, \leq)$ is a partially ordered set and $A \subseteq S$ a subset then neither a supremum of $A$, nor an infimum of $A$ need to exist. If it does, however, then it is unique, and is denoted by $\sup A$ and $\inf A$ respectively.

Notice that in the special case of $(\mathbb{R},\leq)$ the above definition coincides with the usual notion of the supremum and infimum of a set of real numbers. In the case of the extended real numbers $\mathbb{R}\cup \{-\infty,\infty\} = [-\infty,\infty]$ we have the nice property that each subset $S \subseteq [-\infty,\infty]$ has a supremum (possibly $\infty$) and an infimum (possibly $-\infty$). Such ordered sets are called complete lattices.

Definition: A ordered set $(S,\leq)$ is called a complete lattice if for each subset $A \subseteq S$ both $\sup A$ and $\inf A$ exist.

Aside from the extended real numbers $[-\infty,\infty]$ another complete lattice which we commonly encounter are power sets:

Example: Let $X$ be any set and denote by $\mathcal{P}(X) = \{T \mid T \subseteq X\}$ the power set of $X$. With the usual subset relation $\subseteq$ the power set becomes a partially ordered set $(\mathcal{P}(X),\subseteq)$. Let $\mathcal{A} \subseteq P(X)$ (i.e. $\mathcal{A}$ is a collection of subsets of $X$).

For any subset $S \in \mathcal{P}(X)$ we have that $S$ is an upper bound of $\mathcal{A}$ if and only if $T \subseteq S$ for all $T \in \mathcal{A}$. Therefore $S := \bigcup_{T \in \mathcal{A}} T$ is an upper bound of $\mathcal{A}$. If $S' \in \mathcal{P}(X)$ is any upper bound of $\mathcal{A}$, then we have $T \subseteq S'$ for all $T \in \mathcal{A}$, and thus also $S \subseteq S'$. So $S$ is a supremum of $\mathcal{A}$.

In the same way we also find that $\bigcap_{T \in \mathcal{A}} T$ is an infimum of $\mathcal{A}$. So $(\mathcal{P}(X), \subseteq)$ is a complete lattice, and for any collection of subsets $\mathcal{A} \subseteq \mathcal{P}(X)$ we have $\sup \mathcal{A} = \bigcup_{T \in \mathcal{A}} T$ and $\inf \mathcal{A} = \bigcap_{T \in \mathcal{A}} T$.

Notice that this result is not very suprising: The smallest set containing all sets of $\mathcal{A}$ in naturally the union of these sets. In the same way the biggest set which is contained in all sets of $\mathcal{A}$ is naturally the intersection of these sets.

Since in complete lattices we have suprema and infima we have all that we need to define the limit superior and limit inferior.

Definition: Let $(S,\leq)$ be a complete lattice and $(s_n)_{n \in \mathbb{N}}$ a sequence of elements $s_n \in S$. Then the limit superior and limit inferior of this sequence are $$\limsup_{n \to \infty} s_n = \inf_{n \geq 0} \sup_{k \geq n} s_k$$ and $$\liminf_{n \to \infty} s_n = \sup_{n \geq 0} \inf_{k \geq n} s_k.$$ If $\limsup_{n \to \infty} s_n = \liminf_{n \to \infty} s_n$ then we also write $$\lim_{n \to \infty} s_n = \limsup_{n \to \infty} s_n = \liminf_{n \to \infty} s_n$$ and call this the limit of the sequence $(s_n)_{n \in \mathbb{N}}$.

Notice that for the extended real line $[-\infty,\infty]$ this is the usual definition of limit superior and limit inferior. But what about power sets?

Example: Let $X$ be any set and $(A_n)_{n \in \mathbb{N}}$ a sequence of subsets $A_n \subseteq X$. Then $(A_n)_{n \in \mathbb{N}}$ is a sequence in the complete lattice $(\mathcal{P}(X), \subseteq)$. From the previous example we see that the limit superior of this sequence is given by $$\limsup_{n \to \infty} A_n = \inf_{n \geq 0} \sup_{k \geq n} A_k = \bigcap_{n \geq 0} \bigcup_{k \geq n} A_k,$$ and the limit inferior is given by $$\liminf_{n \to \infty} A_n = \sup_{n \geq 0} \inf_{k \geq n} A_k = \bigcup_{n \geq 0} \bigcap_{k \geq n} A_k.$$

So we see that the definiton of the limit superior and limit inferior of a sequence of sets really comes down to what the supremum and infimum of a collections of sets is, which naturally is their union and intersection respectively.

• What a great answer! Good job! – Ant Jan 5 '16 at 22:24

This is a generalization of limsup for sequence $(a_n)$. Given a sequence $(a_n)$, we know $\limsup a_n=\inf_{n\ge 1}\sup_{k\ge n}a_k$, and for a sequence of set $A_n$, we can view union as $\sup$ of sequence (larger than each one), and intersection as $\inf$ of sequence (smaller than each one).

Also, using this definition, we can check $\limsup_{n} 1_{A_n}=1_{\limsup_{A_n}}$, where $1_B$ means the characteristic function of set $B$.

• This lim sup is the set of all those and only those $x$ for which $\{n : x\in A_n\}$ is infinite. – DanielWainfleet Jan 4 '16 at 10:00
• @user254665 Yes. You are correct. – John Jan 4 '16 at 10:32