150
$\begingroup$

A while back I saw posted on someone's office door a statement attributed to some famous person, saying that it is an instance of the callousness of youth to think that a theorem is trivial because its proof is trivial.

I don't remember who said that, and the person whose door it was posted on didn't remember either.

This leads to two questions:

  1. Who was it? And where do I find it in print—something citable? (Let's call that one question.)

  2. What are examples of nontrivial theorems whose proofs are trivial? Here's a wild guess: let's say for example a theorem of Euclidean geometry has a trivial proof but doesn't hold in non-Euclidean spaces and its holding or not in a particular space has far-reaching consequences not all of which will be understood within the next 200 years. Could that be an example of what this was about? Or am I just missing the point?

$\endgroup$
16
  • 14
    $\begingroup$ This is anti-climactic since you (rather quickly!) chose an answer, but what is your definition of "nontrivial theorem"? For example, would Schur's Lemma or Maschke's theorem have counted? $\endgroup$
    – Boyarsky
    Jun 20, 2010 at 2:10
  • 9
    $\begingroup$ Very often non-trivial theorems become definitions, or new definitions are specifically chosen so that they become trivial. Thereafter, they have trivial proofs. For example, the fact that homology is invariant under homotopy is (almost) trivial once you know singular homology. Even more often, our whole way of viewing math changes so that we get used to some new amazing discovery (as in Joel's example of existence of uncountable sets below) $\endgroup$ Jun 20, 2010 at 3:03
  • 24
    $\begingroup$ "callousness" or "callowness"? $\endgroup$
    – Yemon Choi
    Jun 20, 2010 at 3:12
  • 4
    $\begingroup$ To Boyarsky: he chose the answer because it gave the source of the quote. $\endgroup$ Jun 20, 2010 at 11:43
  • 11
    $\begingroup$ Something from Spivak's "Calculus on Manifolds" is particularly germane to this discussion: "There are good reasons why theorems should all be easy and the definitions hard [...] Definitions serve a twofold purpose: they are rigorous replacements for vague notions, and machinery for elegant proofs. [...] A fully evolved major theorem has three important attributes: (1) It is trivial. (2) It is trivial because the terms appearing in it have been properly defined. (3) It has significant consequences." $\endgroup$ Jun 10, 2011 at 0:37

45 Answers 45

147
$\begingroup$

Bertrand Russell proved that the general set-formation principle known as the Comprehension Principle, which asserts that for any property $\varphi$ one may form the set $\lbrace\ x \mid \varphi(x)\ \rbrace$ of all objects having that property, is simply inconsistent.

This theorem, also known as the Russell Paradox, was certainly not obvious at the time, as Frege was famously completing his major treatise on the foundation of mathematics, based principally on what we now call naive set theory, using the Comprehension Principle. It is Russell's theorem that showed that this naive set theory is contradictory.

Nevertheless, the proof of Russell's theorem is trivial: Let $R$ be the set of all sets $x$ such that $x\notin x$. Thus, $R\in R$ if and only if $R\notin R$, a contradiction.

So the proof is trivial, but the theorem was shocking and led to a variety of developments in the foundations of mathematics, from which ultimately the modern ZFC conceptions arose. Frege abandoned his work in this area.

$\endgroup$
11
  • 9
    $\begingroup$ Hi Joel. Frege actually finished the treatise, didn't he? He acknowledged the inconsistency, and attributed the discovery to Russell. (The book was going to press when this happened.) He kept working in logic afterward, and as for the project of reducing mathematics to logic, I do not think he ever abandoned it, or stopped believing that it was possible. $\endgroup$ Jun 20, 2010 at 1:37
  • 7
    $\begingroup$ Andres, yes he finished it, since it was in press when the contradiction was found, but clearly he had lost heart in it. His famous response to Russell was to write " "Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished." en.wikipedia.org/wiki/Gottlob_Frege Did he go on to do any significant work salvaging it? $\endgroup$ Jun 20, 2010 at 1:51
  • 8
    $\begingroup$ I'm not a philosophical historian, but I do know that Frege discovered (what he thought was) a way to fix his theory; it turned out to result in the universe having a single element, which is another contradiction if one assumes, as (if I recall correctly) Frege seems to implicitly, that "true$\not=$false". $\endgroup$ Nov 10, 2010 at 5:19
  • 13
    $\begingroup$ According to Gregory Moore's history of the axiom of choice, your description of the paradoxes leading to the development of ZFC is incorrect. I'm not an expert in this area, but by his account Zermelo wasn't particularly troubled by the paradoxes. Zermelo's axiomatisation of set theory was produced to overcome criticism of his claimed solution to the well-ordering problem (in which he stated the axiom of choice and derived the well-ordering of the continuum). Russell's theory of types was clearly based on his concerns about the paradoxes, but (Moore claims that) Zermelo's work was not. $\endgroup$ May 25, 2011 at 9:52
  • 13
    $\begingroup$ I am not sure what the word "trivial" means here. Surely Russell's proof is "short" but I think it is not "easy to discover". As a reformulation of Cantor's diagonal proof for existence of more than one infinity which is one the most fundamental theorems of mathematics with a creative proof, I think Russell's theorem and its proof are as non-trivial as Cantor's theorem and its diagonal proof. I believe the idea of forming a really unnatural set $X$ of all sets which don't belong to themselves and asking about $X\in X$ is a really complicated idea in its own type and non-trivial in any sense. $\endgroup$
    – user45939
    May 9, 2014 at 1:10
112
$\begingroup$

The additivity of expected value is absolutely trivial to prove, but (I think) mind-blowing that it is true.

Also, the fact that (finite) sums/products of vector spaces are isomorphic. Extremely easy, but amazingly powerful. It is the reason we can do linear algebra with matrices.

$\endgroup$
8
  • 58
    $\begingroup$ +1 for the linearity of expectation. Even after all these years I still find myself occasionally thinking about some subtle correlations between random variables and (in effect) worrying about whether the correlation affects the expected value, before slapping my forehead and realizing that I'm questioning whether expectation is linear. More than once I've stated the principle to someone who was otherwise quite mathematically sophisticated, and been greeted by a flat refusal to believe that expectation is always linear. $\endgroup$ May 25, 2011 at 15:10
  • 11
    $\begingroup$ I would have to say, though, that additivity of expected value for absolutely integrable random variables on an abstract probability space is not completely trivial to prove, without having gone through all the requisite measure theory... $\endgroup$
    – Terry Tao
    Jan 23, 2015 at 4:38
  • 7
    $\begingroup$ One of the early delights in reading "Categories for the Working Mathematician" was the realization that any map from a direct sum to a direct product can be represented by a matrix of morphisms. Then the fact you mention, together with linear maps from $\mathbb{R} \to \mathbb{R}$ being given by scalar multiplication, gives rise to matrices in the familiar sense. $\endgroup$ Dec 1, 2015 at 16:15
  • 6
    $\begingroup$ @MichaelHardy The importance of such a theory would be immeasurable! $\endgroup$ Dec 6, 2016 at 21:43
  • 7
    $\begingroup$ A good corollary is Buffon's noodle which becomes almost trivial once you believe expectation is additive, despte being a much stronger result than Buffon's needle which is usually proved in a much harder way. en.wikipedia.org/wiki/Buffon%27s_noodle $\endgroup$
    – Dan Piponi
    Apr 4, 2017 at 0:11
96
$\begingroup$

A nontrivial geometric theorem of the type you are looking for may be the Desargues theorem:

If two triangles are in perspective then the intersections of their corresponding sides lie on a line.

In three dimensions there is a trivial visual proof:

Desargues
(source: schillerinstitute.org)

But the theorem is nontrivial because there is no projective proof in two dimensions -- there are projective planes in which the theorem does not hold.

The plot thickens when one investigates the algebraic reasons for this. Hilbert discovered that the Desargues theorem is equivalent to associativity of the underlying coordinate system. So, a projective plane with octonion coordinates, for example, does not satisfy the Desargues theorem.

Addendum. In answer to your first question, the quote is a garbled version of Grothendieck, quoting Ronnie Brown quoting J.H.C. Whitehead. I found it on p.188 of the PDF version of Récoltes et Semailles. Translating back into English, it becomes:

... the snobbery of the young, who think that a theorem is trivial because its proof is trivial.

$\endgroup$
9
  • 7
    $\begingroup$ So it was Whitehead. I found this within "pithypedia": It is the snobbishness of the young to suppose that a theorem is trivial because the proof is trivial. --- Henry Whitehead $\endgroup$ Jun 21, 2010 at 22:01
  • 4
    $\begingroup$ The picture is a nice illustration of the theorem, but I don't see how it makes the proof trivial. At best, it seems to reduce it to a bunch of motivated calculations, but then, any theorem of this sort can be proved by a bunch of calculations. $\endgroup$
    – Ryan Reich
    Feb 14, 2011 at 16:50
  • 17
    $\begingroup$ @Ryan: The picture translates directly into a proof from the axioms for a projective space, which say things like "any two planes meet in a unique line." No calculation is needed. Just the opposite in fact: the possibility of calculation follows from the Desargues theorem. It enables one to introduce coordinates and prove that they form a skew field. $\endgroup$ Feb 14, 2011 at 23:33
  • 2
    $\begingroup$ This proof is beautiful. $\endgroup$ May 25, 2011 at 8:46
  • 8
    $\begingroup$ To expand on John Stillwell's reply: the two planes of the triangles intersect in the unique line EF. A'B' and AB intersect, but as A'B' lies in the plane of A'B'C' and AB lies in the plane of ABC, they must be concurrent with that unique line. Therefore all three intersection points lie on the unique line. This proof breaks down in the coplanar case. $\endgroup$ Dec 1, 2015 at 11:55
90
$\begingroup$

Schur's lemma states in its basic version, that the only endomorphisms of a finite dimensional, irreducible representation over an algebraically closed field are scalars.

It is maybe one of the most useful results in representation theory, however its proof fits into a single line:

Each endomorphism has an eigenvalue and eigenspaces are sub-representations.

$\endgroup$
4
  • 2
    $\begingroup$ Excellent example! $\endgroup$ Jun 21, 2010 at 0:39
  • 1
    $\begingroup$ To be honest, Schur's theorem alone is rather helpless - it doesn't tell us why we should care about irreducibles. It is the semisimplicity of so many interesting algebras / the complete reducibility of so many representations that enables us to have some use for Schur's lemma. As for this complete reducibility, it is in itself a good example of a trivially provable nontrivial result (I am talking about Maschke and the invariant Hermitian form). I remember I have been trying to prove Maschke's theorem for a month until I finally gave up and read the 2-lines proof. – darij grinberg 0 secs ago $\endgroup$ Jun 21, 2010 at 9:52
  • 20
    $\begingroup$ @darij: au contraire, we should care about the simple objects in any category for which all object have finite length, since that is step 0 of any classification theory. For the infinite-dimensional admissible representations which arise in Lie theory, $p$-adic groups, etc. often semisimplicity fails but finite-length holds, and understanding Ext^1's is quite serious. The version of Schur's Lemma there is also "trivial" to prove (by a trick) and extremely important. So oddly, the importance of Schur's Lemma becomes more apparent when extended to a context for which Maschke's theorem fails! $\endgroup$
    – Boyarsky
    Jun 21, 2010 at 12:11
  • 1
    $\begingroup$ Is this the proof Dick Palais mathoverflow.net/questions/24913/quick-proofs-of-hard-theorems/… says that Mackey used, and is it due to Mackey? $\endgroup$ May 25, 2011 at 2:56
76
$\begingroup$

Conway, in chapter IV section 3 of Functions of One Complex Variable, after giving a short proof of Liouville's theorem, says:

"The reader should not be deceived into thinking that this theorem is insignificant because it has such a short proof. We have expended a great deal of effort building up machinery and increasing our knowledge of analytic functions. We have plowed, planted, and fertilized; we shouldn't be surprised if, occasionally, something is there for easy picking."

$\endgroup$
1
  • 3
    $\begingroup$ A great paragraph from my favourite complex analysis book. $\endgroup$
    – user78249
    Jan 23, 2017 at 1:43
72
$\begingroup$

I think a lot of basic category theory fits what you've described. For instance, Yoneda's lemma: an object is determined up to unique isomorphism by the corresponding hom-functor. The proof uses nothing more than the definition of a category. But the lemma is really useful. For instance, suppose you want to show that $X \times Y \simeq Y \times X$ functorially in an arbitrary category (i.e. that products are commutative). Clearly this is true in the category of sets. But if $X,Y$ are in a category, then consider the associated functors $\hom(T, X \times Y) = \hom(T,X) \times \hom(T,Y)$ and $\hom(T, Y \times X) = \hom(T,Y) \times \hom(T,X)$. These are naturally isomorphic (by the case of the category of sets) and so by Yoneda, $X \times Y \simeq Y \times X$ in the arbitrary category.

This is a rather uninteresting example (the universal property of products could have been immediately applied), but let's say one wanted to prove that a certain commutative diagram was cartesian, say that $X,T$ are $S$-objects and $X \to T$ is an $S$-morphism, and we want to show that the "graph morphism" $X \to X \times_S T$ is the pull-back of $T \to T \times_S T$ under $X \to T$. One implication of this is that the graph morphism in the category of schemes is a closed immersion when $T$ is separated over $S$ (and an immersion in any case). Here, using Yoneda's lemma to prove the cartesian claim makes life easier.

In addition, things like moduli spaces make no sense at all without it. (I realize moduli spaces are far more important than anything I just said, but I don't know enough to say anything.)

$\endgroup$
7
  • 6
    $\begingroup$ OK, Yoneda's Lemma is a great example (though your given application is not good, as you say). Something you'll learn if you read Grothendieck's Seminaire Cartan exposes: he always was careful to say the "moduli space" is a pair $(M, \xi)$ with $\xi \in F(M)$, not just $M$ by itself (i.e., $\xi$ encodes a specific isomorphism $F \simeq {\rm{Hom}}(\cdot,M)$). The relevance to your silly examples is that one should not just say that there is "some" isomorphism $X \times Y \simeq Y \times X$ but always make clear what the isomorphism is (i.e., specify its composites with the projections). $\endgroup$
    – Boyarsky
    Jun 20, 2010 at 3:14
  • 17
    $\begingroup$ +1: Yoneda's Lemma is a fantastic example, maybe even close to optimal. $\endgroup$ Jun 20, 2010 at 7:47
  • 16
    $\begingroup$ I think I remember a Gower's quote: "Here is something category theorists will like: it's trivial but not trivially trivial" $\endgroup$ Jun 20, 2010 at 12:54
  • 4
    $\begingroup$ I think these kind of sayings have been with us for a while. Here's another, similar example, having nothing to do with category theory, and which I heard attributed to George Mackey: he was supposedly lecturing, wrote something down on the board, and said it was obvious. Then he stopped, evidently realizing he didn't know why. He left the room and came back 10 minutes (?) later, and said, "It is obvious. But it's not obvious that it's obvious." Did this actually happen? I don't know. But I wouldn't be surprised if this kind of story goes back to the ancient Greeks. $\endgroup$ Jul 27, 2010 at 22:35
  • 11
    $\begingroup$ Well, the original quote is due to Peter Freyd, and it looks almost opposite to the way it's being recounted above: "Perhaps the purpose of categorical algebra is to show that which is trivial is trivially trivial." That is, category theory aids in making the softer bits of mathematics look utterly natural and obvious, so that one can more easily isolate the harder nuggets and attack them with abandon (I wrote words to this effect on the nLab). This is a tremendous service that category theory provides. $\endgroup$
    – Todd Trimble
    Jun 19, 2011 at 13:08
72
$\begingroup$

Bayes' theorem follows directly from the definition of conditional probability and yet it is a very subtle result. The theorem may look trivial, but intelligent people frequently make errors that amount to ignoring or misapplying Bayes' theorem.

$\endgroup$
3
  • 35
    $\begingroup$ The probabilistic content of Bayes' theorem is trivial. The statistical content is not. $\endgroup$ Jun 20, 2010 at 14:39
  • 7
    $\begingroup$ @JohnD.Cook : What is called "Bayesian statistics" is essentially statistical inference in which one assigns probabilities to everything that is uncertain, regardless of whether it is random. Thus the proportion of voters who will vote for Donary Clintrump in a sample of $100$ voters will change if you take a different sample of $100$ voters, and for some purposes that it what it means to call that proportion "random". But is there a probability of $0.4$ that there was life on Mars a billion years ago? That is not "random" in that sense: it is not something that holds in $40\%\ldots\,\qquad$ $\endgroup$ Nov 6, 2016 at 21:06
  • 6
    $\begingroup$ $\ldots\,$of all instances. So a Bayesian may assign probability $0.4$ to that proposition about Mars, whereas a frequentist will refuse to do so, for lack of randomness. The debate about the appropriateness of these approaches probably involves all the philosophical questions about inductive inference. It is because of that the the mathematical triviality known as Bayes's theorem is nontrivial. (@SteveHuntsman) $\qquad$ $\endgroup$ Nov 6, 2016 at 21:06
71
$\begingroup$

Cantor proved that the set of real numbers is uncountable---it cannot be put in bijective correspondence with the natural numbers---but the proof is a simple diagonalization: if the real numbers could be put on a list $z_0$, $z_1$, and so on, then design a real number $d$ whose $n$-th digit differs from the $n$-th digit of $z_n$. Thus, $d\neq z_n$ for every $n$, contradiction!

So the proof seems trivial, perhaps especially now that diagonalization is (as a result) a standard proof method, but the theorem nevertheless seems profound. It was even controversial for various reasons at the time, and certainly it opened up a completely new understanding and treatment of infinity in mathematics.

$\endgroup$
12
  • 13
    $\begingroup$ I hesitate to agree with this one. Cantor's original uncountability proof was not a diagonal argument and did not mention digits at all, and the argument that does mention digits relies on the fact that the numeral system actually behaves in certain ways. And if a mathematician in about 1870 had been handed the question of whether there is some sequence that contains all reals, I don't think one would consider it a routine exercise. $\endgroup$ Jun 20, 2010 at 1:24
  • 7
    $\begingroup$ Also, diagonalization gives a trivial proof that transcendental numbers exist -- a result whose first proof (by Liouville) was considerably less trivial. $\endgroup$ Jun 20, 2010 at 1:25
  • 19
    $\begingroup$ Well, my view is that the theorem is still profound today and the proof is trivial, however things may have seemed in 1870, and so it seems to be an example of what you requested. $\endgroup$ Jun 20, 2010 at 2:05
  • 15
    $\begingroup$ Is this proof really trivial, or is it just that we were all forced to learn it? Is it trivial that there are infinitely many primes? $\endgroup$ Jun 20, 2010 at 2:42
  • 9
    $\begingroup$ The diagonal proof is short and elegant, but I personally don't consider it trivial. $\endgroup$ Jun 21, 2010 at 0:32
47
$\begingroup$

If $D$ is an at most countably dimensional division algebra over $\mathbb{C}$ then $D=\mathbb{C}.$

Proof Let $x\in D\setminus\mathbb{C},$ then $\{(x-a)^{-1}, a\in\mathbb{C}\}$ is an uncountable linearly independent set. $\square$

This is an algebraic variant of the Gelfand–Mazur theorem and it implies countably-dimensional Schur's Lemma over $\mathbb{C}$ (or any uncountable field).

$\endgroup$
1
  • 8
    $\begingroup$ And it can be used to give a simple proof of the Hilbert Nullstellensatz over $\mathbb C$. $\endgroup$
    – Joël
    May 8, 2014 at 22:35
46
$\begingroup$

The union bound:

Pr[A or B] ≤ Pr[A] + Pr[B]

for any two events A and B, regardless of their dependence. This is probably the single most trivial-to-prove theorem I know whose explicit formulation I've actually found useful. (Indeed, more than useful: indispensable! There's a huge number of problems in theoretical computer science and combinatorics that are much easier for a beginner to solve if you give the two-word hint "union bound," than if you don't. And one stops being a beginner at roughly the point when one internalizes the "union bound" hint, and starts applying it to every problem one encounters... :-) )

$\endgroup$
2
  • 3
    $\begingroup$ Thumbs up for this answer. Every single paper in Coding Theory uses the "union bound". I remember the first time I read a paper that uses the "union bound". I didn't know the meaning of the expression at that time and had to google it. My reaction was: pff... is THAT the so-called union bound? $\endgroup$
    – Campello
    Mar 4, 2014 at 11:39
  • 5
    $\begingroup$ In the version that says $\Pr(A_1\cup \cdots\cup A_n) \le \Pr(A_1)+\cdots+\Pr(A_n),$ this is called Bonferroni's inequality. $\qquad$ $\endgroup$ Nov 6, 2016 at 21:12
45
$\begingroup$

Lagrange's Theorem in group theory follows almost straight away from the definition of an equivalence relation. But lots of theorems in finite group theory stem from it in some way.

$\endgroup$
1
  • 7
    $\begingroup$ So should that be taken to express agreement with the guess that the nontriviality would be located in the theorems consequences? $\endgroup$ Jun 20, 2010 at 1:20
33
$\begingroup$

Euclid's proof for the infinitude of prime numbers seems to satisfy your criteria for a trivial proof for a non-trivial theorem.

Theorem. There are more primes than found in any finite list of primes. Proof. Call the primes in our finite list p1, p2, ..., pr. Let P be any common multiple of these primes plus one (for example, P = p1p2...pr+1). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of p1, p2, ..., pr, because all of them leave a remainder of 1 when dividing P. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete.

$\endgroup$
15
  • 10
    $\begingroup$ The Wiles/Taylor-Wiles proof of Fermat's Last Theorem relies crucially at one point on the existence of infinitely many primes, when constructing the auxiliary sets Q_n of primes with certain properties in order to perform the patching argument to prove R=T. More precisely it relies on the Cebotarev density theorem, which says even more---there are infinitely many primes with certain Galois-theoretic properties. $\endgroup$ Jun 20, 2010 at 6:14
  • 5
    $\begingroup$ Adrian, it is crucial in many applications that one can choose a prime number that avoids a certain number of bad properties. Typical may be a prime fitting a congruence condition while also not dividing some number. In principle this stuff is settled using Dirichlet's theorem on primes in arithmetic progressions, which is midway between Euclid's raw theorem that there are infinitely many primes and the Chebotarev density theorem that Kevin refers to. For example, the most elementary proof of the Hasse--Minkowski theorem that classifies quadratic forms over Q uses this method in the proof. $\endgroup$
    – KConrad
    Jun 20, 2010 at 6:30
  • 11
    $\begingroup$ Kevin, since your brought up the FLT topic, you'll like this story: so when Wiles was teaching his graduate course on his proof of FLT (the proof that had a gap, not known at that time), at some point he gave an argument which required that some prime not be too small, maybe bigger than 5 or something. Then Faltings said "So this proof doesn't need any primes bigger than 7", which got a big laugh from everyone. $\endgroup$
    – BCnrd
    Jun 20, 2010 at 7:09
  • 7
    $\begingroup$ @KConrad: indeed, your description hits upon my favorite way of phrasing Euclid's proof. If there were only finitely many primes, then their product, $N$, would be divisible by every prime number and thus would not be relatively prime to any integer greater than $1$. But that's ridiculous: consider $N+1$... $\endgroup$ Jun 20, 2010 at 7:46
  • 5
    $\begingroup$ Thanks a lot you guys. Your replies to my initial comment are great. $\endgroup$ Jun 20, 2010 at 14:23
30
$\begingroup$

Chebyshev's inequality is the following:

Suppose $X, \mu$ is a measure space, and $f \in L^p(X, \mu)$, then for all $t > 0$

$\mu( \{x \in X : |f(x)| \geq t \} ) \leq \frac{1}{t^p} \|f\|_{L^p(X, \mu)}^p$.

The proof is trivial:

Observe that

$\mu( \{x \in X : |f(x)| \geq t \} )t^p = \int_{X} 1_{|f| \geq t}(x)t^p \leq \int_{X} |f|^p = \|f\|_{L^p(X, \mu)}^p$

and divide both sides by $t^p$.

This is a fundamental inequality in the the study of the interpolation of L^p spaces.

$\endgroup$
28
$\begingroup$

Let me add to this long list the famous Nakayama lemma, a crucial result in commutative algebra, and whose original claim is as follows:

Let $(R,\mathfrak m)$ be a local ring and $M$ a finitely generated $R$-module. If $\mathfrak mM=M$ then $M=0$.

Its proof is very simple: consider $x_1,\dots,x_n$ a minimal system of generators; then $x_n=a_1x_1+\cdots+a_nx_n$ with $a_i\in\mathfrak m$, so $(1-a_n)x_n=a_1x_1+\cdots+a_{n-1}x_{n-1}$ and since $1-a_n$ is invertible we get $x_n\in\langle x_1,\dots,x_{n-1}\rangle$, so $x_1,\dots,x_{n-1}$ is a system of generators, a contradiction.

$\endgroup$
27
$\begingroup$

What about the pigeonhole principle?

$\endgroup$
8
  • 67
    $\begingroup$ Some might call that a trivial theorem with a non-trivial proof ... $\endgroup$
    – gowers
    May 25, 2011 at 18:09
  • 5
    $\begingroup$ Agreed. I don't even know a proof, or where to find one. $\endgroup$ May 27, 2011 at 3:01
  • 15
    $\begingroup$ One usually proves the pigeonhole principle---in the form of the assertion that there is no injection from a natural number $n$ to a smaller natural number $k$---by induction on $n$. It is clearly true for $n=0$; if true at $n$, and we have an injection of $n+1$ to some smaller $k+1$, then by swapping two points we can produce an injection from $n$ to $k$. It is an interesting result that in very weak formal systems, one can separate the weak pigeonhole principal that there is no injecton from $2n$ to $n$ from the stronger assertion that there is no injection from $n+1$ to $n$. $\endgroup$ Jul 24, 2013 at 3:41
  • 6
    $\begingroup$ @Servaes I find it valuable and important to give names to one's fundamental mathematical principles and to understand when they are serving as axioms or whether they are reducible to still more fundamental principles. $\endgroup$ May 18, 2017 at 10:46
  • 4
    $\begingroup$ Here's another form of the pigeonhole principle: if $a_1+\cdots+a_n>b_1 + \cdots + b_n$ then $a_i>b_i$ for some $i$. The proof is that the contrapositive is trivial. (The "usual" form of the pigeonhole principle is the case in which $b_i=1$ for all $i$.) $\endgroup$
    – Ira Gessel
    Dec 26, 2020 at 2:43
24
$\begingroup$

How about the theorem that there are two irrational numbers $a$ and $b$ with $a^b$ rational?

Proof. Either $c:=\sqrt{2}^\sqrt{2}$ is rational, or else $c$ is irrational and $c^\sqrt{2}=\sqrt{2}^2=2$ is rational.

$\endgroup$
9
  • 1
    $\begingroup$ Nothing comes to mind. But is this any more than a puzzle with a clever solution? Was this proven before using some deep results, and then someone noticed it had a clever one-line proof? $\endgroup$ May 9, 2014 at 1:29
  • 2
    $\begingroup$ @MonroeEskew: There is something subtle here: The proof uses the excluded middle principle, which of course I consider valid but Brouwer and the Intuitionistic school do not. I wonder whether this is the first theorem ever that has a large gap between excluded-middle proof and an explicit proof. I also do not know who proved it first this way. It must be a classic. $\endgroup$ May 9, 2014 at 11:42
  • 20
    $\begingroup$ @BoazTsaban There is also a constructive proof: take $a=\sqrt{2}$ and $b=\log_2 (9)$, which are both irrational, but $a^b=3$ is rational $\endgroup$
    – user49822
    Jul 23, 2014 at 10:13
  • 7
    $\begingroup$ Along similar prime factorization lines, it's very easy to show that the solution to $x^x = 2$ must be irrational. $\endgroup$
    – Todd Trimble
    Nov 23, 2015 at 19:06
  • 13
    $\begingroup$ Michael Hardy's proof idea can be made to work as follows. Think about the function $x\mapsto 2^{1/x}$ for $x>0$. This is a monotonic function so for cardinality reasons there is an irrational number $x$ such that $2^{1/x}$ is also irrational. Put $a=2^{1/x}$ and $b=x$. $\endgroup$ Dec 1, 2015 at 9:54
24
$\begingroup$

The Chevalley-Warning theorem.

The story goes that the $r=1$ case was conjectured by Artin and given to Ewald Warning as a thesis problem, but when Chevalley visited town he heard it and immediately suggested expanding $f^{q-1}$ and summing over ${\bf F}_q^n$, so Warning's thesis problem became Chevalley's theorem $-$ but Warning recovered by generalizing to $r$ simultaneous equations, so all was well.

(warning [sic]: I can't easily corroborate that Ewald Warning actually wrote his thesis on this result, or indeed completed a doctorate at all; the Mathematics Genealogy Project doesn't show a student of Emil Artin named Ewald Warning, nor indeed does it have any entry for the name Warning. There's an Obituary that might give more information.)

$\endgroup$
23
$\begingroup$

What about the irrationality of $\sqrt{2}$, the non-triviality of which is witnessed by the fact that the philosophy of the school of Pythagoreans was based on the belief that such numbers do not exist. The proof, on the other hand, is a well-known elementary one.

$\endgroup$
6
  • $\begingroup$ I disagree that elementary is the same as trivial. If I'm thinking of the same elementary one as you are, it relies on unique factorization, whose proof is not trivial. $\endgroup$
    – Ryan Reich
    May 24, 2011 at 23:19
  • $\begingroup$ Does it really require unique factorization, or only a special case of unique factorization whose proof might be a lot simpler? $\endgroup$ May 25, 2011 at 1:40
  • 2
    $\begingroup$ I think that it only requires the fact that every integer is even or odd, and a very weak form of infinite descent: If $\sqrt2 = a/b$, then we may factor out all common $2$'s (there's the infinite descent) so that not both $a$ and $b$ are even. Then $\Rightarrow$ $a^2 = 2b^2$ $\overset*\Rightarrow$ $a = 2k$ $\Rightarrow$ $b^2 = 2k^2$ $\overset*\Rightarrow$ $b = 2\ell$, where the ($*$)'s indicate steps requiring the even–odd dichotomy. $\endgroup$
    – LSpice
    May 25, 2011 at 2:24
  • 17
    $\begingroup$ On the same lines, the proof of irrationality of the golden ratio: If $x=1+1/x$ and $x=p/q$ with positive integers $p>q$, then also $x=q/(p−q)$, so there is no minimal fraction for x. $\endgroup$ May 25, 2011 at 10:05
  • 12
    $\begingroup$ The proof of the irrationality of $\sqrt{2}$ can also be done by a method similar to what Pietro Majer proposes for the golden ratio. Assume $n/m = \sqrt{2}$ and this is in lowest terms. Then $(2m-n)/(n-m) = \sqrt{2}$, but this is in still lower terms, so there's a contradiction. $\endgroup$ Jun 21, 2011 at 23:49
23
$\begingroup$

M.H. Stone showed in the following paper that a Boolean algebra is nothing but a ring with an identity in which every element is an idempotent. The proof is trivial but the discovery caused a revolution in the theory of Boolean algebras.

Subsumption of the Theory of Boolean Algebras under the Theory of Rings (1935)

$\endgroup$
3
  • 3
    $\begingroup$ Now I am curious. Could you please say something about the content of the revolution in the theory of Boolean Algebras that was caused by the theorem, for someone who knows not too much about the theory of Boolean algebras? $\endgroup$
    – user22882
    May 19, 2014 at 16:23
  • $\begingroup$ @rem Stone proved Stone's representation theorem using the aforementioned fact. This theorem has great many applications, e.g. the Stone–Weierstrass theorem and the Stone-Cech compactification. For other applications see for example Stone Spaces by Johnstone and Appendix of the book Boolean Algebras by Sikorski. $\endgroup$ May 19, 2014 at 22:10
  • 8
    $\begingroup$ I once got an email from Gian-Carlo Rota in which he told me that the fact that Boolean algebras are rings had not been very fruitful. I presume he meant not much in the way of research on Boolean algebras resulted from it. But one thing it's useful for is that if you know that something is true of all commutative rings, you don't need to write a separate proof that it's true of Boolean algebras. $\endgroup$ Jul 4, 2014 at 3:26
22
$\begingroup$

I think Akhil may be right. I believe Grothendieck did say something along the lines of this quote, specifically in reference to Belyi's Theorem . My recollection is that Belyi proved this theorem without knowing that Grothendieck was interested in it, and in working out his theory of Dessin D'Enfants, Grothendieck found he needed this result, but couldn't prove it. He then discovered that Belyi had given a rather elementary proof (I'll hesitate to call it trivial myself, since I recall finding it pretty clever).

If anyone has a copy of Grothendieck's Esquisse D'un Programme, maybe the specific quote is in there? I don't seem to have an English copy on my laptop, and all of Grothendieck's writing has been removed from the Grothendieck Circle's webpage per Grothendieck's request. (Interestingly, Wikipedia says this request was made in a letter to Illusie in January 2010.) I don't immediately see such a quote in the French version.

Edit: Here is the English translation of a relevant passage from Esquisse d'un Programme due to Leila Schneps and Pierre Lochak, as it appears in London Math. Soc. Lecture Notes Series vol. 242 (pp. 254-255; around page 15 on Grothendieck's typewritten manuscript):

Every finite oriented map gives rise to a projective non-singular algebraic curve defined over $\overline{\mathbb{Q}}$, and one immediately asks the question: which are the algebraic curves over $\overline{\mathbb{Q}}$ obtained in this way -- do we obtain them all, who knows? In more erudite terms, could it be true that every projective non-singular algebraic curve defined over a number field occurs as a possible "modular curve" parametrising elliptic curves equipped with a suitable rigidification? Such a supposition seemed so crazy that I was almost embarrassed to submit it to the competent people in the domain. Deligne when I consulted him found it crazy indeed, but didn't have any counterexample up his sleeve. Less than a year later, at the International Congress in Helsinki, the Soviet mathematician Bielyi announced exactly that result, with a proof of disconcerting simplicity which fit into two little pages of a letter of Deligne -- never, without a doubt, was such a deep and disconcerting result proved in so few lines!

In the form in which Bielyi states it, his result essentially says that every algebraic curve defined over a number field can be obtained as a covering of the projective line ramified over the points $0, 1$ and $\infty$. This result seems to have remained more or less unobserved. Yet it appears to me to have considerable importance. To me, its essential message is that there is a profound identity between the combinatorics of finite maps on the one hand, and the geometry of algebraic curves defined over number fields on the other. This deep result, together with the algebraic-geometric interpretation of maps, opens the door onto a new, unexplored world -- within reach of all, who pass by without seeing it.

$\endgroup$
18
$\begingroup$

Stokes' theorem is certainly important, but it's proof is very easy: it essentially reduces (by a standard partition-of-unity argument) to the case where the compact manifold-with-boundary is a half-space, and then the definitions show that it is just the fundamental theorem of calculus.

$\endgroup$
8
  • $\begingroup$ Hm. Maybe I'm not remembering the proof I learned correctly then (or I missed something then). $\endgroup$ Jun 20, 2010 at 2:42
  • 15
    $\begingroup$ You may be thinking of the proof of the generalized Stokes theorem for differential forms ($\int_M d\omega=\int_{\partial M}\omega$), in which a partition of unity reduces the proof to the case where $M$ is a half space and $\omega$ has compact support – a case where the theorem becomes trivial indeed. But due to the need for partitions of unity and good coordinate choices, I don't agree that the proof can be called trivial. $\endgroup$ Jun 20, 2010 at 2:58
  • 4
    $\begingroup$ If a non-trivial result seems to be proved by a trivial method, then the work has likely been shifted elsewhere or missed. In the present circumstances, what you slipped under the rug is justification of methods of computing these integrals, illustrated by the fact that global coordinates on the plane don't restrict to local coordinates used in the definition of integration on the closed unit disc as a 2-manifold with boundary (e.g., the circle isn't locally the zero locus of either coordinate). This ties in with Harald's comments. To patch it needs nothing deep, but does require work. $\endgroup$
    – Boyarsky
    Jun 20, 2010 at 3:39
  • 14
    $\begingroup$ One of the origins of Bourbaki: no rigorous proof of Stokes' theorem could be found in contemporary books. $\endgroup$ Jun 21, 2010 at 0:41
  • 13
    $\begingroup$ Michael Spivak discusses this precise example in his "Calculus on Manifolds": "There are good reasons why theorems should all be easy and the definitions hard ... Definitions serve a twofold purpose: they are rigorous replacements for vague notions, and machinery for elegant proofs ... Stokes' Theorem shares three important attributes with many fully evolved major theorems: (1) It is trivial. (2) It is trivial because the terms appearing in it have been properly defined. (3) It has significant consequences." $\endgroup$ May 25, 2011 at 12:50
