Awfully sophisticated proof for simple facts [closed]

It is sometimes the case that one can produce proofs of simple facts that are of disproportionate sophistication which, however, do not involve any circularity. For example, (I think) I gave an example in this M.SE answer (the title of this question comes from Pete's comment there) If I recall correctly, another example is proving Wedderburn's theorem on the commutativity of finite division rings by computing the Brauer group of their centers.

Do you know of other examples of nuking mosquitos like this?

-

closed as no longer relevant by Fernando Muro, Emil Jeřábek, Felipe Voloch, Mark Sapir, Andy PutmanMay 14 '13 at 23:13

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I once saw someone proving resolutions of singularities of curves by quoting Hironaka's theorem. –  Richard Borcherds Oct 17 '10 at 15:23
Brauer groups and cohomology are certainly overkill for Wedderburn's theorem: if $D$ is a finite division algebra and $L$ is a maximal subfield, then the Noether-Skolem theorem shows that the multiplicative group of $D$ is a union of conjugates of that of $L$; hence $D$=$L$. –  JS Milne Oct 17 '10 at 20:07
@Maxime: I have trouble believing that such a proof is actually non-circular. Surely such proofs form a step, however easy, in the classification. –  Qiaochu Yuan Oct 17 '10 at 21:59
I once convinced myself the Cantor set is non empty because it is a descending intersection of non empty closed subsets of a compact set, before noticing it contains 0. –  roy smith Jan 29 '11 at 6:48

Irrationality of $2^{1/n}$ for $n\geq 3$: if $2^{1/n}=p/q$ then $p^n = q^n+q^n$, contradicting Fermat's Last Theorem. Unfortunately FLT is not strong enough to prove $\sqrt{2}$ irrational.

I've forgotten who this one is due to, but it made me laugh. EDIT: Steve Huntsman's link credits it to W. H. Schultz.

-
LoL ! –  Qfwfq Oct 17 '10 at 16:47
Yes, Fermat's Last Theorem is an important generalization of the fact that $2^{1/n}$ is irrational. :-) –  Greg Kuperberg Oct 17 '10 at 20:42
This argument is essentially circular. Indeed, we can assume $n$ is prime (just like for FLT) and then the proof of FLT first passes from a hypothetical nontrivial solution to $a^n + b^n = c^n$ for prime $n > 2$ to a suitable "Frey curve" $y^2 = x(x-a^n)(x+b^n)$ where one has to rig certain congruential and gcd conditions on $(a,b,c)$, including that $a$, $b$, and $c$ are pairwise coprime. Yet that step applied to $(p,q,q)$ is exactly what would be the "Euclid-style" proof that $2$ is not a rational $n$th power. Hmm, another disguised version of a Euclid proof. Like the Furstenberg thing...:) –  BCnrd Oct 18 '10 at 4:25
A student in the BeNeLux olympiad apparently proved that 56 is not a cube by observing that 56 = 4^3 - 2^3 and referring to Fermat's Last Theorem for the exponent 3. –  Franz Lemmermeyer Jun 15 '11 at 15:07
So here is an argument which is not circular: $X^n-2$ is irreducible (Eisenstein). –  Martin Brandenburg Mar 14 '12 at 10:15

An example that came up in my measure theory class today:

The harmonic series $\sum_{n=1}^\infty \frac{1}{n}$ diverges, because otherwise the functions $f_n := \frac{1}{n} 1_{[0,n]}$ would be dominated by an absolutely integrable function. But $$\int_{\bf R} \lim_{n \to \infty} f_n(x)\ dx = 0 \neq 1 = \lim_{n \to \infty} \int_{\bf R} f_n(x)\ dx,$$ contradicting the dominated convergence theorem.

-
I love this one. –  Mariano Suárez-Alvarez Nov 4 '10 at 3:17
Isn't this the standard proof? –  Harry Gindi Dec 9 '10 at 4:58
@Harry, no it isn't: this depends on knowing the dominated convergence theorem (which very few people prove for the Riemann integral, so usually has to wait until you are studying measure theory) The divergence of the harmonic series follows from the integral comparison thorem, for example, a much more elementary proof! –  Mariano Suárez-Alvarez Dec 9 '10 at 13:13
The standard proof is $\sum_{n=2^i+1}^{2^{i+1}} n^{-1} \geq \sum_{n=2^i+1}^{2^{i+1}} 2^{-(i+1)} = \frac 12$. –  Kevin O'Bryant Jun 19 '11 at 22:26
I remember someone had an article giving 20 different proofs of this fact. –  John Jiang Nov 28 '11 at 9:42

Here's a topological proof that $\mathbb{Z}$ is a PID.

