247
$\begingroup$

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?

$\endgroup$
37
  • 36
    $\begingroup$ I once saw someone proving resolutions of singularities of curves by quoting Hironaka's theorem. $\endgroup$ Oct 17, 2010 at 15:23
  • 21
    $\begingroup$ rjlipton.wordpress.com/2010/03/31/april-fool $\endgroup$ Oct 17, 2010 at 15:42
  • 27
    $\begingroup$ 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$. $\endgroup$
    – JS Milne
    Oct 17, 2010 at 20:07
  • 12
    $\begingroup$ @Maxime: I have trouble believing that such a proof is actually non-circular. Surely such proofs form a step, however easy, in the classification. $\endgroup$ Oct 17, 2010 at 21:59
  • 49
    $\begingroup$ 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. $\endgroup$
    – roy smith
    Jan 29, 2011 at 6:48

67 Answers 67

15
$\begingroup$

A number of high school contest problems in number theory reduce to Mihailescu's theorem. (The only perfect powers with a difference of 1 are 8 and 9.)

$\endgroup$
2
15
$\begingroup$

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?

$\endgroup$
15
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ Could you derive this result from supposing Goldbach's conjecture? $\endgroup$ Feb 24, 2013 at 15:06
15
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ By the index theorem, there is no nonvanishing continuous vector field on $S^{2n}$. $\endgroup$ Oct 17, 2010 at 17:35
  • 16
    $\begingroup$ 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. $\endgroup$ Oct 17, 2010 at 17:55
  • 17
    $\begingroup$ 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. $\endgroup$ Oct 18, 2010 at 17:53
  • 1
    $\begingroup$ @MarianoSuárez-Alvarez: I know it's been years since you left this comment, but would you happen to be able to direct me to a paper that shows this? I'm dying to see how it's done. $\endgroup$
    – JamalS
    Nov 14, 2014 at 19:59
  • $\begingroup$ www3.nd.edu/~lnicolae/ind-thm.pdf @JamalS $\endgroup$ Nov 5, 2018 at 21:24
13
$\begingroup$

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.

$\endgroup$
1
  • 7
    $\begingroup$ 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! $\endgroup$ Aug 20, 2012 at 13:00
13
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

$\endgroup$
0
11
$\begingroup$

There is a simple pigeonhole argument for the following fact, due to Erdős and Szekeres I believe:

In any sequence $a_1, a_2, \ldots, a_{mn+1}$ of $mn+1$ distinct integers, there must exist either an increasing subsequence of length $m+1$ or a decreasing subsequence of length $n+1$ (or both).

The "sophisticated" proof of this fact is that any Young tableau with $mn+1$ boxes must either have more than $m$ columns or more than $n$ rows, and so the result follows because the number of columns/rows corresponds to the length of the longest increasing/decreasing subsequence of the corresponding permutation under the Robinson--Schensted correspondence.

$\endgroup$
6
  • 1
    $\begingroup$ Isn't the proof involving Young tableau the simple one? $\endgroup$
    – Will Sawin
    Aug 20, 2012 at 3:54
  • $\begingroup$ To each $a_i$, associate an ordered pair $(b_i,c_i)$, where $b_i$ (respectively, $c_i$) is the length of the longest increasing (respectively, decreasing) subsequence in $a_1,\ldots,a_i$. If $i\ne j$ then clearly $(b_i,c_i)\ne (b_j,c_j)$. There are only $mn$ possible ordered pairs with $b_i\le m$ and $c_i\le n$, and we have more than $mn$ ordered pairs, so necessarily $b_i>m$ or $c_i > n$ for some $i$. QED. Easier than Young tableaux IMO. $\endgroup$ Aug 20, 2012 at 16:14
  • 1
    $\begingroup$ $(b_i,c_i)$ is a a Young tableau, just with different notation. $\endgroup$
    – Will Sawin
    Nov 9, 2012 at 21:28
  • $\begingroup$ How about if say instead, "Easier than the Robinson-Schensted correspondence IMO"? $\endgroup$ Nov 12, 2012 at 15:19
  • 1
    $\begingroup$ @Will: Right, it's easier than the sophisticated proof using Robinson-Schensted. $\endgroup$ Dec 6, 2012 at 22:46
10
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 30, 2012 at 5:29
10
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ (You can avoid the strange substraction of two equal numbers in the end by using the reduced Euler characteristic; this is a standard trick) This of course subjective, as it depends on one's background, but this does not seem awfully sophisticated at all to me and, instead, appears quite natural! :-) $\endgroup$ May 14, 2013 at 20:26
9
$\begingroup$

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

$\endgroup$
8
$\begingroup$

