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