X to the x is not of Exponential Order

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $f: \R_{>0} \to \R$ be definedas:

$\forall x \in \R_{>0}: \map f x = x^x$.


Then:

$f$ is not of exponential order.

That is, it grows faster than any exponential.


Proof

Lemma

Let $f: \R_{>0} \to \R$ be defined as:

$\forall x \in \R_{>0}: \map f x = x^x$

Let there exist strictly positive real constants $M, K, a \in \R_{> 0}$ such that:

$\forall t \ge M: \size {\map f t} < K e^{a t}$


Then there exists a constant $C$ such that:

$\forall t > C: \size {\map f t} > K e^{a t}$

$\Box$


By the definition of power:

$\map f t = \map \exp {t \ln t}$


The theorem is equivalent to that there do not exist strictly positive real constants $M$, $K$, $a$ such that:

$\forall t \ge M: \size {\map f t} < K e^{a t}$


Aiming for a contradiction, suppose such constants $M$, $K$ and $a$ exist.

From the lemma, there exists a constant $C$ such that:

$\forall t > C: \size {\map f t} > K e^{a t}$


For any $M$ chosen, $M + C > C$, thus from the lemma:

$\size {\map f {M + C} } > K e^{a t}$

However, $M + C > M$, thus from the assumption:

$\size {\map f {M + C} } < K e^{a t}$

Thus a contradiction has arisen.

It follows by Proof by Contradiction that our assumption was false.

Hence the result.

$\blacksquare$