# Hausdorff limits

In order to prove o-minimality for structures generated by Rolle sets, we need another tool from topology: Hausdorff limits (see Section 21 of Kuratowski’s book).

Definition
For compact sets $A,B \subseteq \RR^n$, the Hausdorff distance $d(S,T)$ is the greater of the two values $\sup\set{d(x,T):\ x \in S}$ and $\sup\set{d(x,S):\ x \in T}$.

Note that $d_n(A,\emptyset) = \infty$ whenever $A$ is nonempty, and that $d_n(\emptyset, \emptyset) = 0$.

Remark
For any set $S \subseteq \RR^n$ and $\epsilon \gt 0$, we set $$T(S,\epsilon):= \set{x \in \RR^n:\ d(x,S) \lt \epsilon}.$$ We can picture Hausdorff distance as follows: for two compact sets $A,B \in \RR^n$ and $\epsilon \gt 0$, we have $d(A,B) \lt \epsilon$ if and only if $A \subseteq T(B,\epsilon)$ and $B \subseteq T(A,\epsilon)$.

We let $\K_n$ be the set of all compact subsets of $\RR^n$, equipped with the Hausdorff distance.

The following facts can be found in Kuratowski’s book. I would say they are good and straightforward exercises to work out for yourself, but due to the rather involved nature of the definition of Hausdorff distance, they require a bit of patience.

Facts

1. $(\K_n,d)$ is a metric space.
2. Every bounded sequence in $\K_n$ contains a convergent subsequence; in particular, every bounded and closed subset of $\K_n$ is compact.
3. Let $A_i \in \K_n$ for $i \in \NN$, and assume that $$\lim_i A_i = A \in \K_n.$$ Then $A$ is the set of all limits of convergent sequences $(x_i)_{i \in \NN}$ such that $x_i \in A_i$ for each $i$.
4. Let $A_{i,j} \in \K_n$ for $i,j \in \NN$, and assume that $$\lim_j A_{i,j} \to A_i \in \K_n,\ \text{ for each } i,$$ and that $$\lim_i A_i = A \in \K_n.$$ Then there exist $j(i) \in \NN$, for each $i$, such that $A = \lim_i A_{i,j(i)}$.

It makes sense for us to extend the notion of convergence in $\K_n$ to sequences of bounded subsets of $\RR^n$: below, let $A_i \subseteq \RR^n$ be bounded, for $i \in \NN$, and let $A \subseteq \RR^n$ be compact.

Definition

1. The sequence of all $A_i$ is bounded if the sequence of all $\cl A_i$ is a bounded sequence in $\K_n$.
2. The sequence of all $A_i$ converges to $A$ if $\lim_i \cl A_i = A$ in $\K_n$; in this situation, we write $\lim_i A_i = A$.
3. We call $A$ a Hausdorff limit of the sequence of all $A_i$ if some subsequence converges to $A$.

The main reason why we are interested in Hausdorff limits is that they preserve bounds on the number of connected components:

Exercise
Assume that $\lim_i A_i = A$ and that there exists $N \in \NN$ such that each $A_i$ has at most $N$ connected components. Show that $A$ has at most $N$ connected components. Moreover, if $\left|A_i\right| \le N$ for each $i$, show that $|A| \le N$.

The key result for us is the following: recall that a set is meager if it is a countable union of nowhere dense sets.

Theorem
Assume that $\lim_i A_i = A$ and

1. for each $m \le n$ and each open box $U \subseteq \RR^{n-m}$, there exists $N = N(U) \in \NN$ such that the set $U \cap (A_i)_a$ has at most $N$ connected components, for all $a \in \RR^m$;
2. each $A_i$ is meager.

Then $A$ is meager.

The conclusion of the theorem is false without some uniform bound assumption on the number of connected components of the $A_i$: since the rational numbers are dense in $\RR$, it is easy to construct a sequence of finite subsets of $[-1,1]$ that converges to $[-1,1]$.

Proof of the theorem.
We proceed by induction on $n$, taking fibers over the first coordinate.

If $n=1$, then the assumptions imply that there exists $N \in \NN$ such that each $A_i$ has at most $N$ elements; so this case follows from the exercise above.

So we assume $n>1$ and the theorem holds for lower values of $n$. In order to show that $A$ is meager it suffices, by the Kuratowski-Ulam theorem, to show that the set of all $a \in \RR$ such that $A_a$ is not meager is itself meager.

Note that assumption 1 of the theorem implies that same assumption with the fibers $(A_i)_a$ in place of $A_i$, for all $a \in \RR$. Also, by the Kuratowski-Ulam theorem, the set of all $a \in \RR$ such that some fiber $(A_i)_a$ is not meager is itself meager. Therefore, by the inductive hypothesis, it suffices to show:

Claim
The set $S$ of all $a \in \RR$ such that the fiber $A_a$ is not a Hausdorff limit of the sequence of fibers $(A_i)_a$ is meager.

To prove the claim, we need the following criterion:

Lemma
Assume that $a \in \RR$ is such that the fiber $A_a \neq \emptyset$ and $A_a$ is not a Hausdorff limit of the sequence of fibers $(A_i)_a$. Then there are open boxes $U_1, \dots, U_l \subseteq \RR^{n-1}$ such that

($\ast$)

$A_a \cap U_j \neq \emptyset$ for $j=1, \dots, l$ and, for all sufficiently large $i$, there is a $j$ such that $(A_i)_a \cap U_j = \emptyset$.

Show proof

Proof. By the definition of Hausdorff limit, there is an $\epsilon \gt 0$ such that, for all sufficiently large $i$, we have either $(A_i)_a = \emptyset$, or $(A_i)_a \nsubseteq T(A_a,\epsilon)$, or $A_a \nsubseteq T\big((A_i)_a,\epsilon\big)$, where $$T(S,\epsilon):= \set{x:\ d(x,S) \lt \epsilon}.$$ If $(A_i)_a = \emptyset$ for all but finitely many $i$, then the lemma is trivial, so we assume that $(A_i)_a \neq \emptyset$ for infinitely many $i$.

Passing to the subsequence of all $A_i$ with $(A_i)_a \neq \emptyset$, we may assume that $(A_i)_a \neq \emptyset$ for all $i$.

Subclaim. $A_a \nsubseteq T\big((A_i)_a,\epsilon\big)$ for all sufficiently large $i$.

To see this, assume $(A_i)_a \nsubseteq T(A_a,\epsilon)$ for infinitely many $i$. Then there are $i(j) \in \NN$ and points $x_j \in (A_{i(j)})_a$, for $j \in \NN$, such that the sequence of all $i(j)$ is strictly increasing and $d(x_j,A_a) \geq \epsilon$ for each $j$. Since the sequence of all $A_i$ is bounded, the sequence $(x_j)$ has a limit point $x \in \RR^{n-1}$. By Fact 3 above, since $A$ is the limit of the sequence of all $A_i$, we have $x \in A_a$, which contradicts that $d(x_j,A_a) \geq \epsilon$ for all $j$, so the subclaim is proved.

By the subclaim, there is a sequence $(x_i)$ in $A_a$ such that $d(x_i,(A_i)_a) \geq \epsilon$ for all sufficiently large $i$. Let $B$ be the compact set of limit points of the sequence $(x_i)$. Choose $y_1, \dots, y_l \in B$ such that the boxes $U_j$, with center $y_j$ and all edges of length $\epsilon/2$, cover $B$. Clearly $x_i \in U_1 \cup \dots \cup U_l$ for all sufficiently large $i$.

Hence for all sufficiently large $i$, there is a $j \in \{1, \dots, l\}$ such that $d(y_j,(A_i)_a) \gt \epsilon/2$, that is, $(A_i)_a \cap U_j = \emptyset$, which finishes the proof. $\qed$

By the above lemma, we have $S = \bigcup_U S_U$, where $U$ ranges over all finite tuples $U = (U_1, \dots, U_l)$ of open boxes in $\RR^{m-1}$ with rational vertices and $$S_U := \set{a \in \RR:\ \text{ condition } (\ast) \text{ holds for } a}.$$ Fix $U = (U_1, \dots, U_l)$ and let $N_1, \dots, N_l \in \NN$ be such that each $A_\iota \cap (\RR \times U_j)$ has at most $N_j$ connected components. We show, by a pidgeonhole argument, that $$\left|S_U\right| \leq N:= 2 N_1 + \dots + 2 N_l;$$ it follows that $S$ is countable (and hence meager), which then finishes the proof of the claim.

Assume for a contradiction that there are distinct elements $a_1, \dots, a_{N+1} \in S_U$, and choose $\rho>0$ such that the intervals $I_p:= (a_p – \rho,\ a_p + \rho)$ are pairwise disjoint.

Since $A_{a_p} \cap U_j \neq \emptyset$, for each $p$ and $j$, and since the sequence of all $A_i$ converges to $A$, there exists $i_0 \in \NN$ such that $$\tag{I} A_i \cap (I_{p} \times U_j) \neq \emptyset$$ for all $p$, $j$ and $i \ge i_0$.

Now choose $i \ge i_0$ such that, for each $p$, there is a $j(p)$ with $(A_i)_{a_p} \cap U_{j(p)} = \emptyset$. Then, for some $k \in \{1, \dots, l\}$, there are distinct $$p(1), \dots, p(2 N_k+1) \in \{1, \dots, N+1\}$$ such that $j(p(q)) = k$ for $q=1, \dots, 2 N_k+1$, that is, such that $$\tag{II} (A_i)_{a_{p(q)}} \cap U_k = \emptyset \text{ for }q = 1, \dots, 2 N_k+1.$$ But (I) and (II) together imply that $A_i \cap (\RR \times U_k)$ has at least $N_k+1$ components, contradicting our choice of $N_k$. $\qed$

This site uses Akismet to reduce spam. Learn how your comment data is processed.