Let $p,q$ be relatively prime. Then the line from the origin to the point $(p,q)\in\mathbb{R}^2$ does not pass through any lattice point, and therefore defines a simple closed curve in the torus $\mathbb{T}=\mathbb{R}^2/\mathbb{Z}^2$. Cut the torus along this curve. By classification of surfaces, the resulting surface is a cylinder. Therefore, we can reglue it to get a torus, but where our simple closed curve is now a "stupid" such thing, i.e., a ring around the torus.

Which is all to say that in this case, there exists an automorphism of the torus which takes $(p,q)\in\mathbb{Z}^2=\pi_1(\mathbb{T})$ to $(1,0)$. But this gives a matrix $\begin{bmatrix} p & x \\ q & y \end{bmatrix}\in GL_2(\mathbb{Z})$, so $py-qx\in\mathbb{Z}^{\times}$, i.e., $py-qx=\pm 1$.

The only two things this proof needs are the computation of the homology of a torus and the classification of surfaces, neither of which actually relies on $\mathbb{Z}$ being a PID!

-
Strictly speaking this is a bit weaker than Z being a PID, but wow. –  Harry Altman May 5 '11 at 20:53
I think that in the brain of many low-dimensional topologists, rational numbers, Euclid's algorithm and SL(2,Z) are really instantaneously replaced by topological data on the torus (say homotopy classes of essential curves, Dehn twists and mapping class groups). –  Maxime Bourrigan May 6 '11 at 0:32
I recently discovered that this is exactly how I think about this when I found myself very gingerly giving the algebraic argument in class (which graduate students find obvious) and then cavalierly dispensing the topological argument as the trivial one. –  Richard Kent Jan 1 '12 at 15:57
wow that's cool. are there analogous arguments for the other euclidean domains? –  Vivek Shende Dec 20 '12 at 13:08

There are infinitely many primes because $\zeta(3)=\prod_p \frac{1}{1-p^{-3}}$ is irrational.

