Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

closed as no longer relevant by Fernando Muro, Emil Jeřábek, Felipe Voloch, Mark Sapir, Andy Putman May 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.

31  
I once saw someone proving resolutions of singularities of curves by quoting Hironaka's theorem. –  Richard Borcherds Oct 17 '10 at 15:23
16  
22  
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
9  
@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
21  
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

67 Answers 67

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

share|improve this answer
18  
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
6  
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
1  
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
3  
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

Claim: $\sum\limits_{k=0}^n (-1)^k {n\choose k} = 0$ for all integers $n≥1$

Proof: Take the $n-1$-dimensional simplex $\Delta_{n-1}$. We can compute it's Euler characteristic by using simplicial homology. There are exactly $n \choose k+1$ many $k$-sub-simplexes of $\Delta_{n-1}$. Thus we get a simplicial chain complex of the form $\mathbb{Z}^{n\choose n} \to \mathbb{Z}^{n\choose n-1} \to \cdots \to \mathbb{Z}^{n\choose 2}\to\mathbb{Z}^{n\choose 1}$. So the Euler characteristic is $\chi(\Delta_{n-1}) = \sum\limits_{k=0}^{n-1} (-1)^k {n\choose k+1}=-\sum\limits_{k=1}^{n} (-1)^k {n\choose k}$
On the other hand $\Delta_{n-1}$ is contractible, and $\chi$ is homotopy-equivalence-invariant, so $\chi(\Delta_{n-1})=\chi(pt) =1$.
Putting those toghether we obtain: $0=\chi(\Delta_{n-1})-\chi(\Delta_{n-1})=1+\sum\limits_{k=1}^{n} (-1)^k {n\choose k}=\sum\limits_{k=0}^n (-1)^k {n\choose k}$

share|improve this answer

Around year 1970 a popular way to compute cohomology groups of the finite cyclic groups was by applying spectral sequences (which was quite an overkill).

share|improve this answer
1  
This was popular among whom? The book by Cartan and Eilenberg, the very first textbook on the subject, already has the computation done in terms of the usual very small periodic projective resolution: after that, using anything else to compute this seems pretty weird! –  Mariano Suárez-Alvarez May 11 '13 at 7:37

The following theorem has several essentially different proofs that need quite different levels of mathematical background, ranging from high school to graduate level. Which proof is most natural depends on who you ask, but many people (including me) will find at least some proof unnecessarily complicated.

There exists a set $ A $ that is everywhere dense on the square $ [0, 1]^2 $, but such that for any real number $ x $, the intersections $ A \cap (\{x\} \times [0, 1]) $ and $ A \cap ([0, 1] \times \{x\}) $ are both finite.

(This is a variant of a homework problem posed by Sági Gábor.)

Here's the idea of a few proofs.

  • $ A = \{(p/r, q/r) \mid p, q, r \in \mathbb{Z} \text{ and } \gcd(p,r) = \gcd(q,r) = 1 \} $ is dense because if you subdivide the square to $ 2^n $ times $ 2^n $ squares, $ A $ contains the center of each square; and has only as many points on each horizontal or vertical line as the denominator of $ x $.

  • $ A = \{(x + y\sqrt3, y - x\sqrt3) \mid x, y\in\mathbb{Q} \} $ is dense because it's a scaled rotation of $ \mathbb{Q}^2 $, but has at most one point on every horizontal or vertical line otherwise $ \sqrt3 $ would be rational.

  • Choose $ a_0, b_0, a_1, b_1 $ as four reals linear independent over rationals, this is possible because of cardinalities. $ A = \{(ma_0 + na_1, mb_0 + nb_1) \mid m, n \in \mathbb{Q}\} $ has no two points sharing coordinates because of rational independence, and $ A $ is dense because it's a non-singular affine image of $ \mathbb{Q}^2 $.

  • A is the set of a countably infinite sequence of random points independent and uniform on the square. This is almost surely dense, but almost surely has no two points that share a coordinate.

  • Choose a countable topological base of the square, then choose a point from each of its elements inductively such that you never choose a point that shares a coordinate with any point chosen previously.

  • Choose a continuum (or smaller) size topological base of the square, then choose a point from each by transfinite induction such that when you choose a point, the cardinality of points chosen previously is less than continuum, thus you can avoid sharing coordinates with those points.

  • Choose $ a, b $ as reals such that $ a, b, 1 $ are linear independent over rationals, possible because of cardinalities. Let $ A = \{((ma + nb) \bmod 1, (ma - nb) \bmod 1) \mid m, n \in \mathbb{Z}\} $. No two points share coordinates because of rational independence. Looking on the torus, A is dense somewhere on the square and the difference of any two points of A is in A so it must be dense in the origin. As A is closed to addition, it must be dense on a line passing through the origin. As it's also closed to rotation by $ \pi/2 $, it's also dense on the rotation of that line, thus, because it's closed to addition, dense everywhere.

  • Choose $ a, b $ like above. Let $ A = \{(an \bmod 1, bn \bmod 1) \mid n \in \mathbb{Z}\} $. Prove A is dense by ergodic theory and Fourier analysis.

