# Using Overpowered Theorems to Solve Easy Problems

I thought it would be interesting to start a thread about using overpowered theorems to solve easy problems. Two examples come to mind. Post your favorite example of problem and solution!

1). $\sqrt[3]{2}$ is irrational.
Proof: Suppose $\sqrt[3]{2} = \frac{a}{b}$ for $a,b \in \mathbb{N}$. Then, $a^3=2b^3 = b^3+b^3$, contradicting Fermat's Last Theorem.

2). There are infinitely many primes.
Proof: By the Prime Number Theorem, the asymptotic density of primes is $\frac{x}{\ln(x)}$, so by L'Hopitals Rule, $\lim_{x \to \infty} \frac{x}{\ln(x)} = \lim_{x \to \infty} \frac{1}{1/x} = \lim_{x \to \infty} x = \infty$, so there must be infinitely many primes.

• Cracking a nutshell with a nuke, as it were Dec 24 '16 at 22:14
• There are many examples in this mathoverflow post :mathoverflow.net/questions/42512/… Dec 24 '16 at 22:21
• I guess you've always got to be careful about circular logic here. i.e does the proof of the Prime Number Theorem use that there are infinitely many primes? does the proof of Fermat's Last Theorem use that $\sqrt 2$ is irrational? Dec 24 '16 at 22:22
• @user2520938: "There are infinitely many proofs of a given statement". Could you give a sketch of your three favourite proofs of the Riemann hypothesis? Dec 25 '16 at 0:12
• Possible duplicate of Swatting flies with a sledgehammer Dec 25 '16 at 5:40

You can use forcing and then Shoenfield's theorem to prove the following theorem:

There exists a continuous function from $\Bbb R$ to $\Bbb R$ which is nowhere differentiable.

Essentially the idea is to define a countable forcing whose conditions are continuous approximations for our function, then the generic filter (i.e., our Cohen real) is easily continuous but nowhere differentiable. To get this as a proof, rather than a consistency proof, note that the statement "There is a continuous function which is nowhere differentiable" is a $\Sigma^1_2$-statement, so by absoluteness it was true in the ground model, which was arbitrary and therefore we have proved the wanted statement.

• I see... how exactly did Weierstrass miss this? ;-) Dec 24 '16 at 22:28
• Btw. Doesn't a similar proof - using random forcing - show that there is a subset of reals that is not Lebesgue measurable? Dec 24 '16 at 23:06
• Well, how would that work? I mean, other than disprove the existence of inaccessible cardinals. Note that "There is a set of reals ..." is, in general, a $\Sigma^2_n$ statement. So I suspect that "There is a non-measurable set" is something like $\Sigma^2_1$. Dec 24 '16 at 23:07
• If the same argument would work, it would prove from $\sf ZF+DC$ that a non-measurable set exists. Which proves the inconsistency of inaccessible cardinals as was shown by Solovay--Shelah. Dec 24 '16 at 23:20
• @Mingus: Your conditions are piecewise linear functions with rational "breaking points" where the rationals obtain rational values. You can only extend a function by adding a point which is "sufficiently close" to ensure uniform convergence, but with a different "direction" and slope of the linear pieces added by the function, thus ensuring that there is no differentiability. Dec 24 '16 at 23:46

I have known someone who liked to invoke Fubini's theorem to justify using $$\sum_{m=a}^b \sum_{n=c}^d f(m,n) =\sum_{n=c}^d \sum_{m=a}^b f(m,n)$$

• Rudin's real and complex analysis book uses monotone convergence theorem I believe ;) Dec 25 '16 at 2:14
• Sir, I believe we are mad. Dec 25 '16 at 2:38
• Well. Summation is just integration over finite measures! Dec 25 '16 at 12:03

I found this one in a very old putnam mock test:

Show that the sum of two consecutive positive cubes is never a cube.

• I think that this one can be proven by using the ABC conjecture :) Dec 24 '16 at 22:25
• Poor $0$, nobody ever remembers them. :(
– Ryan
Dec 25 '16 at 5:56

Here, we will prove by exhaustion that the solution for $x$ in $ax-b=0$ is $x=\frac ba$ if $a$ and $b$ are integers.

First, apply the rational roots theorem to see that all rational roots must be of the form $x=\pm\frac pq$, where $p$ and $q$ are the factors of $b$ and $a$ respectively. Since this must be done in general, we can't directly factor $a$ and $b$, so we just cheat by noting that all factors must be whole numbers between $1$ and $a$ or $b$ inclusively. Thus,

$$x\stackrel?=\pm\begin{cases}\frac11&\frac21&\frac31&\dots&\frac b1\\\frac12&\frac22&\frac32&\dots&\frac b2\\\frac13&\frac23&\frac33&\dots&\frac b3\\\vdots&\vdots&\vdots&\ddots&\vdots\\\frac1a&\frac2a&\frac3a&\dots&\frac ba\end{cases}$$

And since there is a finite amount of cases ($a\times b$ at worst), a proof by exhaustion is possible. Going through, we find $x=\frac ba$ to be one such solution, and by the fundamental theorem of algebra, there is at most one distinct root, so all other solutions we may have found in our trial and error are equal to this one.

I'm not sure whether the following proof qualifies - arguably all of its ingredients are pretty basic. However, I believe that their interplay might still be surprising to most non-set-theorists:

Claim. $\mathcal{P}(\mathbb N)$ (and hence $\mathbb{R}$) is uncountable.

Proof. Let $\{ x_n \mid n \in \mathbb N \} \subseteq \mathcal{P}(\mathbb N)$ be any countable subset. Let $(\mathbb P; \leq)$ be the poset whose elements are finite subsets of $\mathbb N$ ordered by inverse inclusion. So $x \leq y$ iff $x \supseteq y$. For each $n \in \mathbb N$ let $$D_n = \{ x \in \mathbb P \mid x \Delta x_n \neq 0 \wedge \operatorname{card}(x) \ge n \}$$ and note that $D_n$ is an open subset of $\mathbb P$. By the Rasiowa–Sikorski lemma there is a filter $G \subseteq \mathbb P$ such that $G \cap D_n \neq \emptyset$ for all $n \in \mathbb N$. Now $x := \bigcup G \subseteq \mathbb N$ is such that $x \neq x_n$ for all $n \in \mathbb N$. Q.E.D.

• This is just diagonalization in its finest. But it seems that you're asking for the Rasiowa-Sikorski lemma here, which is more obscure and therefore "more overpowered". Dec 24 '16 at 22:52
• @AsafKaragila Yeah, I should attribute it to Rasiowa and Sikorski. Since I learned about the Baire Category Theorem first and the proof is basically the same, I always end up attributing it to Baire... Dec 24 '16 at 22:57