-
Or since $\frac12+\frac13+\frac15+\frac17+\ldots$ diverges (by Bertrand's postulate). –  J.C. Ottem Oct 17 '10 at 15:47
@J.C. Ottem, How does Bertrand's postulate give us divergence? –  Andres Caicedo Oct 17 '10 at 16:51
Even better, there are infinitely many primes because there are arbitrarily long arithmetic progressions in them (the Green-Tao theorem). –  Mark Oct 17 '10 at 19:39
@Mark: surely the proof of the Green-Tao theorem uses at some point the infinitude of the primes... –  Qiaochu Yuan Oct 17 '10 at 22:04
@Qiaochu,Mark: It does (they need to embed [1,N] in $Z_p$ for some prime bigger than N to get a nice field structure for some arguments to work). –  Thomas Bloom Oct 18 '10 at 5:06

Theorem: $5!/2$ is even.

Proof: $5!/2$ is the order of the group $A_5$. It is known that $A_5$ is a non-abelian simple group. Therefore $A_5$ is not solvable. But the Feit-Thompson Theorem asserts that every finite group with odd cardinal is solvable, so $5!/2$ must be an even number.

-
+1 - I love it! –  Todd Trimble Dec 30 '12 at 2:26

The number of real functions is $c^c=2^c$ which is bigger than $c$ by Cantor's theorem ($c$ is cardinality continuum). The number of real continuous functions is at most $c^{\aleph_0}=c$ as they can be recovered from restrictions to ${\bf Q}$, and there are $c^{\aleph_0}$ many functions ${\bf Q}\to {\bf R}$. This argument, which requires several minor steps in an introductory set theory class, eventually shows that there exists a discontinuous real function.

-
Same reasoning: there exists a non-Borel real function. Or there exists a non-Borel set of reals. Now it's not so extreme-seeming. –  Gerald Edgar Oct 17 '10 at 20:40
Also noteworthy is that this is a constructive proof of the existence of a discontinuous real function. –  Tsuyoshi Ito Oct 18 '10 at 3:55
@Tsuyoshi: I don't follow. As I understand the term, a constructive proof of the existence of a discontinuous real function would be something like "Consider the characteristic function of the origin. Notice that it is discontinuous at zero because..." Komjath's answer is an exemplar of a nonconstructive proof. –  Pete L. Clark Oct 18 '10 at 11:23
@Pete: Of course, it is an extremely simple fact that there is a constructive example of a discontinuous real function. This proof is an awfully sophisticated proof of it (because Cantor’s theorem can be proved constructively, if I am not mistaken). But now I know that my joke fell flat…. –  Tsuyoshi Ito Oct 18 '10 at 22:41
While this is obviously overkill, the general technique is so useful that perhaps students should see this proof -- when cardinality is introduced, it's not immediately obvious just how useful it is. For example, even before saying what a computer program is (but knowing that they are specified by strings), one can deduce that there are uncomputable sets, and similarly non-regular languages, etc. I'd say the general idea is that we often have countably many descriptions (programs, grammars, restrictions to $\mathbf{Q}$) but uncountably many objects, so most objects cannot be described. –  Max Oct 14 '11 at 11:22

D J Lewis, Diophantine equations: $p$-adic methods, in W J LeVeque, ed., Studies In Number Theory, 25-75, published by the MAA in 1969, stated on page 26, "The equation $x^3-117y^3=5$ is known to have at most 18 integral solutions but the exact number is unknown." No proof or reference is given.

R Finkelstein and H London, On D. J. Lewis's equation $x^3+117y^3=5$, Canad Math Bull 14 (1971) 111, prove the equation has no integral solutions, using ${\bf Q}(\root3\of{117})$.

Then Valeriu St. Udrescu, On D. J. Lewis's equation $x^3+117y^3=5$, Rev Roumaine Math Pures Appl 18 (1973) 473, pointed out that the equation reduces, modulo 9, to $x^3\equiv5\pmod9$, which has no solution.

I suspect Lewis was the victim of a typo, and some other equation was meant, but Finkelstein and London appear to have given an inadvertently sophisticated proof for a simple fact.

-
The minus sign is inconsequential,just change $y$ to $-y$. –  Gerry Myerson Jun 6 '11 at 7:05

The fundamental group of the circle is $\mathbb{Z}$ because:

It is a topological group, so its fundamental group is Abelian by the Eckmann-Hilton argument. Thus its fundamental group and first singular homology group coincide by the Hurewicz theorem. Since singular homology is the same as simplicial homology, I can just do the one line of computation to obtain the result.

-
Yes, but the fundamental group of the circle is so basic that it is usually the first thing computed in any algebraic topology course or book. Isn't using Hurewicz and the equivalence of singular and simplicial homology a nuke for this problem? If not, I do not see why any of the other answers work –  Steven Gubkin Oct 18 '10 at 19:34
"The fundamental group of the circle is $\mathbb Z$" In my opinion this is one of the most consequential theorems in all of mathematics. So I don't mind if people suggest proofs coming from very different sources. –  Christian Blatter Oct 18 '10 at 19:40
Somehow this proof doesn't feel like a pointless nuke to me, rather it does explain from some perspective what's going on. The usual proof, i.e. proving the path-lifting property for the covering $\mathbb{R} \to S^1$, is also a bit of work, and breaking up loops into paths on $\mathbb{R}$ feels unsatisfying. It also seems odd to never mention that $[s \mapsto e^{2 \pi n s}] * [s \mapsto e^{2 \pi m s}] = [s \mapsto e^{2 \pi (m+n) s}]$ has something to do with a group structure on $S^1$... –  Arend Bayer Oct 18 '10 at 21:38
I'm surprised people don't like this. It's not the most extreme example here, but imagine this scenario: you see a colleague in the hall and ask what he's teaching today. "I'm introducing the fundamental group." And you ask if he'll compute $\pi_1(S1)$. "Well, not today. I'll define the fundamental group, but before I can compute $\pi_1(S1)$ I'll have to set up singular cohomology (long exact sequences, excision, all that) and then once I've explained simplicial homology we can get back to $\pi_1(S1)$. It'll be a month or two." I bet you'd worry about your colleague's sanity. –  Dan Ramras Oct 23 '10 at 13:52
On the other hand, it's perfectly natural to use the Eckmann-Hilton argument in order to show that the degree map is a homomorphism. I don't know a reference that uses E-H here, but that's how I did it in class this semester. –  Dan Ramras Oct 23 '10 at 13:57

Another example from Math Underflow:

We can prove Fermats Last Theorem for $n=3$ by a simple application of Nagell-Lutz (to compute the torsion subgroup) then Mordells Theorem (to see that the group must be $\mathbf{Z}^r \times \mathbf{Z}/3\mathbf{Z}$) then to finish Gross-Zagier-Kolyvagin theorem (which gives $r = 0$) - and that shows it has no nontrivial solutions. I beleive a similar approach works for $n=4$.

-
1+ for "Math Underflow" (and your answer). –  Martin Brandenburg Oct 17 '10 at 16:32
This is actually a nice answer, because it treats $x^3 + y^3 = z^3$ like what it is -- a rational elliptic curve -- and proceeds to find all rational points on it in the way which is easiest given the current level of technology. –  Pete L. Clark Oct 17 '10 at 18:03
@adrian But isn't the Jacobian of the Fermat quartic isogenous to a product of 3 elliptic curves, each of analytic rank 0? –  paul Monsky Oct 18 '10 at 4:41
@Pete: Nice point. It's like arguing that sending email is frivolous overkill since a carrier pigeon could do the same job with much less technology. –  Cam McLeman Oct 18 '10 at 16:39
If such a proof works for n = 4, then it's a better answer for this question than the n = 3 one, because the simplest proof for n = 4 is much simpler than the simplest proof for n = 3. –  Zsbán Ambrus Mar 4 '12 at 12:37

In his 1962 article "A unique decomposition theorem for 3-manifolds", Milnor is actually interested in the unicity of a prime decomposition. For the existence, the method is very natural: if you find an irreducible sphere, you cut the manifold along it and obtain a decomposition $M = M_1 \sharp M_2$, and you do it again with each factor, and so on.

Of course, the hard part is now to prove that this process terminates after a finite number of steps. For that, Milnor refers to Kneser but remarks that "if one assumes the Poincaré hypothesis then there is a much easier proof. Define $\rho(M)$ as the smallest number of generators for the fundamental group of M. It follows from the Gruško-Neumann theorem that $\rho(M_1\sharp M_2) = \rho(M_1) + \rho(M_2)$. Hence if $M\simeq M_1 \sharp \cdots \sharp M_k$ with $k > \rho(M)$ then some $M_i$ must satisfy $\rho(M_i)=0$, and hence must be isomorphic to $S^3$."

A nice follow-up of this proof/joke is that Perel'man's proof of Poincaré's conjecture doesn't even use Kneser-Milnor decomposition and this argument is therefore valid.

-
This sounds to me somewhat similar to assertions of the form: "if the generalized Riemann hypothesis is assumed, then a relatively easy proof of such-and-such fact may be given as follows." The emphasis is less on the length of a complete proof than on what one believes is true, and proceeding from there -- sort of like saying, "morally, this should hold because...". –  Todd Trimble May 5 '11 at 19:29

In the recent paper by Ono and Bruinier (it's currently on the AIM web site) "An algebraic formula for the partition function" they use their formula to determine the number of partitions of 1.

This calculation involves CM points, evaluating a certain weak Maass form at these points, the Hilbert class field of $\mathbb{Q}(\sqrt{-23})$, ... etc.

-
Now I have to wonder if the formula is valid for 0... –  Harry Altman Jan 29 '11 at 5:43
–  François G. Dorais Dec 30 '12 at 6:32

Using character theory, any group of order $4$ is abelian since the only way to write $4$ as a sum of squares is $4 = 1^2 + 1^2 + 1^2 + 1^2$.

-
Well, any way that includes the required one copy of 1^2. Otherwise 2^2 would be a possibility... –  Harry Altman Jan 29 '11 at 4:26
I guess, you can make it more striking: "Using character theory, since any group of order 4 is abelian hence the only way to write 3 as a sum of squares is 3 =1^2 + 1^2+ 1^2" Right? –  Ostap Chervak May 17 '12 at 8:53
Well, 4 is already the sum of one square. To complete the proof, one should say "the only way to write 4 as a sum of squares, one of which is 1, coming from the trivial representation, is..." –  Todd Trimble Aug 20 '12 at 1:10
When I first learned character theory, I asked if one could prove the four-square theorem by exhibiting a group of every order with exactly four conjugacy classes. While it became obvious a second later that this was only a fantasy, I'm excited that someone else thought of the relation between character theory and the four-square theorem! –  David Corwin Dec 21 '12 at 18:33

Proposition. Let $f$ be a bounded measurable function on $[0,1]$. Then there is a sequence of $C^\infty$ functions which converges to $f$ almost everywhere.

Proof (by flyswatter). Take the convolution of $f$ with a sequence of standard mollifiers.

Proof (by nuke). By Carleson's theorem the Fourier series of $f$ is such a sequence.

-

No finite field $\mathbb{F}_q$ is algebraically closed:

Let $k$ be an algebraically closed field. Then every element of $GL_2(k)$ has an eigenvector, and hence is similar to an upper triangular matrix. Therefore $GL_2(k)$ is the union of the conjugates of its proper subgroup $T$ of upper triangular matrices. No finite group is the union of the conjugates of a proper subgroup, so $GL_2(k)$ is not finite. Hence $k$ is not finite either.

-
That's actually a pretty simple argument. –  Ian Agol Aug 20 '12 at 21:49
Not as simple as the "canonical" argument. –  Igor Rivin Aug 20 '12 at 23:52
• There is no largest natural number. The reason is that by Cantor's theorem, the power set of a finite set is a strictly larger set, and one can prove inductively that the power set of a finite set is still finite.

• All numbers of the form $2^n$ for natural numbers $n\geq 1$ are even. The reason is that the power set of an $n$-element set has size $2^n$, proved by induction, and this is a Boolean algebra, which can be decomposed into complementary pairs $\{a,\neg a\}$. So it is a multiple of $2$.

• Every finite set can be well-ordered. This follows by the Axiom of Choice via the Well-ordering Principle, which asserts that every set can be well-ordered.

• Every non-empty set $A$ has at least one element. The reason is that if $A$ is nonempty, then $\{A\}$ is a family of nonempty sets, and so by the Axiom of Choice it admits a choice function $f$, which selects an element $f(A)\in A$.

-
The absurdity of the examples, to my way of thinking, is the idea that one should appeal to a big axiom such as AC to prove the completely trivial facts that every finite set has a well-order or that nonempty sets have members. Of course, AC is completely unnecessary here, and so this is using a nuclear weapon to kill fleas. –  Joel David Hamkins Oct 20 '10 at 16:28
Well, what one could do here is first prove the claim using AC, and then use Godel's theorem that every statement in Peano Arithmetic that is provable in ZFC can be proven in ZF, which I think is very much in the "using a nuclear weapon to kill fleas" spirit of this exercise. –  Terry Tao Nov 3 '10 at 22:17
@andres: "finite" does not have to use ordinals. A set $M$ is Tarski-finite iff every nonempty subset of $P(M)$ has a maximal element with respect to inclusion. Tarski-finite is equivalent to the usual notion of finite (in a weak version of ZF). –  Goldstern Feb 21 '12 at 20:07
Zsban, the usual definition of $\omega$ is that it is the least inductive set (containing $0$ and closed under successor $x\mapsto x\cup\{x\}$). The concept of finite is defined after this, since a set is finite if it is bijective with a proper initial segment of $\omega$. –  Joel David Hamkins Mar 5 '12 at 0:56
-
A nice quote from the book: “Little minds love to ask big questions, or what appears to them as big questions; never stopping to reflect how trivial the answer must be, if only the questioner would take the trouble to think it through. Sometimes it is necessary for the writer of such a serious work as the present one to call a halt in the consideration of matters of real weight and interest and to remember how weak and frail are the reasoning powers of his lowly readers.” –  Harald Hanche-Olsen Oct 17 '10 at 18:55
I wonder if this wonderful book will be reprinted. –  paul Monsky Oct 18 '10 at 7:36
Ah, this book is wonderful... In the wake of this post, someone recalled the copy I had out from the library. :) –  Gwyn Whieldon Oct 18 '10 at 18:10
This book is fantastic. From the bottom of page 47: "As an axiom on which to base the positive numbers and the integers, which have in the past produced much harmless amusement and are still widely accepted as useful by most mathematicians, some such proposition as the following is sometimes considered as being pleasant, elegant, or at least handy: AXIOM: Equalisers exist in the category of categories." –  Qiaochu Yuan Oct 19 '10 at 12:54
Peter Johnstone’s wonderful review of Paul Taylor’s Practical Foundations of Mathematics is worth reading in this connection: cs.man.ac.uk/~pt/Practical_Foundations/Johnstone-review.html “Nearly 30 years later, Paul Taylor has finally written the book of which Mathematics Made Difficult was a parody. That is not intended as a criticism of Practical Foundations of Mathematics...” –  Peter LeFanu Lumsdaine Oct 21 '10 at 4:28

If two elements in a poset have the same lower bounds then they are equal by Yoneda lemma. (I actually said this in a seminar two weeks ago, and of course I explained I killed a mosquito with a nuke.)

-
I don't think this is overkill; it is actually how I think about this result. –  Qiaochu Yuan Oct 17 '10 at 22:01
But surely normal human beings (i.e., those who have never applied Yoneda lemma of their own free will) prefer to hear "therefore they are lower bounds of each other, hence equal"? –  Andrej Bauer Oct 18 '10 at 6:02
Well, some of us have applied the Yoneda lemma and prefer the non-Yoneda argument here, too! :) –  Mariano Suárez-Alvarez Oct 18 '10 at 17:52
The widely used "non-Yoneda" arguments are essentially repetitions of the Yoneda argument in special cases. –  Martin Brandenburg Dec 28 '10 at 9:56
@Martin Brandenburg: +1 can't stop laughing. –  Vectornaut Aug 20 '12 at 16:54

