¿Podemos decidir que una conjetura es decidible sin saber si es correcta o falsa?

Question

¿Podemos decidir que una conjetura es decidible sin saber si es correcta o falsa?

Hice esta pregunta porque asumo que el problema del premio del milenio ya es decidible, de lo contrario el matemático necesitaría considerar infinidad de casos para conseguir el dinero o la lógica de la pregunta la convierte en una pregunta falsa.

Answer 1

Tenemos que ser muy claros y precisos, así que permítanme inundarles con un montón de definiciones.

Si hablamos de "decidible" e "indecidible", hablamos de sistemas formales.

En un sistema formal, tenemos nociones primitivas (términos indefinidos y relaciones/funciones entre ellos), axiomas, reglas de inferencia y "reglas gramaticales" que nos indican cuándo una secuencia de símbolos es una fórmula bien formada.

Una fórmula bien formada $F$ es demostrable en el sistema formal si existe una secuencia finita de fórmulas bien formadas tal que cada término de la secuencia es un axioma, o una consecuencia de fórmulas previas en la secuencia que se sigue de las reglas válidas de inferencia, y tal que el último término de la secuencia es $F$ .

Decimos que una fórmula bien formada $F$ es decidible en el sistema formal si y sólo si $F$ es demostrable, o su negación $\neg F$ es demostrable. Es indecidible de lo contrario.

A modelo de un sistema formal es una interpretación específica de los términos primitivos que hace que los axiomas sean verdaderos.

Un sistema formal es coherente si y sólo si tiene al menos un modelo.

Es un teorema de la lógica de primer orden que una fórmula bien formada $F$ es demostrable en un sistema axiomático si y sólo si $F$ es cierto en cada modelo del sistema. En particular, $F$ es indecidible si y sólo si existen modelos del sistema en los que $F$ es cierto, y existen modelos del sistema en los que $F$ es falso.

Ahora, note que mientras "decidible" e "indecidible" y formal se refieren a si una fórmula concreta puede deducirse formalmente del sistema axiomático. Por el contrario, "verdadero" y "falso" son semántica nociones: dependen de la Significado (el modelo) de los términos, y no sólo en sus propiedades formales (que vienen dadas por los axiomas y las reglas de inferencia).

En cierto sentido, demostrar que una fórmula es indecidible significa demostrando que es ni verdadera ni falsa... sino que su verdad o falsedad dependerá de la interpretación que demos a los términos. Un ejemplo clásico es la Hipótesis del Continuo: no existe un subconjunto infinito de $\mathbb{R}$ que no es biyectable con $\mathbb{N}$ o con $\mathbb{R}$ . Resulta que esto no es ni verdadero ni falso, es indecidible (suponiendo que la propia Teoría de Conjuntos tenga modelos): hay modelos de teoría de conjuntos en los que es verdadero, y hay modelos en los que es falso. Tienes una teoría en la que puedes asumirlo como axioma, y otra teoría en la que asumes su negación como axioma (de hecho, infinitas teorías, una para cada uno de los diferentes tipos de conjuntos que pueda haber).

En cierto sentido, si ya conocía si la conjetura es "verdadera o falsa" (es decir, verdadera en todos los modelos o falsa en todos los modelos), entonces ya la has demostrado, ya no es una conjetura y no puede ser indecidible. O si no, podrías estar hablando de "verdadera en el modelo estándar " (algunas teorías tienen una forma "estándar" de interpretar los términos, como la Aritmética de Peano), o "falso en la modelo estándar ". En ese caso, saber esto sólo te dice que el enunciado es demostrable o formalmente indecidible. (Por ejemplo, Goedel demostró que existe un modelo de Teoría de Conjuntos en el que el axioma de elección es verdadero; eso demostraba que era imposible refutar el Axioma de Elección, pero no estableció si el Axioma de Elección era demostrable o si era indecidible; Paul Cohen demostró más tarde que hay un modelo en el que el Axioma de Elección es falso, y eso demostró que el Axioma de elección no era demostrable, y por tanto debe ser formalmente indecidible).

Para los Problemas del Milenio, se sabe que algunos problemas son decidibles; otros pueden ser indecidibles. En algunos casos, la indecidibilidad establecería la verdad en el modelo estándar . Para ver un ejemplo de esta última situación, piense en la conjetura de Goldbach:

Conjetura de Goldbach. Cada entero par mayor que $2$ se puede escribir como una suma de dos primos.

Supongamos que podemos demostrar que la Conjetura de Goldbach es indecidible en Aritmética Peano. Esto demostraría que es verdadero en el modelo estándar . ¿Por qué? Porque si existiera un contraejemplo a la Conjetura de Goldbach, éste podría establecerse en tiempo finito simplemente repasando todos los números pares y comprobando todas las sumas de primos menores que ellos; esto significaría que su falsedad en el modelo estándar sería demostrable, por lo que la CG no puede ser a la vez indecidible y falsa en el modelo estándar. Por supuesto, hay otras formas de interpretar el significado de "número" ("modelos no estándar") en las que la CG sería falsa, pero en el modelo estándar modelo sería cierto.

