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

Aparte de su ejemplo específico, la idea de verdad por accidente se ha estudiado en el contexto de la de primer orden, que incluye el lenguaje de la teoría de grafos teoría de grafos, y en su disertación, Kurt Gödel demostró que los enunciados que resultan ser verdaderos en todos los modelos de una teoría de primer orden $T$ son exactamente las declaraciones que son demostrables en $T$ . Este es su famoso integridad teorema .

Así, cualquier afirmación expresable en la teoría de primer orden de grupos que resulte ser verdadera en todos los grupos será de los grupos, y cualquier afirmación expresable en el expresable en el enunciado de primer orden de los grafos que que resulte ser verdadera en todos los grafos será demostrable a partir de los axiomas de la teoría de grafos. axiomas de la teoría de grafos.

Su declaración, sin embargo, no parece ser expresable directamente en el lenguaje de la teoría de grafos, ya que también utiliza el concepto de cardinalidad y de subgrafos, por lo que el teorema de completitud no se aplica directamente a ella para el lenguaje de los grafos. Más bien, es un enunciado de la teoría de números de la teoría de números, y los modelos relevantes para este caso incluirían todos los modelos estándar y no estándar de la aritmética.

Así que la conclusión relevante sería que si la declaración no fuera demostrable en el primer orden Axiomas de Peano PA , entonces hay existe un modelo no estándar de aritmética que tiene un (pseudo)finito.

Pero la forma particular de la declaración significa que tiene complejidad $\Pi^0_1$ lo que significa que es universal cuantificando sobre los números naturales, y si cualquier afirmación es independiente de PA, entonces es verdadera, porque si es verdadera en cualquier modelo, entonces como el modelo estándar es un segmento inicial segmento inicial de todos los demás, se deduce que debe ser verdadera en el modelo estándar y, por tanto, verdadera. Este nivel de complejidad es el mismo que el de muchas de las enunciados independientes interesantes, incluyendo los enunciados de consistencia de los enunciados.

---

Por cierto, esta parece ser mi respuesta número 500 en mathoverflow. Ha sido muy divertido, ¡y seguro que he aprendido muchas matemáticas!

Answer 2