The sum of the degrees of the vertices of a graph is even.

Proof: The number $N$ of graphs with degrees $d_1,\ldots,d_n$ is the coefficient of $x_1^{d_1}\cdots x_n^{d_n}$ in the generating function $\prod_{j\lt k}(1+x_jx_k)$. Now apply Cauchy's Theorem in $n$ complex dimensions to find that $$N = \frac{1}{(2\pi i)^n} \oint\cdots\oint \frac{\prod_{j\lt k}(1+x_jx_k)}{x_1^{d_1+1}\cdots x_n^{d_n+1}} dx_1\cdots dx_n,$$ where each integral is a simple closed contour enclosing the origin once. Choosing the circles $x_j=e^{i\theta_j}$, we get $$N = \frac{1}{(2\pi)^n} \int_{-\pi}^\pi\cdots\int_{-\pi}^\pi \frac{\prod_{j\lt k}(1+e^{\theta_j+\theta_k})}{e^{i(d_1\theta_1+\cdots +d_n\theta_n)}} d\theta_1\cdots d\theta_n.$$ Alternatively, choosing the circles $x_j=e^{i(\theta_j+\pi)}$, we get $$N = \frac{1}{(2\pi)^n} \int_{-\pi}^\pi\cdots\int_{-\pi}^\pi \frac{\prod_{j\lt k}(1+e^{\theta_j+\theta_k})}{e^{i(d_1\theta_1+\cdots +d_n\theta_n+k\pi)}} d\theta_1\cdots d\theta_n,$$ where $k=d_1+\cdots+d_n$. Since $e^{ik\pi}=-1$ when $k$ is an odd integer, we can add these two integrals to get $2N=0$.