17
$\begingroup$

Diagram chasing gives an entire class of examples of nontrivial theorems with trivial proofs.

$\endgroup$
2
  • 25
    $\begingroup$ I think the claim that proofs by diagram chasing are trivial needs justification. Recently I watched an excellent mathematician try to prove something by diagram chasing (on the blackboard, in the middle of a class). He tried briefly, failed, and then gave up, instead assigning it as homework. I agree that diagram chasing arguments do not feel very deep (or very interesting), but that's not the same thing as trivial...is it? $\endgroup$ Jun 20, 2010 at 7:54
  • 1
    $\begingroup$ The best I can do is this: mathoverflow.net/questions/9930/… $\endgroup$ Jun 20, 2010 at 11:52
16
$\begingroup$

Proofs of identities in line with the book A=B (Petkovsek, Wilf & Zeilberger) are trivial - they amount to simple computation. However, the theorems are certainly non-trivial. It is possibly hard to find the right "Ansatz", and you need a computer to find the certificate, but checking the certificate is trivial.

$\endgroup$
16
$\begingroup$

If ${n \choose k} < 2^{k(k-1)/2-1}$, then there exists a 2-coloring of the edges of the complete graph on $n$ vertices with no monochromatic $k$-clique.

Proof: Color randomly and the expected number of monochromatic $k$-cliques is smaller than 1.

