$$$$
(この記事は
https://muse-energy.github.io/math-memo/vitali.html
の再録です)
測度論とかに出てくる定理だが、久々に証明を読んだら面白かったのでメモ。
Vitaliの被覆定理(無限バージョン)
$(X,d)$を距離空間とする。$X$内の(開)球の族$\{B(x_i,r_i)\}_{i \in I}$が与えられたとする($I$は無限集合でもよい)。いま、$R:= \sup_{ i \in I}r_i < +\infty$であると仮定する。このとき、$ I_0 \subset I$をうまく選び、以下の条件を満たすようにすることができる。
- 選ばれた球は、どのふたつも交わらない。すなわち、$ i,j \in I_0$のとき、$B(x_i,r_i) \cap B(x_j, r_j) = \emptyset$である。
- 選ばれた球の半径を$5$倍すると、もともと与えられた球をすべて覆うことができる。すなわち、
$$\bigcup_{i \in I} B(x_i, r_i) \subset \bigcup_{j \in I_0} B(x_j, 5r_j)$$
が成り立つ。
一見なんだかよく分からないが、とりあえず$\mathbb{R}^2$とか$\mathbb{R}^3$内で球2つの場合を考えてみると雰囲気がわかってくる気がする。
- 与えられた2つの球が交わらないとき：このときは、2つとも選べばよい。すなわち、$I_0 = I$とすればよい。
- 与えられた2つの球が交わっているとき：このときは、高々一方の球しか選ぶことができない。そこで覆いやすいほうがどちらかを検討してみると、半径の大きいものを選んだほうがよさそうである。
ここでちょっと考えると、大きいほうの球を$5$倍すると、もう一方の球がすっぽり含まれることがわかる。さらによく考えると、この状況であれば$5$倍する必要はなく、$3$倍で済むこともわかる。
実は、与えられた球が有限個であれば次が成り立つ：
Vitaliの被覆定理(有限バージョン)
$(X,d)$を距離空間とする。$X$内の(開)球の有限族$\{B(x_i,r_i)\}_{i \in I}$が与えられたとする。このとき、$I_0 \subset I$をうまく選び、以下の条件を満たすようにすることができる。
- 選ばれた球は、どのふたつも交わらない。すなわち、$i,j \in I_0$のとき、$B(x_i,r_i) \cap B(x_j, r_j) = \emptyset$である。
- 選ばれた球の半径を$3$倍すると、もともと与えられた球をすべて覆うことができる。すなわち、
$$\bigcup_{i \in I} B(x_i, r_i) \subset \bigcup_{j \in I_0} B(x_j, 5r_j)$$
が成り立つ。
有限個だと$3$倍でよいというわけである。実は無限個の場合も「$5$倍」より小さくすることができるのだが、「$3$倍」まで減らしてしまうと反例が存在する。このあたりの事情は後で述べることにする。
まずは有限バージョンの証明を紹介する。
定理(有限バージョン)の証明
与えられた有限個の球を半径の大きいものから順に並べておく。このとき、列の初め(半径の大きいもの)から見ていって、いままでに選んだどの球とも交わらないならば選び、そうでなければ選ばないようにする。このようにして選ばれた添え字の集合を$I_0$とおき、これが条件を満たすことを示す。選んだ球のうち、どのふたつも交わらないことは選び方からok。
最初に与えられた球のうちのひとつ$B(x_i, r_i)$を固定する。
- $i \in I_0$であれば、当然$B(x_i, r_i) \subset B(x_i, 3r_i)$である。
- $i \not \in I_0$とする。このとき、$j \in I_0$であって、$r_j \geq r_i$かつ$B(x_j, r_j) \cap B(x_i, r_i )\neq \emptyset$であるものが存在する。
選ばれなかったのだから、それより前に選んだ球と交わっているはずである。
$y \in B(x_j, r_j) \cap B(x_i, r_i)$を固定する。このとき、任意の$x \in B(x_i, r_i)$に対して、
$$d(x,x_j) \leq d(x,x_i) + d(x_i, y) + d(y,x_j) < r_i + r_i + r_j \leq 3r_j$$
なので、$x \in B(x_j, 3r_j)$である。
したがって、任意の$i \in I$に対してある$j \in I_0$が存在して、$B(x_i, r_i) \subset B(x_j, 3r_j)$が成り立つことがわかる。これで定理が示された。$\square$
このように、競プロなどでよく見かける「貪欲法」がうまく適用できるわけである。
球が無限個のときは、「半径が最大の球」は存在するとは限らないので、選び方を少し工夫する必要がある。仮定より、与えられた球の半径はすべて$R$以下であったことに注意する。
定理(無限バージョン)の証明
次のように順次球を選んでいく。
(Step 1) 半径が$\frac{R}{2} < r_i \leq R$であるような球からなる族であって、どのふたつも交わらないようなもののうち極大なものをとる。
- 互いに交わらないようにできるだけたくさん取ると言っている。極大なものが存在するのはZornの補題による。(…とか書くとこの定理がどの程度選択公理案件なのかが気になりますが、どうなんでしょうか？)
(Step 2) 「半径が$\frac{R}{4} < r_i \leq \frac{R}{2}$であるような球であって、(Step 1)で選んだ球のいずれとも交わらないようなもの」からなる族であって、さらにどのふたつも交わらないもののうち極大なものをとる。
- 分かりにくくなってしまったが、(Step 1)と(Step 2)で選んだものたちが互いに交わらないようにたくさん取ると言っている。ここもZornの補題による。
(Step 3) 「半径が$\frac{R}{8} < r_i \leq \frac{R}{4}$であるような球であって、(step 1)(Step 2)で選んだ球のいずれとも交わらないようなもの」からなる族であって、さらにどのふたつも交わらないようなもののうち極大なものをとる。
以下同様に繰り返す。この操作の中で選ばれた球の添え字の集合を$I_0$とおく。これが条件を満たすことを示す。各段階でそこまでに選んだ球たちが互いに交わらないように取っているので、選ばれた球のうちどのふたつも交わらないことはok。
最初に与えられた球のうちのひとつ$B(x_i, r_i)$を固定する。
- $i \in I_0$であれば、$B(x_i, r_i) \subset B(x_i, 5r_i)$である。
- $i \not \in I_0$であるとする。先ほどの操作のうち、半径$r_i$の球が当てはまる段階が$\frac{R}{2^{n}} < r_i \leq \frac{R}{2^{n-1}}$であったとする。
このとき、その段階における構成から、ある$j \in I_0$であって、$B(x_j, r_j) \cap B(x_i, r_i) \neq \emptyset$かつ$\frac{R}{2^n} < r_j \leq \frac{R}{2^{n-1}}$となるものが存在する。 - $y \in B(x_j, r_j) \cap B(x_i, r_i)$を固定する。
- $B(x_i, r_i)\subset B(x_j, 5r_j)$であることを示そう。$x \in B(x_i, r_i)$を任意にとる。このとき、
$$d(x, x_j) \leq d(x, x_i)+d(x_i, y) + d(y,x_j) < r_i + r_i + r_j \leq 2r_j + 2r_j + r_j = 5r_j$$
だから、$x \in B(x_j, 5r_j)$である。これでok。$\square$
- $r_i$も$r_j$も$\left(\frac{R}{2^n}, \frac{R}{2^{n-1}}\right\rbrack$に含まれるので、$r_i \leq 2r_j$が成り立つ。
無限個のときもおおまかには貪欲法のようなことをしているが、「大きい順」に並べることが不可能なので、代わりに半径$R/2$から$R$までを同時に考えるというおおざっぱなことをしている。その関係で、「$3$倍」の部分が「$5$倍」になっているとみることができる。
ちなみに、ステップごとの刻む幅を$1/2$ごとではなく$1/c$ごと($c>1$)にすると、全く同じ議論で「$1+2c$倍」を証明することができる。
- このときは、最後の評価が$r_i + r_i + r_j \leq cr_j + cr_j + r_j = (1+2c)r_j$となる。
したがって、無限バージョンのときは、$3$倍よりわずかに大きい$3+\epsilon$倍については定理を証明することができる。
一方、無限バージョンで「$3$倍」とした命題には反例が存在する：
$\mathbb{R}$内の球(=開区間)の族として、
$$ Z := \left\{B(x,r): |x|<\frac{1}{2}, |x|< r<\frac{|x|+1}{3}\right\}$$
を考えると、以下のことがわかる：
- $Z$に属する区間のunionは$(-1, 1)$である。(最終的にこれを覆わなくてはいけない)
- $Z$に属する区間はすべて$0$を含む。
- 特に、$Z$から互いに交わらないようにいくつかの区間を選ぼうとすると、高々ひとつしか選ぶことができない。
- しかし、$Z$に属する任意の区間$B(x,r)$に対して、$B(x,3r)$はどれも$(-1,1)$より真に小さい。
- したがって、$Z$はVitaliの被覆定理において「$3$倍」とした命題の反例である。$\square$
なぜこの例では$3$倍で上手くいかないのかを考えると、やはり「最大の半径をもつ球を選ぶ」という操作ができないことに由来しているように思われる。ここに有限個と無限個の違いが反映されているような気がして面白いのではないかと思う。