¿Cuando son dos pruebas "lo mismo"?

Question

A menudo, nos encontramos con diferentes pruebas para algunos teoremas que, superficialmente, parecen ser muy diferentes, pero usen las mismas ideas fundamentales. Por ejemplo, la prueba topológica de la infinitud de números primos es muy diferente que el estándar, pero los argumentos son esencialmente los mismos, utilizando diferente vocabulario.

Por lo tanto, mi pregunta es la siguiente:

¿Existe una noción rigurosa de "isomorfismo prueba"?

Answer 1

La pregunta de la prueba de equivalencia es un viejo! De hecho, David Hilbert considerado la adición de la misma (o similar) a su célebre lista de problemas abiertos, pero finalmente decidió dejarlo fuera, por lo que se refiere a veces como Hilbert del 24 de problema.

Hay un lugar bien establecido el campo de la investigación de la prueba de equivalencia, aunque definitivamente no existe una respuesta clara a su o de Hilbert pregunta (y es probable que esto está completamente fuera de su alcance). Sin embargo, aquí están algunas de las diversas nociones de la prueba de equivalencia de aumentar la fuerza.

1. La igualdad w.r.t. variable re-nomenclatura (también llamado $\alpha$-cambio de nombre). Esto es demasiado fina: es evidente que hay pruebas de que son "moralmente" de la misma, pero que difieren por más de variable re-namings.

2. La igualdad w.r.t. definición de despliegue. Esto no resuelve todos los problemas anteriormente citados, pero es claro que si una prueba implica un compacto definición y el otro no, que debe ser visto de la misma.

3. La igualdad w.r.t. corte de eliminación. Este es mucho más interesante! Para las dos pruebas $\Delta$, $\Phi$, decimos que $\Delta\simeq_{\mathrm{cortar}}\Phi$ si las dos pruebas son las mismas (modulo variable re-nomenclatura) después de haber eliminado a todos los cortes. Ahora un montón de diferentes pruebas de llegar a ser bastante similares, por ejemplo, las pruebas de cálculo que implican abstracto "abierto/cerrado" terminología puede ser reducido a simples pruebas que involucren $\epsilon$-$\delta$ notación. Esto todavía no es satisfactorio, pues por ejemplo, algunas hipótesis que pueden ser utilizados en diferentes órdenes, o algún inútil pasos a seguir siendo. También no está claro que esto no es demasiado gruesa, ya que a veces el uso de crucial lemas hace una prueba mucho más simple, y la corte de eliminación hace que todos los intermedios de los lemas de "desaparecer".

4. La igualdad w.r.t. corte de eliminación con el conmutativa cortes. Véase, por ejemplo, estas muy agradable diapositivas por Clemente Houtmann. Esto podría acercarse a la "derecha" noción, aunque como se puede ver las cosas empiezan a ponerse un poco subjetivo en este punto. ¿Qué significa "usar la misma idea"?

Como Bruno se mencionó, existe una profunda conexión entre las pruebas de las proposiciones y ciertos programas, en particular, lenguajes de programación, de manera que uno puede volver a formular la pregunta como

Cuando son dos programas de la misma?

con muy buenos resultados. La conclusión debe ser que ésta es un área de investigación muy activa en la prueba de la teoría, con conexiones a la computadora de la ciencia y de la lógica categórica.

Answer 2

Esta prueba de la irrelevancia es uno de los problemas clásicos de las fundaciones.

En el Tipo de Teoría, sin embargo, que representan los enunciados matemáticos como los tipos, lo que nos permite tratar a las pruebas como objetos matemáticos. Esto es debido a un conocido isomorfismo entre los tipos y las proposiciones de una.k.una. Curry-Howard Correspondencia, que a grandes rasgos dice que para encontrar una prueba de una declaración de Un es encontrar a un habitante de este tipo: $$:$$ Que, en el punto de vista de la lógica, se puede leer 'una es una prueba de la proposición de Una'.

En este sentido, para demostrar una proposición para la construcción de un habitante de un tipo, lo que significa que cada prueba matemática puede ser visto como un algoritmo. Esto está relacionado con "constructivo" (intuitionistic) la concepción de la lógica que (i) para demostrar que un enunciado de la forma "a y B" es para encontrar una prueba de Una y de una prueba de B, (i) demostrar que implica que B es encontrar una función que convierte una prueba de Una en una prueba de B (iii) cada demostrar que existe algo que se lleva con suficiente información para exponer el objeto y así sucesivamente. Por lo tanto la igualdad de los elementos de un tipo (pruebas) se trata intensionally.

Ahora Homotopy Tipo de Teoría que piensa de tipos como "homotopical espacios", interpretación, como se indica en los comentarios, la relación de identidad $a=b$ entre los elementos (pruebas) del mismo tipo (proposición) $a,b:$ como homotopical equivalencia, entendida como un camino desde el punto $$ en el punto $b$ en el espacio de $A$. La HoTT libro está disponible de forma gratuita en la página web del proyecto.