$\endgroup$
3
  • $\begingroup$ Nice. How good an estimate does it give? For k=3, n = 4 seems to be the upper limit guaranteed by the inequality, where as a 2-coloring exists for n=5. Similarly for k=4 I would hope for such colorings for n larger than the guaranteed 7 given by the inequality. Gerhard "Ask Me About System Design" Paseman, 2011.05.25 $\endgroup$ May 25, 2011 at 8:01
  • 3
    $\begingroup$ Gerhard, these so-called Ramsey numbers are notoriously hard to compute. I don't have the latest news on the subject, but the lower and upper bounds on $n$ are very roughly $\sqrt{2}^k$ and $4^k$ respectively (the lower one coming from this "trivial" proof by Erdös from 1947), and improving on either the $\sqrt{2}$ or the 4 is a famous open problem. $\endgroup$ May 25, 2011 at 10:18
  • 1
    $\begingroup$ @Gerhard: Although Johan is right about the difficulty of computing these Ramsey numbers, the particular one you mentioned, for $k=4$, is known. Take the complete graph whose vertices are the elements of the 17-element field, and color edges according to whether their endpoints differ by a square. This has no monochromatic 4-clique. But every 2-coloring of the edges of the complete graph on 18 vertices has a monochromatic 4-clique. (I believe the problem for $k=5$ remains open, though rather tight bounds are known. For larger $k$ things get really bad.) $\endgroup$ May 25, 2011 at 13:09
