Proof synopsis collection - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T21:37:31Z http://mathoverflow.net/feeds/question/43889 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43889/proof-synopsis-collection Proof synopsis collection Jon Bannon 2010-10-27T22:15:08Z 2012-12-01T17:11:00Z <p>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!</p> <blockquote> <p>Definition (Fraleigh): A <em>proof synopsis</em> is a one or two sentence synopsis of a proof, explaining the idea of the proof without all the details and computations.</p> </blockquote> <p>My question is this:</p> <blockquote> <p>What is your favorite proof synopsis of a theorem we all should know?</p> </blockquote> <p>(I'm sorry, I'll do my time in big-list hell...)</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43890#43890 Answer by David Roberts for Proof synopsis collection David Roberts 2010-10-27T22:22:04Z 2010-10-27T22:22:04Z <p>Fermat-Wiles theorem.</p> <p>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.</p> <p>A bit cheeky, but true.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43891#43891 Answer by David MJC for Proof synopsis collection David MJC 2010-10-27T22:22:30Z 2010-10-27T23:38:11Z <p>(1) Proof of a theorem in finite dimensional linear algebra.</p> <p>The hypotheses invite us to construct a linearly independent set: extend this set to a basis and conclude.</p> <p>(2) Proof of a theorem related to compact topological spaces.</p> <p>The hypotheses invite us to construct an open cover: observe this open cover has a finite subcover and conclude.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43892#43892 Answer by Mark Schwarzmann for Proof synopsis collection Mark Schwarzmann 2010-10-27T22:27:15Z 2010-10-27T22:27:15Z <p>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).</p> <p>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.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43896#43896 Answer by Nate Eldredge for Proof synopsis collection Nate Eldredge 2010-10-27T22:47:24Z 2010-10-27T22:47:24Z <p>Central limit theorem: Take the Fourier transform of your distribution and expand it with Taylor's theorem.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43897#43897 Answer by Dick Palais for Proof synopsis collection Dick Palais 2010-10-27T22:52:03Z 2010-10-27T22:52:03Z <p>If a self map $f$ of a metric space $X$ satisfies $d(fx,fy) \le K d(x,y)$ for $K &lt; 1$, then by the triangle inequality $d(x,y) \le d(x,fx) + d(fx,fy) + d(fy,y)$ which gives $d(x,y) &lt; {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) &lt; {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. </p> <p>(Note: we have used the obvious fact that $d(f^n(x),f^n(y)) \le K^n d(x,y)$)</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43898#43898 Answer by Bruno Stonek for Proof synopsis collection Bruno Stonek 2010-10-27T22:53:25Z 2010-10-27T22:53:25Z <p>$\mathbb{R}$ is uncountable:</p> <p>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.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43901#43901 Answer by Georges Elencwajg for Proof synopsis collection Georges Elencwajg 2010-10-27T23:17:13Z 2010-10-27T23:25:16Z <p>Fermat's little theorem: $n^p\equiv n \; (mod \;p)$ for $p$ prime and all integers $n$.</p> <p><strong>Synopsis of proof:</strong> 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.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43907#43907 Answer by Gerhard Paseman for Proof synopsis collection Gerhard Paseman 2010-10-27T23:53:21Z 2010-10-28T00:27:23Z <p>Birkhoff's HSP theorem.</p> <p>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.</p> <p>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. </p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.10.27</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43910#43910 Answer by Jeff Strom for Proof synopsis collection Jeff Strom 2010-10-28T00:03:29Z 2010-10-30T15:27:57Z <p>Toda's Proof of the Bott Periodicity Theorem:</p> <p>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. </p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43911#43911 Answer by Manuel Rivera for Proof synopsis collection Manuel Rivera 2010-10-28T00:08:06Z 2010-10-28T00:08:06Z <p>Brouwer's Fixed Point Theorem: Every map $f: D^n \rightarrow D^n$ has a fixed point.</p> <p>$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$.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43914#43914 Answer by K. Henriksen for Proof synopsis collection K. Henriksen 2010-10-28T00:12:38Z 2010-10-28T00:12:38Z <p>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.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43919#43919 Answer by Alex R. for Proof synopsis collection Alex R. 2010-10-28T00:57:45Z 2011-02-15T04:21:41Z <p>Picard Existence Theorem:</p> <p>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$. </p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43945#43945 Answer by Gerry Myerson for Proof synopsis collection Gerry Myerson 2010-10-28T06:01:05Z 2010-10-28T06:01:05Z <p>Theorem: If a field extension is radical, then the Galois group of its normal closure is solvable. </p> <p>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. </p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/43952#43952 Answer by Martin Brandenburg for Proof synopsis collection Martin Brandenburg 2010-10-28T08:25:25Z 2010-10-28T08:25:25Z <p><a href="http://en.wikipedia.org/wiki/Algebraic_geometry_and_analytic_geometry" rel="nofollow">Serres GAGA Theorem</a>.</p> <p>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]]$.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/44233#44233 Answer by Amueller for Proof synopsis collection Amueller 2010-10-30T10:28:26Z 2010-10-31T05:19:59Z <p>Maximum Principle for holomorphic functions:</p> <p>let <code>$f \colon G\to {\mathbb C}\$</code> 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.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/44263#44263 Answer by Arturo Magidin for Proof synopsis collection Arturo Magidin 2010-10-30T18:44:31Z 2010-10-30T18:44:31Z <p><strong>Mean Value Theorem:</strong> Tilt your head and apply Rolle's Theorem.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/55490#55490 Answer by Abhinav Kumar for Proof synopsis collection Abhinav Kumar 2011-02-15T05:55:30Z 2011-02-15T05:55:30Z <p>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}$.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/55497#55497 Answer by awllower for Proof synopsis collection awllower 2011-02-15T08:50:00Z 2011-02-15T08:50:00Z <p>The well-known Kronecker-Weber theorem.<br> 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.<br> I must say that this is not my idea, instead, it is contained in <a href="http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/cfthistory.pdf" rel="nofollow">here</a><br> which is by <em>Keith Conrad</em>.<br> And if <em>@K Conrad</em> is upset about what I do, then I will delete my post <strong><em>then and there</em></strong>. </p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/55508#55508 Answer by Michael Greinecker for Proof synopsis collection Michael Greinecker 2011-02-15T11:13:50Z 2011-02-15T11:13:50Z <p>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. </p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/109789#109789 Answer by Benjamin Braun for Proof synopsis collection Benjamin Braun 2012-10-16T06:31:41Z 2012-10-16T06:31:41Z <p>Urysohn's metrization theorem </p> <p>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}.$</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/109812#109812 Answer by Johan Wästlund for Proof synopsis collection Johan Wästlund 2012-10-16T12:59:23Z 2012-10-16T12:59:23Z <p>The halting problem is algorithmically unsolvable: </p> <p>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. </p> <p>Gödel's incompleteness theorem: </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/109815#109815 Answer by Dedalus for Proof synopsis collection Dedalus 2012-10-16T13:18:52Z 2012-10-16T13:18:52Z <p>Yoneda Lemma:</p> <p>The natural transformation is determined in fully by where the identity goes.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/109828#109828 Answer by Todd Trimble for Proof synopsis collection Todd Trimble 2012-10-16T16:05:48Z 2012-10-16T18:40:29Z <p>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. </p> <p>Proposition. Let $A$ be a real symmetric $n \times n$ matrix. Then $A$ is diagonalizable over the real numbers.</p> <p>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.</p> http://mathoverflow.net/questions/43889/proof-synopsis-collection/109882#109882 Answer by Benoît Kloeckner for Proof synopsis collection Benoît Kloeckner 2012-10-17T07:29:10Z 2012-10-17T07:29:10Z <p>I am surprised that this one did not already occurred : <strong>Perelman's proof of the Poincaré conjecture</strong>.</p> <blockquote> <p>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.</p> </blockquote> http://mathoverflow.net/questions/43889/proof-synopsis-collection/115087#115087 Answer by Pablo Lessa for Proof synopsis collection Pablo Lessa 2012-12-01T17:11:00Z 2012-12-01T17:11:00Z <p>The dimension reduction argument in Whitney's embedding theorem:</p> <p>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}$.</p> <p>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. </p>