Eventual domination is a relation describing the asymptotic behavior of two functions.[1] The function \(f\) is said to eventually dominate \(g\) if there exists a constant \(N\) such that \(f(n) > g(n)\) holds for all \(n \geq N\). That is, \(f\) asymptotically outgrows \(g\).
Theorems of the form "\(f\) eventually dominates every function with property \(P\)" are useful in formally giving a sense of scale for fast-growing functions. A common choice for \(P\) is the property of being provably recursive in certain formal theory, like Peano arithmetic or ZFC. In hypercomputable scenarios, \(P\) can be the property of being computable within a system such as Turing machines.
Over \(\mathbb{N} \rightarrow \mathbb{N}\), eventual domination is transitive relation. It is not total, since we can construct two different functions such that neither eventually dominates the other. This relation is however antisymmetric, and extending the relation to "\(f(n)\) eventually dominates \(g(n)\) or \(f(n)=g(n)\)" gives rise to a partial order.
Common Mistake[]
As the definition refers to a constant \(N\), the eventual domination does not imply the pointwise domination. In other words, even if a function \(f\) eventually dominates another function \(g\), we do not necessarily have \(f(n) > g(n)\) for small \(n\).
For example, we know that \(f_{\omega}\) eventually dominates \(f_{100}\) with respect to Wainer hierachy, but we have \(f_{\omega}(10) < f_{100}(10)\). Such a mistake is frequently made when people consider small values of large functions, e.g. \(f_{\varepsilon_0}(2)\) with respect to Wainer hierarchy and \(\textrm{TREE}[3]\).
Notation[]
There is no standard symbol for eventual domination. Radó uses \(> -\),[2] while Long and Stanley use \(>^*\).[3]
Sbiis Saibian uses \([>]\) to represent a stronger condition:[4]
\[f\,[<]\,g \Leftrightarrow \forall k,m : \exists N: \forall n: n \geq N \Rightarrow f(n + m) + k < g(n)\]
In English, \(f\,[<]\,g\) means that any translation of the graph of \(f\) horizontally or vertically will still be eventually dominated by \(g\); Saibian suggests "\(g\) grows faster than \(f\)" as the name for this relation.[5] Of course, it implies that \(f\) is eventually dominated by \(g\).
On the wiki, Long and Stanley's \(>^*\) is used. The term is also used more loosely: for predicate \(P\), the statement "\(f >^*\) every function with property \(P\)" is simply abbreviated to \(f >^* P\). Furthermore, given a formal theory \(T\), the statement \(f >^* T\) means "\(f >^*\) every function provably recursive in theory \(T\)".
Sources[]
See also[]
Concepts: googology · large number · eventual domination · ordinal · cardinal · recursion · infinity
Important numbers and functions: googol · googolplex · -illions · hyper operators · Graham's number · Extensible-E System · Bowers' Exploding Array Function · Bird's array notation · TREE sequence · Busy beaver function · fast-growing hierarchy · Rayo's number
People: Chris Bird · Jonathan Bowers · Harvey Friedman · Lawrence Hollom · André Joyce · Leo Moser · Robert Munafo · Sbiis Saibian · Aarex Tiaokhiao