# What is a Cantor-style proof of 2n>nk2^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?)

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: and, if $n\ge 5$, all three terms appear in different places in

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. 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.