ブロック部分列定理


ブロック部分列定理
型	組合せ数学
急増加関数	\(f_{\omega^\omega}(n)\)

ブロック部分列定理とは、特定の性質を持つ列の長さについての定理である。数理論理学者の Harvey Friedman は、この定理を示し、これを用いて急増大する関数を構成した。^[1]

ブロック部分列定理[]

\(k\)以下の正整数のみからなる有限列\(S = s_1s_2\cdots s_n\)が以下の性質をもつとき、\(S\)はFriedman-列であるという。

任意の正整数\(i,j \le n \div 2\)に対して、\(s_is_{i+1}\cdots s_{2i-1}s_{2i}\)は\(s_js_{j+1}\cdots s_{2j-1}s_{2j}\)に埋め込めない。

ただし、「列\(X\)が列\(Y\)に埋め込める」とは、\(Y\)からいくつかの文字を取り除いたとき、\(X\)と等しくなることを指す。例えば、列\(123\)は列\(31323\)に埋め込めるが、\(32313\)には埋め込めない。

ブロック部分列定理とは、「\(k\)以下の正整数のみからなるFriedman-列には、長さに上限が存在する」という定理である。^{[注 1]}

ブロック部分列定理により、\(k\)以下の正整数のみからなるFriedman-列には、長さが最大のものが存在する。この長さを\(n(k)\)と表すことで、自然数上の関数\(n\)が定義される。

\(n(k)\)、つまり\(k\)以下の正整数のみからなるFriedman-列の最大長について、Friedmanは以下のように主張した。

\(111\)は\(1\)以下の正整数のみからなるFriedman-列のうち長さが最大のものであり、\(n(1) = 3\)である。
\(12221111111\)は\(2\)以下の正整数のみからなるFriedman-列のうち長さが最大のものの1つであり、\(n(2) = 11\)である。
\(n(3)\)は非常に大きく、\(2 \uparrow^{7197} 158386 < n(3) < 2\uparrow^{2 \uparrow^4 5} 4\)が成り立つ。^[2]^{[注 2]}
\(A(n) := 2\uparrow^{n-1}n\)とすると、\(n(4) > A^{A(187196)}(1)\)であり、特に\(n(4)\)はグラハム数よりも大きい。^{[注 3]}
\(H\)をハーディ階層とすると、任意の\(\beta < \omega^\omega\)について関数\(n\)は\(H_{\omega^\beta}\)を支配する。また、関数\(n\)は\(H_{\omega^{\omega^\omega+1}}\)に支配される。

関数\(n\)は\(WPO\)に関する定理を用いて定義されている。その点で、同じくFriedmanによって定義された\(\textrm{tree}\)関数や\(\textrm{SCG}\)関数などと関係している。なお、\(\textrm{tree}\)関数は、\(n\)よりも非常に速く増加する。