12
$\begingroup$

Here is what Grothendieck says in Recoltes et semailles.

Dans le cas cohérent, la démonstration du théorème de bidualité est d’ailleurs triviale. Cela n’empêche que c’est ce que j’appelle sans hésitation un théorème profond”, car il donne une vision simple et profonde de choses qui ne sont pas comprises sans lui. (Voir à ce sujet l’observation de J. H. C. Whitehead sur “le snobisme des jeunes, qui croient qu’un théorème est trivial, parce que sa démonstration est triviale”, observation que je reprends et sur laquelle je brode dans la note “Le snobisme des jeunes — ou les défenseurs de la pureté”, n◦27).

May be someone who has the english version can provide a translation. This is note 947, page 763 in the French pdf version, a search for the word biduality should find it quickly.

So, in short, the biduality theorem is a profound theorem with a trivial proof in the coherent case. And the quote you are referring to is probably due to Whitehead.

$\endgroup$
3
  • $\begingroup$ So maybe J.H.C. Whitehead is the answer to my first question. (?) $\endgroup$ Jun 20, 2010 at 16:20
  • 9
    $\begingroup$ Well, with all due respect, I beg to differ with A.G. on this one. Whether in the coherent or etale cases I think that to call the proof of the bi-duality theorem trivial is seriously misleading to anyone who has not gone through the proof (especially if to prove the result in a form which can be used in examples). It's a good example of calling something "trivial" because all of the gigantic effort went into setting up the foundations to make the "trivial" proof. One could likewise call Grothendieck-Riemann-Roch trivial... $\endgroup$
    – BCnrd
    Jun 20, 2010 at 18:38
  • 2
    $\begingroup$ Grothendieck duality: trivial and profound at the same time. $\endgroup$ Jun 21, 2010 at 0:30
