Can infinity shorten proofs a lot? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:14:13Z http://mathoverflow.net/feeds/question/5751 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot Can infinity shorten proofs a lot? gowers 2009-11-16T23:37:08Z 2013-03-24T12:50:54Z <p>I've just been asked for a good example of a situation in maths where using infinity can greatly shorten an argument. The person who wants the example wants it as part of a presentation to the general public. The best I could think of was Goodstein sequences: if you take a particular instance of Goodstein's theorem, then the shortest proof in Peano arithmetic will be absurdly long unless the instance is very very small, but using ordinals one has a lovely short proof. </p> <p>My question is this: does anyone have a more down-to-earth example? It doesn't have to be one where you can rigorously prove that using infinity hugely shortens the shortest proof. Just something where using infinity is very convenient even though the problem itself is finite. (This is related to the question asked earlier about whether finite mathematics needs the axiom of infinity, but it is not quite the same.)</p> <p><del>A quick meta-question to add: when I finally got round to registering for this site, I lost the hard-earned reputation I had gained as a non-registered user. I am now disgraced, so to speak. Is that just my tough luck?</del></p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5752#5752 Answer by Ryan Budney for Can infinity shorten proofs a lot? Ryan Budney 2009-11-16T23:41:23Z 2009-11-16T23:41:23Z <p>The Mazur Swindle? See the Wikipedia page, for example. </p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5753#5753 Answer by Mariano Suárez-Alvarez for Can infinity shorten proofs a lot? Mariano Suárez-Alvarez 2009-11-16T23:44:02Z 2012-02-15T17:47:37Z <p>A simple instance where infinity makes things simple is when proving that there exist transcendental numbers. Instead of having to come up with ways to tell a transcendental number from an algebraic one, you simply say «well, there are too many numbers for all of them to be algebraic, so there you have it».</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5754#5754 Answer by Qiaochu Yuan for Can infinity shorten proofs a lot? Qiaochu Yuan 2009-11-16T23:51:00Z 2009-11-17T22:52:54Z <p>The precise <a href="http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Rademacher.27s_series" rel="nofollow">asymptotics of the partition function</a> $p(n)$ are, as far as I know, totally inaccessible by finitary tools. More generally the methods of complex analysis are a great way to obtain incredibly precise asymptotics on many finitary sequences of concrete interest, i.e. trees satisfying certain properties or sequences related to the running times of algorithms, etc. </p> <p>A related example is comparing the elementary and non-elementary proofs of the <a href="http://en.wikipedia.org/wiki/Prime_number_theorem" rel="nofollow">prime number theorem</a>; my recollection is that the elementary proof is quite a bit more involved.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5755#5755 Answer by Ori Gurel-Gurevich for Can infinity shorten proofs a lot? Ori Gurel-Gurevich 2009-11-17T00:11:37Z 2012-02-01T05:00:20Z <p>I'm not sure whether this is more "down-to-earth" but take 0-1 laws of random graphs. The probability of a first order property to be satisfied by a random graph distributed $G(n,p)$ tends to 0 or 1.</p> <p>The proof is by showing that the limit theory satisfied by these graphs has only one countable model, and is therefore complete.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5758#5758 Answer by Harrison Brown for Can infinity shorten proofs a lot? Harrison Brown 2009-11-17T00:25:00Z 2012-12-03T20:28:20Z <p>This isn't particularly down-to-earth, but of course before February or March you had the situation where the density Hales-Jewett theorem (which can be phrased in completely finitary language) was only provable via ergodic-theory methods (which are infinitary.)</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5759#5759 Answer by Kristal Cantwell for Can infinity shorten proofs a lot? Kristal Cantwell 2009-11-17T00:40:51Z 2009-11-17T00:40:51Z <p>If you want a situation where there is only an infinite proof then there is the strengthened finite Ramsey theorem which is not provable in PA but can be deduced from the infinite Ramsey theorem. see:</p> <p><a href="http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington%5Ftheorem" rel="nofollow">http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem</a></p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5765#5765 Answer by Dan Piponi for Can infinity shorten proofs a lot? Dan Piponi 2009-11-17T02:02:26Z 2009-11-17T02:48:40Z <p><a href="http://www.cs.tau.ac.il/~nachum/nachumd/Homepage.html" rel="nofollow">Nachum Dershowitz</a> has lots of <a href="http://www.cs.tau.ac.il/~nachumd/pub.html" rel="nofollow">work</a> on termination proofs and many of these make use of ordinal arithmetic. In particular, if you have a computer program that moves from one state to another, and you can label each state with an ordinal, and you know that the ordinal for each new state is strictly less than the ordinal for the previous state, then the program must eventually terminate. Goodstein's Theorem is a special case, showing termination for a highly contrived sequence. But more realistic examples arise when studying termination of rewrite rules.</p> <p>A basic example is proving termination of the rewrite rules that define symbolic differentiation. Like in the case of Goodstein's theorem you have the same problem that differentiation might take a step forward in decreasing the powers in a monomial, but then takes what looks like a giant step back as applying the Leibniz rule to a product can lead to many more terms. But Floyd came up with a neat labelling by ordinals resulting in a really simple termination proof. See example 8 <a href="http://www.cs.tau.ac.il/~nachumd/papers/printemp-print.pdf" rel="nofollow">here</a> for example.</p> <p>Also see the conclusion in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.5142&amp;rep=rep1&amp;type=pdf" rel="nofollow">this</a> paper.</p> <p>Apparently the idea for this originated with Alan Turing.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5770#5770 Answer by Scott Carter for Can infinity shorten proofs a lot? Scott Carter 2009-11-17T03:23:07Z 2012-02-15T17:44:20Z <p>One of my colleagues (Silver) gave a general purpose talk last week. You can't untie a knot $A$ by tying another knot $B$ into the rope. </p> <p>Proof. First show that the connect-sum of long knots is abelian by sliding $A$ through $B$. Then form the decreasing-in-size connect-sum $(AB)(AB)(AB) \dots$. Regroup: $A(BA)(BA) \dots$. If $AB = 0$, i.e. the unknot, then the left-hand grouping is the unknot. The right-hand-grouping is $A$ since $BA=AB=0$. Since $A$ is a knot, then $A=0$, a contradiction. QED</p> <p>The nice thing about the argument is that it uses an infinitely long piece of rope, an infinite sequence of knots, and the knots shrink to being infinitesimally small.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5825#5825 Answer by Jose Brox for Can infinity shorten proofs a lot? Jose Brox 2009-11-17T15:09:45Z 2009-11-17T15:09:45Z <p>Maybe you could use some complex transformation related to Möebius functions (of the kind "circles and lines are the same") to prove several 2D-geometric statements at once.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5831#5831 Answer by Kevin Lin for Can infinity shorten proofs a lot? Kevin Lin 2009-11-17T15:53:05Z 2009-11-17T15:53:05Z <p>I can't think of any good specific examples off the top of my head, but I'm sure that there must be lots of examples where you can much more easily prove something about an affine variety by adding "points at infinity", i.e. by looking at the projectivization of the variety.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5918#5918 Answer by Jonathan Wise for Can infinity shorten proofs a lot? Jonathan Wise 2009-11-18T04:06:37Z 2009-11-18T04:06:37Z <p>This is probably neither the sort of infinity nor the sort of simplification you're looking for, but B&eacute;zout's theorem is a challenge to prove, let alone state, without a line at infinity. I don't know if it would be suitable for a general audience either, but in its favor, it has a very nice statement using both the infinite and the infinitesimal (i.e., contact multiplicity).</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5939#5939 Answer by David Corfield for Can infinity shorten proofs a lot? David Corfield 2009-11-18T08:49:57Z 2009-11-18T08:49:57Z <p>Is there anything wrong with the simplest case - mathematical induction? If I want to show that the sum of the first million cubes is whatever it is, much easier to prove the general formula then specialise to n = 1000000.</p> <p>Now I see from above Qiaochu Yuan has discounted induction as an answer. But why? Induction relies on the natural numbers being a certain <a href="http://ncatlab.org/nlab/show/induction" rel="nofollow">initial algebra</a>, i.e., being taken as an entity, which happens to have infinite cardinality.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5953#5953 Answer by Neel Krishnaswami for Can infinity shorten proofs a lot? Neel Krishnaswami 2009-11-18T11:54:46Z 2009-11-18T11:54:46Z <p>One way of generating very simple examples of this kind is to define a family of predicates $F(n)$ by recursion over the natural numbers. Then, there can usually be no proof of $\forall n. F(n)$ in Peano arithmetic, since $F(n)$ won't usually be a schema in the sense the first-order Peano induction axiom requires -- it can be a different formula at each numeral. </p> <p>For example, one very simple example is to define </p> <p>$F(0) = (0 = 0)$</p> <p>$F(n+1) = (n+1 = n+1) \wedge F(n)$</p> <p>Now, it's clearly the case that $\forall n. F(n)$. However, since it's a different tautology for each argument, Peano arithmetic can't prove this proposition correct (indeed, it's not even a formula of first-order logic). We can only prove each instance correct, which becomes an infinite number of (incredibly trivial) propositions to prove....</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5960#5960 Answer by Gil Kalai for Can infinity shorten proofs a lot? Gil Kalai 2009-11-18T13:00:50Z 2012-02-15T17:46:40Z <p>There is a theorem that if a set of edge colored square tiles can be used to tile the positive orthant then it can also be used to tile the entire plane. (The edges are colored and in the edge-to edge tiling you need to match the colors). </p> <p>The easy argument (using infinity) is: draw a rooted tree where the level $k$ vertices are all possible tilings of a $(2k-3) \times (2k-3)$ squares (and there is a root at level 1). This is a tree with each vertex has a finite number of children. The fact about the positive quadrant asserts that there are vertices of arbitrary large level, and Konig's theorem then asserts that there is an infinite path which then gives the tiling of the plane. (Proving Konig's theorem is based on moving from a vertex with infinitely many descendants to one of his children with infinitely many descendants.)</p> <p>I am not sure that this qualifies as an answer since I am not aware of any "finite" proof and there is something infinite in the statement itself. But there may be special cases where a tiling of the positive orthant be explicitly presented, and it will allow a finite proof which can be very complicated.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/5971#5971 Answer by Gerald Edgar for Can infinity shorten proofs a lot? Gerald Edgar 2009-11-18T13:43:59Z 2009-11-18T13:43:59Z <p>Perhaps fitting in here is Lindenstrauss's proof of Lyapunov's convexity theorem.</p> <p><a href="http://atlas-conferences.com/c/a/e/y/06.htm" rel="nofollow">http://atlas-conferences.com/c/a/e/y/06.htm</a> </p> <p>"the slickest proof to end all proofs" (Halmos)</p> <p>although the result is in $\mathbb{R}^n$, for the proof we go to an infinite-dimensional space</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/6008#6008 Answer by Jose Brox for Can infinity shorten proofs a lot? Jose Brox 2009-11-18T20:17:15Z 2009-11-18T20:17:15Z <p>While browsing Wikipedia, I came across this statement:</p> <p>"The introduction of projective techniques made many theorems in algebraic geometry simpler and sharper: For example, Bézout's theorem on the number of intersection points between two varieties can be stated in its sharpest form only in projective space".</p> <p>I think this fact can be stated in simple terms without any explicit reference to algebraic geometry and projective space, just talking about intersections of graphics of polynomials, the product of their degrees, and "combing space to get the point of infinity" (or some better and longer explanation).</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/87213#87213 Answer by Michael Greinecker for Can infinity shorten proofs a lot? Michael Greinecker 2012-02-01T09:43:20Z 2012-02-01T09:43:20Z <p>Every finite partial order has a maximal element. </p> <p>One can prove that by induction and looking at cases, but I think the most natural way is to argue that if there is no maximal element, one must have a strictly increasing infinite sequence, which is impossible.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/87225#87225 Answer by Carl Mummert for Can infinity shorten proofs a lot? Carl Mummert 2012-02-01T13:07:19Z 2012-02-01T13:17:39Z <p>The axiom system PRA of "primitive-recursive arithmetic" is finitistic, but it has been known for a few decades that it has the same set of $\Pi^0_1$ consequences as the infinitistic theory $\text{WKL}_0$ of second-order arithmetic. In particular, there is a primitive recursive function $f$ that turns a formal proof of a $\Pi^0_1$ statement in $\text{WKL}_0$ into a proof in PRA. Roughly put, a $\Pi^0_1$ formula says that all natural numbers have some particular property, depending on the formula, where the property can be stated using a formula in the language of rings with no quantifiers. </p> <p>The advantage of working in $\text{WKL}_0$ is that the proofs can be much shorter. I think this was always suspected, but Caldon and Ignjatovic recently established (<a href="http://www.cse.unsw.edu.au/~ignjat/inst.pdf" rel="nofollow">pdf</a>) a formal superexponential lower bound for $f$, at least on an infinite set of formulas. Their result is phrased for a different infinitary system, $I\Sigma^0_1$, that lies between PRA and $\text{WKL}_0$. $I\Sigma^0_1$ is a fragment of Peano arithmetic, unlike $\text{WKL}_0$; its main difference from PRA is that $I\Sigma^0_1$ allows direct universal quantification over the set of natural numbers during the proof, while PRA does not. </p> <p>In their paper, the set of formulas for the lower bound is explicitly laid out. These may not be particularly concrete, because they relate to consistency statements.</p> <p>If we expand PRA to allow for existential quantification, we can get a slightly larger theory in which $\Pi^0_2$ statements can be expressed. It is known that $\text{WKL}_0$ is still conservative over this larger theory for $\Pi^0_2$ statements. In 1994, Kikuchi and Tanaka (<a href="http://projecteuclid.org/euclid.ndjfl/1040511346" rel="nofollow">pdf</a>) gave a nice example of how this could be used to show that the second incompleteness theorem is provable in PRA, by using model-theoretic, infinitary methods in $\text{WKL}_0$ and relying on the conservation result. </p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/87236#87236 Answer by Igor Khavkine for Can infinity shorten proofs a lot? Igor Khavkine 2012-02-01T14:56:43Z 2012-02-01T14:56:43Z <p>A down-to-earth example: the <a href="http://en.wikipedia.org/wiki/Stirling_formula" rel="nofollow">Stirling approximation</a> to the factorial.</p> <p>At least the derivation given on the Wikipedia page compares the explicit sum representation of $\ln(n!)$ with a Riemann sum approximation of the integral $\int \ln(x) \mathrm{d}x$. One only needs finite integers to talk about factorials. On the other hand, one needs at least a couple of kinds of infinities for the real analysis involved in describing the integral and accompanying error estimates. However, the simplicity of this derivation of the Stirling formula is undeniable.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/94527#94527 Answer by Terry Tao for Can infinity shorten proofs a lot? Terry Tao 2012-04-19T13:31:21Z 2012-04-19T13:31:21Z <p>The Poincare conjecture might qualify as an example. One can phrase this conjecture in a purely combinatorial fashion, involving finite simplicial complexes, but the only known proof of this conjecture uses Ricci flow, and in particular the various monotonicity properties of this flow which are proven by integration by parts, as well as the repeated use of limits. In principle, this proof can be finitised by working with finite element versions of Ricci flow, but it would definitely lengthen the proof substantially. (On the other hand, Perelman's proof is not exactly short to begin with, so this may not be the best example...) </p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/94534#94534 Answer by Gerald Edgar for Can infinity shorten proofs a lot? Gerald Edgar 2012-04-19T14:24:52Z 2012-04-19T14:24:52Z <p>Maybe "analytic number theory" belongs here as an answer. Certain number theory results are most simply proved using complex analysis.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/94546#94546 Answer by Andreas Blass for Can infinity shorten proofs a lot? Andreas Blass 2012-04-19T16:58:56Z 2012-04-19T16:58:56Z <p>Hindman's theorem is an example where (slightly?) higher infinity simplifies a proof greatly. The theorem asserts that, if you partition the set of positive integers into finitely many subsets, then there is an infinite set $H$ of positive integers such that all sums of finitely many members of $H$ lie in the same piece of your partition. (If, like me, you consider 0 to be such a finite sum, of 0 terms, then explicitly exclude it from the conclusion, so that the statement makes sense.) Hindman's original proof worked in the natural domain of the result, second-order arithmetic, but Hindman himself has suggested that this proof is such as would be useful for torturing students. There is a non-torturous proof, due to Galvin and Glazer, but an essential part of that proof involves considering a semigroup whose points are ultrafilters on the natural numbers - so we're well beyond second-order arithmetic. In fact, a key lemma in the proof depends on applying Zorn's Lemma to a certain poset of subsemigroups of this semigroup. So we're even farther "up" from the natural domain of the theorem. (By the way, the reason for "slightly?" in the first line of this answer is that, although we're well above where most mathematicians like to work, we're nowhere near what set theorists would call "large cardinals".)</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/94604#94604 Answer by Johan Wästlund for Can infinity shorten proofs a lot? Johan Wästlund 2012-04-20T06:48:42Z 2012-04-20T06:48:42Z <p>An example that I came to think of even though it doesn't have to involve infinity is the existence of a finite field with a specified number $q=p^n$ of elements. One can show by an enumerative argument (Möbius inversion) that there must be an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$ (there simple aren't enough lower degree polynomials to factor all of them). If $f$ is such a polynomial, then $\mathbb{Z}_p[x]/f(x)$ provides a field of $q$ elements. </p> <p>An alternative is to use the fact that every field has an algebraic closure, and to verify that the set of zeros of $x^q-x$ in the algebraic closure of $\mathbb{Z}_p$ is closed under the field operations (and that they are distinct).</p> <p>It's true that we really only need the splitting field of $x^q-x$ which, as it turns out, consists of only those $q$ zeros, but that's something that emerges from the proof, and it might conceivably have been much bigger.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/94641#94641 Answer by Larry Rolen for Can infinity shorten proofs a lot? Larry Rolen 2012-04-20T13:37:55Z 2012-04-20T13:37:55Z <p>Using Eilenberg-Maclane spaces (namely $K(\mathbb{Z},2)=\mathbb{P}^{\infty}(\mathbb{C})$) and cellular approximation,one can show that any 3-fold with a positive Betti number has a map to the sphere $S^2$ which is not nullhomotopic. I am not sure how "down to earth" this example is, but it shows that even when studying finite dimensional objects it is natural to consider infinite-dimensional things. </p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/115319#115319 Answer by Chris Pressey for Can infinity shorten proofs a lot? Chris Pressey 2012-12-03T18:04:58Z 2012-12-03T18:04:58Z <p>Short version of "there exist functions not computable by Turing machine" using infinities:</p> <p>There are an uncountable number of predicates, but only a countable number of Turing machines, so there are some predicates that are not computable by a Turing machine.</p> <p>(That's weaker than the usual proof of the uncomputability of the Halting Problem of course, because it doesn't tell you that "does this Turing machine halt?" is one of those predicates.)</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/115345#115345 Answer by none for Can infinity shorten proofs a lot? none 2012-12-04T00:39:28Z 2012-12-04T02:05:46Z <p>Maybe you want something more proof-theoretic, like <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_speed-up_theorem" rel="nofollow">Gödel's speed-up theorem</a>. The example from the Wikipedia article says: the statement "This statement cannot be proved in Peano arithmetic in fewer than a googolplex symbols" is provable in Peano arithmetic, but the shortest proof has at least a googolplex symbols (explanation given there). On the other hand, the theory PA+CON(PA) gives a short proof. </p> <p>Similarly, second-order arithmetic (since it proves CON(PA)) gives a short proof, and I guess that would count as "adding infinity". Or you could look at hereditarily finite set theory (ZFC with the axiom of infinity replaced by its negation). I'm pretty sure regular ZFC proves this theory consistent, so again the speed-up theorem works out about the same way as it does with PA.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/115389#115389 Answer by Pablo Zadunaisky for Can infinity shorten proofs a lot? Pablo Zadunaisky 2012-12-04T11:28:11Z 2012-12-04T11:28:11Z <p>I am surprised no one has mentioned any examples from physics. Fluid mechanics for example obtains some beautiful results by assuming that a fluid is continuous, while at the molecular level it is a discrete object. An example from my physics highschool textbook:</p> <blockquote> <p>Suppose you have a circular grain storage, with a diameter of 2 meters and 10 meters high. The grain weights about $X \ kg/m^3$. What is the pressure at two meters depth? at four meters depth?</p> </blockquote> <p>The problem is easier to solve if we think of the grain as a fluid and apply, say, Pascal's principle.</p> http://mathoverflow.net/questions/5751/can-infinity-shorten-proofs-a-lot/125455#125455 Answer by katz for Can infinity shorten proofs a lot? katz 2013-03-24T12:50:54Z 2013-03-24T12:50:54Z <p>I once had a teaching assistant in calculus who admitted that he was unable to give an epsilon, delta proof that a the Heaviside stepfunction was not continuous. To take a slightly less trivial example, the proof that $y=x^2$ is not uniformly continuous using $\epsilon, \delta$ is somewhat involved for a freshman. Using an infinite number $H$, this becomes transparent. Consider the infinitesimal $e=1/H$. Then the points $x=H$ and $x=H+e$ are infinitely close, but the corresponding values of $y$ are not by a trivial calculation. This implies a failure of uniform continuity by general theory.</p>