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 2n>n for every n. The classic application is when n is an infinite cardinal, but in this question I’m interested in finite n.

2n 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×k×S2S, can you construct an explicit element of 2S 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 2m>m2 is not provable without an appeal to the axiom of choice: In the basic Fraenkel model there is a set A such that if m=|A| then m2 (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.

Source : Link , Question Author : Trivial Inequality , Answer Author : Community

Leave a Comment