Cierto por accidente (y por lo tanto no se puede probar)

Question

El gráfico conjetura de reconstrucción afirma que (salvo ejemplos triviales) un grafo de n vértices está determinado (hasta el isomorfismo) por su colección de subgrafos inducidos de (n-1) vértices (también hasta el isomorfismo).

La forma en que está redactado ("reconstrucción") sugiere que una prueba de la conjetura sería un procedimiento, de hecho un algoritmo, que toma la colección de subgráficos y luego "construye" ingeniosamente el gráfico original a partir de ellos.

Pero basándome en alguna experiencia con una conjetura relacionada (la conjetura de reconstrucción de vértices), me lleva a preguntarme si esto es algo que simplemente es cierto "por accidente". Con esto quiero decir que es algo que simplemente es abrumadoramente improbable que sea falso ... tendría que haber una enorme coincidencia para que dos grafos no isomórficos tuvieran la misma "baraja" (como se suele llamar a la colección de subgrafos inducidos por (n-1)-vértices). En otras palabras, la única razón para que la afirmación sea verdadera es que "casualmente" no sea falsa.

Por supuesto, esto significa que nunca podría probarse realmente ¡y por lo tanto sería una muy mala elección de problema para trabajar!

Mi pregunta (por fin) es si alguien ha formalizado este concepto -resultados que no se pueden demostrar o refutar, no porque sean formalmente indecidibles, sino simplemente porque son "verdaderos por accidente"- o al menos lo ha discutido con más sofisticación de la que yo puedo reunir.

EDIT: Disculpas por el retraso en la respuesta y gracias a todos los que han contribuido de forma reflexiva a la pregunta más bien vaga. He aceptado la respuesta de Gil Kalai porque es quien mejor ha adivinado mi intención al formular la pregunta.

Probablemente no debería haber utilizado las palabras "formalmente indemostrable", sobre todo porque no tengo un conocimiento profundo de la lógica formal y, aunque algunas de las respuestas de "fundamentos lógicos" contenían ideas interesantes, no era eso a lo que realmente quería llegar.

A lo que realmente quería llegar es a que algunas afirmaciones / conjeturas parecen a mí para hacer una afirmación muy poco obvia sobre los objetos combinatorios, cuya verdad depende de algún conocimiento estructural fundamental del que carecemos actualmente. Otras afirmaciones / conjeturas parecen, de nuevo, a mí para estar diciendo algo que simplemente esperaríamos que fuera cierto "por casualidad" y que realmente nos asombraríamos si fuera falso.

Aquí hay unas cuantas afirmaciones no demostradas, todas las cuales creo que son verdaderas: algunas de ellas creo que deben reflejar la estructura y otras simplemente parecen ser "por casualidad" (que es lo que responderé más tarde, si alguien sigue interesado en este tema).

(1) Todo plano proyectivo tiene un orden de potencia primo

(2) Todo plano proyectivo no-desarguesiano contiene un subplano de Fano

(3) La conjetura de reconstrucción de gráficos

(4) Todo grafo cúbico de vértice transitivo tiene un ciclo de Hamilton (excepto Petersen, Coxeter y dos grafos relacionados)

(5) Todo grafo de 4 regularidades con un ciclo de Hamilton tiene un segundo

Ciertamente hay una posibilidad significativa de que me equivoque, y que algo que aparece accidentalmente se revelará como un teorema estructural profundo cuando se vea exactamente de la manera correcta. Sin embargo, tengo que elegir en qué trabajar (como hacemos todos) y una de las cosas que utilizo para decidir qué NO para trabajar es si creo que la declaración dice algo real o accidental.

Otro aspecto de la respuesta de Gil que me gustó fue la idea de considerar una "versión finita" de cada afirmación: supongamos que S(n) es la afirmación de que "todos los planos proyectivos no-desarguesianos de orden a lo sumo n tienen un subplano de Fano". Supongamos entonces que todos los S(n) son verdaderos, y que para cualquier n particular, podemos encontrar una prueba - en el peor de los casos, "simplemente" enumerar todos los planos proyectivos de orden n y comprobar cada uno de ellos para un subplano de Fano. Pero supongamos que la longitud de la prueba más corta posible de S(n) tiende a infinito a medida que n tiende a infinito - esencialmente no hay OTRA prueba que comprobar todos los ejemplos. Entonces nunca podríamos hacer una prueba de longitud finita que cubriera todo n. Esto es más o menos lo que querría decir con "verdadero por accidente".

Se agradecen más comentarios y gracias por dejarme divagar.

Answer 1

El enunciado en cuestión puede formalizarse en el lenguaje de la Aritmética de Peano, y lo trataré como un enunciado en ese lenguaje. Un análisis similar funciona para cualquier teoría efectiva más fuerte que PA, como ZFC.

Considere el conjunto de todas las oraciones en el lenguaje de PA; defina una relación de orden $R$ para que $\phi \mathbin{R} \psi$ si $\phi \to \psi$ es demostrable en PA. Esto da un preorden; si realizamos la construcción habitual de clases de equivalencia, el álgebra resultante es un orden parcial llamado álgebra de Lindenbaum (*).

Porque la conjetura de reconstrucción del grafo corresponde a una frase $G$ en PA, corresponde a un nodo particular en esta álgebra.

• Si $G$ es demostrable en PA, entonces $G$ corresponde al elemento inferior del álgebra
• Si $G$ es falso, corresponde al nodo superior del álgebra, pero en este caso no nos preocupa mucho su demostrabilidad
• Por lo demás, $G$ corresponde a algún nodo intermedio del álgebra. En ese caso, no podemos demostrar $G$ de PA, pero podemos probar $G$ asumiendo PA más cualquier axioma ya sea en la clase de equivalencia de oraciones que forma $G$ o en la clase de equivalencia de cualquier nodo superior a $G$ El nodo de la empresa.

En todos los casos, a menos que $G$ es falso, $G$ es susceptible de ser demostrada, pero la prueba tendrá que asumir axiomas lo suficientemente fuertes como para demostrar la conclusión deseada. No hay ninguna frase que "nunca pueda demostrarse", aunque hay muchas frases que no pueden demostrarse en AP, y las frases falsas sólo pueden demostrarse a partir de axiomas falsos. La cuestión es simplemente qué axiomas son necesarios para demostrar una sentencia concreta.

---

*: Tradicionalmente, un "álgebra de Lindenbaum" o "álgebra de Lindenbaum-Tarski" debería definirse con el ordenamiento dual del que yo uso. Pero el ordenamiento en el que $0=1$ corresponde a la parte superior del álgebra coincide mejor con los diagramas que creamos para ilustrar las relaciones entre los diferentes sistemas de axiomas, como 1 . La gente también utiliza el ordenamiento inverso en el contexto de la teoría de conjuntos, donde los axiomas cardinales grandes se ordenan por fuerza de consistencia, por ejemplo 2 .