Is all ordinary mathematics contained in high school mathematics? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T19:57:45Z http://mathoverflow.net/feeds/question/36580 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics Is all ordinary mathematics contained in high school mathematics? Richard Borcherds 2010-08-24T18:39:34Z 2010-11-23T13:05:42Z <p>By high school mathematics I mean Elementary Function Arithmetic (EFA), where one is allowed +,&times;, x<sup>y</sup>, and a weak form of induction for formulas with bounded quantifiers. This is much weaker than primitive recursive arithmetic, which is in turn much weaker than Peano arithmetic, which is in turn much weaker than ZFC that we normally work in. </p> <p>However there seem to be very few theorems (about integers) that are known to require anything more than this incredibly weak system to prove them. The few theorems that I know need more than this include:<br> *Consistency results for various stronger systems (following Godel). This includes results such as the Paris Harrington theorem and Goodstein sequences that are cleverly disguised forms of consistency results.<br> *Some results in Ramsey theory, saying that anything possible will happen in a sufficiently large set. Typical examples: Gowers proved a very large lower bound for Szemeredi's lemma showing that it cannot be proved in elementary function arithmetic, and the Robertson-Seymour graph minor theorem is known to require such large functions that it is unprovable in Peano arithmetic. </p> <p>I can think of no results at all (about integers) outside these areas (mathematical logic, variations of Ramsey theory) that are known to require anything more than EFA to prove. A good rule of thumb is that anything involving unbounded towers of exponentials is probably not provable in EFA, and conversely if there is no function this large then one might suspect the result is provable in EFA. </p> <p>So my question is : does anyone know of natural results in "ordinary" mathematics (number theory, algebraic geometry, Lie groups, operator algebras, differential geometry, combinatorics, etc...) in which functions larger than a finite tower of exponentials occur in a serious way? In practice this is probably more or less equivalent to asking for theorems about integers unprovable in EFA.</p> <p>Related links: <a href="http://en.wikipedia.org/wiki/Grand_conjecture" rel="nofollow">http://en.wikipedia.org/wiki/Grand_conjecture</a> about Friedman asking a similar question.</p> <p>By the way, encoding deep results as Diophantine equations and so on is cheating. And please do not make remarks suggesting that Fermat's last theorem needs inaccessible cardinals unless you understand Wiles's proof.</p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/36584#36584 Answer by Kiochi for Is all ordinary mathematics contained in high school mathematics? Kiochi 2010-08-24T18:58:56Z 2010-08-24T18:58:56Z <p>The statement that the periodicity of <a href="http://en.wikipedia.org/wiki/Laver_table" rel="nofollow">Laver tables</a> tends to infinity is not provable in PRA (hence also EFA), although it is provable under the assumption of a <a href="http://en.wikipedia.org/wiki/Rank-into-rank" rel="nofollow">rank-into-rank</a> embedding.</p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/36595#36595 Answer by Joseph O'Rourke for Is all ordinary mathematics contained in high school mathematics? Joseph O'Rourke 2010-08-24T22:43:06Z 2010-08-25T10:27:06Z <p>This is a <em>great</em> question! And this is <em>not</em> an answer. The paper by Shelah and Soifer, <a href="http://portal.acm.org/citation.cfm?id=989570.989584" rel="nofollow">Axiom of choice and chromatic number of the plane</a> shows that <a href="http://en.wikipedia.org/wiki/Chromatic_number_of_the_plane" rel="nofollow">the chromatic number in the plane</a> "is not countable (if it exists) in a consistent system of axioms with limited choice." Is the chromatic number of plane part of "ordinary mathematics"? Unclear...</p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/36603#36603 Answer by Richard Stanley for Is all ordinary mathematics contained in high school mathematics? Richard Stanley 2010-08-24T23:54:02Z 2010-08-25T00:34:35Z <p>I don't know whether this is what you had in mind, but in 1980 Alex Wilkie showed that if one uses the axioms</p> <ol> <li>$x + y = y + x$</li> <li>$(x + y) + z = x + (y + z)$</li> <li>$x \cdot 1 = x$</li> <li>$x \cdot y = y \cdot x$</li> <li>$(x \cdot y) \cdot z = x \cdot (y \cdot z)$</li> <li>$x \cdot (y + z) = x \cdot y + x \cdot z$</li> <li>$1^x = 1$</li> <li>$x^1 = x$</li> <li>$x^{y + z} = x^y \cdot x^z$</li> <li>$(x \cdot y)^z = x^z \cdot y^z$</li> <li>$(x^y)^z = x^{y \cdot z}$,</li> </ol> <p>then one cannot prove the (true) identity $$((1+x)^y+(1+x+x^2)^y)^x\cdot ((1+x^3)^x+(1+x^2+x^4)^x)^y$$ $$\ \ \ \ \ \ \ \ \ = ((1+x)^x+(1+x+x^2)^x)^y\cdot ((1+x^3)^y+(1+x^2+x^4)^y)^x.$$ See <a href="http://en.wikipedia.org/wiki/Tarski%27s_high_school_algebra_problem" rel="nofollow">http://en.wikipedia.org/wiki/Tarski%27s_high_school_algebra_problem</a>.</p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/36610#36610 Answer by Andres Caicedo for Is all ordinary mathematics contained in high school mathematics? Andres Caicedo 2010-08-25T02:08:19Z 2010-11-03T05:46:10Z <p>I believe this example may qualify. It is open whether Thompson's group $F$ is amenable. </p> <p>We may present $F$ as $\langle A,B\mid [AB^{-1},A^{-1}BA]=[AB^{-1},A^{-2}BA^2]={\rm id}]\rangle$.</p> <p><em>Amenability</em> of a finitely presented group $G$ with finite generating set $\Gamma$ is equivalent to the finiteness of the <em>Følner function</em> $$Føl_{G,\Gamma}(n)=\min(|X|\mid X\subseteq G,\text{ X is (1/n)-Følner with respect to \Gamma} ),$$ where $X$ is $\varepsilon$-Følner with respect to $\Gamma$ iff $$\sum_{\gamma\in\Gamma}|(X\cdot\gamma)\triangle X|&lt;\varepsilon|X|.$$ Here, $\triangle$ denotes symmetric difference, as usual.</p> <p>Justin Moore <a href="http://www.math.cornell.edu/~justin/Ftp/tower.pdf" rel="nofollow">proved</a> recently the following:</p> <p><strong>Theorem.</strong> For every ﬁnite symmetric generating set $\Gamma\subseteq F$ there is a constant $C>1$ such that if $X\subseteq F$ is a $C^{-n}$-Følner set with respect to $\Gamma$, then $X$ contains at least $exp_n(0)$ elements.</p> <p>Here, $exp_0(n)=n$ and $exp_{m+1}(n)=2^{exp_m(n)}$. </p> <p>This means that either $F$ is not amenable, or its amenability is not provable in primitive recursive arithmetic.</p> <hr> <p>On the recent arguments about amenability or not of $F$, see this nice <a href="http://mathoverflow.net/questions/26821/is-thompsons-group-f-amenable/29065#29065" rel="nofollow">answer</a> by Mark Sapir.</p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/36980#36980 Answer by Greg Graviton for Is all ordinary mathematics contained in high school mathematics? Greg Graviton 2010-08-28T16:32:07Z 2010-08-28T16:32:07Z <p>Since Ackermann's function is not available in EFA, Tarjan's upper bound – the <a href="http://en.wikipedia.org/wiki/Ackermann_function#Inverse" rel="nofollow">inverse Ackermann function</a> – for the run-time of the <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow">union-find data structure</a> is not provable in EFA. This probably doesn't matter much, since a weaker upper bound like $\mathcal{O}(\log (\log (\log n)))$ is not really worse from a practical point of view.</p> <p>Another example: is the unsolvability of the <a href="http://en.wikipedia.org/wiki/Halting_problem" rel="nofollow">Halting Problem</a> provable in EFA? While this is an example from logic, I would argue that this has very practical and thus "ordinary" implications, like the impossibility of automatically checking whether the source code of an arbitrary computer program adheres to the specification. (Well, you can restrict the programming language to make this possible, but then you lose the ability to write interpreters for this programming language.)</p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/39478#39478 Answer by gowers for Is all ordinary mathematics contained in high school mathematics? gowers 2010-09-21T09:53:55Z 2010-09-21T09:53:55Z <p>An innocent looking problem in which the Ackermann function unexpectedly comes up is the length of Davenport-Schinzel sequences. I won't bother to say in detail what they are, because Wikipedia does a good job.</p> <p><a href="http://en.wikipedia.org/wiki/Davenport%E2%80%93Schinzel_sequence" rel="nofollow">http://en.wikipedia.org/wiki/Davenport%E2%80%93Schinzel_sequence</a></p> <p>Actually, what one gets is a bound of the form na(n), where a is the <em>inverse</em> of the Ackermann function, but then one can ask how big n needs to be for the bound to be worse than Cn.</p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/39483#39483 Answer by Mark Sapir for Is all ordinary mathematics contained in high school mathematics? Mark Sapir 2010-09-21T10:39:12Z 2010-09-21T10:39:12Z <p>Here is another example: The 1-related Baumslag group $\langle a,b | a^{a^b}=a^2\rangle$ has Dehn function $d(n)$ which is exactly (up to the natural equivalence) $2^{2^{2...}}$ $\log n$ times, see Platonov, A. N. An isoparametric function of the Baumslag-Gersten group. (Russian. Russian summary) Vestnik Moskov. Univ. Ser. I Mat. Mekh. 2004, , no. 3, 12--17, 70; translation in Moscow Univ. Math. Bull. 59 (2004), no. 3, 12--17 (2005). Recall that the Dehn function is the smallest function that bounds the number of defining relations needed to deduce a relation $w=1$ with $|w|\le n$ which is true in the group (or the minimal number of factors in the product of conjugates of the defining relations that are equal to $w$ in the group). The notation $a^b$ means $b^{-1}ab$. </p> http://mathoverflow.net/questions/36580/is-all-ordinary-mathematics-contained-in-high-school-mathematics/47089#47089 Answer by anon for Is all ordinary mathematics contained in high school mathematics? anon 2010-11-23T13:05:42Z 2010-11-23T13:05:42Z <p>I think we're heading towards an era where "ordinary" mathematics includes logic, at least the parts of it that can be described as applied mathematics (used in practical problems of the real world). For example, the ML programming language is based on polymorphic lambda calculus. I'm no expert but I have the impression that the proof that polymorphic lambda calculus is strongly normalizing is equivalent to second order arithmetic. There are fancier languages based in even more powerful (?) theories, like Coq implements Martin-Lof type theory more or less directly. I'm just a programmer trying to learn these languages but people disigning them and writing compilers for them (e.g. implementing type inference) seem to me to often be up to their elbows in proof theory. I saw a thesis by someone about ordinal analysis of programs (after all, by the Curry-Howard correspondence, programs are proofs..). I wondered if software engineers (at least those in high-assurance programming) will someday use proof-theoretic ordinals in their daily work just like electrical engineers now use complex numbers. </p> <p>In complexity theory, there are some proofs that P vs NP is independent of some sizeable fragments of PA, but maybe those fragments are weaker than EFA.</p>