-
This integral representation can actually be used to asymptotically estimate the number of graphs if the degrees are large enough. –  Brendan McKay Feb 24 '13 at 22:25

There is a Fourier analytic proof for Sperner's theorem which is much more complicated than the combinatorial proof (and give less in certain respects). This was part pf the polymath1 project.

A general point is that sometime trying to prove a Theorem X using method Y is valuable even if the proof is much more complicated than needed. So while simplification of complicated proofs is a noble endeavor, complicafication of simple theorems is also not without merit!

Here is another example (taken from lecture notes by Spencer): Suppose you want to prove that there is always a 1-1 function from a (finite) set |A| to a set |B| when |B|>=|A|. But you want to prove it using the probabilistic method. Write |A|=n. If |B| is larger than n^2 or so you can show that a 1-1 map exist by considering a random function and applying the union bound. If |B| is larger than 6n or so you can apply the much more sophisticated Lovasz Local Lemma to get a proof. I am not aware of probabilistic proofs of this nature which works when |B| is smaller and this is an interesting challenge.

-
«complicafication» is a great word :-) –  Mariano Suárez-Alvarez Jul 18 '12 at 18:31

I was once flamed because I gave (in my book on Matrices) a short proof of a weak version of Perron-Frobenius' theorem (the spectral radius of a non-negative matrix is an eigenvalue, associated with a non-negative eigenvector), by using Brouwer's fixed point theorem. In my mind, that was to give students an occasion to illustrate the strength of Brouwer's theorem. Of course, there are more elementary proofs of the Perron-Frobenius theorem, even of the stronger version of it.

