5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ – Daniel Fischer Jan 4 '16 at 21:14
12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What a great answer! Good job! $\endgroup$ – Ant Jan 5 '16 at 22:24
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.