10
$\begingroup$

Poincare Recurrence Theorem: https://en.wikipedia.org/wiki/Poincar%C3%A9_recurrence_theorem

Let $(X,\Sigma,m)$ be a finite measure space and let $f:X \to X$ be a measure-preserving map. If $E \in \Sigma$, then almost every point in $E$ returns to $E$; i.e., $m (\{x \in E: \exists N: \forall n>N \quad f^n(x) \not \in E \})=0$

A proof can be found e.g. in Arnold's "Mechanics"; there are some on PlanetMath, too. All use basically the definition of a measure, and maybe (or not) a necessary condition for convergence of a series of real numbers.

The theorem describes behavior of certain systems in statistical mechanics or thermodynamics, but it also has many mathematical consequences. It was one of first results in ergodic theory. It can be used to prove e.g. that an orbit of an irrational rotation of a circle is dense. Relations with recent developments in ergodic theory and dynamical systems are discussed by Barreira, doi:10.1142/9789812704016_0039.

$\endgroup$
2
  • $\begingroup$ Does the nontriviality of this theorem reside in the fact that it has many mathematical consequences? (Could it be that if a theorem is nontrivial, the nontriviality is either in its proof or in its consequences?) $\endgroup$ Jun 19, 2011 at 15:36
  • $\begingroup$ Poincare recurrence is a manifestation of the pigeonhole principle, which has made many appearances in this thread! $\endgroup$
    – pre-kidney
    Feb 14, 2016 at 5:10
