1

Vitaliの被覆定理

498
0

(この記事は https://muse-energy.github.io/math-memo/vitali.html の再録です)
測度論とかに出てくる定理だが、久々に証明を読んだら面白かったのでメモ。

Vitaliの被覆定理(無限バージョン)

(X,d)を距離空間とする。X内の(開)球の族{B(xi,ri)}iIが与えられたとする(Iは無限集合でもよい)。いま、R:=supiIri<+であると仮定する。このとき、I0Iをうまく選び、以下の条件を満たすようにすることができる。

  1. 選ばれた球は、どのふたつも交わらない。すなわち、i,jI0のとき、B(xi,ri)B(xj,rj)=である。
  2. 選ばれた球の半径を5倍すると、もともと与えられた球をすべて覆うことができる。すなわち、
    iIB(xi,ri)jI0B(xj,5rj)
    が成り立つ。

一見なんだかよく分からないが、とりあえずR2とかR3内で球2つの場合を考えてみると雰囲気がわかってくる気がする。

  • 与えられた2つの球が交わらないとき:このときは、2つとも選べばよい。すなわち、I0=Iとすればよい。
  • 与えられた2つの球が交わっているとき:このときは、高々一方の球しか選ぶことができない。そこで覆いやすいほうがどちらかを検討してみると、半径の大きいものを選んだほうがよさそうである。
    ここでちょっと考えると、大きいほうの球を5倍すると、もう一方の球がすっぽり含まれることがわかる。さらによく考えると、この状況であれば5倍する必要はなく、3倍で済むこともわかる。

実は、与えられた球が有限個であれば次が成り立つ:

Vitaliの被覆定理(有限バージョン)

(X,d)を距離空間とする。X内の(開)球の有限{B(xi,ri)}iIが与えられたとする。このとき、I0Iをうまく選び、以下の条件を満たすようにすることができる。

  1. 選ばれた球は、どのふたつも交わらない。すなわち、i,jI0のとき、B(xi,ri)B(xj,rj)=である。
  2. 選ばれた球の半径を3すると、もともと与えられた球をすべて覆うことができる。すなわち、
    iIB(xi,ri)jI0B(xj,5rj)
    が成り立つ。

有限個だと3倍でよいというわけである。実は無限個の場合も「5倍」より小さくすることができるのだが、「3倍」まで減らしてしまうと反例が存在する。このあたりの事情は後で述べることにする。

まずは有限バージョンの証明を紹介する。

定理(有限バージョン)の証明

与えられた有限個の球を半径の大きいものから順に並べておく。このとき、列の初め(半径の大きいもの)から見ていって、いままでに選んだどの球とも交わらないならば選び、そうでなければ選ばないようにする。このようにして選ばれた添え字の集合をI0とおき、これが条件を満たすことを示す。選んだ球のうち、どのふたつも交わらないことは選び方からok。

最初に与えられた球のうちのひとつB(xi,ri)を固定する。

  • iI0であれば、当然B(xi,ri)B(xi,3ri)である。
  • iI0とする。このとき、jI0であって、rjriかつB(xj,rj)B(xi,ri)であるものが存在する。
    選ばれなかったのだから、それより前に選んだ球と交わっているはずである。
    yB(xj,rj)B(xi,ri)を固定する。このとき、任意のxB(xi,ri)に対して、
    d(x,xj)d(x,xi)+d(xi,y)+d(y,xj)<ri+ri+rj3rj
     なので、xB(xj,3rj)である。
    したがって、任意のiIに対してあるjI0が存在して、B(xi,ri)B(xj,3rj)が成り立つことがわかる。これで定理が示された。

このように、競プロなどでよく見かける「貪欲法」がうまく適用できるわけである。

球が無限個のときは、「半径が最大の球」は存在するとは限らないので、選び方を少し工夫する必要がある。仮定より、与えられた球の半径はすべてR以下であったことに注意する。

定理(無限バージョン)の証明

次のように順次球を選んでいく。

(Step 1) 半径がR2<riRであるような球からなる族であって、どのふたつも交わらないようなもののうち極大なものをとる。

  • 互いに交わらないようにできるだけたくさん取ると言っている。極大なものが存在するのはZornの補題による。(…とか書くとこの定理がどの程度選択公理案件なのかが気になりますが、どうなんでしょうか?)

(Step 2) 「半径がR4<riR2であるような球であって、(Step 1)で選んだ球のいずれとも交わらないようなもの」からなる族であって、さらにどのふたつも交わらないもののうち極大なものをとる。

  • 分かりにくくなってしまったが、(Step 1)と(Step 2)で選んだものたちが互いに交わらないようにたくさん取ると言っている。ここもZornの補題による。

(Step 3) 「半径がR8<riR4であるような球であって、(step 1)(Step 2)で選んだ球のいずれとも交わらないようなもの」からなる族であって、さらにどのふたつも交わらないようなもののうち極大なものをとる。

以下同様に繰り返す。この操作の中で選ばれた球の添え字の集合をI0とおく。これが条件を満たすことを示す。各段階でそこまでに選んだ球たちが互いに交わらないように取っているので、選ばれた球のうちどのふたつも交わらないことはok。
最初に与えられた球のうちのひとつB(xi,ri)を固定する。

  • iI0であれば、B(xi,ri)B(xi,5ri)である。
  • iI0であるとする。先ほどの操作のうち、半径riの球が当てはまる段階がR2n<riR2n1であったとする。
    このとき、その段階における構成から、あるjI0であって、B(xj,rj)B(xi,ri)かつR2n<rjR2n1となるものが存在する。
  • yB(xj,rj)B(xi,ri)を固定する。
  • B(xi,ri)B(xj,5rj)であることを示そう。xB(xi,ri)を任意にとる。このとき、
     d(x,xj)d(x,xi)+d(xi,y)+d(y,xj)<ri+ri+rj2rj+2rj+rj=5rj
    だから、xB(xj,5rj)である。これでok。
    • rirj(R2n,R2n1]に含まれるので、ri2rjが成り立つ。

無限個のときもおおまかには貪欲法のようなことをしているが、「大きい順」に並べることが不可能なので、代わりに半径R/2からRまでを同時に考えるというおおざっぱなことをしている。その関係で、「3倍」の部分が「5倍」になっているとみることができる。

ちなみに、ステップごとの刻む幅を1/2ごとではなく1/cごと(c>1)にすると、全く同じ議論で「1+2c倍」を証明することができる。

  • このときは、最後の評価がri+ri+rjcrj+crj+rj=(1+2c)rjとなる。
    したがって、無限バージョンのときは、3倍よりわずかに大きい3+ϵ倍については定理を証明することができる。

一方、無限バージョンで「3倍」とした命題には反例が存在する:

Stack Exchangeのスレッド で紹介されている例

R内の球(=開区間)の族として、
Z:={B(x,r):|x|<12,|x|<r<|x|+13}
を考えると、以下のことがわかる:

  • Zに属する区間のunionは(1,1)である。(最終的にこれを覆わなくてはいけない)
  • Zに属する区間はすべて0を含む。
    • 特に、Zから互いに交わらないようにいくつかの区間を選ぼうとすると、高々ひとつしか選ぶことができない。
  • しかし、Zに属する任意の区間B(x,r)に対して、B(x,3r)はどれも(1,1)より真に小さい。
  • したがって、ZはVitaliの被覆定理において「3倍」とした命題の反例である。

なぜこの例では3倍で上手くいかないのかを考えると、やはり「最大の半径をもつ球を選ぶ」という操作ができないことに由来しているように思われる。ここに有限個と無限個の違いが反映されているような気がして面白いのではないかと思う。

投稿日:2023611
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中