¿Cómo formular el problema P v.s. NP como un enunciado formal dentro del lenguaje de la teoría de conjuntos?

Question

He leído mucho que algunos informáticos creen que P v.s. NP podría resultar independiente de ZFC. Lo que me desconcierta es cómo formular esto dentro del lenguaje de la teoría de conjuntos. No he podido encontrar tal formulación en ningún sitio, así que agradecería que me indicaran dónde puedo encontrarla.

Answer 1

De hecho, $\mathbf{P}=\mathbf{NP}$ es un aritmética declaración. Lo que los lógicos quieren decir con esto es que se puede expresar (o, más precisamente, se puede expresar un enunciado "bastante trivial" equivalente a él) utilizando sólo el lenguaje de aritmética de primer orden es decir, como un enunciado formal construido a partir de {átomos de la forma $s=t$ donde $s$ y $t$ son expresiones construidas a partir de variables (destinadas a abarcar los números naturales) y la constante $0$ utilizando las operaciones binarias $+$ y $\times$ } utilizando conectores booleanos y cuantificadores sobre los números naturales .

Por ejemplo, $$ \forall p\, \forall q\, ((p\times p = 2\times q\times q) \;\Rightarrow\; (q = 0)) $$ es un enunciado aritmético (que expresa, esencialmente, la irracionalidad de $\sqrt{2}$ ).

Así que ahora hay dos cuestiones distintas:

• ¿Por qué es $\mathbf{P}=\mathbf{NP}$ (fácilmente equivalente a) un enunciado aritmético?

• ¿Por qué todo enunciado aritmético es formalmente expresable en el lenguaje de la teoría de conjuntos?

En cuanto a la primera, el hecho clave es que los números naturales pueden utilizarse para codificar secuencias finitas de los números naturales (hay varias formas de hacerlo, por ejemplo, utilizando el teorema chino del resto), por lo que podemos codificar como enunciados aritméticos aquellos que hablan de (y cuantifican sobre) no sólo los números naturales, sino también las secuencias finitas de los mismos. Luego podemos usar esto para codificar el comportamiento de las máquinas de Turing (por ejemplo, codificar una máquina de Turing, o un estado parcial o una traza de ejecución parcial de una máquina de Turing, como secuencias finitas de números enteros), polinomios sobre los números enteros, etc.: esencialmente cualquier cosa que sea "finista", es decir, codificable usando datos finitos, puede traducirse usando números naturales si se usa una codificación suficiente.

Entonces podemos expresar la afirmación: "para cualquier máquina de Turing no determinista $T$ y cualquier polinomio $f$ tal que: {para cualquier entrada finita $x$ o bien (a) existe una traza de ejecución válida de $T$ a partir de $x$ con la duración del tiempo que $f(|x|)$ (donde $|x|$ es la longitud de $x$ ) que termina en el valor del resultado  $1$ o bien (b) todos los rastros de ejecución de $T$ a partir de $x$ tienen una longitud de tiempo que $f(|x|)$ y terminan en el valor del resultado  $0$ }, existe una máquina de Turing determinista $T'$ y un polinomio $f'$ tal que: {para cualquier entrada finita $x$ el rastro de ejecución de $T$ a partir de $x$ tiene una duración inferior a $f'(|x|)$ y termina en el valor del resultado $1$ en el caso (a) y $0$ en el caso (b)}". Todo lo que hay ahí es finista, por lo tanto aritmético.

(Por supuesto, podemos simplificar la afirmación anterior una vez que sepamos que existe un $\mathbf{NP}$ -problema completo. Pero eso nos llevaría a preguntarnos por qué esta pregunta es, en sí misma, aritmética).

En cuanto a la pregunta de por qué todo enunciado aritmético es expresable en el lenguaje de la teoría de conjuntos, lo que ocurre es que el set $\omega$ de los números naturales (que se identifica con el ordinal infinito más pequeño en la visión ortodoxa de las matemáticas) puede definirse dentro de $\mathsf{ZFC}$ y también la suma y la multiplicación sobre los números enteros. Así que cualquier enunciado aritmético puede reescribirse como un enunciado sobre esos establece definible dentro de $\mathsf{ZFC}$ . De nuevo, es una cuestión de codificación.

