支配

支配 (domination) ，あるいは最終的支配 (eventual domination) は関数同士の増大度を測るひとつの方法である．

定義

全順序集合$\langle A,<_A\rangle,\langle B,<_B\rangle$に対して関数$f,g\colon A\to B$を考える． 関数$f$が$g$を支配する (dominate) とは$(\exists x\in A)(\forall y\in A)[x<_A y\to g(y) <_B f(y)]$が成り立つことである．

例

自然数係数多項式関数を考える．次数が高い多項式は低い多項式を支配することや、次数が同じで最高次係数の異なる多項式同士は最高次係数が大きい方がそうでない方を支配することがわかる．例えば$f(x):=x+10^{100}$は$g(x):=2x$に支配される．

またランダウの記号も支配の変種と考えることができる．支配関係との違いは定数の違いを無視するところである．

また支配はグッドスタイン数列のペアノ算術での証明不能性の証明に応用される．

参考文献

• Odifreddi, Piergiorgio. Classical recursion theory: The theory of functions and sets of natural numbers. Elsevier, 1992.