Update: Edited the drafts of proofs to somewhat cleaner. Permuted proofs. Also fixed typo in last proof.

share|improve this answer

One can also show with Fermat's last theorem that $\sqrt{2}$ is irrational - the answer of mt did $2^{1/n}$ for $n\ge 3$. Suppose that $\sqrt{2}$ is rational. Then there is a right-angled triangle with rational sides $(a,b,c)=(\sqrt{2},\sqrt{2},2)$ and area 1. Hence $1$ would be a congruent number. This contradicts Fermat's last theorem with exponent $4$.

share|improve this answer

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

share|improve this answer
1  
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 exists transcendantal numbers because:

-- $x\mapsto \frac{1}{[{\mathbb Q}(x):{\mathbb Q}]}{\rm Tr}_{{\mathbb Q}(x)/{\mathbb Q}}x$ is a well defined, non zero, linear form from $\bar{\mathbb Q}$ to ${\mathbb Q}$.

-- The kernel of a non zero linear form form ${\mathbb R}$ to ${\mathbb Q}$ is not measurable.

-- By Solovay, every subset of ${\mathbb R}$ can be assumed to be measurable.

Conclusion: ${\mathbb R}\neq \bar{\mathbb Q}$.

share|improve this answer

$5/2 = 2 \frac{1}{2}$ since both are the groupoid cardinality of the following action:

image

Thinking about this, it is actually quite enlightening. For more information, see the wonderful paper From Finite Sets to Feynman Diagrams by John Baez and James Dolan.

share|improve this answer

This is kind of an elementary example, but I always thought it was funny to prove that $S_3$ is isomorphic to a subgroup of $S_6$ using Cayley's theorem.

share|improve this answer

I think that the following proof of the fact that every subgroup of index $2$ of a given group is normal might count too. When I first came up with it (sometime during my sophomore year), I believed that I had just found the entrance to a royal road to mathematics.

Let $H\leq G$ be such that $[G:H]=2$. We'll prove that every right coset of $H$ is equal to a left coset of $H$.

Since $[G:H]=2$, $G$ is both the union of two disjoint right cosets of $H$ and the union of two disjoint left cosets of $H$. Let us suppose that $G=He \cup Hx = eH \cup yH$ where $x,y\in G\setminus H$ and $e$ denotes the identity element of $G$. According to standard lore regarding the symmetric difference of sets,

$He \cup Hx = He \triangle Hx \triangle (He \cap Hx) = He \triangle Hx \triangle \emptyset = H \triangle (Hx\triangle \emptyset) = H\triangle Hx$

and

$eH \cup yH = eH \triangle yH \triangle (eH \cap yH) = eH \triangle yH \triangle \emptyset = H \triangle (yH \triangle \emptyset) = H \triangle yH$.

Therefore, $H\triangle Hx = H\triangle yH$. Canceling $H$ on both sides of the latter equality—which is perfectly valid given that $(2^G, \triangle)$ is a group—we conclude that $Hx=yH$. Done.

