Los teoremas que se ha comprobado mediante la prueba de la existencia de una prueba formal sin conocer la prueba formal

Question

Deje $L$ ser de primer orden lenguaje. Deje $T$ ser un conjunto de oraciones en $L$ $S$ una frase en $L$. Vamos a definir una meta a prueba a ser una prueba de que no existe una prueba formal de las $S$$T$.

Pregunta: ¿hay frases en el "conocido" de las matemáticas, cuya meta es la prueba de conocidos, pero cuya prueba formal no es conocido.

Observación: cuando se suman las constantes/defintions a nuestro idioma, y demostrar la frase en el nuevo idioma, sabemos que funciona porque hay un teorema que dice que bajo condiciones adecuadas, una prueba formal en el nuevo lenguaje implica la existencia de una prueba formal en nuestro idioma original. Por lo tanto, una situación en la que cuenta como un ejemplo de una meta a prueba sin conocer la prueba formal, pero que yo consideraría trivial.

Gracias

Answer 1

Parikh frases tienen una corta prueba de que es una prueba de que existe, pero la prueba real puede ser muy larga, por ejemplo, el número de símbolos podría ser mayor que el número de átomos en el universo. Para una discusión ver página 17 de Un Enfoque Universal Para la Auto-Referenctial Paradojas, Incompleto Y Puntos Fijos por Noson Yanofsky. Este papel es muy legible.

Parafraseando a este documento utiliza una diagonal argumento para construir una frase ${\mathcal{C}}_{n}$ que dice "yo no tengo una prueba de mí que es más corto de $n$."

A continuación se presenta una breve prueba de que no existe una prueba de esta frase.

Answer 2

Yo uso polaco notación. Considere la posibilidad de la fórmula CCa$_1$Ca$_2$...Ca$_1$$_0$$_9$$_4$$_6$bCa$_1$Ca$_1$$_0$$_9$$_4$$_6$Ca$_2$Ca$_3$...Ca$_1$$_0$$_9$$_4$$_5$b. Nos puede escribir a cabo un meta-prueba a través de algo como la siguiente:

La ley de conmutación CCpCqrCqCpr junto con la deducción metatheorem nos permite el intercambio de cualquier variable de una$_o$ en un bien formado fórmula de la forma de Ca$_1$Ca$_2$...Ca$_n$b:=Una con cualquier otra variable$_p$, y obtener un wff B a partir de la cual podemos derivar Una y a la inversa. En consecuencia, no existe una prueba formal de que CCa$_1$Ca$_2$...Ca$_1$$_0$$_9$$_4$$_6$bCa$_1$Ca$_1$$_0$$_9$$_4$$_6$Ca$_2$Ca$_3$...Ca$_1$$_0$$_9$$_4$$_5$b es un teorema de la clásica cálculo proposicional.

Sin embargo, en realidad la escritura de la prueba formal viene de otro costal, porque es casi seguramente demasiado largo para que nadie se molesta en escribir la prueba. E incluso si alguien escribe una prueba o un equipo escribe una prueba, la meta-teoría termina implicando incluso más wffs de este tipo son teoremas porque no hay ningún límite superior en el número de variables de aquí... no wffs que son teoremas existe que jamás podría conseguir por escrito con todos los recursos de nuestra galaxia entera.

Así que, sí, esas penas que existen en las matemáticas.