And of course there is Fürstenberg's topological proof of the infinitude of primes. I love this because it shows that all the mathematical "plumbing" works; i.e that number theory and topology connect up as they should.

$\endgroup$
8
  • 12
    $\begingroup$ This is a non-example. Furstenberg's proof is completely elementary. $\endgroup$ Oct 17, 2010 at 16:26
  • 27
    $\begingroup$ To say nothing of the fact that it uses no topological content beyond words... $\endgroup$
    – BCnrd
    Oct 17, 2010 at 16:37
  • 45
    $\begingroup$ Dear trb456: there are no theorems of topology used in the argument, just topology word games, so it does not illustrate any real connection "working" between topology and number theory. This should be more widely recognized. (It is Euclid's proof in disguise, if you unravel the words.) The proofs using divergence of the harmonic series or facts about Dedekind domains are genuine connections with other areas of math to prove the result, since they use actual theorems in those areas. If Furstenberg's proof used Tychonoff or Urysohn, it would be a different story. But I agree: whatever. $\endgroup$
    – BCnrd
    Oct 17, 2010 at 17:24
  • 18
    $\begingroup$ Please no more arguing about Furstenberg's proof! $\endgroup$ Oct 17, 2010 at 18:04
  • 14
    $\begingroup$ The topology does have connections to other areas of math, namely it is the profinite topology on $\mathbb{Z}$. $\endgroup$
    – Ian Agol
    Oct 22, 2010 at 20:36
8
$\begingroup$

The space $C[0,1]$ is not reflexive. If it was, it also had a predual. But then it would be a von Neumann algebra. However von Neumann algebras correspond to very strange topological spaces which have the property that closures of open subsets are again open. Clearly this is not the case for $[0,1]$.

$\endgroup$
1
  • $\begingroup$ So really, this proves C[0,1] has no isometric predual $\endgroup$
    – Yemon Choi
    Aug 20, 2012 at 20:02
7
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

Every finite dimensional complex representation of a finite cyclic group decomposes into a direct sum of irreducible representations. This can be deduced from the decomposition theorem for perverse sheaves as follows: It is enough to show that the group algebra is semi simple. To check this it is enough to lift the regular representation of $\mathbb Z/n$ to $\mathbb Z=\pi^1(\mathbb C^*)$ and show that it decomposes into a direct sum of irreducible representations of $\mathbb Z$.

Consider the covering $z \mapsto z^n$ of $\mathbb C^*$ by itself.

It is easy to see, that the monodromy action on the pushforward of the constant sheaf $\mathbb C[1]$ along this map coincides with the regular representation. On the other hand since the map is small, the decomposition theorem guarantees that the pushforward decomposes into a direct sum of IC complexes. Since our map is a covering and our space is smooth these are actually irreducible local systems on $\mathbb C^*$. But irreducible local systems correspond to irreducible representation of the fundamental group.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
5
$\begingroup$

Here is an example that I learned through MO!

The infinitude of completely split primes in a Galois extension K of Q is an easy consequence of Chebotarev's Density Theorem. A slightly simpler argument involves showing that the Dedekind Zeta Function ζK(s) has a simple pole at s = 1. However, there is a very simple arithmetic argument that accomplishes the desired task...

$\endgroup$
1
5
$\begingroup$

A quiver whose unoriented graph is the affine D4 Dynkin diagram is tame. Therefore the moduli space of four points on a projective line is one dimensional.

$\endgroup$
3
  • $\begingroup$ Well, you really need to know that it is not of finite type in the approppriate dimension, too :) $\endgroup$ Oct 23, 2010 at 21:16
  • $\begingroup$ Well, the dimension vector here is the null root of D4, so we have continuous moduli. Or, for those wondering what we are going on about, the free parameter is the cross ratio of four points on a projective line. (Curses! I ruined the joke by explaining it yet again.) $\endgroup$
    – David MJC
    Oct 27, 2010 at 22:15
  • 3
    $\begingroup$ An excellent exercise for the reader who wants to understand quiver theory: Apply this argument to all the simply laced affine Dynkin types and explain which moduli spaces you have just proved to be one dimensional. $\endgroup$ Nov 1, 2010 at 12:43
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Note that Michael Greinecker has also mentioned Baryshnikov's proof in an earlier reply. $\endgroup$ Feb 24, 2013 at 15:04
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
4
$\begingroup$

The case of Fatou's theorem for H^2 can be proven as follows:

By Carleson's theorem the series $ \sum a_n e^{i \theta n} $ converges for almost all $\theta$ if $ \sum |a_n|^2 < \infty$. Now we can appeal to Abel's theorem to conclude that the function $ f(z)= \sum a_n z^n$ has radial limits almost everywhere on the unit circle. (I am not sure if we can get non-tangential limits this way.)

