X to the x is not of Exponential Order
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$