FANDOM


Eventual domination is a relation describing the asymptotic behavior of two functions[1]. The function f is said to eventually dominate g iff f(n) > g(n) for all sufficiently large 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.

Sources

  1. https://u.osu.edu/friedman.8/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.