¿Por qué algunos problemas matemáticos con enunciados aparentemente sencillos acaban solicitando pruebas extremadamente complicadas y rompedoras o permanecen sin resolver durante largos periodos de tiempo? (Por ejemplo, la conjetura de Collatz, la FLT, la conjetura de los primos gemelos, la conjetura de abc, la conjetura de Legendre, etc.) ¿Tienen algo en común?
No estoy seguro de cómo responder a "¿Tienen algo en común?" Pero he aquí una razón por la que siempre encontraremos conjeturas simples con pruebas sorprendentemente largas:
Teorema de incompletitud de Godel dice (entre otras cosas) que el conjunto de sentencias que se pueden demostrar mediante un conjunto "razonable" fijo de axiomas nunca es computable. Es decir, mientras $T$ es un conjunto "razonable" de axiomas, no hay ningún programa de ordenador que al alimentar una frase $\varphi$ dará como resultado "Sí" si $\varphi$ es un teorema de $T$ y "No" si $\varphi$ no es un teorema de $T$ .
Esto tiene un corolario importante para la longitudes de las pruebas . Fijar algún sistema de axiomas - digamos, la Aritmética de Peano. Entonces afirmo:
No hay ninguna función computable $f$ de manera que cualquier frase de longitud $n$ que es demostrable en $PA$ tiene una prueba de longitud máxima $f(n)$ .
¿Por qué? Bueno, si no, dejemos que $f$ sea una función de este tipo; para saber si $PA$ demuestra alguna frase $\varphi$ sólo hay que buscar entre todas las pruebas (finitas) de longitud $\le f(\vert\varphi\vert)$ . Si no encuentra uno, entonces $\varphi$ no es un teorema de $PA$ ¡!
Esto significa que siempre veremos pruebas "sorprendentemente largas": por ejemplo, habrá algún teorema de $PA$ que cuando se escribe es $n$ caracteres, pero cuya prueba más corta en $PA$ tiene una longitud $$n^{n^{n^{...}}}\quad\mbox{($ n^{100000} $-many times)}.$$ Por supuesto, esto no dice nada $^*$ sobre cómo encontrar teoremas tan sorprendentemente difíciles de probar, especialmente ejemplos naturales del mismo. Una especie de optimismo matemático (bueno, I Creo que es optimismo :P) dice que siempre debemos esperar ejemplos naturales de todos los fenómenos lógicos posibles, pero eso no es un teorema, es una opinión (y tal vez una tontería :P).
$^*$ En realidad, podemos generar efectivamente esos ejemplos. Pero son realmente artificiales.
@Colbi ¡Hay un montón! Busca en Google "proof speedup" o "lengths of proofs" o "proof complexity". Ahora tengo que ir a jugar al Super Smash Bros. con mi hermana, pero añadiré más enlaces cuando tenga tiempo. Tl;dr - ¡esto sí que es una cosa muy chula!
@Colbi: Busca la complejidad de Kolmogorov y la constante y el teorema de incompletitud de Chaitin, que son análogos teóricos de la información de la longitud mínima de prueba y los teoremas de incompletitud de Godel. En cierto sentido, son más fáciles de entender y, por tanto, es más fácil captar la estructura intrínseca que "permite conjeturas matemáticas engañosamente simples". Para un ejemplo geométrico, codificando las máquinas de Turing en baldosas cuadradas con protuberancias, se puede construir un conjunto finito de baldosas tal que si pueden embaldosar algún rectángulo es equivalente a si ZFC es inconsistente. [continuación]
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
5 votos
Estoy muy en desacuerdo con los votos a favor del cierre.
1 votos
¿No es esto un resultado de la estadística? Si hay un gran número de posibles problemas sencillos en matemáticas, algunos estarán en la cola de la distribución de la complejidad. A esto hay que añadir el sesgo de observación: estos problemas reciben mucha más atención que otros problemas sencillos que no son complejos.