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

The finite intersection property: If $C_\alpha$ (for $\alpha\in I$) are closed subsets in a compact space, and every finite intersection of $C_\alpha$-s is nonempty, then the whole intersection $\bigcap_{\alpha\in I}C_\alpha$ is nonempty.

Proof. Otherwise, the complement $\bigcup_{\alpha\in I}C_\alpha^c$ is an open cover of the space without a finite subcover.

You may prefer the version with the $C_\alpha$-s compact and no assumption on the space containing them, but this is the same since we can intersect all $C_\alpha$-s with some fixed $C_{\alpha_0}$.

To me, it is surprising that this trivial proof gives such a useful assertion.

One may argue that this boils down to De Morgan's Laws, which are also trivial but very useful!

Answer 2

I have looked through the answers but haven't come across Cantor's theorem, that the there is no surjection from a set $M$ on its power set $P(M)$.

I don't know whether the proof should be considered trivial, but it is short and easy to understand. The assumption of a surjection $f\colon M\rightarrow P(M)$ leads to the contradictory set $A_f:=\{m\in M\colon m\not\in f(m)\}$, the contradiction being $A_f\in A_f\longleftrightarrow A_f\not\in A_f$.

The implication of the theorem is that there is no "largest" set/infinitude!

Answer 3

The diamond lemma, a.k.a. Newman's lemma, which says that a terminating system is globally confluent if and only if it is locally confluent, has a very simple proof based on Noetherian induction. This proof was first published by Gérard Huet in 1980; see the Wikipedia article.

But this lemma has many nontrivial applications and, somewhat like the example of linearity of expectation mentioned elsewhere, it can often seem amazing that the possibly very complicated ways in which paths can diverge is irrelevant as long as local steps can be corrected.

Answer 4

Many theorems of finite group theory have such nature: they are non-trivial but their proofs are not so hard. But in the frame of infinite groups or finite loops, those are challenging problems. Below are some example:

1- a finite group with just two conjugacy classes is $\mathbb{Z}_2$.

2- a non-trivial finite $p$-group has non-trivial center.

3- finite groups have Lagrange property.

4- a finite group in which its all nontrivial proper subgroup have order a fixed prime $p$ has order $p^2$ and so is abelian.

Many theorems of finite dimensional vector spaces are also non-trivial with trivial proofs: the similar theorems are not true for modules or infinite dimensional cases or have hard proofs.

Answer 5

The Nielsen-Schreier Theorem : a subgroup of a free group is a free group.

The algebraic proofs are rather complicated, whereas the topological proof is trivial : a group is free if and only if it acts freely on a simplicial tree.

Of course the theory of covering spaces and fundamental groups is hidden somewhere.

Answer 6

The ultimate example that I know of is the Central Limit Theorem, described by Tijms as ``the unofficial sovereign of probability theory''. Incidentally, its significance took time to sink in- it has been forgotten and reproved repeatedly throughout its history.

Classical CLT: Given iid random variables $X_1,X_2,\ldots$ of mean $0$ and variance $1$, the sequence of random variables $\frac{X_1+X_2+\cdots+ X_n}{\sqrt{n}}$ converges in distribution to a normal random variable with mean $0$ and variance $1$.

The proof just Taylor's theorem and the definition of the exponential function (and Lévy's continuity theorem to confirm that the trivial proof indeed implies the theorem statement):

Proof: The Taylor expansion of the characteristic function $Ee^{itX}$ is: $1-t^2/2+o(t^2)$. Plugging in, the characteristic function of $\frac{X_1+X_2+\cdots+X_n}{\sqrt{n}}$ is $\left(1-t^2/2n+o(t^2/n)\right)^n$ which converges to $e^{-t^2/2}$. By Lévy's continuity theorem, convergence of characteristic functions implies convergence in distribution.QED

Answer 7

$$ \int u\,dv = uv - \int v \, du. $$ The whole theory of generalized functions follows, as do lots of other things.

Answer 8

My personal favorite is the Noether-Deuring theorem.

Let $K \subseteq L$ be fields with $L$ of finite dimension over $K$, $R$ a finite-dimensional algebra over $K$. Then $L \otimes R$ is naturally an algebra over $L$, thought of as "extending $R$ by scalars in $L$".

Let $U, V$ be finite-dimensional modules over $R$; then $L\otimes U$ and $L \otimes V$ are modules over $L \otimes R$. Obviously, any isomorphism between $U$ and $V$ as $R$-modules can be extended to an isomorphism between $L\otimes U$ and $L \otimes V$ as $L \otimes R$-modules.

Therefore, if $U \simeq V \in R\text{-mod}$, then $L \otimes U \simeq L \otimes V \in L \otimes R\text{-mod}$.

The Noether-Deuring theorem is that the converse is true. That is, if $L \otimes U \simeq L \otimes V \in L \otimes R\text{-mod}$, then $U \simeq V \in R\text{-mod}$.

Proof: If $L \otimes U \simeq L \otimes V \in L \otimes R\text{-mod}$, then it is also true in $R\text{-mod}$. But there, $L \otimes U \simeq U^n$, where $n = [L: K]$. Therefore, $U^n \simeq V^n \in R\text{-mod}$. By Krull-Schmidt, this is enough to show that $U \simeq V \in R\text{-mod}$.

Note that this isomorphism isn't natural; in order to get a natural choice of isomorphism, "descent data" is needed. But it's surprising that even without that "descent data", there is some isomorphism.

Answer 9

Farkas's Lemma and a variety of other theorems of alternatives are fundamental in the theory of optimization. The proof simply couples the Fundamental Theorem of Linear Algebra with the fact that a positive vector and a (nonzero) nonnegative vector in Euclidean space cannot be orthogonal.

