What is a Cantor-style proof of $2^n > n^k$? Cantor's diagonalization argument shows that no function from an $n$-element set to its set of subsets hits every element.  This is one way to see that $2^n > n$ for every $n$.  The classic application is when $n$ is an infinite cardinal, but in this question I'm interested in finite $n$.
$2^n$ grows much faster than $n$.  In fact it grows faster than any polynomial function in $n$.  Can this be proved "in the spirit of Cantor"?  That is, fix $k$.  Given a function $f:S \times \stackrel{k}{\cdots} \times S \to 2^S$, can you construct an explicit element of $2^S$ not in its image?  (Of course, the set $S$ cannot be too small relative to $k$, hopefully this restriction occurs naturally in the construction?)
 A: Nice question. Here is a partial answer. 
First of all, it seems that there is no proof purely "in the spirit of Cantor", because the inequality $2^{\mathfrak m}>{\mathfrak m}^2$ is not provable without an appeal to the axiom of choice: In the basic Fraenkel model there is a set $A$ such that if $\mathfrak m=|A|$ then ${\mathfrak m}^2\nleq 2^{\mathfrak m}$ (see here or here for a description of the model). This means that we will not be able to give an argument showing the inequality that only appeals to general properties of functions.
This answer (or see the other answers in that thread) shows that for any finite $k$, if $n$ is finite but sufficiently large, $2^n>n^k$. The idea is that $\displaystyle 2^n\ge\binom{n}{k+1}$, and the latter is eventually larger than $n^k$. For $k=2$, we can argue in a particularly elegant way: $$n^2=\binom{n}1+\binom{n}2+\binom{n}{n-2}$$ and, if $n\ge 5$, all three terms appear in different places in 
 $$ \sum_k\binom nk=2^n. $$