La hipótesis de Riemann es una de ellas: si la Hipótesis de Riemann fuera falsa, entonces esto podría establecerse exhibiendo un cero y verificando que es un cero (lo que puede hacerse en tiempo finito). Así que si la Hipótesis de Riemann es formalmente indecidible, entonces debe ser cierto en el modelo estándar.

No tengo ni idea de a qué viene lo del "número infinito de casos"...

Answer 2

Hay muchas familias de problemas en las que podemos demostrar de una vez por todas que cada problema de la familia es en principio decidible (digamos, en aritmética Peano), pero donde también es fácil producir instancias donde el actual la respuesta es completamente desconocida y no se conoce ninguna manera factible de producir una respuesta.

Un ejemplo serían los problemas de forma:

En (inserte aquí un número grande) tienen un factor entre (inserte aquí un número grande) y (inserte aquí un número grande) .

Es fácil generar un caso concreto no resuelto de esto por ordenador: basta con programarlo para que genere un par de claves RSA aleatorias, olvidando la parte privada, y seleccione un intervalo aleatorio pero plausible en el que quepa el factor.

Un ejemplo diferente:

¿Existe una prueba de P=NP que pueda codificarse como un script de prueba para un sistema de comprobación de pruebas? $X$ que tenga como máximo 2 gigabytes de longitud?

De nuevo es fácil demostrar que o bien PA demuestra "sí, existe tal prueba" o bien PA demuestra "no, no existe tal prueba".

Answer 3

He aquí un ejemplo genuino de la literatura matemática. Hay muchos otros ejemplos de este tipo.

¿Es cada entero impar mayor que $5$ representable como una suma de $3$ ¿Primas?

Vinogradov demostró que todo número entero impar suficientemente grande es representable de este modo. Ahora se sabe que, de hecho, todo número entero impar mayor que $10^{43000}$ es representable. Así que la pregunta original ha resultado ser decidible. Sólo que no sabemos cuál es la respuesta.

Answer 4

Hay algunas áreas relativamente restringidas de las matemáticas que se sabe que son decidibles, como la aritmética de Presburger. Pero la mayoría de las conjeturas no son decidibles. Que yo sepa, ninguna de las cuestiones del Premio del Milenio (salvo la conjetura de Poincaré, que ya se ha demostrado) es decidible. Esto no las convierte en "falsas". En todo caso, aumenta el desafío: al intentar resolver la conjetura, se intenta hacer algo que puede o no ser posible.

Answer 5

---

He aquí otra perspectiva de una cuestión relacionada: un problema en el que podemos demostrar que existe una "respuesta" en algún sentido, pero también podemos demostrar que no podemos encontrar la respuesta.

A gráfico es un conjunto de vértices y un conjunto de aristas entre esos vértices; por ejemplo, los vértices pueden ser "actores de Hollywood", con una arista entre dos actores que hayan aparecido juntos en una película, o los vértices pueden ser "ciudades de EE.UU. con más de 100.000 habitantes", con una arista entre dos ciudades en un radio de 500 millas.

Un gráfico es un menor de otro si, esencialmente, puedes etiquetar algunos de los vértices del grafo mayor coincidiendo con los vértices del grafo menor y "dibujar aristas" entre ellos coincidiendo con las aristas del grafo menor - en esencia, es como un subgrafo (aunque obviamente hay algunos detalles técnicos menores).

Y por último, decimos que una colección de grafos es menor-cerrado si cada grafo que está en la colección trae también todos sus menores. Por ejemplo, el conjunto de plano (los que se pueden dibujar en el plano sin que ninguna de sus aristas se cruce) es menor-cerrado de esta manera; cualquier subgrafo, o cualquier contracción de un subgrafo, sigue siendo planar.

Ahora, el Teorema de Robinson-Seymour dice que cualquier conjunto menor-cerrado de grafos puede ser definido por un pequeño conjunto de grafos que no son en ella, los llamados "menores prohibidos"; cualquier grafo que tenga uno de estos menores prohibidos como menor no está en la colección, y todos los grafos que no tienen ninguno de los menores prohibidos están en la colección. Por ejemplo, para los grafos planos hay dos menores prohibidos: $K_5$ (un grafo con cinco vértices y aristas entre cada par de vértices) y $K_{3,3}$ (un gráfico con tres nodos "rojos" y tres nodos "azules", y todas las aristas posibles de un color al otro).

Así, sabemos que para cualquier colección de grafos que demos, hay algún conjunto de menores prohibidos que definen esos grafos; en este sentido tenemos una respuesta afirmativa al problema. Pero eso no significa que podamos encontrar el conjunto de menores prohibidos; de hecho, aunque se sabe que ese conjunto existe, también se sabe que no puede haber ningún procedimiento para encontrarlos; cualquier algoritmo para tomar (una descripción de) un conjunto de grafos y encontrar sus menores prohibidos también podría resolver el problema de detención.