Set-theoretic limit

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, the limit of a sequence of sets A1, A2, ... (subsets of a common set X) is a set whose elements are determined by the sequence in either of two equivalent ways: (1) by upper and lower bounds on the sequence that converge monotonically to the same set (analogous to convergence of real-valued sequences) and (2) by convergence of a sequence of indicator functions which are themselves real-valued. As is the case with sequences of other objects, convergence is not necessary or even usual.

More generally, again analogous to real-valued sequences, the less restrictive limit infimum and limit supremum of a set sequence always exist and can be used to determine convergence: the limit exists if the limit infimum and limit supremum are identical. (See below). Such set limits are essential in measure theory and probability.

It is a common misconception that the limits infimum and supremum described here involve sets of accumulation points, that is, sets of x = limk→∞xk, where each xk is in some Ank. This is only true if convergence is determined by the discrete metric (that is, xnx iff there is N such that xn = x for all nN). This article is restricted to that situation as it is the only one relevant for measure theory and probability. See the examples below. (On the other hand, there are more general topological notions of set convergence that do involve accumulation points under different metrics or topologies.)

Definitions[edit]

The two definitions[edit]

The two equivalent definitions are as follows.

\liminf_{n \rightarrow \infty} A_n = \bigcup_{n \ge 1} \bigcap_{j \geq n} A_j
and
\limsup_{n \rightarrow \infty} A_n = \bigcap_{n \ge 1} \bigcup_{j \geq n} A_j.
If these two sets are equal, then the set-theoretic limit of the sequence An exists and is equal to that common set. Either set as described above can be used to get the limit, and there may be other means to get the limit as well.
\liminf_{n \rightarrow \infty} A_n = \{ x \in X: \liminf_{n \rightarrow \infty} \mathbf{1}_{A_n}(x) = 1 \}
and
\limsup_{n \rightarrow \infty} A_n = \{ x \in X: \limsup_{n \rightarrow \infty} \mathbf{1}_{A_n}(x) = 1 \},
where the expressions inside the brackets on the right are, respectively, the limit infimum and limit supremum of the real-valued sequence 1An(x). Again, if these two sets are equal, then the set-theoretic limit of the sequence An exists and is equal to that common set, and either set as described above can be used to get the limit.

To see the equivalence of the definitions, consider the limit infimum. The use of DeMorgan's rule below explains why this suffices for the limit supremum. Since indicator functions take only values 0 and 1, lim infn→∞ 1An(x) = 1 if and only if 1An(x) takes value 0 only finitely many times. Equivalently, \scriptstyle x\ \in\ \bigcup_{n 
\ge 1}\ \bigcap_{j \ge n} A_n for some n if and only if there exists n such that the element is in Am for every mn, which is to say if and only if xAn for only finitely many n.

Therefore, x is in the lim infn→∞ An iff x is in all except finitely many An. For this reason, a shorthand phrase for the limit infimum is "xAn all except finitely often" (or "xAn all but finitely often"), typically expressed by "An a.e.f.o." (or by "An a.b.f.o.").

Similarly, an element of X is in the limit supremum if, no matter how large n is there exists mn such that the element is in Am. That is, x is in the limit supremum iff x is in infinitely many An. For this reason, a shorthand phrase for the limit supremum is "xAn infinitely often", typically expressed by "An i.o.".

Monotone sequences[edit]

The sequence An is said to be nonincreasing if each An+1An and nondecreasing if each AnAn+1. In each of these cases the set limit exists. Consider, for example, a nonincreasing sequence An. Then

\bigcap_{j \geq n} A_j = \bigcap_{j \geq 1} A_j \text{ and } \bigcup_{j \geq n} A_j = A_n.

From these it follows that

\liminf_{n \rightarrow \infty} A_n = \bigcup_{n \geq 1} \bigcap_{j \geq n} A_j = \bigcap_{j \geq 1} A_j = \bigcap_{n \geq 1} \bigcup_{j \geq n} A_j = \limsup_{n \rightarrow \infty} A_n.

