Sauer–Shelahの補題
概要
Sauer–Shelahの補題（Sauer–Shelah lemma）とは、$n$ 元集合の部分集合の族 $\mathcal F$ の VC 次元が $d$ 以下なら、$\mathcal F$ の元の個数は $\sum_{i=0}^{d}\binom ni$ 以下である、という組合せ論の定理である。集合から 1 元ずつ抜く圧縮で族を下に閉じた族に移すと、元の個数は変わらず打ち砕かれる集合は増えないので、$\mathcal F$ は少なくとも $\lvert\mathcal F\rvert$ 個の集合を打ち砕く、というより強い形が得られる。$d$ 元以下の部分集合の全体で等号が成り立ち、上界は $1\le d\le n$ のとき $(en/d)^d$ 以下である。VC 次元が有限な族の跡が多項式個しかないことを表し、ε-ネットや学習理論、モデル理論の NIP 理論で使われる。
$n$ 元集合の部分集合は $2^n$ 個ある。部分集合の族 $\mathcal F$ が、どの $d+1$ 元集合も打ち砕かない（$\mathcal F$ との共通部分としてそのすべての部分集合を切り出すことはできない）とき、$\mathcal F$ の元は何個まであり得るか。答えは $\sum_{i=0}^{d}\binom ni$ 個で、$n$ について $d$ 次の多項式の程度にすぎない。これが Sauer–Shelah の補題（Sauer–Shelah lemma）である。Erdős の問いに答えて Sauer が、安定な理論の研究の補題として Perles と Shelah が、それぞれ独立に示した（Sh72 p. 254、Alo83 p. 199、SSBD14 §6.7）。
この記事では、補題をより強い「$\mathcal F$ は少なくとも $\lvert\mathcal F\rvert$ 個の集合を打ち砕く」という形で、集合を 1 元ずつ縮める圧縮（シフト）によって証明する。帰納法による別証明、等号の例、$\sum_{i\le d}\binom ni\le(en/d)^d$ の評価を述べ、双対 VC 次元とモデル理論の NIP 理論との関係に触れる。
主張
$X$ を集合、$\mathcal F$ を $X$ の部分集合の族とする。$A\subset X$ について $\mathcal F|_A:=\{A\cap F\mid F\in\mathcal F\}$ とおく。有限集合 $A$ が $\mathcal F|_A=2^A$ をみたすとき $\mathcal F$ は $A$ を 打ち砕く といい、打ち砕かれる有限集合の元の個数の最大値を $\operatorname{VC}(\mathcal F)$ と書く（VC次元）。$\mathcal F$ が打ち砕く $X$ の有限部分集合の全体を $\operatorname{sh}(\mathcal F)$ と書き、
$$
\Phi_d(n):=\sum_{i=0}^{d}\binom ni\qquad(\text{$i>n$ の項は $0$})
$$
とおく。$\Phi_d(n)$ は $n$ 元集合の $d$ 元以下の部分集合の個数である。
$X$ を $n$ 元集合、$\mathcal F$ を $X$ の部分集合の族とし、$\operatorname{VC}(\mathcal F)\le d$ とする。このとき $\lvert\mathcal F\rvert\le\Phi_d(n)$ である。
次の thm-ss-pajor から従う。$\operatorname{VC}(\mathcal F)\le d$ なら $\mathcal F$ が打ち砕く集合はどれも $d$ 元以下なので、$\lvert\mathcal F\rvert\le\lvert\operatorname{sh}(\mathcal F)\rvert\le\Phi_d(n)$ である。thm-ss-pajor は下の圧縮による証明で示す。
$X$ を有限集合とすると、$X$ の部分集合のどの族 $\mathcal F$ も $\lvert\operatorname{sh}(\mathcal F)\rvert\ge\lvert\mathcal F\rvert$ をみたす。
証明は節「圧縮による証明」の prf-ss-pajor で与える。
$X$ を任意の集合、$\mathcal F$ を $X$ の部分集合の族とし、$\operatorname{VC}(\mathcal F)\le d$ とする。$n$ 元の $A\subset X$ について $\lvert\mathcal F|_A\rvert\le\Phi_d(n)$ である。
$\mathcal F|_A$ は $A$ の部分集合の族で、$B\subset A$ について $(\mathcal F|_A)|_B=\mathcal F|_B$ だから、$\mathcal F|_A$ が打ち砕く集合は $\mathcal F$ も打ち砕く。よって $\operatorname{VC}(\mathcal F|_A)\le d$ で、thm-ss-main を $A$ と $\mathcal F|_A$ に使えばよい。$\square$
HW87 Theorem 3.2（p. 133）はこの形で述べている。
圧縮による証明
以下 thm-ss-pajor を証明する。$X$ は有限集合で、$\mathcal F$ は $X$ の部分集合の族である。
$i\in X$ と $F\in\mathcal F$ について
$$
S_i(F):=\begin{cases}F\setminus\{i\}&(i\in F\ \text{かつ}\ F\setminus\{i\}\notin\mathcal F),\\ F&(\text{それ以外})\end{cases}
$$
とおき、$S_i(\mathcal F):=\{S_i(F)\mid F\in\mathcal F\}$ とする。$S_i$ を $i$ 方向の 圧縮（下方シフト）という。
$S_i$ は、$i$ を含む元から $i$ を抜き、抜いた結果がまだ $\mathcal F$ になければその元を置き換える操作である。たとえば $X=\{1,2\}$、$\mathcal F=\{\{1\},\{1,2\}\}$ なら $S_1(\mathcal F)=\{\emptyset,\{2\}\}$ である。
$\lvert S_i(\mathcal F)\rvert=\lvert\mathcal F\rvert$ である。
$F\ne G$ で $S_i(F)=S_i(G)$ と仮定する。両方とも置き換えられなければ $F=G$ である。両方とも置き換えられれば $F\setminus\{i\}=G\setminus\{i\}$ で、$F,G$ はともに $i$ を含むので $F=G$ である。$F$ だけが置き換えられれば $G=F\setminus\{i\}\in\mathcal F$ となり、置き換えの条件 $F\setminus\{i\}\notin\mathcal F$ に反する。よって $F\mapsto S_i(F)$ は単射である。$\square$
$\operatorname{sh}(S_i(\mathcal F))\subset\operatorname{sh}(\mathcal F)$ である。
$S_i(\mathcal F)$ が $T$ を打ち砕くとし、$B\subset T$ をとる。$T\cap F=B$ となる $F\in\mathcal F$ を探す。
$i\notin T$ の場合． $T\cap G=B$ となる $G\in S_i(\mathcal F)$ をとり、$G=S_i(F)$（$F\in\mathcal F$）とする。$F$ と $S_i(F)$ の違いは高々 $i$ だけで $i\notin T$ だから、$T\cap F=T\cap G=B$ である。
$i\in T$ の場合． まず次を確かめる：$G\in S_i(\mathcal F)$ が $i$ を含めば、$G\in\mathcal F$ かつ $G\setminus\{i\}\in\mathcal F$ である。実際 $G=S_i(F)$ で $i\in G$ なら $F$ は置き換えられていない（置き換えると $i$ が抜ける）ので $G=F\in\mathcal F$ であり、$i\in F$ で置き換えられなかったのは $F\setminus\{i\}\in\mathcal F$ だからである。
$i\in B$ なら、$T\cap G=B$ となる $G\in S_i(\mathcal F)$ は $i$ を含むので、$G\in\mathcal F$ で $T\cap G=B$ である。$i\notin B$ なら、$T\cap G=B\cup\{i\}$ となる $G\in S_i(\mathcal F)$ をとる。$G$ は $i$ を含むので $G\setminus\{i\}\in\mathcal F$ であり、$T\cap(G\setminus\{i\})=B$ である。
どちらの場合も $\mathcal F$ は $T$ を打ち砕く。$\square$
すべての $i\in X$ について $S_i(\mathcal F)=\mathcal F$ なら、$\mathcal F$ は 下に閉じている、すなわち $F\in\mathcal F$、$E\subset F$ なら $E\in\mathcal F$ である。このとき $\mathcal F\subset\operatorname{sh}(\mathcal F)$ である。
$F\in\mathcal F$、$i\in F$ で $F\setminus\{i\}\notin\mathcal F$ なら、$S_i(F)=F\setminus\{i\}$ は $S_i(\mathcal F)=\mathcal F$ に属し、矛盾する。よって $\mathcal F$ の元から 1 元を抜いても $\mathcal F$ に残り、これを繰り返せば $F$ の部分集合はすべて $\mathcal F$ に属する。このとき $F\in\mathcal F$ と $B\subset F$ について $F\cap B=B\in\mathcal F$ なので、$\mathcal F$ は $F$ を打ち砕く。$\square$
$w(\mathcal G):=\sum_{G\in\mathcal G}\lvert G\rvert$ とおく。$S_i(\mathcal F)\ne\mathcal F$ なら少なくとも 1 つの元が 1 元少ない集合に置き換わり、lem-ss-size により元の個数は変わらないので、$w(S_i(\mathcal F))< w(\mathcal F)$ である。$w$ は $0$ 以上の整数なので、圧縮 $S_{i_1},S_{i_2},\dots$ を族が変わる限り施していくと有限回で止まり、どの $S_i$ でも動かない族 $\mathcal D$ に達する。lem-ss-size により $\lvert\mathcal D\rvert=\lvert\mathcal F\rvert$、lem-ss-shatter を繰り返し使って $\operatorname{sh}(\mathcal D)\subset\operatorname{sh}(\mathcal F)$ である。lem-ss-downclosed により
$$
\lvert\mathcal F\rvert=\lvert\mathcal D\rvert\le\lvert\operatorname{sh}(\mathcal D)\rvert\le\lvert\operatorname{sh}(\mathcal F)\rvert
$$
となる。$\square$
Alo83 Theorem 1（pp. 199–200）は、各座標が $0,\dots,p_i-1$ の値をとるベクトルの族に対して、「値を $1$ 増やし、増やした結果が族になければ置き換える」操作で単調な族に移しても、どの座標の集合への射影の個数も増えないことを示し、その Remark (1)（p. 201）で Sauer–Shelah の補題を導いている。上の $S_i$ は、すべての $p_i=2$ の場合に補集合をとって向きを逆にした同じ操作である。
帰納法による別証明
要点：1 点 $x$ を除いた集合への跡と、「$x$ を入れても抜いても $\mathcal F$ に残る」集合の族に分け、後者の VC 次元が 1 下がることを使う。
詳しい証明を開く
thm-ss-main を $n+d$ についての帰納法で示す。$n=0$ なら $\lvert\mathcal F\rvert\le1=\Phi_d(0)$、$d=0$ なら、2 つの異なる元 $F\ne G$ があれば $x\in F\triangle G$ について $\{x\}$ が打ち砕かれるので $\lvert\mathcal F\rvert\le1=\Phi_0(n)$ である。$n,d\ge1$ とし、$x\in X$、$X':=X\setminus\{x\}$ とする。$\mathcal F_1:=\mathcal F|_{X'}$、$\mathcal F_2:=\{E\subset X'\mid E\in\mathcal F\ \text{かつ}\ E\cup\{x\}\in\mathcal F\}$ とおく。
$E\in\mathcal F_1$ の逆像 $\{F\in\mathcal F\mid F\cap X'=E\}$ は $E$ と $E\cup\{x\}$ のうち $\mathcal F$ に属するものなので、元は 1 個か 2 個で、2 個になるのは $E\in\mathcal F_2$ のときである。よって $\lvert\mathcal F\rvert=\lvert\mathcal F_1\rvert+\lvert\mathcal F_2\rvert$ である。$\mathcal F_1$ が打ち砕く集合は $\mathcal F$ も打ち砕くので $\operatorname{VC}(\mathcal F_1)\le d$ である。$\mathcal F_2$ が $T\subset X'$ を打ち砕けば、$B\subset T$ について $T\cap E=B$ となる $E\in\mathcal F_2$ の $E$ と $E\cup\{x\}$ はともに $\mathcal F$ に属するので、$\mathcal F$ は $T\cup\{x\}$ を打ち砕く。よって $\mathcal F_2$ が空でなければ $\operatorname{VC}(\mathcal F_2)\le d-1$ であり、空なら $\lvert\mathcal F_2\rvert=0$ である。帰納法の仮定とパスカルの関係式 $\binom{n-1}{i}+\binom{n-1}{i-1}=\binom ni$ により $\lvert\mathcal F\rvert\le\Phi_d(n-1)+\Phi_{d-1}(n-1)=\Phi_d(n)$ である。$\square$
この筋は HW87 Lemma 3.1（p. 133）の証明と同じで、SSBD14 Lemma 6.10 の証明も同じ分け方で thm-ss-pajor の形を帰納法で示している。
等号の例
- $X$ を $n$ 元集合、$0\le d\le n$ とし、$\mathcal F$ を $d$ 元以下の部分集合の全体とする。$d$ 元集合 $A$ は、$B\subset A$ について $A\cap B=B$ なので打ち砕かれ、$d+1$ 元集合 $T$ は、跡が $T$ 自身になる元（$T$ を含む $d$ 元以下の集合）がないので打ち砕かれない。よって $\operatorname{VC}(\mathcal F)=d$ で、$\lvert\mathcal F\rvert=\Phi_d(n)$ である。
- 実数 $x_1< \cdots< x_n$ の集合 $A$ と、半直線 $(-\infty,t]$ の族 $\mathcal F$ では、跡は $\emptyset$ と $\{x_1,\dots,x_j\}$（$1\le j\le n$）の $n+1=\Phi_1(n)$ 個である。有界閉区間の族では、跡は $\emptyset$ と $\{x_i,\dots,x_j\}$（$i\le j$）で、$1+n+\binom n2=\Phi_2(n)$ 個である。VC 次元はそれぞれ $1$、$2$ なので（VC次元 の例「半直線と区間」）、どちらも等号が成り立つ。
1 により、thm-ss-main の上界は、どの $n$ と $0\le d\le n$ についても改良できない。
二項係数の和の評価
$1\le d\le n$ なら $\Phi_d(n)\le\left(\dfrac{en}d\right)^d$ である。
$0< d/n\le1$ なので、$i\le d$ について $(d/n)^d\le(d/n)^i$ である。二項定理 と $1+t\le e^t$ により
$$
\Bigl(\frac dn\Bigr)^d\Phi_d(n)\le\sum_{i=0}^{d}\binom ni\Bigl(\frac dn\Bigr)^i\le\sum_{i=0}^{n}\binom ni\Bigl(\frac dn\Bigr)^i=\Bigl(1+\frac dn\Bigr)^n\le e^d
$$
である。両辺に $(n/d)^d$ を掛ければよい。$\square$
$d$ を固定すれば、$\operatorname{VC}(\mathcal F)\le d$ の族の跡は $n$ 点の上で $O(n^d)$ 個しかない。これが VC次元 の ε-ネット定理と学習理論の基本定理の証明で、跡の個数を数える段に使われる（HW87 p. 137、SSBD14 §6.5）。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-ss-main の「$\operatorname{VC}(\mathcal F)\le d$」 | $n$ 元集合の冪集合 $2^X$（$d< n$） | $\lvert\mathcal F\rvert=2^n>\Phi_d(n)$ |
| prop-ss-estimate の「$d\le n$」 | $d=2$、$n=1$ | $\Phi_2(1)=2>(e/2)^2$ |
$\lvert\mathcal F\rvert\le\Phi_d(n)$ でも $\operatorname{VC}(\mathcal F)\le d$ とは限らない。$X=\{1,2,3\}$、$d=1$、$\mathcal F:=2^{\{1,2\}}$ とすると、$\lvert\mathcal F\rvert=4=\Phi_1(3)$ だが、$\mathcal F$ は $\{1,2\}$ を打ち砕くので $\operatorname{VC}(\mathcal F)=2$ である。
双対 VC 次元と NIP 理論
$\mathcal F$ の 双対族 を、$x\in X$ に $x^*:=\{F\in\mathcal F\mid x\in F\}$ を対応させた $\mathcal F$ の部分集合の族 $\mathcal F^*:=\{x^*\mid x\in X\}$ とし、$\operatorname{VC}^*(\mathcal F):=\operatorname{VC}(\mathcal F^*)$ を 双対 VC 次元 という。有限の $\mathcal G\subset\mathcal F$ が $\mathcal F^*$ に打ち砕かれることは、どの $\mathcal G'\subset\mathcal G$ にも「$\mathcal G$ のうち $x$ を含むものがちょうど $\mathcal G'$」となる点 $x$ があることである。次の評価により、VC 次元と双対 VC 次元は同時に有限になる（$x\mapsto x^*$ が単射なら、$\mathcal F^*$ の双対族は $\mathcal F$ と同じ形の族なので、逆向きの評価も同じ命題から従う。単射でないときは、$x^*=y^*$ となる相異なる 2 点を同時に含む集合は打ち砕かれないので、$x^*$ の値ごとに 1 点を選んだ集合 $X'$ に制限しても $\operatorname{VC}$ と $\operatorname{VC}^*$ は変わらず、単射の場合に帰着する）。
$\operatorname{VC}(\mathcal F)=d< \infty$ なら $\operatorname{VC}^*(\mathcal F)< 2^{d+1}$ である。
要点：$2^k$ 個の集合を $k$ 元集合の部分集合で番号づけて双対の意味で打ち砕かれれば、「$i$ を含む番号の集合だけに入る点」$x_i$ が $k$ 個とれ、それらが $\mathcal F$ に打ち砕かれる。
詳しい証明を開く
$\operatorname{VC}^*(\mathcal F)\ge2^k$ とする。打ち砕かれる集合の部分集合も打ち砕かれるので、元の個数がちょうど $2^k$ の $\mathcal G\subset\mathcal F$ で $\mathcal F^*$ に打ち砕かれるものがあり、その元を $\{1,\dots,k\}$ の部分集合 $B$ で $G_B$ と番号づける。各 $i\le k$ について、$\mathcal G$ のうち $x_i$ を含むものがちょうど $\{G_B\mid i\in B\}$ となる点 $x_i\in X$ をとる。$i\ne j$ なら $i\in B$、$j\notin B$ となる $B$ について $x_i\in G_B$、$x_j\notin G_B$ なので、$x_1,\dots,x_k$ は相異なる。$B\subset\{1,\dots,k\}$ について $G_B\cap\{x_1,\dots,x_k\}=\{x_i\mid i\in B\}$ なので、$\mathcal F$ は $k$ 元集合 $\{x_1,\dots,x_k\}$ を打ち砕き、$k\le d$ である。$\operatorname{VC}^*(\mathcal F)\ge2^{d+1}$ なら $k=d+1$ ととれて矛盾する。$\square$
モデル理論では、完全な理論 $T$ の論理式 $\varphi(x;\bar y)$ と $T$ のモデル $M$ について、$M$ の部分集合の族 $\{\varphi(M;\bar b)\mid\bar b\in M^r\}$（$r\ge1$ は $\bar y$ の長さ、$\varphi(M;\bar b):=\{a\in M\mid M\models\varphi(a;\bar b)\}$）の VC 次元を考える。「$n$ 元集合が打ち砕かれる」ことは 1 つの文で書け、$T$ は完全なので、この VC 次元は $M$ によらない。それが有限のとき $\varphi$ は NIP、無限のとき 独立性（independence property、IP）をもつといい、すべての論理式が NIP である理論を NIP 理論という（Sim14 Definition 2.1・Remark 2.3・Definition 2.10、pp. 13–16。$x$ を変数の組にしても同様に定義される）。論理式とその変数の役割を入れ替えた論理式の NIP は同値であり（同 Lemma 2.5、p. 14）、これは prop-ss-dual の論理式版にあたる。安定性理論 の安定な理論は NIP である（prop-ss-stable）。稠密な線形順序の理論は安定でない（安定性理論 の例「稠密な線形順序」と定理「順序性をもつ理論は安定でない」）が、$x< y$ の定める半直線の族の VC 次元は $1$ で、o-minimal構造 の理論はどれも NIP である（Sim14 Example 2.4・2.12、pp. 14、17）。ランダムグラフの理論の辺の関係 $xRy$ は独立性をもつ（同 Example 2.4）。Perles と Shelah がこの補題を示したのも、安定な理論の研究の中であった（SSBD14 §6.7）。
可算な一階言語の完全な理論 $T$ が無限のモデルをもち、ある無限基数で安定なら、$x$ を 1 変数とするどの論理式 $\varphi(x;\bar y)$ も NIP である。
要点：打ち砕かれる点列があれば、始切片を切り出すパラメータを並べて順序性が得られる。
詳しい証明を開く
$\varphi$ が独立性をもつとする。新しい定数記号 $c_i$ と $r$ 個組の定数記号 $\bar d_j$（$i,j\in\mathbb N$）を加え、$\Sigma:=T\cup\{\varphi(c_i;\bar d_j)\mid i< j\}\cup\{\lnot\varphi(c_i;\bar d_j)\mid j\le i\}$ とおく。$\Sigma$ の有限部分集合に現れる添字が $n$ 未満なら、$T$ のモデル $M$ で打ち砕かれる $n$ 元集合 $\{a_0,\dots,a_{n-1}\}$ をとり、$\{a_0,\dots,a_{j-1}\}$ を切り出すパラメータを $\bar b_j$ とすれば、$c_i\mapsto a_i$、$\bar d_j\mapsto\bar b_j$ でこの有限部分集合は満たされる（$M\models\varphi(a_i;\bar b_j)\iff i< j$）。コンパクト性定理(一階論理) により $\Sigma$ はモデルをもち、そこで $\varphi$ は 安定性理論 の定義「順序性」の意味の順序性をもつ。同じ記事の定理「順序性をもつ理論は安定でない」により $T$ はどの無限基数でも安定でなく、仮定に反する。$\square$
変数の組 $\bar x$ についての論理式に広げるには、$\bar x$ が 1 変数の論理式だけを調べれば十分であること（Sim14 Proposition 2.11 と Lemma 2.5）を使う。
関連項目
- 前提: VC次元, 二項係数, 集合族
- 道具: 二項定理, 数学的帰納法
- 比較: Spernerの定理, 安定性理論
- 発展: o-minimal構造, モデル理論, 組合せ論
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