9
$\begingroup$

The number of partitions of $n$ into $m$ parts is equal to the number of partitions of $n$ into parts, the largest of which is $m$.
This can be proved if we read at a graph which represents a partition of $n$ vertically.

$\endgroup$
3
  • 1
    $\begingroup$ Is this really nontrivial? $\endgroup$
    – Asaf Karagila
    May 28, 2016 at 8:09
  • 7
    $\begingroup$ @AsafKaragila Ask someone who does not know much about partitions if he/she thinks that this is "obvious". $\endgroup$ May 28, 2016 at 11:35
  • 1
    $\begingroup$ I think it'll be helpful to specify that the "graph" really refers to a Young tableau $\endgroup$ Apr 11, 2023 at 8:27
7
$\begingroup$

This is a comment to Sunil's answer on Euclid's proof of the infinitude of primes but I don't have enough point to leave a comment.

There is a generalization of Euclid's proof which should be well known but I seldom see it mentioned. If $a_1,\ldots,a_r$ are pairwise relatively prime integers, then for any subset $I \subset \{1,\ldots,r\}$, $a_{r+1}=\prod_{i \in I}a_i +\prod_{i \not\in I}a_i$ is relatively prime to all the $a_1,\ldots,a_r$.

$\endgroup$
1
  • 3
    $\begingroup$ Note that this indeed is a generalization: original Euclid's proof uses $I=\emptyset$ $\endgroup$ Jan 23, 2013 at 14:32