Similarly, if An is nondecreasing then

\lim_{n \rightarrow \infty} A_n = \bigcup_{j \geq 1} A_j.

Properties[edit]

  • If the limit of 1An(x), as n goes to infinity, exists for all x then
\lim_{n \rightarrow \infty} A_n = \{ x \in X: \lim_{i \rightarrow \infty} \mathbf{1}_{A_n}(x) = 1 \}.
Otherwise, the limit for {An} does not exist.
  • It can be shown that the limit infimum is contained in the limit supremum:
\liminf_{n\to\infty}A_n\subset\limsup_{n\to\infty}A_n,
for example, simply by observing that xAn all except finitely often implies xAn infinitely often.
\liminf_{n\to\infty}A_n = \lim_{n\to\infty}\bigcap_{j\ge n}A_j\text{ and }\limsup_{n\to\infty}A_n = \lim_{n\to\infty}\bigcup_{j\ge n}A_j.
\liminf_{n \rightarrow \infty} A_n = \bigcup_i \Bigl(\bigcup_{j \geq n} A_j^c\Bigr)^c
= \Bigl(\bigcap_n \bigcup_{j \geq n} A_j^c\Bigr)^c
= \Bigl(\limsup_{n \rightarrow \infty} A_n^c\Bigr)^c.
That is, xAn all except finitely often is the same as xAn finitely often.
  • From the second definition above and the definitions for limit infimum and limit supremum of a real-valued sequence,
\textbf{1}_{\liminf_{n \rightarrow \infty} A_n}(x) = \liminf_{n \rightarrow \infty}\textbf{1}_{A_j}(x) = \sup_{n \ge 1}\inf_{j \ge n}\textbf{1}_{A_j}(x)
and
\textbf{1}_{\limsup_{n \rightarrow \infty} A_n}(x) = \limsup_{n \rightarrow \infty}\textbf{1}_{A_j}(x) = \inf_{n \ge 1}\sup_{j \ge n}\textbf{1}_{A_j}(x).
  • Suppose \scriptstyle\mathcal{F} is a σ-algebra of subsets of X. That is, \scriptstyle\mathcal{F} is nonempty and is closed under complement and under unions and intersections of countably many sets. Then, by the first definition above, if each An\scriptstyle\mathcal{F} then both lim infn → ∞ An and lim supn → ∞ An are elements of \scriptstyle\mathcal{F}.

Examples[edit]

  • Let An = (−1/n, 1 − 1/n]. Then
\liminf_{n \rightarrow \infty} A_n = \bigcup_n \bigcap_{j\ge n}\Bigl(-\frac{1}{n}, 1-\frac{1}{n}\Bigr]
= \bigcup_n \Bigl[0, 1-\frac{1}{n}\Bigr] = [0, 1)
and
\limsup_{n \rightarrow \infty} A_n = \bigcap_n \bigcup_{j\ge n}\Bigl(-\frac{1}{n}, 1-\frac{1}{n}\Bigr]
= \bigcap_n \Bigl(-\frac{1}{n}, 1\Bigr) = [0, 1).
So limn→∞ An = (0, 1] exists.
  • Change the previous example to An = ((−1)n/n, 1 − (−1)n/n]. Then
\liminf_{n \rightarrow \infty} A_n = \bigcup_n \bigcap_{j\ge n} \Bigl(\frac{(-1)^n}{n}, 1-\frac{(-1)^n}{n}\Bigr]
= \bigcup_n \Bigl(\frac{1}{2n}, 1-\frac{1}{2n}\Bigr] = (0, 1)
and
\limsup_{n \rightarrow \infty} A_n = \bigcap_n \bigcup_{j\ge n} \Bigl(\frac{(-1)^n}{n}, 1-\frac{(-1)^n}{n}\Bigr]
= \bigcap_n \Bigl(-\frac{1}{2n-1}, 1+\frac{1}{2n-1}\Bigr] = [0, 1].
So limn→∞An does not exist, despite the fact that the left and right endpoints of the intervals converge to 0 and 1, respectively.
  • Let An = {0, 1/n, 2/n, ..., (n−1)/n, 1}. Then
