¿Existen razones matemáticas inherentes por las cuales existen pruebas difíciles?

Question

Esto no es una queja sobre la dificultad de mi curso de pruebas, ni sobre cómo puedo aprender a demostrar cosas mejor, como parecen ser todas las demás preguntas de este tipo en Google. Estoy preguntando en un sentido puramente técnico (pero aún solo con respecto a las matemáticas; por eso consideré que esta pregunta era la más apropiada para este Stack Exchange).

Para explicar más: me parece que si tienes algunas suposiciones (matemáticas) y hay una conclusión lógica que se puede deducir de esas suposiciones, esa conclusión no debería ser tan difícil de sacar. ¡Literalmente se sigue de las suposiciones! Sin embargo, claramente este no es el caso (al menos para muchas pruebas). La Conjetura de Poincaré tomó casi un siglo en probarse. No he leído la prueba en sí misma, pero que tenga ~320 páginas no sugiere facilidad. Y hay innumerables ejemplos de dificultad. En 1993, Wiles anunció la prueba final del Último Teorema de Fermat, que fue originalmente propuesto por Fermat en 1637 y fue "considerado inaccesible de probar por los matemáticos contemporáneos" (artículo de Wikipedia sobre la prueba).

Por lo tanto, claramente, en muchos casos, los matemáticos tienen que esforzarse mucho para demostrar ciertas conclusiones lógicas. ¿Cuál es la razón de esto? ¿Es la falta de inteligencia de los humanos? ¿Falta de creatividad? Existe el campo de demostración automatizada de teoremas del que intenté obtener alguna idea, pero parece que los algoritmos producidos en este campo son mediocres en comparación con los humanos, e incluso estos algoritmos son obscenamente difíciles de implementar. Entonces, aparentemente, ciertas pruebas son inherentemente difíciles. Así que vuelvo a suplicar - ¿por qué es esto?

(EDIT) Para reformular mi pregunta: ¿existen alguna razones matemáticas inherentes para que existan pruebas difíciles?

Answer 1

Aunque esta pregunta pueda parecer superficialmente basada en opiniones, de hecho hay una respuesta objetiva. La razón principal es que el problema de detención no se puede resolver de forma computable, y las afirmaciones sobre el comportamiento de detención son arbitrariamente difíciles de probar, y la aritmética elemental es suficiente para expresar nociones que son al menos tan generales como las afirmaciones sobre el comportamiento de detención.

Ahora los detalles. Primero entiende el teorema de incompletitud. A continuación, observa que cualquier sistema de fundamentos razonable puede razonar sobre programas, mediante el uso de codificación de Gödel para expresar y razonar sobre la ejecución de programas finitos. Observa que todo este razonamiento sobre los programas puede ocurrir dentro de un pequeño fragmento de PA (Aritmética de Peano de 1er orden) llamado PA−. Por lo tanto, el teorema de incompletitud implica que, no importa cuál sea tu sistema de fundamentos (siempre y cuando sea razonable), siempre habría oraciones aritméticas verdaderas que no puede probar, y estas sentencias se pueden escribir explícitamente y no son tan largas.

Además, la misma reducción al problema de detención implica que ni siquiera puedes determinar de forma computable si alguna oración aritmética es un teorema de tu sistema de fundamentos favorito S o no. ¡Esto implica en realidad que no hay un límite computable en la longitud de una demostración más corta de un teorema dado! Para ser precisos, no hay una función computable $f$ tal que para cada cadena $X$ tengamos que o bien $X$ no es un teorema de S o hay una demostración de $X$ sobre S de longitud como máximo $f(X)$. Esto proporciona la respuesta (a primera vista sorprendente) a tu pregunta:

Conclusión lógicamente forzada a partir de un conjunto de supuestos explícitamente descritos puede requerir un gran número de pasos para deducirse, tan grande que ¡no hay un límite computable en ese número de pasos! Por lo tanto, ¡sí, las demostraciones son inherentemente difíciles!

Las cosas son aún peores; si crees que S no prueba ninguna oración aritmética falsa (lo cual deberías, de lo contrario ¿por qué estás usando S?), entonces podemos construir explícitamente una oración aritmética Q tal que S pruebe Q pero debes creer que ninguna demostración de Q sobre S tiene menos de $2^{10000}$ símbolos.

Y en caso de que pienses que tales fenómenos pueden no ocurrir en las matemáticas que proponen los no lógicos, considera el hecho de que el problema generalizado de Collatz es indecidible, y el hecho de que el décimo problema de Hilbert fue propuesto sin idea de que sería computablemente insoluble. De manera similar, muchos otros problemas combinatorios discretos como el encaje de azulejos de Wang eventualmente se encontraron ser computacionalmente insolubles.

Answer 2

Ya has recibido buenas respuestas, pero quiero añadir un punto que no se ha cubierto: combinatoria.

Es cierto, puedes comenzar con algunas suposiciones y operaciones simples, pero ¿cuántas formas ordenadas hay de combinar esas suposiciones? En un enfoque ingenuo de fuerza bruta, suponiendo que la solución más corta (ignorando el hecho de que esto es incalculable, solo necesitamos un límite inferior) toma n pasos, incluyendo el uso de suposiciones o operadores; entonces hay $ n! $ formas de dar todos los n pasos, pero solo 1 solución correcta. ¡Y ni siquiera conocemos n de antemano!

Por lo tanto, las pruebas son difíciles porque la fuerza bruta ingenua no es una opción viable.

Answer 3

