Proof synopsis collection

I hate to keep going with the big lists, but the question about one-sentence summaries of topics/areas spurred this question...and I just can't help myself!

Definition (Fraleigh): A proof synopsis is a one or two sentence synopsis of a proof, explaining the idea of the proof without all the details and computations.

My question is this:

What is your favorite proof synopsis of a theorem we all should know?

(I'm sorry, I'll do my time in big-list hell...)

-
I'm not even sure we should restrict this to theorems we all should know. I find these synopses really helpful even for more obscure theorems! –  Jon Bannon Oct 27 '10 at 23:01
With the best will in the world Jon, I can picture this question coming back months down the line like a particularly obstinate revenant, as people with greater and greater ratio of enthusiasm to experience add suggestions of varying insight... –  Yemon Choi Oct 28 '10 at 1:41
...and this is why I will burn in big-list hell! –  Jon Bannon Oct 28 '10 at 5:20
Looking at the synopses, I feel like some intentionally use colorful language, while others are very blunt about the proof. –  David Corwin Oct 16 '12 at 13:51

-
I think I would prefer "Scale your function linearly so $f(a) = f(b)$ and apply Rolle's Theorem", simply because I find it less misleading - when you tilt the function, you may not end up with a function! –  Vince Nov 11 '10 at 4:58
@Vince: I said "tilt your head", not "tilt your function". Tilt your head so that the line from $(a,f(a))$ to $(b,f(b))$ looks horizontal, so that Rolle's theorem applies. (I would say that if $f(a)\neq f(b)$, then no amount of "scaling" will result in $f(a)=f(b)$...) But still. –  Arturo Magidin Nov 11 '10 at 18:30
I agree with Vince - the graph of a function may cease to look like the graph of a function when you tilt your head. This sounds more like a shearing transformation than a tilting (of a head or a function). –  S. Carnahan Feb 15 '11 at 7:30
"shear your head" sounds unappetizing. –  Will Sawin Dec 1 '12 at 18:38

Not a very big theorem, but the rather cute fact that the characteristic polynomials of $AB$ and $BA$ coincide ($A,B$ some $n \times n$ matrices, say complex).

It's true if $A$ is invertible since then $AB = A(BA)A^{-1}$ and similar matrices have the same characteristic polynomial. By the density of $GL(n,\mathbb{C})$ in $Mat_n (\mathbb{C})$, the result follows in general.

-
I like that ! :-) –  Dick Palais Oct 27 '10 at 22:53
I would say that this is not a proof synopsis, but rather a complete proof. What calculations are missing? –  Pete L. Clark Oct 28 '10 at 1:03
I don't really like this proof. AB and BA have the same characteristic polynomial p(x) even if A & B aren't square, as long as both products are defined (with factors of x to make up the difference in degree). To recover this from the given theorem, you can extend the matrices by all-zero rows or columns to make them square...but then you might as well just give a cleaner proof: start with [[I, A],[B, I]]; block-row-reduce it & block-column-reduce it to show that det(I-BA) = det(I-AB); the result for characteristic polynomials follows. –  Darsh Ranjan Oct 28 '10 at 7:09
Darsh: even though the theorem as stated isn't as general as it could be, I think not liking the proof is a bit harsh. First of all, the more general version you describe (with factors of x added on to match degrees) is less succinct. Secondly, many mathematicians would consider a proof with steps involving row or column reducing as less conceptual. And finally, proofs that don't handle the most general case can still be valuable. Classifying f.g. modules over a PID by a technique that doesn't work for f.g. modules over a Dedekind domain doesn't mean the technique is bad. –  KConrad Oct 28 '10 at 8:43
Here's a more complicated but perhaps more conceptual proof [synopsis]: $1/c$ is in the spectrum of $T$ iff $(I-xT)^{-1}$ is not bounded near $x=c$, and the multiplicity is the smallest $p\geq 0$ for which $(x-c)^p (I-xT)^{-1}$ is bounded near $x=c$. But $(x-c)^p(I - xBA)^{-1} = (x-c)^p - xB[(x-c)^p(I - xAB)^{-1}]A$ (which can be proved just by algebra), so clearly $AB$ and $BA$ have identical spectra except at $1/c=0$, QED. –  Darsh Ranjan Oct 29 '10 at 6:20

