# liminf in terms of the point-to-set distance

Let $\mathcal{X}$ be a normed space and $C\subseteq \mathcal{X}$. We define the point-to-set distance for the set $C$ to be:

$$d_C:\mathcal{X}\ni x \mapsto d_c(x):= \inf_{y\in C}\|x-y\| \in [0,\infty]$$

Additionally, we define the inner limit of a sequence of sets $C_n$ in $\mathcal{X}$ to be:

$$\liminf_n C_n = \bigcup_{n=1}^\infty \bigcap_{m=n}^\infty C_m$$

This definition is equivalent to:

$$\liminf_n C_n = \left\{x \in \mathcal{X} | x\in C_k \text{ ultimately for all } k \right\}$$

My initial question was: I need to prove that: $$\liminf_n C_n = \left\{ x \in \mathcal{X} | \liminf_{n\to\infty} \left(d_{C_n}(x)\right)=0\right\}$$

But this is not true!

The following facts hold true:

1. $\liminf_n C_n \subseteq \left\{ x \in \mathcal{X} | \liminf_{n\to\infty} \left(d_{C_n}(x)\right)=0\right\} = \limsup_n C_n$
2. $\liminf_n C_n \subseteq \left\{ x \in \mathcal{X} | \lim_{n\to\infty} \left(d_{C_n}(x)\right)=0\right\}$

Edit 1. The meaning of "ultimately for all $k$" should be interpreted as follows:

$$\liminf_{n\to\infty} C_n = \{x | \forall k\in\mathbb{N} \exists x_k\in C_{n_k}:\ x_k\to x\}$$ where $n_k\in\mathbb{N}$ is a strictly increasing sequence of indices (i.e. $\{C_{n_k}\}_{k\in\mathbb{N}}$ is some subsequence of ${C_n}_{n\in\mathbb{N}}$).