Answer 10

I am surprised that no one has mentioned Cantor-Schröder-Bernstein Theorem. It certainly is a non-trivial theorem until you see it for the first time. The proof I linked here, I believe, could be considered a trivial one if you draw "the picture" and observe how the constructed bijection maps the elements.

Another example could be Łoś's theorem. The proof is basically going through definition of ultraproducts and carrying out an induction on formulas. It is tedious to write down but at its core a trivial one. Though, I am reluctant to call the theorem itself trivial!

Answer 11

What about Zermelo's Theorem?

Every finite game of perfect information with no tie is determined.

Proof. $$ \exists x_1\forall y_1\dots\exists x_n\forall y_n A\vee\forall x_1\exists y_1\dots\forall x_n\exists y_n\neg A $$ where $A$ states that a final position is reached where player 1 wins.

Answer 12

The proof that the deRham cohomology is equivalent to singular cohomology on a smooth manifold is in some sense trivial: one shows that the de Rham complex is a soft (hence cohomologically trivial) resolution of the constant sheaf, and it is not too hard to show that the cohomology of the constant sheaf is the same as singular cohomology. In a sense, it just follows from "abstract nonsense" about derived functors being computable from acyclic resolutions and the fact that soft resolutions are acyclic (a partition of unity argument). But it is certainly a nontrivial theorem.

Answer 13

Though a proof may be trivial that doesn't mean it was trivial to find it in the first place !

Euler's Rotation Theorem of elementary Euclidean Geometry (which states that for any arbitrary rigid motion of a sphere about its center there exists a diameter of the sphere (the 'Euler Axis') and axial rotation about it which results in the same net displacement) is not a trivial statement, but it does have a very simple proof based on the following diagram :

The proof consists simply of :

The desired rigid motion can be performed by a succession of two $180^{\circ}$ axial rotations, namely (1) $180^{\circ}$ about whichever of the horizontal axis $L$ and vertical axis $M$ overlays the great circle upon itself upside down, and (2) a $180^{\circ}$ axial rotation which then rectifies the great circle to its correct final position. Hence etc.

Like the theorem itself the supporting statements relied upon in the above proof are trivial to prove, but unlike the theorem they are intuitively obvious :

1. the final end result of a rigid motion of a sphere about its center has been attained once any great circle has been placed in its correct final position

2. if by such a motion a great circle on a sphere has been overlayed upon itself upside down in any manner then it can be rectified to its original position by a single $180^{\circ}$ axial rotation about one of its diameters

3. a succession of two $180^{\circ}$ axial rotations about respective axes is equivalent to a single axial rotation of some angle, namely about the polar axis of the plane containing the two axes

The above proof along with another longer one was originally posted in this answer to Euler's rotation theorem revisited - Elementary geometric proofs.

An article about this topic, Elementary Geometric Proofs Of Euler’s Rotation Theorem, is also posted here.

Answer 14

The theorem that differential generalized cohomology is characterized by a differential cohomology exact hexagon -- originally asked/conjectured generally and proven for the ordinary case by (Simons-Sullivan 07) -- turns out to follow formally "by stable cohesion" (Bunke-Nikolaus-Völkl 13). A quick review is here: ncatlab.org/schreiber/show/IHP14.

Answer 15

Preliminary content

Suppose that $\alpha$ is an ordinal. A rank-into-rank embedding is an elementary embedding $j:(V_{\alpha},\in)\rightarrow(V_{\alpha},\in)$.

The $n$-th classical Laver table is the unique algebraic structure $A_{n}=(\{1,\dots,2^{n}-1,2^{n}\},*)$ such that

1. $x*(y*z)=(x*y)*(x*z)$, and

2. $x*1=x+1\mod 2^{n}$

whenever $x,y,z\in\{1,\dots,2^{n}-1,2^{n}\}$.

From a single non-identity rank-into-rank embedding, one can generate a free self-distributive algebra, and the Laver tables are finite quotient algebras obtained from the rank-into-rank embeddings.

For more information, please see Chapter 11 in the Handbook of Set Theory or Chapters 10-13 in the book Braids and Self-Distributivity by Patrick Dehornoy.

Result

In the classical Laver table $A_{n}$, we define the critical point by $\operatorname{crit}(r)=\gcd(r,2^n)$. Critical points originally arose from elementary embeddings in set theory, but we translate this notion to a purely algebraic context.

$\mathbf{Proposition:}$ Assume the existence of a non-identity rank-into-rank embedding. Then in the classical Laver tables $A_n$, we have $\operatorname{crit}((x*x)*y) \leq \operatorname{crit}(x*y)$ for all $x,y\in A_{n}$.

The proof of this proposition relies upon the observation that $\mathrm{crit}(j*k)=j(\mathrm{crit}(k))$ and the following easy Lemma.

$\mathbf{Lemma:}$ If $j:V_\lambda\rightarrow V_\lambda$ is an elementary embedding, then $(j*j)(\alpha)\leq j(\alpha).$

$\mathbf{Proof:}$ Let $\beta$ be the least ordinal such that $j(\beta)>\alpha$. Then $$V_{\lambda}\models\forall x<\beta,j(x)\leq\alpha,$$ so by elementarity, $$V_\lambda\models\forall x<j(\beta),(j*j)(x)\leq j(\alpha).$$ Therefore, since $\alpha<j(\beta)$, we have $(j*j)(\alpha)\leq j(\alpha).$

The fact that $\operatorname{crit}((x*x)*y) \leq \operatorname{crit}(x*y)$ is almost trivial when one assumes strong large cardinal hypotheses, but the fact that $\operatorname{crit}((x*x)*y)\leq\operatorname{crit}(x*y)$ has no known proof in ZFC.