Set theoretic limit

The two definitions

Suppose that { A n } n = 1 ∞ is a sequence of sets. The two equivalent definitions are as follows.

Using union and intersection, define

and If these two sets are equal, then the set-theoretic limit of the sequence A_n 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.

Using indicator functions, let 1_An(x) equal 1 if x is in A_n and 0 otherwise. Define

and where the expressions inside the brackets on the right are, respectively, the limit infimum and limit supremum of the real-valued sequence 1_An(x). Again, if these two sets are equal, then the set-theoretic limit of the sequence A_n 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 inf_n→∞ 1_An(x) = 1 if and only if 1_An(x) takes value 0 only finitely many times. Equivalently, x   ∈   ⋃ n ≥ 1   ⋂ j ≥ n A n for some n if and only if there exists n such that the element is in A_m for every m ≥ n, which is to say if and only if x ∉ A_n for only finitely many n.

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

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

Monotone sequences

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

⋂ j ≥ n A j = ⋂ j ≥ 1 A j  and  ⋃ j ≥ n A j = A n .

From these it follows that

lim inf n → ∞ A n = ⋃ n ≥ 1 ⋂ j ≥ n A j = ⋂ j ≥ 1 A j = ⋂ n ≥ 1 ⋃ j ≥ n A j = lim sup n → ∞ A n .

Similarly, if {A_n} is nondecreasing then

lim n → ∞ A n = ⋃ j ≥ 1 A j .

Properties

If the limit of 1_An(x), as n goes to infinity, exists for all x then

Otherwise, the limit for {A_n} does not exist.

It can be shown that the limit infimum is contained in the limit supremum:

for example, simply by observing that x ∈ A_n all except finitely often implies x ∈ A_n infinitely often.

Using the monotonicity of B n = ⋂ j ≥ n A j and of C n = ⋃ j ≥ n A j ,

By using DeMorgan's rule twice, with set complement A^c = XA,

That is, x ∈ A_n all except finitely often is the same as x ∉ A_n finitely often.

From the second definition above and the definitions for limit infimum and limit supremum of a real-valued sequence,

and

Suppose F is a σ-algebra of subsets of X. That is, 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 A_n ∈ F then both lim inf_{n → ∞} A_n and lim sup_{n → ∞} A_n are elements of F .

Examples

Let A_n = (−1/n, 1 − 1/n]. Then

and So lim_n→∞ A_n = [0, 1) exists.

Change the previous example to A_n = ((−1)ⁿ/n, 1 − (−1)ⁿ/n]. Then

and So lim_n→∞A_n does not exist, despite the fact that the left and right endpoints of the intervals converge to 0 and 1, respectively.

Let A_n = {0, 1/n, 2/n, ..., (n−1)/n, 1}. Then

(which is all rational numbers between 0 and 1, inclusive) since even for j < n and 0 ≤ k ≤ j, k/j = (n×k)/(n×j) is an element of the above. Therefore, lim sup n → ∞ A n = Q ∩ [ 0 , 1 ] . On the other hand, which implies In this case, the sequence A₁, A₂, ... does not have a limit. Note that lim sup_n→∞ A_n is not the set of accumulation points, which would be the entire interval [0, 1] (according to the usual Euclidean metric).

Probability uses

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, ( X , F , P ) is a probability space, which means F is a σ-algebra of subsets of X and P is a probability measure defined on that σ-algebra. Sets in the σ-algebra are known as events.

If A₁, A₂, ... is a sequence of events in F and lim_n→∞ A_n exists then

P ( lim n → ∞ A n ) = lim n → ∞ P ( A n ) .

Borel–Cantelli lemmas

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

if  ∑ n = 1 ∞ P ( A n ) < ∞  then  P ( lim sup n → ∞ A n ) = 0.

The second Borel–Cantelli lemma is a partial converse:

if  A 1 , A 2 , …  are independent events and  ∑ n = 1 ∞ P ( A n ) = ∞  then  P ( lim sup n → ∞ A n ) = 1.

Almost sure convergence

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 Y₁, Y₂, ... converges to another random variable Y is formally expressed as { lim sup n → ∞ | Y n − Y | = 0 } . It would be a mistake, however, to write this simply as a limsup of events. That is, this is not the event lim sup n → ∞ { | Y n − Y | = 0 } ! Instead, the complement of the event is

{ lim sup n → ∞ | Y n − Y | ≠ 0 } = { lim sup n → ∞ | Y n − Y | > 1 k  for some  k } = ⋃ k ≥ 1 ⋂ n ≥ 1 ⋃ j ≥ n { | Y n − Y | > 1 k } = lim k → ∞ lim sup n → ∞ { | Y n − Y | > 1 k } .

Therefore,

P ( { lim sup n → ∞ | Y n − Y | ≠ 0 } ) = lim k → ∞ P ( lim sup n → ∞ { | Y n − Y | > 1 k } ) .