-
And they fired you for this? OoOoOo,they would have been SO sued... –  Andrew L Oct 17 '10 at 19:36
I mean that someone wrote a nasty review because of that. –  Denis Serre Oct 17 '10 at 20:07
"Flamed", not "fired"! –  Tom Smith Oct 17 '10 at 21:41

Because for some reason no one has mentioned it.

Russell's proof that 1+1=2.

http://quod.lib.umich.edu/cgi/t/text/pageviewer-idx?c=umhistmath;cc=umhistmath;rgn=full%20text;idno=AAT3201.0001.001;didno=AAT3201.0001.001;view=pdf;seq=00000412

-
But maybe this is a proof that $1+1=2$ isn't such a simple fact? –  Gerry Myerson Jan 29 '11 at 22:59
It depends on who you ask. The set theorist and logician will tell you it obvious because S({{}}) = {{},{{}}}. The category theorist and algebraist will ask "you what you mean by 1? are we assuming choice?" The geometer and topologist will tell you, its irrelevant what you call it, an apple and an apple makes two apples. And the number theorist and combinatorist will both wonder what the hell all the fuss is about. –  Michael Blackmon Jan 30 '11 at 0:43
>The category theorist and algebraist will ask "you what you mean by 1? are we assuming choice?" I have my doubts that any category theorist or algebraist would say anything about choice here. Some might ask "what do you mean by 1", but perhaps mostly in a Socratic mode. –  Todd Trimble May 8 '11 at 12:47