If you consider that the prior argument doesn't qualify as awfully sophisticated, there is still another fancy way to derive the result in question. As a consequence of P. Hall's famous marriage theorem, M. Hall proves in Theorem 5.1.7 of his Combinatorial Theory that if $H$ is a finite index subgroup of $G$, there exists a set of elements that are simultaneously representatives for the right cosets of $H$ and the left cosets of $H$ (once he's proven the said theorem, he adds: "Simultaneous right-and-left coset representatives exist for a subgroup in a variety of other circumstances. This problem has been investigated by Ore 1."). In the case $[G:H]=2$, this implies at once that every right coset of $H$ is equal to a left coset of $H$ and we are done...

Last but not least, $[G:H]=2 \Rightarrow H \trianglelefteq G$ in the case when $|G|<\infty$ can also be seen a consequence of the well-known fact according to which any subgroup of a finite group whose index is equal to the smallest prime that divides the order of the group is of necessity a normal subgroup of the group. B. R. Gelbaum showcases in one of his books an action-free proof of this fact. He attributes both the fact and the action-free proof to Ernst G. Straus. Does any of you know on what grounds he did so? I have a Xerox copy of the relevant page in the book here. This is exactly what Gelbaum writes therein:

At some time in the early 1940s Ernst G. Straus, sitting in a group theory class, saw the proof of the ... result [i.e., $[G:H]=2 \Rightarrow H \trianglelefteq G$] ... and immediately conjectured (and proved that night): ... IF G:H [sic] IS THE SMALLEST PRIME DIVISOR P of #(G) THEN H IS A NORMAL SUBGROUP.

P.S. The Galois-theoretic proof given by Matthias Künzer is just fabulous!

share|improve this answer

Here is a Ramsey theory proof every finite semigroup has an idempotent. Let S be a finite semigroup with finite generating set A. Choose an infinite word $a_1a_2\cdots$ over A. Color the complete graph on 0,1,2... by coloring the edge from i to j with $i\lneq j$ by the image in S of $a_{i+1}\cdots a_j$. By Ramsey's theorem there is a monochromatic clique $i\lneq j\lneq k$. This means $$a_{i+1}\cdots a_j=a_{j+1}\cdots a_k=a_{i+1}\cdots a_k$$ is an idempotent.

This proof, generalized to larger clique sizes, actually shows any infinite word contains arbitrarily long consecutive subwords mapping to the same idempotent of S, which is used in studying automata over infinite words.

share|improve this answer
2  
This is nice. It somehow looks like Ramsey's theorem is quite adapted to this line of reasoning, which detracts from its thermonuclearity in this context. –  Mariano Suárez-Alvarez Dec 30 '12 at 5:29

Kn is non-planar for n>4: it contradicts the four-color theorem.

share|improve this answer
3  
To qualify as a good answer, it has to be non-circular... Are we sure this passes that test? –  Mariano Suárez-Alvarez Dec 30 '12 at 2:42

The fundamental theorem of algebra holds because:

  1. For each degree $n$ normed polynomial $p$ over the complex numbers, there is an $n \times n$ matrix $A$ with characteristic polynomial $\pm p$.

  2. We show that $A$ has an eigenvector.

  3. We may assume that $0$ is not an eigenvalue of $A$ (otherwise $p(0)=0$), so $A \in GL_n (\mathbb{C})$.

  4. $A$ induces a self-map $f_A$ of $CP^{n-1}$, and the eigenspaces of $A$ correspond to the fixed points of $f_A$; so we need to show that $A$ has a fixed point.

  5. As $GL_n (\mathbb{C})$ is connected, $f_A$ is homotopic to the identity (this does not depend on the fundamental theorem of algebra; if $A \in GL_n (\mathbb{C})$, then $ z 1 + (1-z )A$ is invertible except for a finite number of values of $z$; and the complement of a finite set of points of the plane is path-connected (this follows, for example, from the transversality theorem).

  6. The Lefschetz number of the identity on $CP^{n-1}$ equals $n\neq 0$, thus the Lefschetz number of $f_A$ is not zero.

  7. By the Lefschetz fixed point theorem, $f_A$ has a fixed point.

share|improve this answer
2  
A slightly different approach is to suppose there is a finite extension $K/\mathbb C$. Then $P(K)$, the projectivisation of $K$ as a complex vector space is a compact abelian Lie group (with multiplication induced by that of the group $K^\times$). Such a thing must be a torus, so its $H^1$ is not zero. Yet it is a complex projective space, and one easily sees that its $H^1$ is zero. –  Mariano Suárez-Alvarez Dec 21 '12 at 20:04
1  
This is a perfectly good proof, and is it so much more sophisticated than any of the others? Many of the favorite proofs of this theorem are similarly topological. –  Ryan Reich Dec 30 '12 at 5:35
1  
@Ryan: yes, in a sense it is a nice proof. Lefschetz fixed point theorem is a hard result, which depends either on Poincare duality or on simplicial approximation. Most topological proofs I know are considerably more elementary (and use the topology of the complex plane, which is more obviously related to the problem than self-maps of $CP^n$). –  Johannes Ebert Jan 30 '13 at 22:54

The skew-field of quaternions $\mathbb H$ is isomorphic to its opposite algebra.

Indeed, by a theorem of Frobenius, division algebras over the reals are isomorphic to either $\mathbb R, \mathbb C$ or $\mathbb H$. Since $\mathbb H^\mathsf{opp}$ is again a division algebra, it must be isomorphic to one of these. There are several ways to conclude: since it is four dimensional, or since it is not commutative, or since it has more than two square roots of $-1$, etc., we conclude that the only possibility is $\mathbb H \cong \mathbb H^\mathsf{opp}$.

If you are only interested in Morita equivalence between these two algebras, you can do better: the Brauer group of $\mathbb R$ is isomorphic to $\mathbb Z_2$, and so all elements are of order $2$. This implies that the class of $\mathbb H$ coincides with its inverse, which is the class of $\mathbb H^{\mathsf{opp}}$. Thus $\mathbb H$ and $\mathbb H^\mathsf{opp}$ are Morita equivalent.

share|improve this answer
1  
Who in his right mind writes $\mathsf{opp}$ with two p's! –  Mariano Suárez-Alvarez Dec 30 '12 at 5:30

Liouville remarked that the fundamental theorem of algebra could be derived from his theorem that elliptic functions (doubly periodic meromorphic functions of one complex variable) must have poles. The proof goes by substituting the inverse of a polynomial as the argument of, say, Weierstrass $\wp$-function with large enough periods, and observing that it has no poles.

Of course, the proof of Liouville's theorem on elliptic functions requires the same kind of arguments used for proving the famous Liouville theorem (due to Cauchy) that bounded holomorphic functions are bounded and, apparently, already used before by Cauchy for algebraic functions.

But Liouville's observation is really more complicated than the present proof. What it simplifies, however, is the compactness argument. For elliptic functions, or for algebraic functions, one has at hand a compact Riemann surface on which some holomorphic function is bounded, hence achieves its supremum, etc. This may be the reason why the general form of Liouville theorem came only after the case of algebraic or elliptic functions.

share|improve this answer

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.

share|improve this answer
2  
By the index theorem, there is no nonvanishing continuous vector field on $S^{2n}$. –  Steve Huntsman Oct 17 '10 at 17:35
14  
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
14  
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

Seen on http://legauss.blogspot.com.es/2012/05/para-rir-ou-para-chorar-parte-13.html

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.

share|improve this answer
3  
+1 - I love it! –  Todd Trimble Dec 30 '12 at 2:26

This is quite late(and just a restatement of the regular proof in fancy terms), but I came around this while goofing off one day:

Theorem: Let $X$ a space, and $\mathscr{F}$ a sheaf of (not necessarily abelian) groups, and denote by $\pi$ the projection from the étalé space $Sp\acute{e}(\mathscr{F})$. Then $\Gamma(X,\mathscr{F})$ inject into $\mathrm{Aut}(\pi)$(taken in the category of spaces étalé over $X$).

Proof: Straightforward and not difficult(but there are a bunch of things to check).

Theorem: (Cayley's theorem) Let $G$ a finite group, then $G$ is a subgroup of a symmetric group.

Proof. Let $X$ a nonempty, connected topological space and take $\mathbb{G}$ the constant sheaf associated to $G$ on $X$. Apply previous theorem and notice that $Sp\acute{e}(\mathbb{G})$ is a globally trivial covering space, and homeomorphic(over $X$) to $\coprod_{|G|} X$, so that $G$ injects into the group of deck transformations of this covering space, which is just $\mathfrak{S}_{|G|}$!

share|improve this answer

$Forest$ is in $P$. Given a finite undirected graph $G$ one can in polynomial time decide whether the input is a forest. The class of all finite forests is a minor-closed property and by the Robertson–Seymour theorem, there are finitely many forbidden minors. We can in $O(n^3)$ time test whether $G$ contains a forbidden minor and if not, output yes.

share|improve this answer
1  
Although I like the example, I'm not sure I follow your argument. For the case of forests we already know the finite set of forbidden minors: $\{C_3\}$. So Robertson-Seymour doesn't really enter the picture except via the $O(n^3)$ test, which is really a different theorem. –  András Salamon Mar 28 '13 at 23:33

The Herbert Simon (Nobel Price Winner, Economics, 1978)--- Karl Egil Aubert Dispute, see

http://www.tandfonline.com/doi/abs/10.1080/00201748208601972

Aubert criticizes Simon for irrelevant use of mathematics for his "Application", but also for the fact that he uses the Brouwer fixed point theorem for a proof, when the Intermediate Value Theorem would be enough.

share|improve this answer

Not really sure if this should count, but: From Chebyshev's proof using the central binomial coefficient that there exists some constant $C>0$ such that

$$ \pi(x) < C\frac{x}{\log x} $$

for sufficiently large $x$, and from the infinitude of primes, we get that

$$ \log x \ll x. $$

share|improve this answer

The density Hales-Jewett theorem implies that there cannot exist perfect magic hypercubes of fixed side length $k$ and arbitrarily high dimension $n$ whose cells are filled with the consecutive numbers $1,2,\dots,k^n$ and for which the numbers in cells along any geometric line sum to the magic constant $\frac{k(k^n+1)}{2}$.

For, take the cells with numbers $ 1,2,\dots,\left\lfloor\frac{k^n}{2}\right\rfloor $.

This always has density about $1/2$, and so by the density Hales-Jewett theorem, will contain a hyperline for sufficiently large $n$. But no $k$ numbers from this set of density about $1/2$ can ever sum to the magic constant.

share|improve this answer
  • 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$.

share|improve this answer
1  
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
29  
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
1  
@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
1  
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

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.

share|improve this answer
4  
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

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

share|improve this answer
7  
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

(1) Let $G$ be a finite group. Let $H\leqslant G$ be a subgroup of index $2$. Let us prove that $H$ is normal in $G$. Let $L|K$ be a Galois extension of fields with Galois group $G$ (easily constructed via a representation of $G$ as a permutation group, taking $L$ to be a function field in suitably many variables on which $G$ acts and $K$ to be the fixed field under $G$). Let $F$ be the fixed field in $L$ under $H$. Then $F|K$ is a quadratic extension, hence normal. By the Main Theorem of Galois Theory, it follows that $H$ is normal in $G$.

(2) Let $G$ be a finite group. Let $K$ be a finite field of characteristic not dividing $|G|$. Let us prove Maschke's Theorem in this situation: $KG$ is semisimple. Given two finite dimensional $KG$-modules $X$ and $Y$, it suffices to show that $\text{Ext}^1_{KG}(X,Y) = 0$. But $\text{Ext}^1_{KG}(X,Y) = \text{H}^1(G,\text{Hom}_K(X,Y)) = 0$, since $|G|$ and $|\text{Hom}_K(X,Y)|$ are coprime.

(Well, not sure whether any of these arguments are really awfully sophisticated. It's rather breaking a butterfly on a small wheel.)

share|improve this answer
3  
The second one is actually a great, non-awfully sophisticated argument :) It is essentially the same as the purely algebraic proof of complete reducibility of finite dimensional modules over a fin. dim. semisimple Lie algebra---in that case, one replaces the coprimality by the action of the Casimir element, a completely parallel argument. –  Mariano Suárez-Alvarez Oct 13 '11 at 7:04

An olympiad-type question I once tried to solve was: prove that all integers $>1$ can be written as a sum of two squarefree integers$^{[1]}$. The proof I came up with (which uses at least $3$ non-trivial results!) went as follows:

We can check that it holds for $n \le 10^4$. Now, let $S$ be the set of all squarefree integers, except for the primes larger than $10^4$. Then by the fact that the Schnirelmann density of the set of squarefree integers equals $\dfrac{53}{88}$ $^{[2]}$ and some decent estimate on the prime counting function$^{[3]}$, we have that the Schnirelmann density of $S$ must be larger than $\dfrac{1}{2}$. By Mann's Theorem$^{[4]}$ we now have that every positive integer can be written as sum of at most $2$ elements of $S$. In particular, every prime number can be written as sum of $2$ elements of $S$, and every integer that is not squarefree can be written as sum of $2$ elements of $S$. All there is now left, is proving the theorem for composite squarefree numbers; $n = pq = (p_1 + p_2)q = p_1q + p_2q$, where $p$ is the smallest prime dividing $n$ and $p_1, p_2$ are squarefree integers.

$^{[1]}$ http://www.artofproblemsolving.com/Forum/viewtopic.php?f=470&t=150908 $^{[2]}$ http://www.jstor.org/pss/2034736 $^{[3]}$ http://en.wikipedia.org/wiki/Prime-counting_function#Inequalities $^{[4]}$ http://mathworld.wolfram.com/MannsTheorem.html

share|improve this answer
1  
Could you derive this result from supposing Goldbach's conjecture? –  Zsbán Ambrus Feb 24 '13 at 15:06

Arrow's theorem is a basic result in social choice theory which has several simple proofs. (For three proofs see this paper: Three Brief Proofs of Arrow's Impossibility Theorem by J. Geanakoplos)

It also has a few complicated proofs: The paper by Tang, Pingzhong and Lin, Fangzhen Computer-aided proofs of Arrow's and other impossibility theorems, Artificial Intelligence 173 (2009), no. 11, 1041–1053. Gives an inductive proof based on rather complicted inductive step and a computerized check for the base case. The paper by Yuliy Baryshnikov, Unifying impossibility theorems: a topological approach. Adv. in Appl. Math. 14 (1993), 404–415, gives a proof based on algebraic topology. My paper: A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem. Adv. in Appl. Math. 29 (2002), 412–426, gives a fairly complicated Fourier-theoretic proof but only to a special case of the theorem.

(A complicated proof to a related theorem is by Shelah, Saharon, On the Arrow property, Adv. in Appl. Math. 34 (2005), 217–251.)

share|improve this answer

Proving the Banach fixed point theorem for compact metric spaces using the structure of monothetic compact semigroups.

Thm. Let $X$ be a compact metric space and $f\colon X\to X$ a strict contraction, meaning $d(f(x),f(y))< d(x,y)$ for $x\neq y$. Then $f$ has a unique fixed point and for any $x_0\in X$, the iterates $f^n(x_0)$ converges to the fixed point. Pf. Contractions are clearly equicontinuous, so by the Arzelà–Ascoli theorem, the closed subsemigroup $S$ generated by $f$ is compact in the compact-open topology. Now, a monothetic compact semigroup has a unique minimal ideal $I$, which is a compact abelian group. Moreover, either $S$ is finite and $I$ consists of all sufficiently high powers of $f$ or $S$ is infinite and $I$ consists of all limit points of the sequence $f^n$. In either case, $I$ consists of strict contractions, being in the ideal generated by $f$. Thus the identity element $e$ of $I$ is a constant map, being an idempotent strict contraction. Thus $I=\{e\}$, being a group. Thus $f^n$ converges to a constant map to some point $y$. Clearly $y$ is the unique fixed point of $f$.

share|improve this answer

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.

share|improve this answer
11  
I love this one. –  Mariano Suárez-Alvarez Nov 4 '10 at 3:17
8  
Isn't this the standard proof? –  Harry Gindi Dec 9 '10 at 4:58
22  
@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
39  
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
4  
I remember someone had an article giving 20 different proofs of this fact. –  John Jiang Nov 28 '11 at 9:42

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