¿Qué porción de las declaraciones matemáticas son ZFC indecidible?

Question

Desde el Teorema de la Incompletitud de Gödel llegamos a la conclusión de que para cualquier lógicamente conjunto coherente de un número finito de axiomas, hay un número infinito de los enunciados matemáticos que son verdad, pero no puede ser demostrada. Qué parte de los enunciados matemáticos son demostrablemente cierto o demostrablemente falso?

Creo que esto podría ser formalizado como sigue:

Deje $C(x)$ la complejidad de un enunciado matemático $x$, y deje $N(\epsilon)$ el número de los enunciados matemáticos $x$ tal que $C(x)\leq\epsilon$. La manera en que definimos $C(x)$ es arbitrario como el tiempo que tiene las siguientes propiedades:

• $0 \leq C(x)$ para todos los posibles de los enunciados matemáticos $x$
• $C(x)$ es finita para todas las posibles de los enunciados matemáticos $x$
• $N(\epsilon)$ es finito para todos finito de valores de $\epsilon$

Ahora vamos a $P(\epsilon)$ el número de los enunciados matemáticos $x$ tal que $C(x)\leq \epsilon$ $x$ es demostrablemente cierto o demostrablemente falsa en ZFC. Porque $P(\epsilon)\leq N(\epsilon)$, $P(\epsilon)$ es también finita para todas las finito de valores de $\epsilon$.

¿Qué es $$\lim_{x \to \infty} \frac{P(x)}{N(x)}$$

Para los efectos de esta pregunta, supongamos que ZFC es consistente, y que sólo estamos tratando con los enunciados matemáticos que pueden ser codificados en un número finito de bits de información. Basado en que podríamos definir $C(x)$ como el número de bits necesarios para codificar una matemática de la declaración de $x$.

Answer 1

Podemos definir una constante de Chaitin para la teoría, lo que representa un provability probabilidad más que el cese de la probabilidad.

El programa de instalación, primero darle un prefijo libre, codificación binaria. Binario significa que hay una cadena de bits que representa cada símbolo, por ejemplo, $\emptyset \rightarrow 0000, \in \rightarrow 0001, \forall \rightarrow 0010, \dots$ y de prefijo libre significa que no hay prefijo de una fórmula en sí misma es una fórmula, una forma de lograr esto es escribir todas las fórmulas en el prefijo de la orden, que es $\neg \exists x \text{:} \in x \emptyset$ en lugar de $\neg \exists x \text{:} x \in \emptyset$. Con un poco de cuidado, esto puede ser codificados de manera que la representación binaria de casi todos los real en $[0,1)$ tiene exactamente un prefijo de codificación válida de la fórmula. Definir a continuación:

$\Omega_{ZFC} = \sum_f{2^{-\vert f \vert}}$

donde la suma es sobre todos los comprobable fórmulas de $f$. Esto corresponde a la probabilidad de que, si leemos una fórmula a partir de una cadena de bits aleatorios, va a ser comprobable. Podemos definir una variante de $\Omega$ para decidable fórmulas sumando más de las fórmulas $f$ que $f$ o $\neg f$ es demostrable.

$\Omega_{ZFC} \lt 1$ es equivalente a $\text{Con}(ZFC)$, por lo que en ZFC no vamos a ser capaces de probar la mejor cota superior sobre su valor (aunque cada límite inferior es comprobable). Pero es posible encontrar límites superiores en la $\Omega$ de teorías que ZFC puede resultar coherente, tales como la Aritmética de Peano, que se define de manera similar. Como la constante de Chaitin, $\Omega_{PA}$ es a través de algoritmos aleatorios (aunque PA no puede demostrar esto) y así es $\Omega_{ZFC}$ si ZFC es consistente.

Si usted toma cualquier tipo de enfoque directo a la definición de una codificación como he comentado anteriormente, la probabilidad de que un azar fórmula es decidable va a estar muy cerca de $1$. Eso es porque el menor fórmulas que tienen la oportunidad de ser indecidible son algo más que la más corta de las fórmulas que puede ser expresado, y el peso de cada fórmula es exponencial en su longitud. Muy corto fórmulas son las más probables y todos se decidable. Que puede ser cambiado mediante la extensión de la teoría a tener indecidible fórmulas con códigos cortos (por ejemplo, si nos dio una nueva relación de símbolos y axiomatized como un provability predicado).

Answer 2

Siento que esta pregunta puede ser un duplicado, porque yo estoy bastante seguro de que vi por primera vez el papel que menciono a continuación en una respuesta aquí. Usted puede estar interesado en la lectura de los siguientes:

MR2141502 (2006c:68092) Revisado. Calude, Cristian S.(NZ-AUCK-C); Jürgensen, Helmut(3-GANÓ-C). Es la complejidad de una fuente de incompletitud? (Resumen en inglés), Adv. en Appl. De matemáticas. 35 (2005), no. 1, 1-15.

El papel es una buena lectura, no demasiado largo o demasiado técnico. Se utiliza la noción de Chaitin complejidad que la otra respuesta se describe así. Permítanme citar el resumen:

En este trabajo se demuestra que Chaitin la "heurística principio," los teoremas de una finitely-especifica la teoría no puede ser mucho más compleja que la teoría en sí misma, una medida adecuada de la complejidad. Nos muestran que la medida es invariante bajo el cambio de la numeración de Gödel. Para esta medida, los teoremas de una finitely especificado, sonido, consistente teoría lo suficientemente fuerte como para formalizar la aritmética que es aritméticamente sonido (como la de Zermelo–Fraenkel conjunto de la teoría con la elección o la Aritmética de Peano) han delimitado complejidad, por lo tanto cada frase de la teoría de que es mucho más compleja que la teoría es improbable. Los resultados anteriores muestran que la incompletitud no es accidental, pero omnipresente están aquí reforzado en términos probabilísticos: la probabilidad de que un enunciado verdadero de la longitud de la $n$ es demostrable en la teoría tiende a cero cuando $n$ tiende a infinito, mientras que la probabilidad de que una sentencia de la longitud de la $n$ es cierto es estrictamente positivo.