Proof synopsis collection - MathOverflow

Proof synopsis collection

2010-10-27T22:15:08Z

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

Answer by David Roberts for Proof synopsis collection

2010-10-27T22:22:04Z

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.

Answer by David MJC for Proof synopsis collection

2010-10-27T22:22:30Z

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

Answer by Mark Schwarzmann for Proof synopsis collection

2010-10-27T22:27:15Z

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.

Answer by Nate Eldredge for Proof synopsis collection

2010-10-27T22:47:24Z

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

Answer by Dick Palais for Proof synopsis collection

2010-10-27T22:52:03Z

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

Answer by Bruno Stonek for Proof synopsis collection

2010-10-27T22:53:25Z

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

Answer by Georges Elencwajg for Proof synopsis collection

2010-10-27T23:17:13Z

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.

Answer by Gerhard Paseman for Proof synopsis collection

2010-10-27T23:53:21Z

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.

Gerhard "Ask Me About System Design" Paseman, 2010.10.27

Answer by Jeff Strom for Proof synopsis collection

2010-10-28T00:03:29Z

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.

Answer by Manuel Rivera for Proof synopsis collection

2010-10-28T00:08:06Z

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

Answer by K. Henriksen for Proof synopsis collection

2010-10-28T00:12:38Z

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.

Answer by Alex R. for Proof synopsis collection

2010-10-28T00:57:45Z

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

Answer by Gerry Myerson for Proof synopsis collection

2010-10-28T06:01:05Z

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.

Answer by Martin Brandenburg for Proof synopsis collection

2010-10-28T08:25:25Z

Serres GAGA Theorem.

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

Answer by Amueller for Proof synopsis collection

2010-10-30T10:28:26Z

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.

Answer by Arturo Magidin for Proof synopsis collection

2010-10-30T18:44:31Z

Mean Value Theorem: Tilt your head and apply Rolle's Theorem.

Answer by Abhinav Kumar for Proof synopsis collection

2011-02-15T05:55:30Z

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

Answer by awllower for Proof synopsis collection

2011-02-15T08:50:00Z

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
which is by Keith Conrad.
And if @K Conrad is upset about what I do, then I will delete my post then and there.

Answer by Michael Greinecker for Proof synopsis collection

2011-02-15T11:13:50Z

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.

Answer by Benjamin Braun for Proof synopsis collection

2012-10-16T06:31:41Z

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

Answer by Johan Wästlund for Proof synopsis collection

2012-10-16T12:59:23Z

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.

Answer by Dedalus for Proof synopsis collection

2012-10-16T13:18:52Z

Yoneda Lemma:

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

Answer by Todd Trimble for Proof synopsis collection

2012-10-16T16:05:48Z

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.

Answer by Benoît Kloeckner for Proof synopsis collection

2012-10-17T07:29:10Z

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

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.

Answer by Pablo Lessa for Proof synopsis collection

2012-12-01T17:11:00Z

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.