Nontrivial theorems with trivial proofs

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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:

_{(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.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.

Answer 13

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.

Answer 14

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.

Answer 15

What about the pigeonhole principle?

Answer 16

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.

Answer 17

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.

Answer 18

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

Answer 19

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)

Answer 20

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.

Answer 21

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.

Answer 22

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

Answer 23

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.

Answer 24

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.

Answer 25

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.

Answer 26

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.

Answer 27

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.

Answer 28

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.

Answer 29

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

Answer 30

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.