In a lecture course I saw a proof of Poincare duality by deducing it from Grothendieck duality. Proving Grothendieck duality for sheaves on topological spaces took a good part of the semester of course, and then deducing Poincare duality was still not a one liner as well, but filled an entire lecture in which we worked out what all the shrieks and derived functors were doing in terms of differential forms or singular cochains.

-
Do you happen to have notes for that course? I think I'd actually like to see that worked out. –  David Speyer Oct 23 '10 at 17:05
Also see people.fas.harvard.edu/~amathew/verd.pdf –  David Corwin Dec 21 '12 at 18:26

Dan Bernstein, "A New Proof that 83 is prime", http://cr.yp.to/talks/2003.03.23/slides.pdf

-
So it actually only is a proof that 83 is a prime power.. Even better as an answer! –  Woett Oct 15 '11 at 16:21

A Turing machine is a mathematical formalization of a computer (program). If $y\in(0,1)$, a Turing machine with oracle $y$ has access to the digits of $y$, and can use them during its computations. We say that $x\le_T y$ iff there is a machine with oracle $y$ that allows us to compute the digits of $x\in(0,1)$.

There are only countably many programs, so a simple diagonalization argument shows that there are reals $x$ and $y$ with $x{\not\le}_T y$ and $y{\not\le}_T x$. $(*)$

Being a set theorist, when I first learned of this notion, I couldn't help it but to come up with the following proof of $(*)$:

Again by counting, every $x$ has only countably many $\le_T$-predecessors. So, if CH fails, there are Turing-incomparable reals. By the technique of forcing, we can find a (boolean valued) extension $V'$ of the universe $V$ of sets where CH fails, and so $(*)$ holds in this extension. Shoenfield's absoluteness theorem tells us that $\Sigma^1_2$-statements are absolute between (transitive) models with the same ordinals. The statement $(*)$, "there are Turing-incomparable reals" is $\Sigma^1_1$ (implementing some of the coding machinery of Gödel's proof of the 2nd incompleteness theorem), so Shoenfield's absoluteness applies to it. Working from the point of view of $V'$ and considering $V'$ and $V$, it follows that in $V'$, with Boolean value 1, $(*)$ holds in $V$. It easily follows from this that indeed $(*)$ holds in $V$.

It turns out that Joel Hamkins also found this argument, and he used it in the context of his theory of Infinite time Turing machines, for which the simple diagonalization proof does not apply. So, at least in this case, the insane proof actually was useful at the end.

-
Also Noam Greenberg has this argument on his homepage. The simple diagonalization that you mention can actually be cast as a Baire category argument: For each Turing machine $M$, the set of pairs $(x,y)$ such that $M$ witnesses $x\leq_Ty$ is nowhere dense. Since there are only countably many Turing machines, there is a pair of incomparable Turing degrees by the Baire category theorem. –  Stefan Geschke Oct 17 '10 at 19:05
Andres, thanks for mentioning this! My view is that many constructions in computability theory are fruitfully thought of as forcing constructions, and this is the natural destination of that view. When I teach computability theory, for example, I try when possible to set up the constructions as the problem of meeting dense sets in a partial order, specifically to emphasize this. –  Joel David Hamkins Oct 19 '10 at 13:38
A lesser form of overkill: Instead of forcing to violate CH, just adjoin two independent Cohen reals. Neither is computable from the other, because neither is in the model of ZFC generated by the other. Then invoke absoluteness. About John Steel's comment that eliminating the machinery leaves one with a Baire category argument: If you eliminate even more machinery by inserting the proof of the Baire category theorem (for this special case), you get back to the original Kleene-Post proof. –  Andreas Blass Dec 28 '10 at 20:38

There's hardly a book on class field theory that doesn't derive Kronecker-Weber as a corollary. Or quadratic reciprocity -)

Disclaimer: I like these proofs. Seeing quadratic reciprocity through the eyes of "Fearless symmetry: exposing the hidden patterns of numbers" by Ash and Gross is an experience you wouldn't want to miss.

-
@Franz: I'll bet you know how to prove Kronecker-Weber without deducing it from a larger edifice of class field theory over $\mathbb{Q}$, but I'm sorry to tell you that most contemporary algebraic number theorists (including me) do not. –  Pete L. Clark Oct 18 '10 at 15:52
@Pete: I learnt number fields from a book by Marcus, and a proof is in there. IIRC there's also a proof very early on in Washington. –  Kevin Buzzard Oct 18 '10 at 19:22
If you google for "Kronecker-Weber via Stickelberger", you'll find a modern version of Weber's classical idea combined with Hilbert's idea of twisting. Washington's proof, if I remember correctly, derives the global version from the local one. There's even a proof in the Monthly: Am. Math. Mon. 81, 601-607 (1974), and a practically unknown proof based on Eisenstein reciprocity due to Delaunay (Delone). –  Franz Lemmermeyer Oct 18 '10 at 20:12
My favourite proof of Kronecker-Weber is the one first given by Shafarevich and reproduced by Cassels in his Local Fields. You do the local case first (as in Lecture 19 of my notes arxiv.org/abs/0903.2615) and then nothing more than the Minkowski bound on the discriminant is needed to derive the theorem over $\mathbf Q$. –  Chandan Singh Dalawat Oct 19 '10 at 3:08