Central limit theorem: Take the Fourier transform of your distribution and expand it with Taylor's theorem.

-
<cough> Levy continuity theorem </cough> –  Yemon Choi Oct 28 '10 at 1:42
Yeah, I suppose several lectures worth of Fourier analysis are implicit in that statement. –  Nate Eldredge Oct 28 '10 at 14:05

I am surprised that this one did not already occurred : Perelman's proof of the Poincaré conjecture using Hamilton's Ricci flow.

Endow a simply connected three-manifold with any Riemannian metric. Let the metric evolve under the Ricci flow. When singularities occur, cut them out and smoothly glue a cap in the hole, checking that the topology has not changed. After some time, you get a round metric so your manifold is a sphere.

-
IMHO Richard Hamilton deserved the credit for the 1st, 2nd, and last sentence of the above synopsis... –  Michael Jul 23 '14 at 19:30
@Michael: I partly agree, and changed a bit my answer to credit Hamilton. I would not say that the last sentence could, as it is, be credited to him though: he only got this under the strong hypothesis that the initial metric is positively Ricci curved. –  Benoît Kloeckner Jul 23 '14 at 20:36

Picard Existence Theorem:

Consider $z'(t)=f(t,z)$. Define $\mathbf{F}y:=y_0+\int_0^t f(x,y(t))dx$. It sure would be nice if $\mathbf{F}$ had a fixed point, so use Banach fixed point theorem to show that it has a fixed point. That would require $f$ to be a contraction, so sprinkle a hint of Lipschitz on $f$.

-

Proof synopsis: After constructing a functorial set up, reduce to the case $X = \mathbb{P}^n$ and $\mathcal{F} = \mathcal{O}(k)$, and use that completions of local rings are faithfully flat, in particular for $\widehat{\mathbb{C}[x_1,...,x_n]} = \mathbb{C}[[x_1,...,x_n]]$.

-

Fermat's little theorem: $n^p\equiv n \; (mod \;p)$ for $p$ prime and all integers $n$.

Synopsis of proof: Reduce to nontrivial case where $p$ doesn't divide $n$, interpret as equality in field of $p$ elements, divide by $n$ and apply Lagrange's theorem saying that the order of a finite group kills all its elements.

-
Consider the set of words of length p on an alphabet of size n. The cyclic group C_p acts in an obvious way on it with n orbits of size 1 and (n^p - n)/p orbits of size p. –  Qiaochu Yuan Oct 27 '10 at 23:54
@Qiaochu: I've seen that proof attributed to Dijkstra, though I'm sure it has been thought of many times. –  Daniel Litt Oct 28 '10 at 6:19
@Daniel, this proofs appears already in Gauss's Disquisitiones. –  Pietro KC Oct 31 '10 at 9:13
Induction: $(n+1)^p \equiv n^p+1^p$, since all other binomials have a $p$ factor which does not simplify. –  Federico Poloni Oct 31 '10 at 11:31
It was already in Gauss:to @Federico Poloni as @Peitro KC said. –  awllower Feb 15 '11 at 8:14

Toda's Proof of the Bott Periodicity Theorem:

The homology algebras of $\Omega SU$ and $BU$ are isomorphic: they are polynomial algebras on the image of the maps induced by certain maps $f: \mathbb{C}P^\infty \to \Omega SU$ and $g: \mathbb{C}P^\infty \to BU$. The Bott map $\beta: BU\to \Omega SU$ is an H-map satisfying $\beta \circ g \simeq f$, so $\beta$ is a (weak) homotopy equivalence.

-

Minkowski's lower bound for density of sphere packings in $\mathbb{R}^n$: take any sphere packing where you can't cram in any more spheres. Then doubling the size of the spheres must cover all space, which gives a lower bound of $\frac{1}{2^n}$.

-

Tychonoff's theorem: Take any ultrafilter, F, on the product space and observe that F's projections onto each factor are ultrafilters and thus convergent. Conclude that F converges to the product of the (not necessarily unique) limits.

