33
$\begingroup$

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.

$\endgroup$

closed as too broad by Namaste, Daniel R. Collins, user21820, Gerry Myerson, Watson Dec 25 '16 at 17:18

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ Cracking a nutshell with a nuke, as it were $\endgroup$ – Akiva Weinberger Dec 24 '16 at 22:14
  • 8
    $\begingroup$ There are many examples in this mathoverflow post :mathoverflow.net/questions/42512/… $\endgroup$ – N. S. Dec 24 '16 at 22:21
  • 15
    $\begingroup$ 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? $\endgroup$ – Zestylemonzi Dec 24 '16 at 22:22
  • 20
    $\begingroup$ @user2520938: "There are infinitely many proofs of a given statement". Could you give a sketch of your three favourite proofs of the Riemann hypothesis? $\endgroup$ – Georges Elencwajg Dec 25 '16 at 0:12
  • 9
    $\begingroup$ Possible duplicate of Swatting flies with a sledgehammer $\endgroup$ – Carmeister Dec 25 '16 at 5:40
15
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ I see... how exactly did Weierstrass miss this? ;-) $\endgroup$ – Stefan Mesken Dec 24 '16 at 22:28
  • $\begingroup$ Btw. Doesn't a similar proof - using random forcing - show that there is a subset of reals that is not Lebesgue measurable? $\endgroup$ – Stefan Mesken Dec 24 '16 at 23:06
  • $\begingroup$ 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$. $\endgroup$ – Asaf Karagila Dec 24 '16 at 23:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Dec 24 '16 at 23:20
  • 2
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Dec 24 '16 at 23:46
17
$\begingroup$

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) $$

$\endgroup$
  • $\begingroup$ Rudin's real and complex analysis book uses monotone convergence theorem I believe ;) $\endgroup$ – mathworker21 Dec 25 '16 at 2:14
  • $\begingroup$ Sir, I believe we are mad. $\endgroup$ – Simply Beautiful Art Dec 25 '16 at 2:38
  • 2
    $\begingroup$ Well. Summation is just integration over finite measures! $\endgroup$ – Asaf Karagila Dec 25 '16 at 12:03
9
$\begingroup$

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

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

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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". $\endgroup$ – Asaf Karagila Dec 24 '16 at 22:52
  • $\begingroup$ @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... $\endgroup$ – Stefan Mesken Dec 24 '16 at 22:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.