\bigcup_{j \geq n} A_j = \mathbb{Q}\cap[0,1]
(which is all rational numbers between 0 and 1, inclusive) since even for j < n and 0 ≤ kj, k/j = (n×k)/(n×j) is an element of the above. Therefore,
\limsup_{n \rightarrow \infty} A_n = \mathbb{Q}\cap[0,1].
On the other hand,
\bigcap_{j \geq n} A_j = \{0,1\},
which implies
\liminf_{n \rightarrow \infty} A_n = \{0,1\}.
In this case, the sequence A1, A2, ... does not have a limit. Note that lim supn→∞ An is not the set of accumulation points, which would be the entire interval [0, 1] (according to the usual Euclidean metric).

Probability uses[edit]

Set limits, particularly the limit infimum and the limit supremum, are essential for probability and measure theory. Such limits are used to calculate (or prove) the probabilities and measures of other, more purposeful, sets. For the following, \scriptstyle(X,\mathcal{F},\mathbb{P}) is a probability space, which means \scriptstyle\mathcal{F} is a σ-algebra of subsets of \scriptstyle X and \scriptstyle\mathbb{P} is a probability measure defined on that σ-algebra. Sets in the σ-algebra are known as events.

If A1, A2, ... is a sequence of events in \scriptstyle\mathcal{F} and limn→∞ An exists then

\mathbb{P}(\lim_{n \rightarrow \infty} A_n) = \lim_{n \rightarrow \infty} \mathbb{P}(A_n).

Borel–Cantelli lemmas[edit]

In probability, the two Borel–Cantelli lemmas can be useful for showing that the limsup of a sequence of events has probability equal to 1 or to 0. The statement of the first (original) Borel–Cantelli lemma is

\text{if } \sum_{n=1}^{\infty} \mathbb{P}(A_n) < \infty \text{ then } \mathbb{P}(\limsup_{n \rightarrow \infty} A_n) = 0.

The second Borel–Cantelli lemma is a partial converse:

\text{if } A_1, A_2, \dots \text{ are independent events and } \sum_{n=1}^\infty \mathbb{P}(A_n) = \infty \text{ then } \mathbb{P}(\limsup_{n \rightarrow \infty} A_n) = 1.

Almost sure convergence[edit]

One of the most important applications to probability is for demonstrating the almost sure convergence of a sequence of random variables. The event that a sequence of random variables Y1, Y2, ... converges to another random variable Y is formally expressed as \scriptstyle\{\limsup_{n\to\infty}|Y_n - Y|=0\}. It would be a mistake, however, to write this simply as a limsup of events. Instead, the complement of the event is

\{\limsup_{n\to\infty}|Y_n - Y| \neq 0\} = \{\limsup_{n\to\infty}|Y_n - Y| > \frac{1}{k} \text{ for some } k\}
= \bigcup_{k\ge 1}\bigcap_{n\ge 1}\bigcup_{j \ge n} \{|Y_n - Y| > \frac{1}{k}\} = \lim_{k\to\infty}\limsup_{n\to\infty} \{|Y_n - Y| > \frac{1}{k}\}.

Therefore,

\mathbb{P}(\{\limsup_{n\to\infty}|Y_n - Y| \neq 0\}) = \lim_{k\to\infty} \mathbb{P}(\limsup_{n\to\infty} \{|Y_n - Y| > \frac{1}{k}\}).

References[edit]

  1. ^ a b Resnick, Sidney I. (1998). A Probability Path. Boston: Birkhäuser. ISBN 3-7643-4055-X.