Higmanの補題

同義語:Higman's lemma

概要

Higmanの補題(Higman's lemma)とは、整擬順序集合 $X$ の元の有限列の全体が、文字を飛ばして各文字を大きいか等しい文字に対応させる埋め込み(部分列の順序)について、再び整擬順序になるという定理である。整擬順序とは、どの無限列にも前の項が後の項以下になる 2 項がある擬順序をいう。Nash-Williams の極小悪列の論法で証明され、積の整擬性(Dickson の補題)や、有限アルファベット上のどんな言語も部分語について下方に閉じれば正規言語になることが系として従う。根付き木への一般化が Kruskal の木定理である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 擬順序, 部分列, 数学的帰納法と整列性

Higman の補題(Higman's lemma)は、比べ方(擬順序)の与えられた集合 $X$ の元を並べた有限列どうしを、「一方を、文字を飛ばしながら他方の中に、各文字を大きいか等しい文字に対応させて埋め込めるか」で比べるとき、$X$ が 整擬順序(どんな無限列にも、前の項が後の項以下になる 2 項がある)なら、有限列の全体も整擬順序になるという定理である。たとえば 2 文字 $a,b$ の語をどれだけたくさん並べても、ある語が後のある語の(飛び飛びの)部分列として現れる。
整擬順序は、整列順序 や整礎関係の「無限に下がり続けない」という性質に、「比べられない元が無限にはない」という性質を合わせたものである。有限の組合せ的対象(語、木、グラフ)の集合が整擬順序であることを示す定理は、Kruskal の木定理(Kruskalの木定理)、Robertson–Seymour のグラフマイナー定理(グラフマイナー)と続く。Higman の補題はその最初の段であり、証明に使う Nash-Williams の 極小悪列 の論法は、木定理の証明でもそのまま使われる。
この記事では、整擬順序の言い換えを示し、Higman の補題を極小悪列の論法で証明する。系として、積の整擬性(Dickson の補題)、有限部分集合の整擬性、部分語の順序についての「どんな言語の下方閉包も正規言語」という定理を導く。最後に、有限列を無限列に替えると結論が成り立たなくなる例などを反例の表にまとめる。

名前と分担

群論の Higman の埋め込み定理(有限生成群の再帰的表示と有限表示群への埋め込み)とは別の結果である。グラフマイナー の記事は整擬順序の定義とグラフマイナー定理の主張を述べている。この記事は語(有限列)の場合を扱い、根付き木の場合は Kruskalの木定理 の記事が扱う。$\mathbb{Z}_{\ge0}^n$ の場合(Dickson の補題)は 単項式順序 の記事が単項式の言葉で証明しており、ここでは系として別の証明を与える。

定義

整擬順序

集合 $X$ の上の反射的かつ推移的な関係 $\le$ を 擬順序 という。$x\le y$ かつ $y\not\le x$ のとき $x< y$ と書く。$X$ の無限列 $x_0,x_1,x_2,\dots$ について、$i< j$ かつ $x_i\le x_j$ となる組 $(x_i,x_j)$ を よい組 という。よい組をもつ無限列を よい列、もたない無限列を 悪い列 という。悪い列をもたない擬順序を 整擬順序(well-quasi-ordering)という。

部分列の埋め込み

$(X,\le)$ を擬順序集合とし、$X$ の元の有限列(長さ $0$ の空列を含む)の全体を $X^*$ と書く。$X^*$ の元を 語 ともよび、$u=(u_1,\dots,u_m)$ の長さを $|u|=m$ と書く。$u=(u_1,\dots,u_m)$、$v=(v_1,\dots,v_n)$ について、狭義単調増加な写像 $\iota\colon\{1,\dots,m\}\to\{1,\dots,n\}$ で、すべての $i$ について $u_i\le v_{\iota(i)}$ となるものがあるとき、$u\le^* v$ と書く。

恒等写像により $u\le^*u$ であり、二つの $\iota$ を合成すると推移律が出るので、$\le^*$ は $X^*$ の擬順序である。空列はどの語に対しても $\le^*$ の左辺になる。$X$ が有限集合(アルファベット)で $\le$ が等号のときは、$u\le^* v$ は「$u$ が $v$ の文字をいくつか消して得られる」ことであり、この順序を 部分語の順序 という。このとき $u\le^*v$ と $v\le^*u$ が同時に成り立てば長さが等しく $u=v$ なので、$\le^*$ は半順序である。

整擬順序の例と、そうでない例
  1. 有限集合の上の擬順序はすべて整擬順序である。無限列のどこかに同じ元が 2 回現れ、反射律からよい組になる。
  2. $(\mathbb{N},\le)$ は整擬順序である。無限列 $(x_n)$ の値の最小値(自然数の整列性による)をとる項を $x_m$ とすると、$x_m\le x_{m+1}$ なので $(x_m,x_{m+1})$ がよい組である。より一般に、整列順序は整擬順序である(prop-hig-equiv の 3 による)。
  3. $(\mathbb{Z},\le)$ は整擬順序でない。$0,-1,-2,\dots$ は悪い列である。
  4. 自然数の上の「割り切る」の関係は整擬順序でない。素数を小さい順に並べた列は、どの 2 項も割り切り合わないので悪い列である。

整擬順序の言い換え

増加部分列

$(X,\le)$ が整擬順序なら、$X$ の任意の無限列 $(x_n)$ は、$n_0< n_1< n_2<\cdots$ で $x_{n_0}\le x_{n_1}\le x_{n_2}\le\cdots$ となる無限部分列をもつ。

後ろによい相手をもたない番号は有限個

番号 $n$ を、$m>n$ かつ $x_n\le x_m$ となる $m$ がないとき 行き止まり とよぶ。行き止まりの番号は有限個である。実際、無限個あるなら、それらを小さい順に $k_0< k_1<\cdots$ と並べた部分列 $(x_{k_i})$ は $X$ の無限列であり、整擬性から $i< j$ で $x_{k_i}\le x_{k_j}$ となるものがあるが、これは $k_i$ が行き止まりであることに反する。
そこで、すべての行き止まりの番号より大きい $N$ をとり、$n_0:=N$ とする。$n_t$ まで定まり $n_t\ge N$ なら、$n_t$ は行き止まりでないので、$m>n_t$ で $x_{n_t}\le x_m$ となる $m$ があり、その最小のものを $n_{t+1}$ とする。こうして得た部分列が求めるものである。$\square$

整擬順序の同値な条件

擬順序集合 $(X,\le)$ について、次は同値である。

  1. $(X,\le)$ は整擬順序である。
  2. $X$ の任意の無限列は、$\le$ について単調増加な無限部分列をもつ。
  3. $X$ には、どの 2 つも比べられない元の無限列(無限の反鎖)も、狭義単調減少な無限列 $x_0>x_1>x_2>\cdots$ もない。

1 ⇒ 2 は lem-hig-increasing である。2 ⇒ 1 は、単調増加な部分列の最初の 2 項がよい組になることによる。1 ⇒ 3:無限の反鎖も狭義減少列も悪い列である。
3 ⇒ 1:無限列 $(x_n)$ をとり、$i< j$ の組 $\{i,j\}$ を、$x_i\le x_j$ なら色 1、$x_i>x_j$ なら色 2、$x_i$ と $x_j$ が比べられなければ色 3 で塗る($x_i\not\le x_j$ かつ $x_j\le x_i$ が $x_i>x_j$ なので、3 色で尽くされる)。Ramseyの定理 の定理「無限 Ramsey の定理」により、無限集合 $H\subset\mathbb{N}$ で、$H$ の 2 元部分集合がすべて同じ色のものがある。$H$ の元を小さい順にたどった部分列は、色 2 なら狭義減少列、色 3 なら無限の反鎖であり、3 の仮定から色は 1 である。よって $(x_n)$ はよい組をもつ。$\square$

この命題は Die25 Proposition 12.1.1・Corollary 12.1.2(p. 364)にある。同書は 1 ⇒ 2 も Ramsey の定理から導いているが、上の補題の証明は Ramsey の定理を使わない(同書の演習 3、p. 405 が求める形)。3 の後半は「$<$ が整礎関係である」ことと同じである。

主定理

Higman の補題

$(X,\le)$ が整擬順序なら、$(X^*,\le^*)$ も整擬順序である。

証明は背理法による。悪い列があると仮定し、その中で「各項がなるべく短い」ものを選ぶ。その列の各語から先頭の文字を取り除くと、より短い語の列ができ、選び方の極小性からそれはよい列になる。そのよい組に先頭の文字を戻すと、もとの列のよい組が得られて矛盾する。

極小悪列の論法

$(X^*,\le^*)$ に悪い列があると仮定する。語の列 $w_0,w_1,w_2,\dots$ を次のように帰納的に選ぶ。$w_0,\dots,w_{n-1}$ まで選ばれ、それで始まる悪い列があるとする($n=0$ では仮定による)。そのような悪い列の $n$ 番目の項として現れる語のうち、長さが最小のものを $w_n$ とする。すると $w_0,\dots,w_n$ で始まる悪い列があるので、選び方を続けられる。
(a) $(w_n)$ は悪い列である。 $i< j$ とすると、$w_0,\dots,w_j$ で始まる悪い列があり、$(w_i,w_j)$ はその列の組なのでよい組でない。
(b) どの $w_n$ も空列でない。 空列 $w_n$ は $w_n\le^*w_{n+1}$ を満たし、(a) に反する。
そこで $w_n$ の先頭の文字を $a_n\in X$、残りの語を $v_n$ と書く($w_n=(a_n)$ のとき $v_n$ は空列)。$\iota(i)=i+1$ により $v_n\le^*w_n$ であり、$|v_n|=|w_n|-1$ である。
(c) lem-hig-increasing を $(a_n)$ に使い、$n_0< n_1<\cdots$ で $a_{n_0}\le a_{n_1}\le\cdots$ となるものをとる。語の列
$$w_0,\dots,w_{n_0-1},\ v_{n_0},\ v_{n_1},\ v_{n_2},\dots$$
を考える。これは $w_0,\dots,w_{n_0-1}$ で始まり、$n_0$ 番目の項 $v_{n_0}$ は $w_{n_0}$ より短い。$w_{n_0}$ の選び方から、この列は悪い列でなく、よい組をもつ。よい組の形で場合を分ける。
・$(w_i,w_j)$($i< j< n_0$):(a) に反する。
・$(w_i,v_{n_t})$($i< n_0$):$w_i\le^*v_{n_t}\le^*w_{n_t}$ で $i< n_0\le n_t$ なので、(a) に反する。
・$(v_{n_s},v_{n_t})$($s< t$):$v_{n_s}\le^*v_{n_t}$ を与える狭義増加写像を $\iota$ とする。$w_{n_s}$ の 1 文字目を $w_{n_t}$ の 1 文字目に、$w_{n_s}$ の $i+1$ 文字目を $w_{n_t}$ の $\iota(i)+1$ 文字目に送る写像は狭義増加で、$a_{n_s}\le a_{n_t}$ と合わせて $w_{n_s}\le^*w_{n_t}$ を与える。$n_s< n_t$ なので (a) に反する。
いずれの場合も矛盾するので、悪い列はない。$\square$

証明の所在と論法の名前

Die25 は Lemma 12.1.3(pp. 364–365)で、有限部分集合の場合(下の cor-hig-subsets)を同じ論法で証明し、第 12 章の注(p. 412)でこれを Higman の補題とよび、論法を Nash-Williams に帰している。上の証明は、その論法を有限列に合わせて書き直したものである。列 $(w_n)$ を 1 項ずつ選ぶところで、従属選択(従属選択公理)を使っている。

系

積と Dickson の補題

$(X,\le)$ と $(Y,\le)$ が整擬順序なら、$X\times Y$ に成分ごとの順序($(x,y)\le(x',y')\iff x\le x'$ かつ $y\le y'$)を入れたものも整擬順序である。とくに $\mathbb{N}^k$ は成分ごとの順序について整擬順序である(Dickson の補題)。

証明を開く

無限列 $(x_n,y_n)$ をとる。lem-hig-increasing により $n_0< n_1<\cdots$ で $x_{n_0}\le x_{n_1}\le\cdots$ となるものがある。$(y_{n_t})_t$ は $Y$ の無限列なので、$s< t$ で $y_{n_s}\le y_{n_t}$ となるものがあり、$(x_{n_s},y_{n_s})\le(x_{n_t},y_{n_t})$ である。$\mathbb{N}^k$ は $(\mathbb{N},\le)$(ex-hig-basic の 2)から $k$ に関する帰納法で従う。$\square$

単項式順序 の記事の定理「Dickson の補題」は、$\mathbb{Z}_{\ge0}^n$ の任意の部分集合が有限個の元の上方に含まれることを述べている。これは、極小元の集合が反鎖で有限になることを通じて、上の系と同じ内容である。

有限部分集合

$(X,\le)$ を整擬順序とし、$X$ の有限部分集合の全体を $[X]^{<\omega}$ と書く。$A,B\in[X]^{<\omega}$ について、単射 $f\colon A\to B$ で各 $a\in A$ について $a\le f(a)$ となるものがあるとき $A\le B$ と定める。$([X]^{<\omega},\le)$ は整擬順序である。

証明を開く

各有限集合 $A$ の元を何らかの順に並べた語を $w(A)$ とする。$[X]^{<\omega}$ の無限列 $(A_n)$ について、thm-hig-main から $i< j$ で $w(A_i)\le^*w(A_j)$ となるものがある。それを与える狭義増加写像 $\iota$ は、$w(A_i)$ の $k$ 文字目を $w(A_j)$ の $\iota(k)$ 文字目に送るので、$A_i$ から $A_j$ への単射 $f$ で $a\le f(a)$ となるものを与える。$\square$

これが Die25 Lemma 12.1.3(p. 364)の主張である。同じ議論で、有限多重集合(同じ元を何度も含んでよい有限集合)についても同様のことがいえる。

部分語の順序と正規言語

$\Sigma$ を有限のアルファベットとし、$\Sigma^*$ に部分語の順序 $\le^*$ を入れる。

  1. $L\subseteq\Sigma^*$ の極小元の集合 $\min L$ は有限であり、$L$ のどの元も $\min L$ のある元以上である。
  2. 任意の $L\subseteq\Sigma^*$ について、その下方閉包 ${\downarrow}L:=\{u\in\Sigma^*\mid$ ある $v\in L$ について $u\le^*v\}$ は正規言語である。
上方に閉じた集合は有限個の語で決まる

1:$\Sigma$ は有限なので等号について整擬順序であり(ex-hig-basic の 1)、thm-hig-main により $(\Sigma^*,\le^*)$ は整擬順序である。$\le^*$ は半順序なので、$\min L$ の相異なる元は比べられず、$\min L$ は反鎖である。prop-hig-equiv の 3 により $\min L$ は有限である。$v\in L$ について、$v$ 以下の $L$ の元のうち長さ最小のもの $u$ をとると、$u$ より真に小さい語は $u$ より短いので、$u\in\min L$ である。
2:$C:=\Sigma^*\setminus{\downarrow}L$ とおく。$c\in C$ かつ $c\le^*c'$ なら $c'\in C$ である($c'\in{\downarrow}L$ なら推移律から $c\in{\downarrow}L$ となる)。よって 1 から、$C$ は有限個の語 $c\in\min C$ について $\{c'\mid c\le^*c'\}$ を合わせたものに等しい。$c=c_1c_2\cdots c_m$ について、この集合は正規表現 $\Sigma^*c_1\Sigma^*c_2\cdots\Sigma^*c_m\Sigma^*$ の表す言語である。正規言語は有限個の和で閉じるので $C$ は正規言語であり、補集合をとっても閉じるので ${\downarrow}L$ も正規言語である(正規言語 の命題「和・連接・Kleene 閉包に関する閉包性」「補集合・共通部分・差に関する閉包性」)。$\square$

$L$ 自身が正規言語である必要はない。どんな言語も、文字を消す操作で閉じたものに広げると、有限オートマトンで認識できるようになる。

例

$a^nb^n$ の下方閉包

$\Sigma=\{a,b\}$、$L=\{a^nb^n\mid n\ge1\}$ とする。$L$ は正規言語でない(正規言語の反復補題 による標準的な例)。$a^nb^n$ から文字を消すと $a^ib^j$($i,j\le n$)の形になり、逆に $a^ib^j\le^*a^nb^n$($n=\max(i,j,1)$)なので、${\downarrow}L=\{a^ib^j\mid i,j\ge0\}$ であり、これは正規表現 $a^*b^*$ の表す正規言語である。補集合 $C$ は「$b$ の後に $a$ が現れる」語の全体で、$\min C=\{ba\}$ である。
また $\min L=\{ab\}$ であり、上方閉包は $\Sigma^*a\Sigma^*b\Sigma^*$、すなわち「$a$ の後に $b$ が現れる」語の全体である。

悪い列を作ろうとしても止まる

$\Sigma=\{a,b\}$ で、悪い列をなるべく長く作ってみる。悪い列では、後に置く語は前のどの語も部分語として含んではいけない。$aa$、$ab$、$ba$、$bb$ と置くと、長さ 2 以上の語は最初の 2 文字としてこのどれかを部分語に含むので、次に置けるのは $a$、$b$、空列だけである。$a$ を置くと次は $a$ を含まない語、つまり $b^j$ に限られ、$j\ge2$ は $bb$ を含むので $b$ か空列になる。こうして $aa,ab,ba,bb,a,b,\varepsilon$($\varepsilon$ は空列)まで来ると、どの語も $\varepsilon$ を部分語に含むので、もう続けられない。thm-hig-main は、どんな作り方をしても悪い列が有限で止まることを保証している。

反例の表

外す・変える条件例成り立たなくなること
$X$ が整擬順序$X=\mathbb{N}$ に等号の順序結論。1 文字の語 $(0),(1),(2),\dots$ が悪い列
埋め込みが飛び飛びでよい(部分列)連続した部分(因子)の順序、$\Sigma=\{a,b\}$結論。$ab^na$($n\ge1$)がどの 2 つも比べられない
列が有限長さ $\omega$ の無限列、下の整擬順序 $R$ の上結論。$R^\omega$ に悪い列がある
反例の確認
確認を開く

1 行目:等号の順序では 1 文字の語 $(i)\le^*(j)$ は $i=j$ のときに限る。$\mathbb{N}$ に等号を入れたものは無限の反鎖で、整擬順序でない。外したのはこの仮定だけである。

2 行目:語 $u$ が語 $v$ の中に連続して現れるとき $u$ を $v$ の因子という。$m< n$ のとき、$ab^ma$ が $ab^na$ の因子なら、その位置は 2 つの $a$ を含むので $ab^na$ の 2 つの $a$ に重なり、$ab^na$ 全体になって長さが合わない。$ab^na$ は長さが $ab^ma$ より長いので、$ab^ma$ の因子にならない。

3 行目:$R:=\{(i,j)\in\mathbb{N}^2\mid i< j\}$ に、$(i,j)\le(k,l)$ を「$i=k$ かつ $j\le l$」または「$j< k$」で定める。反射的であり、推移律は場合を分けて確かめられる($(i,j)\le(k,l)\le(p,q)$ で、後半が $l< p$ なら $j\le l< p$ または $j< k< l< p$ から $j< p$)。$R$ は整擬順序である。無限列 $(i_n,j_n)$ で、$i_n$ が有界なら同じ $i$ が無限回現れ、その $j$ の列から $j\le j'$ となる組がとれる。$i_n$ が有界でないなら $i_m>j_0$ となる $m>0$ があり、$(i_0,j_0)\le(i_m,j_m)$ である。一方、無限列 $u=(u_0,u_1,\dots)$、$v$ について、狭義増加写像 $\iota\colon\mathbb{N}\to\mathbb{N}$ で $u_t\le v_{\iota(t)}$ となるものがあるとき $u\le^\omega v$ と定め、$w_i:=((i,i+1),(i,i+2),(i,i+3),\dots)$ とおく。$i< k$ のとき、$(i,j)\le(k,l)$ には $j< k$ が要るので、$w_i$ の項のうち $(k,\cdot)$ の形の項以下になるものは有限個で、$w_i\le^\omega w_k$ でない。$(k,j)\le(i,l)$ には $j< i$ が要るが $j>k>i$ なので、$w_k\le^\omega w_i$ でもない。よって $(w_i)$ は悪い列である。

3 行目のように、無限の対象に移ると整擬性は保たれないことがある。Nash-Williams は Kruskal の定理を無限の木へ拡張する証明で、整擬順序より強い 良擬順序(better-quasi-ordering)の概念を導入した(Die25 第 12 章の注、p. 412)。

補足

  • 木への一般化:語は、各頂点に $X$ の元を付けた根付きの道とみなせる。道を根付き木に替えたものが Kruskalの木定理 で、その証明は Higman の補題を使う。
  • 整礎性との関係:整擬順序では $<$ が整礎的なので、整擬順序集合の上で整礎関係による帰納法が使える。とくに部分語の順序で上方に閉じた集合は、有限個の語で決まる(cor-hig-regular の 1)。

関連項目

参考文献

[1]
Reinhard Diestel, Graph Theory, 6th edition, Graduate Texts in Mathematics 173, Springer, 2025, §12.1(Proposition 12.1.1・Corollary 12.1.2・Lemma 12.1.3、pp. 364–365)、第 12 章の演習 3(p. 405)、第 12 章の注(p. 412)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する