Editing Set-theoretic limit

{{Short description|In mathematics, notion of limit for sequences of sets}}
{{Referenced|date=April 2015}}
In [[mathematics]], the '''limit''' of a [[sequence]] of [[Set (mathematics)|sets]] <math>A_1, A_2, \ldots</math> ([[subset]]s of a common set <math>X</math>) 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 [[Limit of a sequence|convergence of real-valued sequences]]) and '''(2)''' by convergence of a sequence of [[indicator function]]s which are themselves [[Real number|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 (mathematics)|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 <math>x = \lim_{k \to \infty} x_k,</math> where each <math>x_k</math> is in some <math>A_{n_k}.</math> This is only true if convergence is determined by the [[discrete metric]] (that is, <math>x_n \to x</math> if there is <math>N</math> such that <math>x_n = x</math> for all <math>n \geq N</math>). 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 [[Limit superior and limit inferior#General set convergence|topological notions of set convergence]] that do involve accumulation points under different [[Metric (mathematics)|metrics]] or [[Topological space|topologies]].)

==Definitions==

===The two definitions===
Suppose that <math>\left(A_n\right)_{n=1}^\infty</math> is a sequence of sets. The two equivalent definitions are as follows.

* Using [[Union (set theory)|union]] and [[Intersection (set theory)|intersection]]: define<ref name="probpath">{{cite book| last1=Resnick|first1=Sidney I.|title=A Probability Path|date=1998|publisher=Birkhäuser|location=Boston|isbn=3-7643-4055-X}}</ref><ref>{{Cite book |last=Gut |first=Allan |url=https://link.springer.com/10.1007/978-1-4614-4708-5 |title=Probability: A Graduate Course: A Graduate Course |date=2013 |publisher=Springer New York |isbn=978-1-4614-4707-8 |series=Springer Texts in Statistics |volume=75 |location=New York, NY |language=en |doi=10.1007/978-1-4614-4708-5}}</ref> <math display="block">\liminf_{n \to \infty} A_n = \bigcup_{n \geq 1} \bigcap_{j \geq n} A_j</math> and <math display="block">\limsup_{n \to \infty} A_n = \bigcap_{n \geq 1} \bigcup_{j \geq n} A_j</math> If these two sets are equal, then the set-theoretic limit of the sequence <math>A_n</math> 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 function]]s: let <math>\mathbb{1}_{A_n}(x)</math> equal <math>1</math> if <math>x \in A_n,</math> and <math>0</math> otherwise. Define<ref name="probpath"/> <math display=block>\liminf_{n \to \infty} A_n = \Bigl\{ x \in X : \liminf_{n \to \infty} \mathbb{1}_{A_n}(x) = 1 \Bigr\}</math> and <math display=block>\limsup_{n \to \infty} A_n = \Bigl\{ x \in X : \limsup_{n \to \infty} \mathbb{1}_{A_n}(x) = 1 \Bigr\},</math> where the expressions inside the brackets on the right are, respectively, the [[limit infimum]] and [[limit supremum]] of the real-valued sequence <math>\mathbb{1}_{A_n}(x).</math> Again, if these two sets are equal, then the set-theoretic limit of the sequence <math>A_n</math> 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 <math>0</math> and <math>1,</math> <math>\liminf_{n \to \infty} \mathbb{1}_{A_n}(x) = 1</math> if and only if <math>\mathbb{1}_{A_n}(x)</math> takes value <math>0</math> only finitely many times. Equivalently, 
<math display=inline>x \in \bigcup_{n \geq 1} \bigcap_{j \geq n} A_j</math> 
if and only if there exists <math>n</math> such that the element is in <math>A_m</math> for every <math>m \geq n,</math> which is to say if and only if <math>x \not\in A_n</math> for only finitely many <math>n.</math> 
Therefore, <math>x</math> is in the <math>\liminf_{n \to \infty} A_n</math> if and only if <math>x</math> is in all but finitely many <math>A_n.</math> For this reason, a shorthand phrase for the limit infimum is "<math>x</math> is in <math>A_n</math> all but finitely often", typically expressed by writing "<math>A_n</math> a.b.f.o.".

Similarly, an element <math>x</math> is in the limit supremum if, no matter how large <math>n</math> is, there exists <math>m \geq n</math> such that the element is in <math>A_m.</math> That is, <math>x</math> is in the limit supremum if and only if <math>x</math> is in infinitely many <math>A_n.</math> For this reason, a shorthand phrase for the limit supremum is "<math>x</math> is in <math>A_n</math> infinitely often", typically expressed by writing "<math>A_n</math> i.o.".

To put it another way, the limit infimum consists of elements that "eventually stay forever" (are in {{em|each}} set after {{em|some}} <math>n</math>), while the limit supremum consists of elements that "never leave forever" (are in {{em|some}} set after {{em|each}} <math>n</math>). Or more formally:
:{|
|-
|<math Display="inline">\lim_{n\in\N}A_n = L \quad \Longleftrightarrow</math> &nbsp; &nbsp; || for every <math>x\in L</math> &nbsp; &nbsp; &thinsp; there is a <math>n_0\in\N</math> with <math>x\in A_n</math> for all <math>n\ge n_0</math> and
|-
| ||for every <math>y\in X\!\setminus\! L</math> there is a <math>p_0\in\N</math> with <math>y\not\in A_p</math> for all <math>p\ge p_0</math>.
|}

===Monotone sequences===
{{anchor}}
The sequence <math>\left(A_n\right)</math> is said to be '''nonincreasing''' if <math>A_{n+1} \subseteq A_n</math> for each <math>n,</math> and '''nondecreasing''' if <math>A_n \subseteq A_{n+1}</math> for each <math>n.</math> In each of these cases the set limit exists. Consider, for example, a nonincreasing sequence <math>\left(A_n\right).</math> Then 
<math display=block>\bigcap_{j \geq n} A_j = \bigcap_{j \geq 1} A_j \text{ and } \bigcup_{j \geq n} A_j = A_n.</math>
From these it follows that
<math display=block>\liminf_{n \to \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 \to \infty} A_n.</math>
Similarly, if <math>\left(A_n\right)</math> is nondecreasing then 
<math display=block>\lim_{n \to \infty} A_n = \bigcup_{j \geq 1} A_j.</math>

The [[Cantor set#Construction and formula of the ternary set|Cantor set]] is defined this way.

==Properties==
* If the limit of <math>\mathbb{1}_{A_n}(x),</math> as <math>n</math> goes to infinity, exists for all <math>x</math> then <math display=block>\lim_{n \to \infty} A_n = \left\{ x \in X : \lim_{n \to \infty} \mathbb{1}_{A_n}(x) = 1 \right\}.</math> Otherwise, the limit for <math>\left(A_n\right)</math> does not exist.
* It can be shown that the limit infimum is contained in the limit supremum: <math display=block>\liminf_{n\to\infty} A_n \subseteq \limsup_{n\to\infty} A_n,</math> for example, simply by observing that <math>x \in A_n</math> all but finitely often implies <math>x \in A_n</math> infinitely often.
* Using the [[Set-theoretic limit#Monotone Sequences|monotonicity]] of <math display=inline> B_n = \bigcap_{j \geq n} A_j</math> and of <math display=inline> C_n = \bigcup_{j \geq n} A_j,</math> <math display=block>\liminf_{n\to\infty} A_n = \lim_{n\to\infty}\bigcap_{j \geq n} A_j \quad \text{ and } \quad \limsup_{n\to\infty} A_n = \lim_{n\to\infty} \bigcup_{j \geq n} A_j.</math>
* By using [[De Morgan's law]] twice, with [[set complement]] <math>A^c := X \setminus A,</math> <math display=block>\liminf_{n \to \infty} A_n = \bigcup_n \left(\bigcup_{j \geq n} A_j^c\right)^c
= \left(\bigcap_n \bigcup_{j \geq n} A_j^c\right)^c
= \left(\limsup_{n \to \infty} A_n^c\right)^c.</math> That is, <math>x \in A_n</math> all but finitely often is the same as <math>x \not\in A_n</math> finitely often.
* From the second definition above and the definitions for limit infimum and limit supremum of a real-valued sequence, <math display="block">\mathbb{1}_{\liminf_{n \to \infty} A_n}(x) = \liminf_{n \to \infty}\mathbb{1}_{A_n}(x) = \sup_{n \geq 1} \inf_{j \geq n} \mathbb{1}_{A_j}(x)</math> and <math display="block">\mathbb{1}_{\limsup_{n \to \infty} A_n}(x) = \limsup_{n \to \infty} \mathbb{1}_{A_n}(x) = \inf_{n \geq 1} \sup_{j \geq n} \mathbb{1}_{A_j}(x).</math>
* Suppose <math>\mathcal{F}</math> is a [[Sigma algebra|{{sigma}}-algebra]] of subsets of <math>X.</math> That is, <math>\mathcal{F}</math> is [[Empty set|nonempty]] and is closed under complement and under unions and intersections of [[countably many]] sets. Then, by the first definition above, if each <math>A_n \in \mathcal{F}</math> then both <math>\liminf_{n \to \infty} A_n</math> and <math>\limsup_{n \to \infty} A_n</math> are elements of <math>\mathcal{F}.</math>

==Examples==
* Let <math>A_n = \left(- \tfrac{1}{n}, 1 - \tfrac{1}{n}\right].</math> Then
<math display=block>\liminf_{n \to \infty} A_n = \bigcup_n \bigcap_{j \geq n} \left(-\tfrac{1}{j}, 1 - \tfrac{1}{j} \right] = \bigcup_n \left[0, 1 - \tfrac{1}{n}\right] = [0, 1)</math>
and
<math display=block>\limsup_{n \to \infty} A_n = \bigcap_n \bigcup_{j \geq n}\left(-\tfrac{1}{j}, 1 - \tfrac{1}{j}\right] = \bigcap_n \left(- \tfrac{1}{n}, 1\right) = [0, 1)</math>
so <math>\lim_{n \to \infty} A_n = [0, 1)</math> exists.
* Change the previous example to <math>A_n = \left(\tfrac{(-1)^n}{n}, 1 - \tfrac{(-1)^n}{n}\right].</math> Then
<math display=block>\liminf_{n \to \infty} A_n = \bigcup_n \bigcap_{j \geq n} \left(\tfrac{(-1)^j}{j}, 1-\tfrac{(-1)^j}{j}\right] = \bigcup_n \left(\tfrac{1}{2n}, 1 - \tfrac{1}{2n}\right] = (0, 1)</math>
and
<math display=block>\limsup_{n \to \infty} A_n = \bigcap_n \bigcup_{j \geq n} \left(\tfrac{(-1)^j}{j}, 1 - \tfrac{(-1)^j}{j}\right] = \bigcap_n \left(-\tfrac{1}{2n-1}, 1 + \tfrac{1}{2n-1}\right] = [0, 1],</math>
so <math>\lim_{n \to \infty} A_n</math> does not exist, despite the fact that the left and right endpoints of the [[Interval (mathematics)|intervals]] converge to 0 and 1, respectively.
* Let <math>A_n = \left\{ 0, \tfrac{1}{n}, \tfrac{2}{n}, \ldots, \tfrac{n - 1}{n}, 1\right\}.</math> Then
<math display=block>\bigcup_{j \geq n} A_j = \Q\cap[0,1]</math>
is the set of all [[rational number]]s between 0 and 1 (inclusive), since even for <math>j < n</math> and <math>0 \leq k \leq j,</math> <math>\tfrac{k}{j} = \tfrac{nk}{nj}</math> is an element of the above. Therefore,
<math display=block>\limsup_{n \to \infty} A_n = \Q \cap [0, 1].</math>
On the other hand, <math display=block>\bigcap_{j \geq n} A_j = \{0, 1\},</math> which implies
<math display=block>\liminf_{n \to \infty} A_n = \{0,1\}.</math>
In this case, the sequence <math>A_1, A_2, \ldots</math> does not have a limit. Note that <math>\lim_{n \to \infty} A_n</math> is not the set of accumulation points, which would be the entire interval <math>[0, 1]</math> (according to the usual [[Euclidean distance|Euclidean metric]]).

==Probability uses==
Set limits, particularly the limit infimum and the limit supremum, are essential for [[probability]] and [[Measure (mathematics)|measure theory]]. Such limits are used to calculate (or prove) the probabilities and measures of other, more purposeful, sets. For the following, <math>(X,\mathcal{F},\mathbb{P})</math> is a [[probability space]], which means <math>\mathcal{F}</math> is a [[sigma-algebra|σ-algebra]] of subsets of <math> X</math> and <math>\mathbb{P}</math> is a [[probability measure]] defined on that σ-algebra. Sets in the σ-algebra are known as [[Event (probability theory)|events]].

If <math>A_1, A_2, \ldots</math> is a [[Set-theoretic limit#Monotone_sequences|monotone sequence]] of events in <math>\mathcal{F}</math> then <math>\lim_{n \to \infty} A_n</math> exists and
<math display=block>\mathbb{P}\left(\lim_{n \to \infty} A_n\right) = \lim_{n \to \infty} \mathbb{P}\left(A_n\right).</math>

===Borel–Cantelli lemmas===
{{Main article|Borel–Cantelli lemma}}
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
{{math theorem|name=First Borel–Cantelli lemma|math_statement=If <math display=block>\sum_{n=1}^{\infty} \mathbb{P}\left(A_n\right) < \infty</math> then <math display=block>\mathbb{P}\left(\limsup_{n \to \infty} A_n\right) = 0.</math>}}
The second Borel–Cantelli lemma is a partial converse:
{{math theorem|name=Second Borel–Cantelli lemma|math_statement=If <math display=block>A_1, A_2, \ldots</math> are independent events and <math display=block>\sum_{n=1}^\infty \mathbb{P}\left(A_n\right) = \infty</math> then <math display=block>\mathbb{P}\left(\limsup_{n \to \infty} A_n\right) = 1.</math>}}

===Almost sure convergence===
One of the most important applications to [[probability]] is for demonstrating the [[almost sure convergence]] of a sequence of [[random variable]]s. The event that a sequence of random variables <math>Y_1, Y_2, \ldots</math> converges to another random variable <math>Y</math> is formally expressed as <math display=inline>\left\{\limsup_{n\to\infty} \left|Y_n - Y\right| = 0\right\}.</math> It would be a mistake, however, to write this simply as a limsup of events.  That is, this {{em|is not}} the event <math display=inline>\limsup_{n\to\infty} \left\{ \left|Y_n - Y\right| = 0\right\}</math>! Instead, the {{em|complement}} of the event is 
<math display=block>\begin{align}
\left\{\limsup_{n\to\infty} \left|Y_n - Y\right| \neq 0\right\}
&= \left\{\limsup_{n\to\infty} \left|Y_n - Y\right| > \frac{1}{k} \text{ for some } k\right\}\\ 
&= \bigcup_{k \geq 1} \bigcap_{n \geq 1} \bigcup_{j \geq n} \left\{\left|Y_j - Y\right| > \tfrac{1}{k}\right\} \\
&= \lim_{k\to\infty} \limsup_{n\to\infty} \left\{ \left|Y_n - Y\right| > \tfrac{1}{k}\right\}.
\end{align}</math>
Therefore,
<math display=block>\mathbb{P}\left(\left\{\limsup_{n\to\infty} \left|Y_n - Y\right| \neq 0 \right\}\right) 
= \lim_{k\to\infty} \mathbb{P}\left(\limsup_{n\to\infty} \left\{ \left|Y_n - Y\right| > \tfrac{1}{k} \right\}\right).</math>

== See also ==

* {{annotated link|List of set identities and relations}}
* {{annotated link|Set theory}}

== References ==

{{reflist}}
{{reflist|group=note}}

[[Category:Set theory]] 
[[Category:Probability theory]]
[[Category:Measure theory| ]]