-
Tychonoff's Theorem relies extensively on the axiom of choice, and hence most proofs do not provide any insight as to why it is true (if indeed it is!). To get going, it is a good idea first to suppose that the indexing set is an ordinal (i.e., well-ordered). Now proceed by transfinite induction: Tychonoff's theorem is true for successor ordinals because the product of two compact spaces is compact. It is (arguably) true for limit ordinals because of the finiteness intrinsic to the definition of the product topology (although exploiting this involves the axiom of choice again). –  David MJC Oct 28 '10 at 9:46
Actually the filter-theoretic proof has the advantage that it only needs the ultrafilter lemma in the compact Hausdorff case. But it is definitely true that most proofs don't give much insight into why the theorem is true. There's the proof using nets, but I find the notion of subnet notoriously counter-intuitive (going to a subnet can increase the cardinality of the indexing set, huh?). There's also the proof in Munkres' "Topology" where he uses the FIP characterisation and Zorn's lemma. I guess that's moderately more intuitive since Zorn's lemma gives a maximal element w.r.t the FIP... –  K. Henriksen Oct 28 '10 at 10:29

Maximum Principle for holomorphic functions:

let $f \colon G\to {\mathbb C}\$ be holomorphic and $z_0$ some interior point of $G$. By the Poisson-Formula, $f(z_0)$ is essentially the mean of values of $f$ on a circle around $z_0$. Thus, $|f(z_0)|$ is not maximal.

-
$G$ connected and $f$ non-constant? –  Michael Albanese May 3 '12 at 11:16

(1) Proof of a theorem in finite dimensional linear algebra.

The hypotheses invite us to construct a linearly independent set: extend this set to a basis and conclude.

(2) Proof of a theorem related to compact topological spaces.

The hypotheses invite us to construct an open cover: observe this open cover has a finite subcover and conclude.

-
I daresay that, just as often as the hypotheses of a theorem about compact topological spaces invite us to construct a cover, they invite us to describe a sequence (or net). –  L Spice Feb 15 '11 at 4:19

Theorem: If a field extension is radical, then the Galois group of its normal closure is solvable.

Proof synopsis: Write the extension as a tower of simple radical extensions, show that each simple extension is abelian, and note that piecing together abelian groups gives a solvable group.

-

The halting problem is algorithmically unsolvable:

Suppose there is an algorithm that solves it. Construct a Turing machine that behaves differently from every Turing machine. Then it behaves differently from itself, contradiction.

Gödel's incompleteness theorem:

Suppose a consistent and complete formal system is strong enough to express elementary mathematics. Then it can express the statement that a given Turing machine halts on a given input. By enumerating all proofs, we can solve the halting problem, contradiction.

The synopsis for the incompleteness theorem is is a little bit of cheating. The technically hard part of Gödel's proof is to show that a particular version of Peano arithmetic is strong enough to make the argument work (he had to do this since Turing machines weren't yet invented). But if he hadn't been able to pull this off, he would just have invented a slightly stronger system. The philosophically relevant part of the theorem is contained in this synopsis.

-

Yoneda Lemma:

The natural transformation is determined in fully by where the identity goes.

-

