¿Es posible probar todo en las matemáticas por provers del teorema como Coq?

Question

Coq ha sido utilizado para proporcionar pruebas para el teorema de los Cuatro Colores, el Hecho de–Thompson teorema, y estoy seguro de que muchos más. Me preguntaba - ¿hay algo que no puede ser demostrado en el teorema de provers como Coq?

Un poco más la pregunta es si todo lo que puede ser demostrado, el futuro de las matemáticas consistente de una base de datos masiva de estas pruebas en que todo el mundo va a construir en la parte superior de? A mi ingenua mente, esto se siente como una mucho más rigurosa manera de expresar las matemáticas.

Answer 1

Uno de los resultados de la computabilidad es que no debe existir comprobable teoremas de teoría de números que requieren muy largo pruebas en relación a sus declaraciones.

Si $n$ es la codificación de una declaración en la teoría de números que puede ser probada, y $f(n)$ es la longitud de la menor prueba de que la instrucción, la función de $$G(n)=\max \{f(k): k\leq n, k \text{ encodes a provable theorem}\}$$ no sólo no es computable, pero no puede ser delimitada por parte de cualquier función computable, o de lo contrario podríamos escribir un programa que podría esencialmente "encontrar" todos decidable declaraciones - el conjunto de decidable teoremas sería recusrive, no sólo recursivamente enumerable. (Yo al principio tenía un argumento sobre por qué sería un problema, pero ese argumento era débil. Todavía estoy bastante seguro de que es malo para el decidables a ser recursivo, pero va a tener más trabajo.)

En particular, entonces, para cualquier total computable en función de $h$, no debe ser un teorema demostrable codificada por algunos $n$ tales que el menor prueba, cuando se codifica, es mayor que $h(n)$.

Así, en un sentido práctico, siempre va a ser más difícil teoremas, donde tenemos más capacidad de almacenamiento y el tiempo de cálculo para verificar la totalidad de la prueba.

Answer 2

Es razonable creer que todo lo que ha sido (o puede ser) formalmente demostrado puede bew demostrado en tales explícitamente una manera formal de que un "estúpido" a prueba de sistema de verificación pueden dar su visto bueno. De hecho, mientras típica diaria de las pruebas pueden tener algunos informal handwaving partes en ellos, estos siempre deben ser capaces de ser formalizada en un tan "obvio" de manera que no se molesta, en el hecho de que uno está totalmente convencido de que la formalización es en principio posible; de lo contrario uno no llamarlo una prueba. De hecho, a veces tengo la costumbre de guiar a las personas (por ejemplo, si mantienen la objeción de Cantor en diagonal del argumento) a la página correspondiente en la Prueba Explorer y pídale que señale que, paso a paso de objeto a.

Para algunos teoremas y pruebas de este enfoque puede ayudar a deshacerse de cualquier duda proyectando una sombra sobre la prueba: ¿no hay, posiblemente, algunos de los sub-sub-caso en la página 523 de que se quedó fuera? Pero, de nuevo: se Ha comprobado la validez del código de su teorema de verificador? Incluso es el error en el hardware libre? (Recuerde que el Pentium bug?) Se cree que una prueba de que $10000\cdot10000=100000000$ que consiste en poner a millones de guijarros en $10000$ filas y columnas, y contando con ellos más que informática el resultado de la misma por un tiempo de multiplicación?

Answer 3

Viniendo de una práctica ángulo (es decir, no hablar de los límites en la lógica de que sabemos por el teorema de la incompletitud, etc), su pregunta podría ser reformulado como "Podemos hacer todo de las matemáticas que hacemos en papel, en Coq?"

La respuesta es "no Sé, es difícil. Nos pondremos en contacto con usted." No eres la primera persona a pensar así, a pesar de, y hay esfuerzos para "poner las matemáticas en los equipos". Echa un vistazo Homotopy TT.

Para ampliar un poco: La razón principal es que una gran parte de las matemáticas se hace uso de la teoría de conjuntos como el trabajo de la fundación, pero la teoría de conjuntos no es susceptible de ser expresado con los ordenadores. Es demasiado declarativa. La lógica interna en el Coq (Cálculo de Co-inductivo Construcciones) se basa en Martin-Löf Tipo de Teoría, que es muy diferente de un hervidor de pescado. Así que algunas de las definiciones, aunque equivalentes, no son el mismo, y algunos de los de bajo nivel de cosas no se construye de la misma manera.

El ensanchamiento de la brecha entre el papel y la máquina de los mundos es que hay una preferencia por Constructivo de Matemáticas de la máquina en el mundo. (simplificando: una preferencia por el uso de la ley de medio excluido (o equivalente clásico de axiomas y reglas)) y intuitionistic lógica.

Anexo: Lo que hemos estado hablando anteriormente es cómo los fundamentos lógicos de la coq son diferentes de los fundamentos tradicionales. Dicho esto, Coq sigue haciendo matemáticas, que requiere la lógica de la fundación, que todavía está sujeto a las limitaciones de la lógica formal. Los teoremas de incompletitud etc.

P. S. - No hay sistema físico puede garantizado libre de errores a través de las matemáticas. Incluso si su hardware y software, se verifica, la radiación cósmica/favorito de la fuente de energía puede causar bits en su equipo para dar la vuelta y todo su verificación sale por la ventana. Incluso con la verificación, algunos programas se debe ejecutar en triplicado.

Answer 4

Es poco probable que Arquímedes pensaban en teoremas en teoría de la categoría. En el futuro probablemente habrá nuevas áreas de las matemáticas. Mientras que un prover del teorema puede tener codificación de los resultados en estas nuevas áreas no puede ser legibles para los seres humanos.