Pregunta derivada de la intervención de Voevodsky sobre la incoherencia

Question

Esta pregunta surge a raíz de la charla de Voevodsky mencionada en esta reciente pregunta de MO . En una de sus diapositivas, Voevodsky dice que

una fórmula general incluso con una f números naturales para los que se puede demostrar, utilizando un argumento similar al que se utiliza en la demostración de Goedel, que no existe ningún número n que se pueda demostrar que pertenece o no a este subconjunto.

Y en su comentario oral añade que existe una fórmula que define

un subconjunto sobre el que se puede demostrar que nada sobre este subconjunto, en absoluto.

Interpreto esto como la afirmación de que hay un conjunto definible aritméticamente definible aritméticamente $S$ para el que no existe ningún teorema de la aritmética de Peano de la forma $n\in S$ o $n\not\in S$ . Tal vez estoy malinterpretando, pero ¿puede alguien la definición de dicho conjunto?

Answer 1

Sea $S$ sea un conjunto aleatorio definible de Martin-Löf de primer orden, como el de Chaitin $\Omega$ . Si la Aritmética de Peano, o ZFC, o cualquier otra teoría con un conjunto computable de axiomas, demuestra infinitamente muchos hechos de la forma $n\in S$ o $n\not\in S$ se deduce que $S$ no es inmune o no es co-inmune y por lo tanto no es ML-aleatorio después de todo.

(El conjunto de teoremas de nuestra teoría de la forma $n\in S$ (o $n\not\in S$ ) es computablemente enumerable e infinito, por lo que tiene un subconjunto computable infinito. Ser inmune significa no tener un subconjunto infinito computable).

Por lo tanto, sólo se pueden demostrar un número finito de hechos de este tipo. Ahora usando una biyección efectiva entre $\mathbb N$ y $\mathbb N\times \mathbb N$ descomponer $S$ en infinitas "columnas", $S=S_0\oplus S_1\oplus\cdots$ . Entonces una de estas columnas tiene la propiedad requerida.

La teoría debería ser lo suficientemente sólida como para tratar eficazmente la descomposición de un conjunto definible en columnas y la asociación de valores de una columna con valores del conjunto original, pero esto es ciertamente factible en PA o ZFC.

Answer 2

(n=n)&(con(ZF))