Edit 2. I changed the formula with the closure which was wrong according to Tim (thanks to the answer to Tim's question by Matthias Klupsch). I'll post a new question for what I read in Rockafellar's book and gave me the confusion.

-
(1.) I don't think $\lim\inf_n C_n = \bigcap_{n=1}^\infty \overline{\bigcup_{m=n}^\infty C_m}$ makes sense; the right hand side seems to correspond to $\lim\sup_n C_n$. (2.) Your equivalent characterization is not quite right. The second definition works if we ignore the closure operation in the first definition, but not the way the question is stated now. – Srivatsan Nov 22 '11 at 10:51
@Srivatsan: See R.T. Rockafellar and R. J-B. Wets, "Variational Analysis", Grundlehren der mathematischen Wissenschaften, vol. 317, 1998, p. 110. However, you may omit the closure if it helps you answer my question. – Pantelis Sopasakis Nov 22 '11 at 10:56
@DavideGiraudo: Thanks for the hints... but I still don't see how I can construct this sequence. For $k=1$ I can find a sequence $N=\mathbb{N}_{\geq v_1}$ such that $x\in\lim\inf_n C_n$ implies that $x\in C_n + \mathcal{B}$ for $n\geq v_1$ (where $\mathcal{B}$ is the unit ball). Eventually, $x\in C_n + k^{-1}\mathcal{B}$ for $n\geq v_k$ (and $v_k\geq v_{k-1}\geq \ldots$ ). I feel I'm close... can you give me a hint... – Pantelis Sopasakis Nov 22 '11 at 11:43
@Srivatsan: Why is $\lim\sup_n C_n = \bigcap_{n=1}^\infty \overline{\bigcup_{m=n}^\infty C_m}$? – Tim Nov 22 '11 at 20:35
@Tim Actually, it isn't. But the right hand side looks more like limsup than liminf. See this chat discussion between tb and me: chat.stackexchange.com/transcript/message/2503305#2503305. – Srivatsan Nov 22 '11 at 20:36

Let $x\in \liminf C_n$. Then we construct a strictly increasing sequence of integers $\{n_k\}$ and a sequence $\{x_k\}$ such that $\lVert x-x_k\rVert\leq k^{-1}$ and $x_k\in C_{n_k}$. Since $x\in\overline{\bigcup_{m\geq 1}C_m}$, we can find $x_1\in\bigcup_{m\geq 1}C_m$ such that $\lVert x-x_1\rVert\leq 1$ and we choose $n_1$ an integer such that $x_1\in C_{n_1}$. If $x_1,\ldots,x_k$ and $n_1,\ldots,n_k$ are constructed, since $x\in \overline{\bigcup_{j\geq n_k+1}C_j}$, we can find $x_{k+1}$ such that $\lVert x-x_{k+1}\rVert\leq (k+1)^{-1}$ and we choose $n_{k+1}$ as an integer $\geq n_k+1$ such that $x_{k+1}\in C_{n_{k+1}}$. Since $d_{C_{n_k}}(x)\leq k^{-1}$, we get that $0\leq \liminf_n d_{C_n}(x)\leq \liminf_k d_{C_{n_k}}(x) =0$ and we showed $\subset$.

Conversely, if $\liminf_n d_{C_n}(x)=0$ then we can find a strictly increasing sequence of integers $\{n_k\}$ such that $\lim_k d_{C_{n_k}}(x) =0$. Now, taking $n\in\mathbb N$ and $\delta>0$, we can find $k$ such that $n_k>n$ and $d_{C_{n_k}}(x)\leq \frac{\delta}2$. By definition of infimum, we can choose $y\in C_{n_k}$ such that $\lVert x-y\rVert\leq\delta$. Therefore, $x\in\overline{\bigcup_{m\geq n}C_m}$ for all $n$ and $x\in\liminf_n C_n$.

-
When you say that $x\in\overline{\bigcup_{m\geq 1 }C_m}$ did you use the fact that $\liminf_n C_n=\bigcap_\Sigma\{\overline{\bigcup_{i\in\Sigma}}; \Sigma \text{ is infinite in } \mathbb{N}\}$? Do you think there is a way to show it based only on the fact that $\liminf_n C_n = \bigcup_{n=1}^{\infty}\bigcap_{m=n}^{\infty} C_m$? Thanks a lot! – Pantelis Sopasakis Nov 23 '11 at 9:04
I don't think it's even true with this definition: consider the case $\mathcal X=\mathbb R$ with the usual metric and $C_n=\left[0,1-\frac 1n\right]$, and $x_0=1$. Then $d_{C_n}(x)=\frac 1n$ and converges to $0$, but $1$ is never in $C_n$. – Davide Giraudo Nov 23 '11 at 9:20

Important note: According to @Did 's comments, I need to clarify that in my original question I confused two different definitions of limit for sequences of sets. The limit defined as $\liminf_n C_n = \left\{x \in \mathcal{X} | x\in C_k \text{ ultimately for all } k \right\}$ is different from the inner limit of Rockafellar and Wets. In what follows I use the definition given by Rockafellar and Wets.

Notation: Let $\left( \mathcal{X},\mathcal{T}\ \right)$ be a topological space. We denote the family of open neighbourhoods of $x\in\mathcal{X}$ by $\mho(x):=\{V\in\mathcal{T}:\ x\in V\}$.

Proposition 1: Let $\{C_n\}_{n\in\mathbb{N}}$ be a sequence of sets in a Hausdorff topological space $\left( \mathcal{X},\mathcal{T}\ \right)$. Then, $$\liminf_n C_n = \{x|\forall V\in\mho(x),\ \exists N\in \mathcal{N}_\infty, \forall n\in N: C_n\cap V\neq \emptyset\}$$ or equivalenty: $$\liminf_n C_n = \{ x|\forall V\in\mho(x),\ \exists N_0\in \mathbb{N}, \forall n\geq N_0: C_n\cap V\neq \emptyset \}$$

Proof.

(1). If $x\in\liminf_n C_n$ then we can find a sequence $\{x_k\}_{k\in\mathbb{N}}$ such that $x_k\to x$ while $x_k\in C_{n_k}$ and $\{n_k\}_{k\in\mathbb{N}}\subseteq \mathbb{N}$ is a strictly increasing sequence of indices. For any $V\in\mho(x)$ there is a $N_0\in\mathbb{N}$ such that for all $i\geq N_0$ it is: $x_i\in V$; but also $x_i\in C_{n_i}$. Thus $C_{n_i}\cap V\neq \emptyset$. Therefore $x$ is in the right-hand side set of the equation.

(2). For the reverse direction assume that $x$ belongs to the right-hand side set of given equation. Then, there is a strictly increasing sequence $\{n_k\}_{k\in\mathbb{N}}$. Then, for every $V\in\mho(x)$ we can find a $x_k\in C_{n_k}\cap V$. Hence, $x_k\to x$ ( in the topology $\mathcal{T}$ ).

$\square$

Proposition 2: Let $(\mathcal{X},\|\cdot\|)$ be a normed space and $\{C_n\}_{n\in\mathbb{N}}$ be a sequence of sets in $\mathcal{X}$. The inner limit of a sequence of sets is: $$\liminf_n C_n = \{ x\in X | \lim_n d(x,C_n)=0 \}$$

Proof.

(1). We now need to show that $\limsup_n d(x,C_n)=0$. Let us assume that $\limsup_n d(x,C_n)>0$, i.e. there exists an increasing sequence of indices $\{n_k\}_{k\in\mathbb{N}}$ so that $d(x,C_{n_k})\to_k a > 0$. This suggests that there is a $\varepsilon_0>0$ such that for all $k\in\mathbb{N}$ one has that $d(x,C_{n_k})>\varepsilon_0$. However, according to proposition \ref{propo:un_int}, $x\in\text{cl}\bigcup_{k\in\mathbb{N}}C_{n_k}$ while $d(x,\text{cl}\bigcup_{k\in\mathbb{N}}C_{n_k})\geq\varepsilon_0$ which is a contradiction. Hence, $\limsup_n d(x,C_n)=0$, i.e. $\lim_n d(x,C_n)=0$ and this way we have proven that $x$ is in the right-hand side set.

(2). Assume that $x$ in the right-hand side of the given equation. This is $\lim_n d(x,C_n)=0$. For any $\varepsilon>0$, we can find $n_0\in\mathbb{N}$ such that $d(x,C_{n})\leq \frac{\varepsilon}{2}$ for all $n\geq n_0$. By definition, we have that $d(x,C_{n})=\inf\{\|x-y\|,\ y\in C_{n}\}$, thus we can find a $y_n\in C_{n}$ such that

$$\|y_n-x\|<d(x,C_{n})+\frac{\varepsilon}{2}=\varepsilon$$

we can do that following the steps pointed out by Davide Giraudo in his answer to this question. That is:

$$\exists\ y_n\in C_{n}:\ \|y_n-x\|<\varepsilon$$ Therefore, $x\in C_{n} + \varepsilon \mathcal{B}$ from which it follows that $x\in\liminf_n C_n$ (According to proposition 1).

$\square$

Proposition 3: Let $(\mathcal{X},\|\cdot\|)$ be a normed space and $\{C_n\}_{n\in\mathbb{N}}$ be a sequence of sets in $\mathcal{X}$. The inner limit of a sequence of sets is: $$\limsup_n C_n = \{ x\in X | \liminf_n d(x,C_n)=0 \}$$

Note: We know that $\liminf_n C_n \subseteq \limsup_n C_n$. We may therefore prove that :

$$\liminf_n C_n \subseteq \{ x\in X | \liminf_n d(x,C_n)=0 \}$$

-
Pantelis: This (accepted) answer of yours and the text of the question itself both contain several serious inaccuracies based on a confusion between some distinct definitions (roughly speaking, set theoretic limits vs topological limits). This was pointed to you here and you acknowledged it, if I understand you correctly. I suggest you mention this fact somewhere in the present question and answer, instead of letting people believe otherwise. – Did Jan 9 '12 at 8:42