¿Está toda la matemática ordinaria contenida en las matemáticas de la escuela secundaria?

Question

Por matemáticas de bachillerato me refiero a la Aritmética de Funciones Elementales (AFE), donde se permite +,×, x y y una forma débil de inducción para fórmulas con cuantificadores acotados. Esto es mucho más débil que la aritmética recursiva primitiva, que a su vez es mucho más débil que la aritmética de Peano, que a su vez es mucho más débil que la ZFC en la que trabajamos normalmente.

Sin embargo, parece que hay muy pocos teoremas (sobre números enteros) que se sepa que requieren algo más que este sistema increíblemente débil para demostrarlos. Los pocos teoremas que conozco que necesitan más que esto incluyen:
*Resultados de consistencia para varios sistemas más fuertes (siguiendo a Godel). Esto incluye resultados como el teorema de Paris Harrington y las secuencias de Goodstein que son formas inteligentemente disfrazadas de resultados de consistencia.
*Algunos resultados de la teoría de Ramsey, que dicen que cualquier cosa posible ocurrirá en un conjunto suficientemente grande. Ejemplos típicos: Gowers demostró una cota inferior muy grande para el lema de Szemeredi mostrando que no se puede demostrar en la aritmética de funciones elementales, y se sabe que el teorema menor del grafo de Robertson-Seymour requiere funciones tan grandes que es indemostrable en la aritmética de Peano.

No se me ocurre ningún resultado (sobre los números enteros) fuera de estas áreas (lógica matemática, variaciones de la teoría de Ramsey) que se sepa que requiera algo más que el EPT para ser demostrado. Una buena regla general es que cualquier cosa que implique torres de exponenciales no limitadas probablemente no sea demostrable en el EPT, y a la inversa, si no hay ninguna función tan grande, entonces uno podría sospechar que el resultado es demostrable en el EPT.

Así que mi pregunta es : ¿alguien conoce resultados naturales en las matemáticas "ordinarias" (teoría de los números, geometría algebraica, grupos de Lie, álgebras de operadores, geometría diferencial, combinatoria, etc...) en los que se produzcan de forma seria funciones mayores que una torre finita de exponenciales? En la práctica, esto es probablemente más o menos equivalente a pedir teoremas sobre los números enteros no demostrables en la EPT.

Enlaces relacionados: http://en.wikipedia.org/wiki/Grand_conjecture sobre Friedman haciendo una pregunta similar.

Por cierto, codificar resultados profundos como ecuaciones diofantinas y demás es hacer trampa. Y, por favor, no haga comentarios sugiriendo que el último teorema de Fermat necesita cardinales inaccesibles a menos que entienda la prueba de Wiles.

Answer 1

No sé si esto es lo que tenías en mente, pero en 1980 Alex Wilkie demostró que si uno utiliza los axiomas

1. $x + y = y + x$
2. $(x + y) + z = x + (y + z)$
3. $x \cdot 1 = x$
4. $x \cdot y = y \cdot x$
5. $(x \cdot y) \cdot z = x \cdot (y \cdot z)$
6. $x \cdot (y + z) = x \cdot y + x \cdot z$
7. $1^x = 1$
8. $x^1 = x$
9. $x^{y + z} = x^y \cdot x^z$
10. $(x \cdot y)^z = x^z \cdot y^z$
11. $(x^y)^z = x^{y \cdot z}$ ,

entonces no se puede demostrar la (verdadera) identidad $$ ((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. $$ Ver http://en.wikipedia.org/wiki/Tarski%27s_high_school_algebra_problem .

Answer 2

Creo que este ejemplo puede servir. Está abierto si el grupo de Thompson $F$ es susceptible.

Podemos presentar $F$ como $\langle A,B\mid [AB^{-1},A^{-1}BA]=[AB^{-1},A^{-2}BA^2]={\rm id}]\rangle$ .

Amabilidad de un grupo finitamente presentado $G$ con un conjunto generador finito $\Gamma$ es equivalente a la finitud del Función Følner $$ Føl_{G,\Gamma}(n)=\min(|X|\mid X\subseteq G,\text{ $ X $ is ($ 1/n $)-Følner with respect to $ \N - Gamma $} ), $$ donde $X$ es $\varepsilon$ -Følner con respecto a $\Gamma$ si $$ \sum_{\gamma\in\Gamma}|(X\cdot\gamma)\triangle X|<\varepsilon|X|. $$ Aquí, $\triangle$ denota una diferencia simétrica, como es habitual.

Justin Moore probado recientemente lo siguiente:

Teorema. Para cada conjunto generador simétrico finito $\Gamma\subseteq F$ hay una constante $C>1$ de manera que si $X\subseteq F$ es un $C^{-n}$ -Conjunto de Følner con respecto a a $\Gamma$ entonces $X$ contiene al menos $exp_n(0)$ elementos.

Aquí, $exp_0(n)=n$ y $exp_{m+1}(n)=2^{exp_m(n)}$ .

Esto significa que $F$ no es susceptible, o su susceptibilidad no es demostrable en la aritmética recursiva primitiva.

---

Sobre las recientes discusiones acerca de la amenidad o no de $F$ , ver este bonito respuesta por Mark Sapir.

Answer 3

La afirmación de que la periodicidad de Mesas de laver tiende a infinito no es demostrable en la ARP (por lo tanto, también en la EPT), aunque es demostrable bajo el supuesto de una rank-into-rank incrustación.

Answer 4

Como la función de Ackermann no está disponible en el EPT, el límite superior de Tarjan -el función inversa de Ackermann - para el tiempo de ejecución del estructura de datos union-find no es demostrable en la EPT. Esto probablemente no importa mucho, ya que un límite superior más débil como $\mathcal{O}(\log (\log (\log n)))$ no es realmente peor desde un punto de vista práctico.

Otro ejemplo: es la insolubilidad del Problema de detención ¿Probable en la EPT? Aunque se trata de un ejemplo de lógica, yo diría que esto tiene implicaciones muy prácticas y, por tanto, "ordinarias", como la imposibilidad de comprobar automáticamente si el código fuente de un programa informático arbitrario se ajusta a la especificación. (Bueno, se puede restringir el lenguaje de programación para que esto sea posible, pero entonces se pierde la capacidad de escribir intérpretes para este lenguaje de programación).

Answer 5

He aquí otro ejemplo: El grupo Baumslag relacionado con 1 $\langle a,b | a^{a^b}=a^2\rangle$ tiene la función de Dehn $d(n)$ que es exactamente (hasta la equivalencia natural) $2^{2^{2...}}$ $\log n$ veces, véase Platonov, A. N. Una función isoparamétrica del grupo Baumslag-Gersten. (Ruso. Resumen en ruso) Vestnik Moskov. Univ. Ser. I Mat. Mekh. 2004, , no. 3, 12--17, 70; traducción en Moscow Univ. Math. Bull. 59 (2004), no. 3, 12--17 (2005). Recordemos que la función de Dehn es la función más pequeña que limita el número de relaciones de definición necesarias para deducir una relación $w=1$ con $|w|\le n$ que es verdadera en el grupo (o el número mínimo de factores en el producto de conjugados de las relaciones definitorias que son iguales a $w$ en el grupo). La notación $a^b$ significa $b^{-1}ab$ .