Porque todas las pruebas fáciles ya han sido demostradas o son trivialmente fáciles.

Puedo escribir una serie infinita de afirmaciones que nunca han sido probadas:

(A) Probar que $465458891113223521658103238 + 1 = 465458891113223521658103239$

(B) Probar que $465458891113223521658103239 + 1 = 465458891113223521658103240$

(C) Probar que $465458891113223521658103240 + 1 = 465458891113223521658103241$

Ninguno de estos problemas nunca ha sido planteado, mucho menos demostrado, antes. (En serio, ¡busca cualquiera de esos números! ¡Nunca han sido escritos antes!) Sin embargo, cada uno es trivialmente fácil de probar: de hecho, es suficiente decir que siguen inmediatamente de las definiciones de cómo funcionan los números y qué hace el $+$.

Así que es claro que hay infinitas pruebas "fáciles". ¿Por qué no vemos más pruebas fáciles siendo discutidas en revistas matemáticas? Porque son aburridas, y no aprendemos nada nuevo de ellas.

Entonces la pregunta no es realmente "¿por qué son difíciles las pruebas?", sino más bien "¿por qué las pruebas de las que se habla son difíciles?" y la respuesta es: bueno, la razón principal es porque son difíciles. Los matemáticos pasan mucho tiempo explorando el espacio de posibles pruebas para encontrar exactamente aquellas que sean difíciles e interesantes. Las pruebas se escriben específicamente para cubrir la mayor cantidad de "terreno" posible, de manera que una vez que se demuestran, no haya pruebas "trivialmente similares" que queden sin demostrar (de la misma manera que A, B y C arriba son todas trivialmente similares). Así que simplemente no queda nada por demostrar que sea fácil (con nuestras técnicas actuales de demostración) e interesante.

Por supuesto, de vez en cuando una prueba que parecía extremadamente difícil resulta ser fácil. Estas son las pruebas más interesantes de todas, porque tienden a enseñarnos mucho sobre nuestras técnicas de demostración.

Answer 4

La dificultad proviene de la abstracción. Las matemáticas es un tema en capas. Cada tema se construye sobre una compleja base de muchos temas ligeramente más simples, que son en sí mismos todas abstracciones de ideas más fundamentales. Podrías preguntarte por qué algunos programas de computadora son tan complejos. En su mayor parte, cualquiera de las miles de líneas en un programa de computadora complejo no es tan compleja. Pero, cuando se abstraen y se combinan múltiples procesos diferentes, entender cómo funciona el programa y depurarlo se vuelve muy difícil.

A veces, la dificultad en las demostraciones proviene del hecho de que tienes que empezar con una cebolla entera, pelarla capa por capa hasta llegar al núcleo, y luego reconstruirla desde cero.

Answer 5

Voy a intentar complementar la discusión. Creo que la pregunta también está vinculada a esta otra: ¿por qué es tan difícil elegir buenos axiomas?

Por supuesto, cada teorema, incluso la Conjetura de Poincaré, es trivial si lo insertamos como un axioma en un sistema (siempre podemos hacerlo para una fórmula verdadera). Podríamos ser menos extremos y reducir a axiomas solo los lemas difíciles utilizados para demostrar algo. Entonces el teorema seguiría fácilmente. Toma, por ejemplo, la clásica tríada de teoremas equivalentes en teoría de conjuntos: el Teorema de Bien-ordenación que establece que cada conjunto puede ser ordenado; el lema de Zorn y el axioma de elección. Hay un chiste que dice:

El axioma de elección es obviamente verdadero, el principio de bien-ordenación obviamente falso, y ¿quién puede decir algo acerca del lema de Zorn?

Es complejo (al menos para mí) demostrar el lema de Zorn a partir del axioma de elección. Pero el principio de bien-ordenación sigue fácilmente del lema de Zorn. Vea la discusión en el enlace de arriba.

Las matemáticas inversas son los campos que hacen lo siguiente: danos teoremas y encontraremos qué axioma se necesita. Lo que me parece interesante es que este enfoque permite a alguien más inclinado filosóficamente ser más preciso sobre las cosas que quiere evitar.

Pero digamos que nuestra filosofía es algo así como un pragmatismo de prueba: dados un conjunto de teoremas, ¿existe un sistema de axiomas óptimo para ello? Con óptimo nos referimos no solo al tamaño del axioma, sino tal vez también al tiempo de cómputo consumido (o ambos). Bueno, si podemos asumir que el conjunto de axiomas y el conjunto de reglas que los operan pueden ser implementados en una computadora, esta pregunta resulta estar vinculada a la complejidad computacional. En especial, hay un análogo del Teorema de Incompletitud de Gödel en este contexto, llamado Teorema de Chaitin.

También hay una cosa que vale la pena mencionar, creo: dado el valor de verdad de algunas proposiciones, verificar si alguna fórmula de lógica proposicional es verdadera es pan comido, simplemente sustituye los valores de verdad en ella. Dada una fórmula, encontrar los valores de verdad que hacen que la fórmula sea verdadera: eso es más difícil, en algunos casos, las computadoras que tenemos hoy en día pueden hacerlo, y en el peor de los casos tomará mucho tiempo (no viable para nuestras computadoras). Este es el problema SAT. Pero este problema seguirá siendo decidible para cualquier computadora abstracta (una computadora que no tiene problemas de tiempo): haz la tabla de verdad. Ahora el problema parece comenzar cuando tenemos una lógica con predicados y cuantificadores. No es decidible para ninguna computadora abstracta saber si una fórmula en lógica de predicados es satisfacible.