¿Todos los teoremas tienen una prueba corta?

Question

Esta pregunta es de alguna manera basada en mi creencia de que cada teorema tiene una corta y simple prueba. Por "prueba" me refiero a:

• La prueba de una declaración
• Refutar una declaración
• Demostrar que un enunciado es indecidible

Una vez que hemos formalizado lo que entendemos por un "paso" en una prueba, podría ser probado que cada teorema tiene una prueba que consta de menos de $n$ pasos? Si es así:

• ¿Cuál sería la (mínima) de un valor de $n$?
• Dicha prueba sería de alrededor de todas las pruebas , entonces, lo que dice acerca de sí mismo?
• Podría ser (en algún sentido) pruebas que no tiene un número entero de pasos?

Answer 1

Deje $f(n)$ ser cualquier computable (total) de la función. A continuación, debe haber un teorema $T$ de la longitud de la $N$ tales que el menor prueba de $T$ es más de $f(N)$ pasos.

Esto es debido a que, en el caso de $T$ no existe, podríamos resolver conocido irresoluble preguntas.

Este resultado supone el siguiente hecho básico acerca de la "longitud" de las pruebas:

1. Dado cualquier $m$, hay sólo un número finito de pruebas de longitud en la mayoría de las $m$.
2. Existe un programa que puede tomar $m$ como entrada un retorno de la lista de pruebas de longitud de $m$.

Answer 2

Hay infinitamente muchos teoremas, si por "teorema" simplemente significa "verdadero enunciado matemático". Si permitimos $k$ tipos distintos de paso, sólo hay $k^n$ diferentes pruebas de longitud de $n$ (y muchos de ellos probarían las mismas cosas una y otra vez). Así que no, no $n$, de modo que cada teorema puede ser comprobada en $n$ pasos.

Como cuestión de hecho, el Teorema de la Incompletitud de Gödel afirma que hay algo de cierto enunciado matemático - "teorema" por la definición que se ha sugerido anteriormente - que no tiene ninguna prueba en su totalidad, dada una definición de un "paso" en una prueba.

Por otro lado, jugando con esta idea, se podría decir un "teorema" es un verdadero enunciado matemático para que una prueba ha sido escrito. Entonces realmente hay un $n$, de modo que cada teorema tiene una prueba de longitud en la mayoría de las $n$ - tome $n$ a ser el número de pasos necesarios para escribir la más larga de la prueba de que se ha escrito (probablemente la clasificación teorema para finitos simples grupos, pero no estoy seguro). Pero yo no creo que haya nada interesante que decir acerca de $n$, aparte de que es ENORME, tan largo como la prueba del sistema es bastante simple.

Answer 3

sin duda, un teorema no necesita cumplir con ningún requisito de calidad real, por lo que podría contener una gran cantidad de pasos que deben probarse, más de lo que se pueda imaginar.