If a self map $f$ of a metric space $X$ satisfies $d(fx,fy) \le K d(x,y)$ for $K < 1$, then by the triangle inequality $d(x,y) \le d(x,fx) + d(fx,fy) + d(fy,y)$ which gives $d(x,y) < {1 \over 1-K} (d(x,fx) + d(y,fy))$. Then if $f^n$ denotes $f$ composed with itself $n$ times, substituting $f^n(x)$ for $x$ and $f^m(y)$ for $y$ in the above inequality gives $d(f^n(x),f^m(y) < {K^n + K^m\over 1-K} d(x,fx)$, so $f^n(x)$ is Cauchy, hence if $X$ is complete it converges to a limit $x_0$ which is clearly a fixed point of $f$. This is the Banach Contraction Theorem.

(Note: we have used the obvious fact that $d(f^n(x),f^n(y)) \le K^n d(x,y)$)

-
More than a synopsis, this reads like a full proof! –  José Figueroa-O'Farrill Oct 27 '10 at 22:56
Why not summarize it in a sentence? "If a map from a metric space to itself strictly reduces distances, then its iterates generate Cauchy sequences, which must converge to a fixed point if the metric space is complete." This is, after all, a wonderful result in analysis. –  David MJC Oct 27 '10 at 23:19
@Dick Palais: I don't think the length is so much the issue. All the notation and computation tend to obscure the idea of the proof, in my opinion, which a synopsis like David MJC's communicates the idea much more clearly. –  Nate Eldredge Oct 28 '10 at 0:40
I beg to differ. The way that Banach's theorem is frequently stated is that "Any sequence of iterates of a contraction mapping converges to its unique fixed point." David's "synopsis" is merely a restatement of that. –  Dick Palais Oct 28 '10 at 0:49
It's probably a bit late, but David MJC is simply... wrong. For a non compact space, it is not sufficient that the map strictly reduces distances, as can be seen by the map x + 1/x which has no fixed points. The computation with geometric series is essential - the mapping has to be a contraction. –  mathahada May 20 '11 at 8:39

Brouwer's Fixed Point Theorem: Every map $f: D^n \rightarrow D^n$ has a fixed point.

$S^{n-1}$ is not a retract of $D^n$, otherwise we could then factor the identity map $H_{n-1}(S^{n-1}) \rightarrow H_{n-1}(S^{n-1})$ through the trivial group $H_{n-1}(D^n)$. If $f$ had no fixed point we could then define a retraction $r: D^n \rightarrow S^{n-1}$ by letting $r(x)$ to be the point in the intersection of $S^{n-1}$ and the ray in $\mathbb{R}^n$ starting at $f(x)$ and passing through $x$.

-
As with other answers here, this is more than a synposis and does not fit to the question. –  Martin Brandenburg Oct 28 '10 at 8:08

Fermat-Wiles theorem.

Assume rational solution of Fermat equation, which then defines an non-modular elliptic curve. This contradicts the modularity theorem, so there are no such solutions.

A bit cheeky, but true.

-
This reminds me of a talk I heard a long time ago, by a great mathematician in some rivalry with Hironaka. At some point he said: "All Hironaka does is blow-up and blow-up and blow-up..." (He was not joking !) –  Georges Elencwajg Oct 27 '10 at 23:03
I have discovered a truly marvelous synopsis ot this theorem but this comment box is too narrow to contain it. –  Georges Elencwajg Oct 28 '10 at 9:20
Hmm, then submit it as answer!! –  awllower Feb 15 '11 at 8:18
@awllower: Isn't Georges joking? –  Hans Stricker Feb 15 '11 at 12:03
@HansStricker — Isn't awllower joking? –  jmc Jul 23 '14 at 16:25

Kolmogorov extension theorem: The projections on finitely many factors give you you a net of $\sigma$-algebras. By consistency you get a finitely-additive measure on their union. Extend it to a countably additive one by regularity and apply the Carathedory extension theorem.

-

I don't know that I have a favorite proof-synopsis, but here's one I like which is a little different from the way most people prove it.

Proposition. Let $A$ be a real symmetric $n \times n$ matrix. Then $A$ is diagonalizable over the real numbers.

Proof. Consider the problem of maximizing the function $f(x) = \langle x∣A∣x\rangle$ where $x \in \mathbb{R}$ is subject to the constraint $\langle x∣x \rangle =1$. (Such an extreme point exists, say by compactness.) By the symmetry of $A$, the gradient of f is easily calculated to be $\nabla f(x)=2Ax$, whereas the gradient of the Euclidean norm $\langle x∣x\rangle$ is $2x$. At a point $x$ where a maximum is attained, we have $\nabla f(x) = 2Ax = \lambda (2x)$ for some Lagrange multiplier $\lambda$. Thus $x$ is an eigenvector of $A$ with eigenvalue $\lambda$. The usual arguments show that $A$ restricts to a self-adjoint operator on the hyperplane orthogonal to $x$; by picking an orthonormal basis of this hyperplane, we may represent this restriction of $A$ by a real symmetric matrix of size $(n−1) \times (n−1)$, and the argument repeats.

-

The well-known Kronecker-Weber theorem.
If $L|Q$ is an abelian extension of Q, then use the theory of higher ramification groups to show that L lies in a succession of $L_n(\zeta_n)$ where $L_n$ is a subfield of $L$ and hence we can make the ramification of $L_n$ smaller in exchange for adjoining appropriate roots of unity, and in the end obtain an unramified extension of Q, i.e. Q itself and hence $Q(\zeta_n)$ contains $L$ for some natural integer n.
I must say that this is not my idea, instead, it is contained in here
And if @K Conrad is upset about what I do, then I will delete my post then and there.

-
May I respectfully ask for a synopsis of the proof for the Artin's reciprocity law? –  awllower Feb 16 '11 at 1:13
And here is another one, which is slightly longer than just a synopsis. –  awllower Feb 25 '11 at 15:21

Birkhoff's HSP theorem.

Given a class of algebraic structures which satisfies a set of identities (universally quantified equations in a purely functional language with equality as the only relation; this is known as an equational class), homomorphic images, images of subalgebras, and cartesian products also satisfy the same set of identities (e.g. by inspection) and their consequences in equational logic. Conversely, given a class of algebraic structures of the the same type closed under products, subalgebras, and homomorphisms, one can realize every such algebra as an image of some free algebra with respect to the class; constructing the appropriate image of the term algebra gives a free algebra that lives in the closed class; the (fully invariant) congruences on the term algebra gives the set of equations that the closed class must satisfy; thus a class is an equational class iff it is closed under the class operator HSP.

Garrett Birkhoff's original paper on this theorem (called a preservation theorem when it came out in the 1930's) is easy to read. There may be within it a cleaner synopsis than the one above.

