Godel, Turing Rosser et al demostró que existen.
¿Son más como los primos, infinitos en número, pero consiguiendo más raro y más raro como que avanza? (Considerar las proposiciones más grandes y más grandes?)
¿O son más bien los compuestos, se hace cada vez más dominante?
¿O no sabemos?
¿Hace una diferencia si utilizamos ZF en vez de PA?
Referencias sería mucho apreció.
Respuestas
¿Demasiados anuncios?
Existe una analogía entre indecidible propuestas y programas de ordenador que no se detenga. La densidad de detener los programas que se llama constante de Chaitin (ver http://en.wikipedia.org/wiki/Halting_probability ), y es un trascendental número; en particular, no es ni 0 ni 1, por lo tanto de la suspensión y la no paralización de los programas positiva a las proporciones del conjunto de programas. No podría decir si los resultados pueden ser transferidos directamente a las proposiciones en PA, pero vale la pena un vistazo.
prubini87
Puntos
98
Sólo estoy dando los toques finales a un papel en el que me demuestre que hay al menos tantos Goedelian 'indecidible' aritmética de las proposiciones, ya que hay recursiva relaciones!
http://alixcomsi.com/32_Undecidable_Arithmetical_Propositions_Update
El documento ofrece un finitary vista de Goedel y Rosser " indecidible propuestas desde una perspectiva computacional; donde puedo argumentar en contra de la idea ampliamente aceptada de conclusión de la auto-referencial de la causalidad que Kurt Goedel ha de extraerse de su seminal de 1931 papel en formalmente indecidible aritmética de las proposiciones.
Esta es la conclusión a la que Goedel "indecidible' aritmética de la proposición---que es de la forma [(Ax)R(x)]---es indecidible, porque implica la auto-referencia; en el sentido de que, en virtud de cualquier modelo de la aritmética, la proposición puede ser llevado a afirmar que "La aritmética de la fórmula con número de Goedel GN[(Ax)R(x)] no es demostrable en la aritmética', donde GN[F] indica el número de Goedel de la aritmética fórmula [F].
Sugiero que, en cierta medida, de la percepción de la auto-referencia (y tal vez incluso diagonalisation) como el---y hasta necesario---causa de la aritmética 'undecidability" puede ser engañoso.
Por ejemplo, en el Goedelian caso anterior, [R(x)] es el estándar de la aritmética representación de una norma (aunque excepcionalmente se define en un aparentemente circular manera) primitiva recursiva relación y me muestran que, si asumimos la interpretación estándar de PA como de sonido (en el sentido de la definición de un modelo de PA), entonces Goedel la aritmética representación de cualquier relación recursiva de los rendimientos de un similarmente, "indecidible' PA fórmula.
Me muestran, además, que este Goedelian característica es meramente un reflejo del hecho de que, por el instantiational la naturaleza de su definición constructiva en términos de Goedel Beta de la función, tales fórmulas están diseñadas para ser verificable a través de algoritmos, pero no a través de algoritmos computable, en virtud de la interpretación estándar de la PA.
Desde esta perspectiva, la importancia de Goedel de 1931 la construcción de un "indecidible' la proposición es que permite la formalización de una distinción entre 'algorítmicamente verificable' aritmética fórmulas y 'algorítmicamente computable' fórmulas aritméticas.
Esta distinción nos lleva a dos claramente diferentes---y hasta entonces insospechada---finitary interpretaciones de primer orden Aritmética de Peano PA que había presentado en Birmingham el pasado mes de julio en el Simposio sobre Computacional de la Filosofía en el AISB/IACAP World Congress 2012-Alan Turing 2012.
http://events.cs.bham.ac.uk/turing12/proceedings/04.pdf
La primera es la interpretación estándar de la PA sobre los números naturales en la que el verdadero penas se definen como todos aquellos PA-fórmulas que a través de algoritmos verificable como verdadero. Esta interpretación admite la existencia de formalmente 'indecidible' Goedelian proposiciones, pero no ofrece una finitary interpretación de el Axioma Esquema de Inducción Finita (por lo que no puede ser llevado a definir un modelo de PA a partir de una finitary perspectiva).
El segundo es un algoritmo de interpretación sobre los números naturales, en la que el verdadero penas se define como sólo los PA-de las proposiciones que a través de algoritmos computable como verdadero. Prima facie, esta interpretación no admitir la existencia de formalmente 'indecidible' Goedelian proposiciones, pero sí ofrecen una finitary interpretación de el Axioma Esquema de Inducción Finita (por lo que puede ser tomado para definir un modelo de PA a partir de una finitary perspectiva).
