Intereting Posts

Number of total possible outcomes when calculating probablities in Yahtzee
How do I prove that $\lim_{x→0} x⋅\ln x=0$
Completion of Topological Group with Metric
Counterexample of polynomials in infinite dimensional Banach spaces
Tough Inverse Fourier Transform
Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime
Number of permutations of order k
Calculating an Angle from $2$ points in space
A limit problem $\lim\limits_{x \to 0}\frac{x\sin(\sin x) – \sin^{2}x}{x^{6}}$
What is the lowest positive integer multiple of $7$ that is also a power of $2$ (if one exists)?
Graph of symmetric linear map is closed
$PGL(n, F)=PSL(n, F)$
Local central limit theorem for sum of random variables (size of unrooted trees) with infinite variance
Period of a Markov Chain: Why is this one aperiodic?
Coupon collector problem doubts

Cantor’s Diagonal Argument is the standard proof of this theorem. However there must be other proofs, what are some of these proofs?

I am asking this because whenever I think of this question, I immediately think of the Cantor’s Argument, which kills the possibility of other interesting finds.

- Sum of the alternating harmonic series $\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k} = \frac{1}{1} - \frac{1}{2} + \cdots $
- The ratio $\frac{u(z_2)}{u(z_1)}$ for positive harmonic functions is uniformly bounded on compact sets
- Solve $\lim_{x\to +\infty}\frac{x^x}{(\lfloor x \rfloor)^{\lfloor x \rfloor }}$
- How to show that $\lim_{n\to \infty} f_n(x) = 0$.
- The set of functions which map convergent series to convergent series
- A nontrivial everywhere continuous function with uncountably many roots?

- Intuition: Power Set of Intersection/Union (Velleman P77 & Ex 2.3.10, 11)
- bounded sequence in $L^p(\mathbb{R}^n)$ that converges a.e.
- Union of Cartesian products: $X \times (Y \cup Z)= (X \times Y) \cup(X\times Z)$
- Prove that any function can be represented as a sum of two injections
- Limit of solution of linear system of ODEs as $t\to \infty$
- Is there an infinite countable $\sigma$-algebra on an uncountable set
- Sequences of sets property
- If $f \in L^2$, then $f \in L^1$ and$\|f\|_{L^1} \leq \sqrt{2\pi} \|f\|_{L^2}$
- Supremum of closed sets
- Question about integral and unit step function

picakhu: This was posted on MO and there were some interesting answers. I believe the answer I gave there avoids any hidden use of diagonalization. Other answers there are interesting and useful to think about even if, at the end, a diagonal argument is lurking.

Below is an abridged version of my answer there. It assumes some knowledge of ordinals.

In a more general fashion, the question can be restated as:

Is there a proof of Cantor’s theorem that ${}|X|<|{\mathcal P}(X)|$ that is not a diagonal argument?

I learned the following in A. Kanamori-D. Pincus. “Does GCH imply AC locally?”, in **Paul Erdős and his mathematics, II (Budapest, 1999)**, 413-426, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002. It dates back to Zermelo’s 1904 well-ordering paper.

**a.** It is enough to show that there is no injection $F:{\mathcal P}(Y)\to Y$ for any set $Y$.

**b.** If there is such an injection $F$ we can (definably from $F$) produce a pair $(A,B)$ with $A\ne B$ and $F(A)=F(B)$. In effect, Zermelo proved that:

For any $F:{\mathcal P}(Y)\to Y$ there is a unique a unique well-ordering $(W, \lt)$ with $W\subseteq Y$ such that:

- $\forall x\in W (F (\{y ∈ W \mid y \lt x\}) = x)$, and
- $F (W )\in W$.

We can then take $A=W$ and $B=\{y\in W\mid y\lt F(W)\}$.

**c.** *Zermelo’s theorem* can be proved using the (set theoretic) recursion theorem and *Hartogs theorem* that for any set $A$ there is a least ordinal $\alpha$ does not inject into $A$. Neither uses diagonalization.

Cantor’s diagonal argument shows that a given function cannot be surjective.

One can construct the Cantor set and thus show $|P(\mathbb{N})| \le |\mathbb{R}|$ and from Cantor’s theorem it follows that $|\mathbb{N}| < |P(\mathbb{N})|$.

(of course, I’ve been using the fact $|\mathbb{N}| = |\mathbb{Z}|$ freely here)

Edit:

Do note that this way doesn’t really use any implicit diagonalization argument. It just uses the two facts that $|\mathbb{N}|<|P(\mathbb{N})|$ and that $|P(\mathbb{N})|\le|\mathbb{R}|$. There’s something to be said about the fact that the “natural” injection of $P(\mathbb{N})$ into the Cantor set only works for the infinite subsets and not for most finite subsets, however from Cantor’s theorem we have that the “most” of the power set is the infinite subsets anyway, and thus this is not a real problem.

