In mathematics, the limit of a sequence of sets (subsets of a common set ) 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 where each is in some This is only true if convergence is determined by the discrete metric (that is, if there is such that for all ). 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

Suppose that   is a sequence of sets. The two equivalent definitions are as follows.

  • Using union and intersection: define[1][2]   and   If these two sets are equal, then the set-theoretic limit of the sequence   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   equal   if   and   otherwise. Define[1]   and   where the expressions inside the brackets on the right are, respectively, the limit infimum and limit supremum of the real-valued sequence   Again, if these two sets are equal, then the set-theoretic limit of the sequence   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 De Morgan's law below explains why this suffices for the limit supremum. Since indicator functions take only values   and     if and only if   takes value   only finitely many times. Equivalently,   if and only if there exists   such that the element is in   for every   which is to say if and only if   for only finitely many   Therefore,   is in the   if and only if   is in all but finitely many   For this reason, a shorthand phrase for the limit infimum is "  is in   all but finitely often", typically expressed by writing "  a.b.f.o.".

Similarly, an element   is in the limit supremum if, no matter how large   is, there exists   such that the element is in   That is,   is in the limit supremum if and only if   is in infinitely many   For this reason, a shorthand phrase for the limit supremum is "  is in   infinitely often", typically expressed by writing "  i.o.".

To put it another way, the limit infimum consists of elements that "eventually stay forever" (are in each set after some  ), while the limit supremum consists of elements that "never leave forever" (are in some set after each  ). Or more formally:

      for every         there is a   with   for all   and
for every   there is a   with   for all  .

Monotone sequences

edit

The sequence   is said to be nonincreasing if   for each   and nondecreasing if   for each   In each of these cases the set limit exists. Consider, for example, a nonincreasing sequence   Then   From these it follows that   Similarly, if   is nondecreasing then  

The Cantor set is defined this way.

Properties

edit
  • If the limit of   as   goes to infinity, exists for all   then   Otherwise, the limit for   does not exist.
  • It can be shown that the limit infimum is contained in the limit supremum:   for example, simply by observing that   all but finitely often implies   infinitely often.
  • Using the monotonicity of   and of    
  • By using De Morgan's law twice, with set complement     That is,   all but finitely often is the same as   finitely often.
  • From the second definition above and the definitions for limit infimum and limit supremum of a real-valued sequence,   and  
  • Suppose   is a 𝜎-algebra of subsets of   That is,   is nonempty and is closed under complement and under unions and intersections of countably many sets. Then, by the first definition above, if each   then both   and   are elements of  

Examples

edit
  • Let   Then

  and   so   exists.

  • Change the previous example to   Then

  and   so   does not exist, despite the fact that the left and right endpoints of the intervals converge to 0 and 1, respectively.

  • Let   Then

  is the set of all rational numbers between 0 and 1 (inclusive), since even for   and     is an element of the above. Therefore,   On the other hand,   which implies   In this case, the sequence   does not have a limit. Note that   is not the set of accumulation points, which would be the entire interval   (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,   is a probability space, which means   is a σ-algebra of subsets of   and   is a probability measure defined on that σ-algebra. Sets in the σ-algebra are known as events.

If   is a monotone sequence of events in   then   exists and  

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

First Borel–Cantelli lemma — If   then  

The second Borel–Cantelli lemma is a partial converse:

Second Borel–Cantelli lemma — If   are independent events and   then  

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   converges to another random variable   is formally expressed as   It would be a mistake, however, to write this simply as a limsup of events. That is, this is not the event  ! Instead, the complement of the event is   Therefore,  

See also

edit

References

edit
  1. ^ a b Resnick, Sidney I. (1998). A Probability Path. Boston: Birkhäuser. ISBN 3-7643-4055-X.
  2. ^ Gut, Allan (2013). Probability: A Graduate Course: A Graduate Course. Springer Texts in Statistics. Vol. 75. New York, NY: Springer New York. doi:10.1007/978-1-4614-4708-5. ISBN 978-1-4614-4707-8.