The argument is purely elementary but not quite à la Cantor. 
We can now use the finite case to show Specker's theorem from 1954 that, for any infinite $\mathfrak m$, $2^{\mathfrak m}\nleq {\mathfrak m}^k$. This is best possible, based on the first paragraph. Assuming choice, we can improve this to ${\mathfrak m}^k<2^{\mathfrak m}$, because it follows from choice that $\mathfrak m^2=\mathfrak m$ for all infinite $\mathfrak m$ -- see the first lemma in section 6, here, where it is also shown that there are explicit bijections $f_\alpha:\alpha\to\alpha\times\alpha$ for all infinite ordinals $\alpha$; we will use this below. As you will see, at its heart, the proof uses Cantor's diagonal argument, but it takes some work to get there.
Assume that $A$ is infinite. We argue that there is no injection $f:\mathcal P(A)\to A^k$. The argument uses some properties of ordinals, notably the result just stated in the previous paragraph on the existence of bijections, and Hartogs's theorem that for any set $A$ there is an ordinal that cannot be injected into $A$. To simplify notation, I show here the case $k=2$, but this does not affect the proof (in fact, instead of $A^k$ we can use any "polynomial in $A$ with natural number coefficients", that is, any set that is a disjoint union of finitely many copies of finitely many powers $A^k$.
The argument is by contradiction: Assume that $f:\mathcal P(A)\to A^2$ is injective. Begin with distinct $x_0,\dots,x_4$ in $A$. Recursively, suppose $4\le n\in\mathbb N$, and distinct $x_0,\dots,x_n$ in $A$ have been defined.  Since $2^{n+1}>(n+1)^2$,  the image of the power set of $C=\{x_0,\dots,x_n\}$ under $f$ cannot be completely 
contained in $C^2$.  Linearly order ${\mathcal P}(C)$ lexicographically, using the ordering $x_0<\dots<x_n$.  Let $U$ be the first subset of $C$ such that $f(U)=(x,y)\notin C^2$.  Let $x_{n+1}=x$,  unless $x\in C$,  in which case let $x_{n+1}=y$.  This procedure defines an injection of $\omega$ (the first infinite ordinal, the size of $\mathbb N$, into $X$. 
We now continue through the infinite ordinals. Assume $x_\beta$ has been defined for $\beta<\alpha$. Using the bijection $f_\alpha:\alpha\to\alpha\times\alpha$, we define a partial function $g$ from a subset of $\alpha$ to $\mathcal P(A)$ as follows: $\beta<\alpha$ is in the domain of $g$, and $g(\beta)=B$ iff, letting $f_\alpha(\beta)=(\gamma,\delta)$, then $f(B)=(x_\gamma,x_\delta)$. 
Now let $D=\{x_\xi\mid \xi<\alpha$, $g(\xi)$ is defined, and $x_\xi\notin g(\xi)\}$. This should be reminiscent of the diagonal argument in Cantor's proof. Indeed, letting $f(D)=(x,y)$, we quickly see that either $x$ is not one of the $x_\xi$, and we set $x_\alpha=x$, or else $y$ is not, and we set $x_\alpha=y$. 
This argument produces an injective sequence $x_\alpha$ of elements of $A$, where $\alpha$ runs through all the ordinals. But this is impossible, by Hartogs's result. The contradiction implies that the injection $f$ does not exist after all, and we are done.
Specker used this result to show that, for any finite $n$, $n\cdot\mathfrak m<2^{\mathfrak m}$. He also used it to give a proof that the generalized continuum hypothesis implies the axiom of choice.
Much more recently, Halbeisen and Shelah generalized Specker's result in several directions. All their proofs use at their core a diagonal argument precisely as in Cantor's result, but also require a careful analysis similar to the proof just sketched. As examples of their results, they showed (without using choice) that if $X$ is not empty, then there is no bijection between $\mathcal P(X)$ and the set $\mathrm{Seq}(X)$ of finite sequences of elements of $X$. In fact, if there is an injection from $\mathbb N$ into $X$, then $\mathcal P(X)\nleq\mathrm{Seq}(X)$. They also show that if there is an injection from $\mathbb N$ into the set $\mathrm{Fin}(X)$ of finite subsets of $X$, then for any $n,m\in\mathbb N$, there is no bijection between $n|\mathrm{Fin}(X)|^m$ and $\mathcal P(X)$. This is a pretty argument that also generalizes earlier results of Kuratowski. These, and additional results, can be found in Halbeisen's recent book on Combinatorial set theory.
A: Great question. It is an unfortunately little-known fact that Cantor's classical diagonalization argument is in fact a fixed-point theorem (this formulation is usually referred to as Lawvere's theorem). So if I were to try to make "the spirit of Cantor" precise, it would be as follows.
Specifically, a function $f\colon S\to 2^S$ corresponds to a unique function $\bar f\colon S\times S\to 2$ given by $\bar f(s,-)=f(s)$. We say that a function $\phi\colon S\to 2$ is "$\bar f$-represented" if there is an $s\in S$ so that $f(s,t)=\phi(t)$ for every $t\in S$. Note that $\phi$ is $\bar f$-represented by $s\in S$ if $\phi=f(s)$.
Now, consider the composition $\psi\colon S\overset{\Delta}\to S\times S\overset{f}\to2\overset{g}\to 2$, where $\Delta\colon s\mapsto(s,s)$. Supposing that $\psi$ is $\bar f$-represented by $s\in S$, we obtain that $\psi(s)=g\circ \bar f(s,s)=g\circ\psi(s)$. Hence, $\psi(s)$ is a fixed point for $g$.
But now notice that $g\colon 2\to 2$ was arbitrary, so if $g$ was the negation which has no fixed, the above implies that the composition $\psi$ cannot be $\bar f$-represented by any $t\in S$, which means that $f$ is not surjective.
To reiterate the point, the crux of Cantor's Diagonal Argument is that one can obtain a fixed point for a $g\colon Y\to Y$ from any map $\bar f\colon S\times S\to Y$ and an $s\in S$ that $\bar f$-represents the composite map $S\overset{\Delta}\to S\times S\overset{\bar f}\to Y\overset{g}\to Y$ (one can use this idea to prove the Recursion Theorem, for example, as well as Tarski's Undefinability of Truth, and other results in logic).
Anyway, let us see what happens if we try to adapt this to $f\colon T\to Y^S$. Let us assume that we have a map $\xi\colon S\to T$. Then $f$ corresponds to a map $\bar f\colon T\times S\to Y$, and there is again a composite $\psi\colon S\overset{\operatorname{id}\times\xi}\longrightarrow T\times S\to Y\overset{g}\to Y$.
Here, we run into a problem, which is that a function $\phi\colon S\to Y$ is in the image of $f\colon T\to S^Y$ if and only if there is a $t\in T$ that $\bar f$-represents $\psi$, i.e. a $t\in T$ so $f(s,t)=\psi(s)$ for all $s\in S$. But then it makes no sense to consider $\psi(t)$, since $t$ is an element of $T$, not $S$. However, if there exists a surjective $\xi\colon S\to T$, then setting $s$ to be the preimage of $t$, we obtain $\psi(s)=g\circ\bar f(t,s)=g(\psi(s))$, so that $\psi(s)$ is again a fixed point for $g$.
Consequently, when $Y$ has at least two distinct elements and there being a $g\colon Y\to Y$ without a fixed point, we have that for any $T$ that maps surjectively onto $S$, the above $\psi$ associated to $f\colon T\to Y^S$ is not in the image of $f$.
Based on these considerations, it seems unlikely that there is a proof of the exponential growing faster than the polynomial that is in the "spirit of Cantor".
A: Let 
$$A = \{ f : \{1,2,.., k \} \to \{1,2,.., n\} \} \,.$$
$$B= \{ f : \{1,2,.., k \} \to \{1,2,.., n\} | \mbox{f is non-decreasing}\} \,.$$
Then, it is easy to embed 
$$A \subset B \times S_k \,,$$
where $S_k$ dennotes the symmetric group. 
This proves that 
$$n^k \leq k! \times |B| \,.$$
Now, $B$ can be embedded into 
$$C:= \{ f : \{1,2,.., k \} \to \{1,2,.., n, n+1,..,n+k\} | \mbox{f is strictly increasing}\} \,.$$
For example 
$$F(f(x))=f(x)+x \,.$$
is such an embedding.
Thus 
$$|B| \leq |C|$$
Finally, as every function in $C$ is uniquely determined by its image, we get
$$|C| \leq \binom{n+k}{k} <2^{n+k} \,.$$
Combining all inequalities we get
$$n^k < k! 2^{n+k}=k! 2^k 2^n$$
or
$$\frac{n}{k!2^k} n^{k-1} < 2^n$$
Thus, for all $n > k!2^k$ we get
$$n^{k-1} < \frac{n}{k!2^k} n^{k-1} < 2^n$$
Now, just replace $k$ by $k+1$ in this argument....
P.S. I expect that the inequality $$\binom{n}{k+1} >n^k$$
should be easy to prove for $n$ large enough, but can't figure a simple proof....