A recent example from MO (I found it quite entertaining) - testing primality of one and two digit numbers using Stirling's formula and Wilson's theorem (to make it even more complicated, one has to use some extensions, calculation tricks and high-precision calculations):

Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem?

-

The proof that the reduced $C^*$-algebra of the free group has no projections has the nice corollary that the circle is connected.

-
I sometimes wonder if the fact that the circle is connected (sorry, that the integers satisfy the Kadison-Kaplansky conjecture) is used somewhere in the building-block observations about the Fredholm index;) But maybe it isn't. –  Yemon Choi Oct 17 '10 at 20:14

The Gauß-Bonnet theorem and the Riemann-Roch theorem for Riemann surfaces have both reasonably elementary proofs. Of course, they follow from the general Atiyah-Singer index theorem.

-
By the index theorem, there is no nonvanishing continuous vector field on $S^{2n}$. –  Steve Huntsman Oct 17 '10 at 17:35
But it should be noted that the discovery and the original proof of the Atiyah-Singer Theorem came from thinking about how to generalize Gauß-Bonnet-Chern and the Hirzebruch-Riemann-Roch formulas and their proof. –  Dick Palais Oct 17 '10 at 17:55
I did read somewhere, in an expository paper, the fact that the sum of the interior angles of an Euclidean triangle to be $\pi$ stated as a Corollary to (some form of) the A-S index theorem. –  Mariano Suárez-Alvarez Oct 18 '10 at 17:53

I claim that the rational canonical model of the modular curve $X(1) = \operatorname{SL}_2(\mathbb{Z}) \backslash \overline{\mathcal{H}}$ is isomorphic over $\mathbb{Q}$ to the projective line $\mathbb{P}^1$.

Indeed, by work of Igusa on integral canonical models, the corresponding moduli problem (for elliptic curves) extends to give a smooth model over $\mathbb{Z}$. By a celebrated 1985 theorem of Fontaine, this implies that $X(1)$ has genus zero. Therefore it is a Severi-Brauer conic, which by Hensel's Lemma and the Riemann Hypothesis for curves over finite fields is smooth over $\mathbb{Q}_p$ iff it has a $\mathbb{Q}_p$-rational point. By the reciprocity law in the Brauer group of $\mathbb{Q}$, this implies that $X(1)$ also has $\mathbb{R}$-rational points and then by the Hasse-Minkowski theorem it has $\mathbb{Q}$-rational points. Finally, it is an (unfortunately!) very elementary fact that a smooth genus zero curve with a rational point must be isomorphic to $\mathbb{P}^1$.

I did actually give an argument like this in a class I taught on Shimura varieties. Like many of the other answers here, it is ridiculous overkill in the situation described but begins to be less silly when looked at more generally, e.g. in the context of Shimura curves over totally real fields.

-

Theorem (ZFC + "There exists a supercompact cardinal."): There is no largest cardinal.

Proof: Let $\kappa$ be a supercompact cardinal, and suppose that there were a largest cardinal $\lambda$. Since $\kappa$ is a cardinal, $\lambda \geq \kappa$. By the $\lambda$-supercompactness of $\kappa$, let $j: V \rightarrow M$ be an elementary embedding into an inner model $M$ with critical point $\kappa$ such that $M^{\lambda} \subseteq M$ and $j(\kappa) > \lambda$. By elementarity, $M$ thinks that $j(\lambda) \geq j(\kappa) > \lambda$ is a cardinal. Then since $\lambda$ is the largest cardinal, $j(\lambda)$ must have size $\lambda$ in $V$. But then since $M$ is closed under $\lambda$ sequences, it also thinks that $j(\lambda)$ has size $\lambda$. This contradicts the fact that $M$ thinks that $j(\lambda)$, which is strictly greater than $\lambda$, is a cardinal.

-
It seems that having merely a strong cardinal suffices in your argument, Jason. It seems that this improves the upper bound on the consistency strength of the assertion that there is no largest cardinal! –  Joel David Hamkins Aug 20 '12 at 13:00