Esta es una pregunta muy interesante (aunque bastante vaga). La mayoría de las respuestas iban en la dirección de la lógica matemática, pero no estoy seguro de que ésta sea la única manera (o incluso la más apropiada) de pensar en ello. La noción de coincidencia es en sí misma muy complicada. (Véase https://en.wikipedia.org/wiki/Coincidence ). Una forma de plantearlo con rigor es utilizar el marco probabilístico/estadístico. De hecho, como mencionó Timothy, a veces es posible dar una heurística probabilística en apoyo de alguna afirmación matemática. Pero es un problema estadístico notorio tratar de determinar a posteriori si algunos eventos representan una coincidencia.

No estoy seguro de que (como supone la OP) si una afirmación es "verdadera por accidente" implique que nunca pueda demostrarse. Tampoco estoy seguro (como implica la mayoría de las respuestas) de que "nunca puede demostrarse" deba interpretarse como "no se deduce de los axiomas". También puede referirse a situaciones en las que el enunciado admite una prueba, pero la prueba también es "accidental" como el enunciado original, por lo que es poco probable que se encuentre en la forma sistemática en que se desarrollan las matemáticas.

En cierto sentido (como se menciona en la respuesta de quid), la noción de "verdadero por accidente" está relacionada con la psicología de las matemáticas. Está más relacionada con la forma en que percibimos las verdades matemáticas que con algunos hechos objetivos sobre ellas.

En cuanto a la conjetura de reconstrucción. Podemos preguntarnos si la conjetura es cierta para grafos con un máximo de un millón de vértices. En este caso, si es cierta es ciertamente demostrable. Así que las cuestiones lógicas desaparecen, pero el problema principal de la pregunta permanece. (Podemos sustituir las distinciones lógicas por distinciones de complejidad computacional. Pero todavía no estoy seguro de que esto cpature la esencia de la cuestión). Hay una forma más débil de la conjetura llamada la conjetura de reconstrucción de aristas (el mismo problema pero se eliminan las aristas en lugar de los vértices) donde se sabe mucho. Hay una prueba muy conceptual de que todo grafo con n vértices y más de nlogn aristas es reconstruible por aristas. Así que esto da cierto apoyo a la sensación de que tal vez la reconstrucción de vértices también puede ser tratada.

Por último, no conozco ningún argumento heurístico que diga que "tendría que haber una enorme coincidencia para que dos grafos no isomórficos tuvieran la misma 'baraja'", como sugiere el OP. (Se sabe que varios invariantes de los grafos deben tener el mismo valor en esos dos grafos.

Answer 3

Sí, esto es lo que constructivismo ¡es todo! En lógica intuicionista la ley del medio excluido no suele cumplirse, por lo que no siempre es posible derivar $A$ (es decir $A$ es verdadero) de $\lnot\lnot A$ (es decir $A$ no es falso).

El caso particular que está considerando es una forma de Principio de Markov que puede ser redactado como si no es el caso de que no exista un ejemplo, entonces sí existe un ejemplo . Simbólicamente, la regla es $$\lnot\forall x\lnot A(x) \to \exists x A(x),$$ donde $A(x)$ se requiere que sea decidible: $\forall x(A(x) \lor \lnot A(x))$ . En las matemáticas constructivas, la existencia es muy fuerte: no es aceptable limitarse a mostrar que debe haber un ejemplo, sino que hay que producir realmente un ejemplo de una forma u otra. El principio de Markov dice que mostrar que debe haber un ejemplo es suficiente para demostrar la existencia. Por lo tanto, este principio no es generalmente aceptado por la mayoría de las escuelas del constructivismo, excepto en casos limitados.

Answer 4

La primera vez que me encontré con este tipo de especulación fue en el capítulo 3 del libro de Richard Stanley Combinatoria Enumerativa donde el ejercicio 3(c) (o, en la segunda edición, el ejercicio 5(c)) sugiere que si $f(n)$ es el número de posets no isomórficos en $n$ elementos, entonces la afirmación de que infinitamente muchos $f(n)$ son palíndromos en base diez es independiente de los axiomas de ZF. Evidentemente, este ejercicio no pretende ser abordado con seriedad; en realidad es una expresión del sentimiento de que hay algunas afirmaciones que son verdaderas o falsas, pero que no podemos esperar demostrar de una manera u otra porque casi seguro que carecen de la "estructura" que normalmente buscamos al hacer matemáticas.

Si se quiere tratar de formalizar esta noción, un enfoque es mirar ciertas pruebas del teorema de incompletitud de Gödel. Por ejemplo, si se fija un sistema axiomático como ZF, entonces los teoremas del sistema son computables, pero el conjunto de verdades aritméticas no es computable, por lo que deben existir algunas verdades que no son demostrables simplemente porque (hablando informalmente) son "demasiado complicadas de calcular". Si se quiere enfatizar la idea de que los enunciados no demostrables son "complejos" o "no estructurados" en algún sentido, entonces se podría preferir Prueba de Chaitin del teorema de incompletitud que muestra que para cualquier sistema formal $S$ hay una constante $L$ de manera que la declaración " $K(s) > L$ " es indemostrable en $S$ para todas las cadenas $s$ (aquí $K$ denota la complejidad de Kolmogorov). La gran mayoría de estas afirmaciones son verdaderas "al azar" porque una cadena aleatoria tendrá una alta complejidad de Kolmogorov.

Sin embargo, es posible que no esté satisfecho con el enfoque anterior, porque su intuición sobre la conjetura de reconstrucción del grafo es no basado en la idea de que el declaración oficial de la conjetura es tan compleja o incalculable que no se puede demostrar. Al fin y al cabo, la conjetura puede enunciarse de forma muy sencilla. Es la aparente falta de estructura relevante en el conjunto de todos los gráficos que está causando problemas.

Podría ser útil especificar más cuidadosamente en qué tipo de afirmaciones "verdaderas por accidente" está pensando. Un enfoque sería construir una heurística modelo probabilístico que predice que ciertas cosas deberían ser ciertas sólo por "razones aleatorias". Por ejemplo, hay El modelo aleatorio de Cramér para los primos que puede utilizarse para dar "pruebas" heurísticas de varias conjeturas teóricas de los números; por ejemplo, se puede utilizar el modelo para predecir que sólo habrá un número finito de primos con tal o cual propiedad, porque la probabilidad de que un primo $p$ tiene la propiedad de disminuir rápidamente a cero a medida que $p\to\infty$ . Es fácil que surjan muchas conjeturas de este tipo que tienen un aire de "verdad por accidente". (En particular, creo que sería interesante si se pudiera idear un modelo probabilístico heurístico para la teoría de grafos, en el espíritu del modelo de Cramér, que pudiera "predecir" varias conjeturas conocidas de la teoría de grafos, incluida la conjetura de reconstrucción).

El problema con este enfoque es que no parece haber ninguna forma clara de declarar que alguna afirmación particular de interés (como la conjetura de reconstrucción del grafo) no lo hace tienen una buena prueba. En un pregunta relacionada con MO La conjetura de Goldbach se propone como ejemplo de algo que podría ser "verdadero por accidente", pero hay suficiente estructura relevante como para que tal afirmación sea muy controvertida. El espacio de todas las pruebas posibles es en sí mismo un objeto matemático muy complejo, así que ¿quién puede decir que la afirmación "La conjetura X de aspecto intratable tiene una prueba sencilla" no podría ser "cierta por accidente"? Tal vez exista una prueba muy sencilla, pero es una pequeña aguja enterrada en un pajar totalmente desestructurado, por lo que los humanos nunca seremos capaces de encontrarla.

En resumen, hay algunas formas en las que se podría intentar formalizar esta noción, pero desafortunadamente, no creo que ninguna de ellas conduzca a una dirección prometedora (aparte de mi sugerencia anterior de que sería interesante formular un modelo probabilístico heurístico para la teoría de grafos que pudiera "predecir" la verdad de ciertas conjeturas sin demostrarlas realmente).

---

EDITAR (agosto de 2022): Hace poco me enteré de la publicación de John Conway en 2013 Amer. Math. Monthly artículo, Sobre problemas aritméticos irresolubles que, entre otras cosas, da ejemplos de razonamiento probabilístico en apoyo de la afirmación de que alguna proposición es "inestable". Para darles el sabor, permítanme citar la posdata de Conway:

El siguiente argumento me ha convencido que el Collatz $3n + 1$ La conjetura es en sí misma muy probable que sea inestable, más que que ésta sólo tenga la ligera posibilidad mencionada anteriormente. Utiliza el hecho de que hay montañas" arbitrariamente altas en el gráfico del juego de Collatz. Para ver esto, observe que $2m − 1$ pasa en dos movimientos a $3m − 1$ de lo que se deduce que $2^k m − 1$ pasa en $2k$ se traslada a $3^k m − 1$ . Ahora, por el Teorema del Resto Chino podemos disponer que $3^k m − 1$ tiene la forma $2^l n$ que pasa por $l$ se traslada a $n$ . Hay una muy pequeña posibilidad de que $n$ resulta ser el mismo que el número $2^k m − 1$ con la que empezamos. Supongamos que el número inicial $2^k m − 1$ es aproximadamente un googol; entonces la pendiente descendente pendiente de la montaña contiene ciertamente un número entre uno y dos googoles, por lo que la probabilidad de que éste sea el mismo que el número inicial es de al menos un googol. (Esto se justifica por las observaciones para los $n$ mostrando que el primer iterado que se encuentra en el rango $[n, 2n)$ se distribuye aproximadamente de manera uniforme en este rango). En mi opinión, el hecho de que esta probabilidad, aunque muy pequeña, sea positiva, hace extremadamente improbable que se pueda demostrar que el juego de Collatz no tiene ciclos que contengan sólo números grandes. números grandes. Esto no debe confundirse con una sugerencia de que realmente hay ciclos que contengan números grandes. Al fin y al cabo, los sucesos cuya probabilidad es de una googolésima son claramente improbables.

Answer 5

Se trata de una opinión sobre esta cuestión de forma diferente a las demás respuestas, en la línea de los comentarios de Gjergji Zaimi y André Henriques.

Sin duda, en las matemáticas actuales hay algunas conjeturas o quizás incluso resultados que tienen una sensación "accidental", mientras que otros no tienen esta sensación.

Sin embargo, me parece que hasta cierto punto, y creo que de forma considerable, se trata de una impresión subjetiva, o tal vez subjetiva no sea realmente el término adecuado y debería decir más bien que esta impresión está informada por la estado actual de las matemáticas.

No tengo a mano ejemplos históricos realmente buenos y precisos, pero creo que es cierto que, por ejemplo, ciertos resultados sobre ecuaciones diofantinas (resultados de finitud de las soluciones, por ejemplo) hace mucho tiempo tenían un aspecto mucho más accidental. Pero ahora con el desarrollo de la Geometría Aritmética (por ejemplo, la conj. de Mordell) algunos de ellos se entienden mucho mejor y conceptualmente y ahora se sienten naturales o, al menos, ya no son accidentales.

Quizás algunos de los resultados y conjeturas que hoy parecer accidental será en algún momento del futuro consecuencia natural de teorías aún por desarrollar. De hecho, creo que es un patrón bastante común de progreso en las matemáticas que los desarrollos comienzan con resultados y preguntas concretas y aisladas, y luego siguen teorías que explican los "accidentes" y los "milagros".

La conjetura de Goldbach se mencionó y se menciona con frecuencia como algo accidental. Veamos algo no muy lejano.

Los números primos contienen infinitas progresiones aritméticas de 3 términos (van der Corput, 1930). ¿Accidente, sí o no? Tal vez se podía pensar así, cuando se demostró, pero hoy la situación es diferente y se conjetura ampliamente (resultados muy recientes de Sanders lo consiguen para conjuntos de una densidad apenas mayor) que cualquier conjunto de enteros positivos con la densidad de los primos tiene esta propiedad.

¿Quién sabe dónde estará la teoría de la adición de conjuntos (más generalmente la combinatoria aditiva/teoría de los números) dentro de algunas décadas o siglos? Tal vez, entonces la conjetura de Goldbach será un corolario de alguna teoría natural.

En resumen, creo que "verdadero por accidente" (en la forma informal en que lo entiendo, que no parece estar tan lejos de la intención de los preguntantes) es en gran medida una noción dependiente del tiempo; por lo tanto, me parece difícil imaginar que su espíritu pueda ser capturado en una teoría formal (independiente del tiempo).