7
$\begingroup$

Here was a progression of elegant short proofs, with an increasing content:

  1. M.Mather, Counting homotopy types of manifolds. Topology 4 (1965), 93-94.
  2. James M. Kister, Homotopy types of ANR's. Proc. Amer. Math. Soc. 19 (1968), 195.
  3. Włodzimierz Holsztyński, A remark on homotopy and category domination. Michigan Math. J. Volume 18, Issue 4 (1971), 409.

The last one was trivial.

$\endgroup$
6
$\begingroup$

I like the Connectedness argument, which follows straight from the axioms of a topology. A topological space $\left(\mathbf{X},\,\mathcal{T}\right)$ is connected iff $\mathbf{X}$ and $\emptyset$ are the only members of $\mathcal{T}$ which are both open and closed at once. $\mathbf{A} \subset \mathbf{X}$ is both open and closed iff its complement $\mathbf{X} \sim \mathbf{A}$ is also both open and closed, thus $\mathbf{X} = \mathbf{A} \bigcup \left(\mathbf{X} \sim \mathbf{A}\right)$ is not a union of disjoint open sets iff either $\mathbf{A} = \emptyset$ or $\mathbf{A} = \mathbf{X}$.

It is main idea in "the" (I don't know of any others) proof that a connected topological group $\left(\mathfrak{G},\,\bullet\right)$ is generated by any neighbourhood $\mathbf{N}$ of the group's identity $e$, i.e. $\mathfrak{G} = \bigcup\limits_{k=1}^\infty \mathbf{N}^k$. Intuitively: you can't have a valid "neighbourhood" in the connected topological space without its containing "enough inverses" of its members to generate the whole group in this way.

For completeness, the proof runs: We consider the entity $\mathbf{Y} = \bigcup\limits_{k=1}^\infty \mathbf{N}^k$. For any $\gamma \in \mathbf{Y}$ the map $f_{\gamma} : \mathbf{Y} \to \mathbf{Y}; f_{\gamma}(x) = \gamma^{-1} x$ is continuous, thus $f_{\gamma}^{-1}\left(\mathbf{N}\right) = \gamma \, \mathbf{N}$ contains an open neighbourhood $\mathbf{O}_{\gamma} \subseteq \mathbf{N}$ of $\gamma$, thus $\mathbf{Z} = \bigcup\limits_{\gamma \in \mathbf{Y}} \mathbf{O}_{\gamma}$ is open. Certainly $\mathbf{Y} \subseteq \mathbf{Z}$, but, since $\mathbf{Y}$ is the collection of all products of a finite number of members of $\mathbf{N}$, we have $\mathbf{Z} \subseteq \mathbf{Y}$, thus $\mathbf{Z} = \mathbf{Y}$ is open. If we repeat the above reasoning for members of the set $\mathbf{X} \sim \mathbf{Y}$, we find that the complement of $\mathbf{Y}$ is also open, thus $\mathbf{Y}$, being both open and closed, must be the whole (connected) space $\mathfrak{G}$.

The above is one of my favourite proofs of all time, up there in my favourite thoughts with Beethoven's ninth and Bangles "Walk Like an Egyptian" (or anything by Captain Sensible) and it all hinges on the connectedness argument. It is extremely simple, (not trivial, so it itself doesn't count for the Wiki, sadly) and its result unexpected and interesting: you can't define a neighbourhood without including enough inverses. This is an example of "homogeneity" at work: throwing the group axioms into another set of axioms makes a strong brew and tends to be the mathematical analogue of turfing a kilogram chunk of native sodium into a bucket of water: the group operation tends to clone structure throughout the whole space, thus not many axiom systems can withstand this assault by this cloning process and be consistent. When all the bubbling, fizzing, toiling and trouble is over, only very special systems can be left, thus all kinds of unforeseen results are forced by homogeneity, and the above is a very excitingly typical one.

$\endgroup$
2
  • $\begingroup$ Wonderful answer. $\endgroup$
    – Arrow
    Dec 8, 2015 at 14:14
  • $\begingroup$ @Arrow Thanks. I can recall being a little bothered by the proof of a topological group's being generated by any neighborhood when I first saw it in Sagle and Wade "Introduction to Lie Groups and Lie Algebras" many years ago. It was so unexpected simple and clear that I mistrusted it! (understanding something at depth at very first reading doesn't happen all that often to me). It was only some years later - maybe ten or so - that I suddenly realized that the "cloning" of local structure that happens by dent of translation is what makes things so "rigid" and a topological group so specialized. $\endgroup$ Dec 9, 2015 at 5:27

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