ヒグマンの補題

数学において、ヒグマンの補題は、有限アルファベット 上の有限シーケンスの集合が、部分列関係によって部分的に順序付けられている場合、準順序付けされていることを示している。つまり、 が有限アルファベット 上の無限単語シーケンスである場合、 からいくつかの (場合によってはゼロの) 記号を削除することによって得られるようなインデックスが存在する。より一般的には、 が必ずしも有限ではないがそれ自体準順序付けされている場合にもこれは当てはまり、部分列関係は、 の準順序付けにおいて記号を前の記号で置き換えることを可能にする「埋め込み」関係に一般化される。これは、後のクラスカルの木定理の特殊なケースである。これは、1952 年にこれを発表したグラハム・ヒグマンにちなんで名付けられた。 ${\displaystyle \Sigma ^{*}}$${\displaystyle \Sigma }$${\displaystyle w_{1},w_{2},\ldots \in \Sigma ^{*}}$${\displaystyle \Sigma }$${\displaystyle i<j}$${\displaystyle w_{i}}$${\displaystyle w_{j}}$${\displaystyle \Sigma }$${\displaystyle \Sigma }$

を準整列した記号のアルファベットとします（特に、 は有限で恒等関係で順序付けられている可能性があります）。矛盾として、無限の悪いシーケンス、つまりが後の に埋め込まれないような無限の単語シーケンスが存在するとします。すると、次の意味で最小である無限の悪い単語シーケンスが存在します。は、無限の悪いシーケンスで始まるすべての単語の中から最小の長さの単語です。 は、で始まるすべての無限の悪いシーケンスの中から最小の長さの単語です。 は、 で始まるすべての無限の悪いシーケンスの中から最小の長さの単語です。などです。一般に、は、で始まるすべての無限の悪いシーケンスの中から最小の長さの単語です。 ${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle w_{1},w_{2},w_{3},\ldots \in \Sigma ^{*}}$${\displaystyle w_{i}}$${\displaystyle w_{j}}$${\displaystyle W=(w_{1},w_{2},w_{3},\ldots )}$${\displaystyle w_{1}}$${\displaystyle w_{2}}$${\displaystyle w_{1}}$${\displaystyle w_{3}}$${\displaystyle w_{1},w_{2}}$${\displaystyle w_{i}}$${\displaystyle w_{1},\ldots ,w_{i-1}}$

は空語にはなり得ないので、 およびについてと書くことができます。は準順序付けされているため、先頭の記号のシーケンスには を含む無限増加シーケンスが含まれている必要があります。 ${\displaystyle w_{i}}$${\displaystyle w_{i}=a_{i}z_{i}}$${\displaystyle a_{i}\in \Sigma }$${\displaystyle z_{i}\in \Sigma ^{*}}$${\displaystyle \Sigma }$${\displaystyle a_{1},a_{2},a_{3},\ldots }$ ${\displaystyle a_{i_{1}}\leq a_{i_{2}}\leq a_{i_{3}}\leq \cdots }$${\displaystyle i_{1}$

ここで、単語のシーケンスについて考えます。は より短い ため、このシーケンスは より「最小限」であり、したがって、後の単語 に埋め込まれる単語が含まれている必要があります。 しかし、 と は両方とも になることはできません。その場合、元のシーケンスは悪くありません。 同様に、が でありであるということはあり得ません。その場合、も に埋め込まれるためです。 また同様に、および、、になることもできません。その場合、 はに埋め込まれるためです。 どの場合も、矛盾に至ります。 $${\displaystyle w_{1},\ldots ,w_{{i_{1}}-1},z_{i_{1}},z_{i_{2}},z_{i_{3}},\ldots .}$$${\displaystyle z_{i_{1}}}$${\displaystyle w_{i_{1}}=a_{i_{1}}z_{i_{1}}}$${\displaystyle W}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w_{j}}$${\displaystyle W}$${\displaystyle u}$${\displaystyle w_{j}}$${\displaystyle v}$${\displaystyle z_{i_{k}}}$${\displaystyle w_{j}}$${\displaystyle w_{i_{k}}=a_{i_{k}}z_{i_{k}}}$${\displaystyle u=z_{i_{j}}}$${\displaystyle v=z_{i_{k}}}$${\displaystyle j<k}$${\displaystyle w_{i_{j}}=a_{i_{j}}z_{i_{j}}}$${\displaystyle w_{i_{k}}=a_{i_{k}}z_{i_{k}}}$

の順序型は、の順序型と以下のように関連している: ^{[1] [2]}${\displaystyle \Sigma ^{*}}$${\displaystyle \Sigma }$ $${\displaystyle o(\Sigma ^{*})={\begin{cases}\omega ^{\omega ^{o(\Sigma )-1}},&o(\Sigma ){\text{ 有限}};\\\omega ^{\omega ^{o(\Sigma )+1}},&o(\Sigma )=\varepsilon _{\alpha }+n{\text{ ある }}\alpha {\text{ およびある有限 }}n について;\\\omega ^{\omega ^{o(\Sigma )}},&{\text{それ以外の場合}}.\end{cases}}}$$

ヒグマンの補題は、 （ 2階算術の部分系の観点から）基底理論上のと同値として数学的に逆較正されている。^[3]${\displaystyle ACA_{0}}$${\displaystyle RCA_{0}}$

• ヒグマン、グラハム（1952）、「抽象代数における割り切れる順序」、ロンドン数学会紀要、（3）、2（7）：326–336、doi：10.1112/plms/s3-2.1.326