-
I think using that many semicolons is cheating. –  Nate Eldredge Oct 28 '10 at 0:37
I could instead say that the fully invariant congruences on the term algebra which produce members of the given class lead to the equations satisfied by the class, but that seems too terse. Gerhard "Semicolons Breathe Life Into Paragraphs" Paseman, 2010.10.27 –  Gerhard Paseman Oct 28 '10 at 1:05

Urysohn's metrization theorem

Take your topology $\mathcal{T}$ (it must be second countable, regular, and Hausdorff) and choose a basis for it, and choose a counting for that basis. Construct continuous functions $f_i(x): \mathcal{T} \rightarrow $0,1$$ such that $f_i(x) > 0$ whenever $x$ is in the $i$th basis element. Define the distance between any two points $x$ and $y$ to be some weighted sum with exponentially decaying weights over $|f_i(x) - f_i(y)|$, for all $i\in \mathbb{N}.$

-

$\mathbb{R}$ is uncountable:

The set $\{0,1\}^\mathbb{N}$ is uncountable using Cantor's diagonal argument: if it were countable, list all the sequences and take the diagonal, it is a sequence which is not on the list, which is absurd. Then the open interval $(0,1)$ is uncountable via (taking the infinite) binary expressions: the result follows because $\mathbb{R}$ is in bijection with $(0,1)$ via $x\mapsto \frac{2}{\pi}\tan(x)$, for example.

-
This is messy if you aren't careful about the slight non-uniqueness in binary expansions, and the last step is unnecessary since you already know that (0, 1) is contained in R. Here's another way: once you've done the first step, prove that continued fraction expansions are unique and consider the set of infinite continued fractions whose terms are either 1 or 2. –  Qiaochu Yuan Oct 27 '10 at 23:56
Shouldn't you flip the bits in the diagonal to obtain the sequence that is not in the list ?. It could happen that a object listed coincides with the diagonal. –  Felipe Olmos Oct 30 '10 at 13:23

The dimension reduction argument in Whitney's embedding theorem:

Suppose a $d$ dimensional manifold $M$ is embedded in $\mathbb{R}^N$ with $N$ larger than $2d+1$. Look at $M$ from a random direction and notice that you can see all of it. Hence you can embed it in $\mathbb{R}^{N-1}$.

Formally one needs Sard's theorem, the map from $M\times M$ minus the diagonal to the unit sphere defined by $(x,y) \mapsto (x-y)/|x-y|$ can't be surjective.

-

To construct the spectral resolution of a bounded normal operator $T$ on a Hilbert space:

Use the Gelfand-Neumark and Riesz Representation Theorems in a natural way to obtain the spectral resolution for an abelian C*-algebra. Now use the fact that the Gelfand transform is a homeomorphism of the maximal ideal space of $W^{\ast}(T)$ with $\sigma(T)$ that preserves the identity function.

To construct the spectral resolution of an unbounded self-adjoint operator $A$ on a Hilbert space:

Since $A$ is self-adjoint, its Cayley transform is unitary, and the the spectral resolution of $A$ is essentially that of the Cayley transform.

-