But Carleson's theorem is a much more difficult theorem than what we have proved here. (I got this example from a Hardy space course I am taking right now.)

$\endgroup$
1
  • $\begingroup$ I don't understand the details of Carleson's Theorem (who does? Genius required!), but I thought one of the main standard techniques for both results was to use maximal functions; so the two results definitely have strongly related proofs (with the Carleson one being much more difficult, of course). Although that doesn't mean it's actually circular, of course! $\endgroup$
    – Zen Harper
    Dec 9, 2010 at 8:42
4
$\begingroup$

Every finite semigroup contains an idempotent element.

You can nuke this problem using a theorem by Ellis that every compact, semi-topological semigroup contains an idempotent (which uses Zorn's Lemma).

$\endgroup$
3
  • $\begingroup$ This is essentially the same proof because you use compactness to get a minimal closed subsemigroup. The rest of the proof is essentially the same (just keeping track of which side keeps things compact). $\endgroup$ Jul 8, 2011 at 23:27
  • 3
    $\begingroup$ Wouldn't you rather look at the power of an arbitrary element and cycles therein? $\endgroup$ Jul 10, 2011 at 15:24
  • 2
    $\begingroup$ Not really. The minimal subsemigroup proof is much more elegant in my opinion. $\endgroup$ Aug 20, 2012 at 2:44
4
$\begingroup$

Baryshnikov gave a topological proof of Arrow's impossibility theorem, a result for which there are well known short and elementary proofs.

$\endgroup$
1
  • 16
    $\begingroup$ One can also prove Arrow's impossibility theorem by noting (a) that the space of ultrafilters $\beta X$ on a set $X$ is equal to its Stone-Cech compactification; and (b) every finite set is already compact. $\endgroup$
    – Terry Tao
    Nov 9, 2010 at 3:41
4
$\begingroup$

There is an elementary problem that goes more or less like this: you have a special telephone keyboard with nine lighted buttons (one for each number from $1$ to $9$); when pushing each button other than number $5$ (the central button) then this switches the state of the lights of the button itself and of all its surrounding buttons; pushing number $5$ only switches the state of the lights of its surrounding buttons, but not of itself. Starting with all lights off, the question asks whether we can get all lights on by pushing buttons. The obvious solution to the negative answer relies on the fact that the parity of lighted buttons at every state of the keyboard is an invariant. But there is also a sophisticated solution.

Take the set $X$ of $9$ elements and think of $\mathcal{P}(X)$ as a vector space over the field $\mathbb{Z}_2$ with the sum being the symmetric difference and the product given by $0.v=\emptyset$ and $1.v=v$. Then we can identify each state of the keyboard with a corresponding vector in this space, while pushing the button $i$ corresponds to summing a special vector $v_i$ (associated to the button) to the vector representing the state of the keyboard. Thus, we are wondering if there are some scalars $\alpha_i$ such that $\sum_{i=1}^{9} \alpha_iv_i=X$. Writing each $v_i$ and $X$ in the base of the space given by the singleton elements $1, ..., 9$, we get a system of linear equations which can be seen to have no solutions by computing the $9 \times 9$ determinant and verifying it is null.

$\endgroup$
6
  • $\begingroup$ There's another way to see that there are no such scalars $\alpha_i$ such that $\Sigma_{i = 1}^{9} \alpha_i v_i = X$ (i.e., that $X$ is not in the span of the $v_i$): consider the linear functional which sends each singleton to 1 (as you note, the singletons comprise a basis). The $v_i$ all lie in its kernel, yet $X$ does not. Of course, this is the parity argument again, but it makes it seem more sophisticated, not less, than the crude determinant calculation... $\endgroup$ Jun 19, 2011 at 19:32
  • $\begingroup$ [Put another way, taking the singleton basis to be orthonormal, the $v_i$ are all orthogonal to the non-zero vector $X$, and thus $X$ is not in their span. (Parity is the same thing as dot product with $X$)] $\endgroup$ Jun 19, 2011 at 19:36
  • $\begingroup$ @Sridhar: It does seem more sophisticated, disguising parity in that way...though I feel that relying on a determinant calculation is a surprisingly odd thing to expect as a solution to the problem. $\endgroup$
    – godelian
    Jun 19, 2011 at 19:57
  • 2
    $\begingroup$ The determinant thing doesn't seem so odd to me, since it is, as you note, the default mechanical way of finding the solutions to the system of linear equations straightforwardly describing the problem. But I suppose "oddness" is in the eye of the beholder. $\endgroup$ Jun 19, 2011 at 20:21
  • 3
    $\begingroup$ Are all these references to "oddness" puns? $\endgroup$ Jun 20, 2011 at 0:12
4
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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|}$!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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