Por supuesto, estoy complicando las cosas por la vía "aritmética": se pueden codificar las máquinas de Turing (y sus huellas de ejecución, etc.) y los polinomios y todo lo demás, dentro de la teoría de conjuntos. De hecho, la ortodoxia de las matemáticas es que (salvo cosas exóticas de la propia teoría de conjuntos) todo objeto matemático puede ser "codificado" como un conjunto, y por lo tanto, cualquier enunciado formalizable hecho por los matemáticos, puede traducirse en un enunciado de la teoría de conjuntos (o, para los ultraortodoxos, que "es" un enunciado de la teoría de conjuntos en primer lugar, y que todas las matemáticas se hacen dentro de $\mathsf{ZFC}$ ).

Hay que verlo como una cuestión de codificación: al igual que todo lo que maneja un ordenador está "codificado" como una cadena binaria finita, todo lo que maneja un matemático está "codificado" como un conjunto. Algunos (pero no todas) de estas cosas pueden, además, ser "codificadas" como un número natural, porque son de naturaleza finista. Así, muchos enunciados matemáticos son aritméticos, pero todos son teóricos de conjuntos. (Un ejemplo de enunciado que es teórico del conjunto pero no aritmético es la hipótesis del continuo: es pas equivalente a cualquier enunciado aritmético).

Ahora la decidibilidad es algo diferente. Existe un sistema formal para tratar los enunciados aritméticos, a saber $\mathsf{PA}$ (:= aritmética de Peano de primer orden), al igual que existe uno para tratar los enunciados de la teoría de conjuntos, a saber $\mathsf{ZFC}$ . Esta última es más fuerte que la primera, en dos aspectos: primero, puede hablar de más cosas, porque no todos los enunciados de la teoría de conjuntos son aritméticos; segundo, incluso entre los enunciados aritméticos, hay algunos que $\mathsf{ZFC}$ puede probar y que $\mathsf{PA}$ no puede (el ejemplo más sencillo es " $\mathsf{PA}$ no demuestra $0=1$ ", una afirmación que es aritmética porque dice esencialmente que una máquina de Turing que busca una prueba de $0=1$ en $\mathsf{PA}$ nunca termina, y no se puede probar en $\mathsf{PA}$ mientras que es demostrable en $\mathsf{ZFC}$ ).

Pero en la vida real (es decir, fuera de la lógica matemática), los enunciados aritméticos demostrables en $\mathsf{ZFC}$ pero no en $\mathsf{PA}$ sont raro (un ejemplo es Teorema del árbol de Kruskal En la actualidad se discute si, por ejemplo, el último teorema de Fermat es demostrable en $\mathsf{PA}$ pero no creo que nadie lo dude seriamente, aunque a primera vista La prueba de Wiles utiliza técnicas que van más allá $\mathsf{PA}$ ).

Y los enunciados aritméticos (a diferencia de los enunciados generales de la teoría de conjuntos) que son indemostrables en $\mathsf{ZFC}$ pero que aún se sabe/se cree que son verdaderas porque se desprenden de sistemas más fuertes como la adición de grandes cardenales, son bastante inauditas (quiero decir que no hay duda de que existen: " $\mathsf{ZFC}$ no demuestra $0=1$ " es un aritmética declaración que $\mathsf{ZFC}$ no demuestra y que todavía se sabe/se cree que es verdadera porque se deduce de la existencia de cardenales inaccesibles; pero a menudo se piensa que tales afirmaciones simplemente no se producen en el trabajo matemático ordinario a menos que se busque activamente).

Así que es lógicamente concebible que ni (el enunciado aritmético) $\mathbf{P}=\mathbf{NP}$ ni su negación se desprenden de $\mathsf{ZFC}$ pero no creo que nadie se lo crea en serio. (Incluso si sucede, podría ser porque $\mathbf{P}=\mathbf{NP}$ es verdadera, existe un algoritmo que resuelve un $\mathbf{NP}$ -problema completo pero $\mathsf{ZFC}$ no puede probarlo; o podría ser porque $\mathbf{P}\neq\mathbf{NP}$ es verdadera y $\mathsf{ZFC}$ no puede demostrarlo).