I read about this proof in Raymond Smullyan’s book “Satan, Cantor and Infinity”. The proof is due to Willaim Zwicker (according to the book) and involves something called a hypergame. I’ll first mentioned the hypergame paradox (because it’s fun and can give an insight about the proof) and then write the proof.

Let’s call a game with turns a *normal* game if it always ends in finite turns. For example tic-tac-toe and checkers are both normal games. Now imagine the following game which I will call *hypergame*: In the first turn the first player names a normal game. In the second turn the second player plays the first move of the normal game named and then the players continue playing that game in turns.

The paradox arises from the question: Is the hypergame a normal game? Assume that it is and assume that we try to play hypergame: I go first and say “Let’s play hypergame” (I can do that since it’s a normal game). Then it’s your turn and you can say “Let’s play hypergame” and so forth. Thus the hypergame cannot be normal since if it is we can start a hypergame that doesn’t end in finite turns. But if the hypergame isn’t normal then every hypergame will end in finite turns (since every game I will name will end in finite moves and our game will last that number of turns plus one) which will make the hypergame normal!

Now the proof: Assume that a function $f:\mathbb{N}\to\mathcal{P}(\mathbb{N})$ and let’s assume that $f$ sends $n$ to $X_n$. We define a *path* of numbers as a finite or infinite sequence of numbers such that an element $n$ of the path is either the last (and the path is finite) or the successor of $n$ belongs in $X_n$. For example take a number $n$. If $m\in X_n$ then a successor of $n$ in a path can be $m$. If $X_n$ is empty then $n$ is always the last element of a path. Now we call an element $n\in\mathbb{N}$ *normal* if every path that begins with $n$ is finite.

Finally take the set $Z$ that contains exactly all the normal elements of $\mathbb{N}$. It’s easy to see that there doesn’t exist an $n_0$ such that $Z=X_{n_0}$, which would mean that $f$ is not onto. The argument is essentially the same as the one I used above: Assume that $Z=X_{n_0}$. If $n_0\in Z$ then there is an infinite path, namely $(n_0,n_0,n_0,\ldots)$, but $Z$ is the set of all normal elements so that’s impossible. If $n\notin Z$ then there is an infinite path that begins with $n_0$ (by the definition of $Z$). Let’s call it $(n_0,m,k,\ldots)$. But then there is an infinite path that begins with $m$ (take the aforementioned path and remove $n_0$ from the start). This is again impossible since $m\in Z$ (by the definition of a path) and every element of $Z$ is normal.

This proof uses self-reference but doesn’t seem to use the diagonal lemma. I don’t know if it’s hidden somewhere in the proof (though it looks to me like it isn’t).

Cantor had several other proofs before coming up with the diagonalization argument. (See http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof for one version. Or https://mathoverflow.net/questions/23953/earliest-diagonal-proof-of-the-uncountability-of-the-reals.)

I also read a recent account of this in a Math Monthly article. (I think a version of that article is at http://www.math.jhu.edu/~wright/Cantor_Pick_Phi.pdf.)

The “Nested Intervals” proof is really very nice. Assume the reals are countable and so arrange them as a sequence. Then use that ordering to create intervals $[a_n, b_n]$ where $a_{n-1}<a_n<b_n <b_{n-1}$. The intersection of this sequence of nested intervals is nonempty (this is the Nested Intervals theorem) yet no real number in our list can be inside it! This contradiction proves that we could not have originally arranged the reals in a sequence.

- Does the fibres being equal dimensional imply flatness?
- Alternative to Axler's “Linear Algebra Done Right”
- Example of a Borel set that is neither $F_\sigma$ nor $G_\delta$
- A condition for a function to be constant
- Axiom of choice, non-measurable sets, countable unions
- The Lebesgue Criterion for Riemann Integrability — a proof without using the concept of oscillation.
- Different axiomatizations of set equality
- Suppose that $f(x)= xg(x)$ for some function $g$ which is continuous at $0$. Prove that $f$ is differentiable at 0 , and find $f'(0)$ in terms of $g$.
- How to solve Kepler's equation $M=E-\varepsilon \sin E$ for $E$?
- Differentiable function has measurable derivative?
- Importance of Representation Theory
- Given $a\in\mathbb{R}^2\backslash X$ and $v\in\mathbb{R}^2$, $\exists\delta$ such that $t\in[0,\delta) \Rightarrow a+tv\in \mathbb{R}^2\backslash X$.
- Why does the hard-looking integral $\int_{0}^{\infty}\frac{x\sin^2(x)}{\cosh(x)+\cos(x)}dx=1$?
- Show that a p-group has a faithful irreducible representation over $\mathbb{C}$ if it has a cyclic center
- History of the predicate calculus