¿Cuál es un ejemplo sencillo de una afirmación indemostrable?

Question

La mayoría de los sistemas que interesan a los matemáticos son consistentes, lo que significa, por los teoremas de incompletitud de Gödel, que debe haber enunciados indemostrables.

He visto una simple declaración en lenguaje natural aquí y en otros lugares que se supone que ilustra esto: "No soy un enunciado demostrable", que conduce a una paradoja si es falso y a una desconexión lógica si es verdadero (es decir, la lógica no funciona para demostrarlo por definición). Como explica esta respuesta: https://math.stackexchange.com/a/453764/197692 .

La declaración en lenguaje natural es lo suficientemente sencilla como para que la gente entienda por qué hay un problema aquí. Pero los teoremas de incompletitud de Gödel muestran que existen enunciados similares en los sistemas matemáticos.

Mi pregunta entonces es, ¿hay una simple ¿enunciados indemostrables, que parecerían intuitivamente verdaderos al profano, o que son intuitivamente indemostrables, para ilustrar el mismo concepto en, por ejemplo, la aritmética de números enteros o el álgebra?

Tengo entendido que la hipótesis del continuo es un ejemplo de afirmación indemostrable en la teoría de conjuntos de Zermelo-Fraenkel, pero eso no es realmente sencillo ni intuitivo.

¿Puede alguien dar un buen ejemplo que pueda señalar y decir "De eso hablan los teoremas de incompletitud de Gödel"? ¿O es simplemente algo que es fundamentalmente difícil de demostrar matemáticamente?

Actualización: Hay algunas respuestas fantásticas aquí que son ciertamente accesibles. Será difícil elegir una "correcta".

Al principio esperaba algo que pudiera entender un estudiante de secundaria, sin tener que explicar la teoría axiomática de conjuntos, o la aritmética de Peano, o lo contable frente a lo incontable, o la geometría no euclidiana. Pero la impresión que tengo es que en un sistema matemático suficientemente desarrollado, los matemáticos han sondeado las profundidades del mismo hasta el punto de que los enunciados potencialmente indemostrables o bien permanecen como conjeturas y, por tanto, son difíciles de entender por naturaleza (porque gente muy inteligente se queda perpleja ante ellos), o bien, una vez que se demuestra que son indemostrables, se convierten en axiomáticos en algún nuevo sistema o rama de sistemas.

Answer 1

He aquí un bonito ejemplo que creo que es más fácil de entender que los ejemplos habituales del teorema de Goodstein, Paris-Harrington, etc. Tomemos una caja de pintura contablemente infinita; esto significa que tiene un color de pintura por cada número entero positivo; por tanto, podemos llamar a los colores $C_1, C_2, $ y así sucesivamente. Tomemos el conjunto de los números reales, e imaginemos que cada número real está pintado con uno de los colores de la pintura.

Ahora haz la pregunta: ¿Hay cuatro números reales $a,b,c,d$ , todos pintados del mismo color, y no todos cero, tal que $$a+b=c+d?$$

Parece razonable imaginar que la respuesta depende de cómo se hayan coloreado exactamente los números. Por ejemplo, si se colorea cada número real con el color $C_1$ entonces, obviamente, hay $a,b,c,d$ que satisfacen los dos desideratos. Pero al menos se puede contemplar la posibilidad de que si los números reales se colorearan de forma suficientemente complicada, no habría cuatro números del mismo color con $a+b=c+d$ ; tal vez un pintor lo suficientemente inteligente podría arreglar que para cualquier cuatro números con $a+b=c+d$ siempre habría al menos uno de un color diferente al resto.

Así que ahora puedes hacer la pregunta: ¿Debe tal $a,b,c,d$ existe independientemente de lo inteligentemente que están coloreados los números?

Y la respuesta, demostrada por Erdos en 1943 es: sí, si y sólo si la hipótesis del continuo es falsa y, por tanto, es independiente de los axiomas fundacionales habituales de las matemáticas.

---

El resultado se menciona en

• Fox, Jacob " Un análogo de color infinito del teorema de Rado ", Journal of Combinatorial Theory Series A 114 (2007), 1456-1469.

Fox dice que el resultado que he descrito se desprende de un resultado más general de Erdos y Kakutani, según el cual la hipótesis del continuo es equivalente a que exista una coloración contable de los reales tal que cada subconjunto monocromático sea linealmente independiente sobre $\Bbb Q$ que se demuestra en:

• Erdos, P y S. Kakutani " En los gráficos no numerables ", Bull. Amer. Math. Soc. 49 (1943) 457-461.

Una prueba para el $a+b=c+d$ situación, originalmente demostrada por Erdos, se da en:

• Davies, R.O. " Partición del plano en un número innumerable de conjuntos sin distancia repetida " Proc. Cambridge Philos. Soc. 72 (1972) 179-183.

Answer 2

Cualquier afirmación que no sea lógicamente válida (léase: siempre verdadera) es indemostrable. La afirmación $\exists x\exists y(x>y)$ no es demostrable a partir de la teoría de los órdenes lineales, ya que es falsa en el orden del singleton. Por otro lado, no es refutable ya que cualquier otro tipo de orden lo satisfaría.

La declaración $\exists x(x^2-2=0)$ no es demostrable a partir de los axiomas del campo, ya que $\Bbb Q$ cree que esto es falso, y $\Bbb C$ cree que es verdad.

La declaración " $G$ es un grupo abeliano" no es demostrable ya que dado un grupo $G$ puede ser abeliano y puede ser no abeliano.

La declaración " $f\colon\Bbb{R\to R}$ es continua/diferenciable/suave/analítica/polinómica" y así sucesivamente, son todas indemostrables, porque así, dada una función arbitraria, no sabemos nada de ella. Incluso si sabemos que es continua, no podemos saber si es continuamente diferenciable, o suave, o cualquier otra cosa. Así que todas estas son suposiciones adicionales que tenemos que hacer.

Por supuesto, dada una función particular, como $f(x)=e^x$ podemos sentarnos y probar cosas al respecto, pero la afirmación " $f$ es una función continua" no se puede demostrar ni refutar hasta que se añadan más supuestos.

Y ese es el punto que estoy tratando de hacer aquí. Todo enunciado que no se pueda demostrar siempre será indemostrable a partir de algunos supuestos. Pero tú pides una afirmación intuitiva, y eso causa un problema.

El problema de la "afirmación intuitiva" es que cuanto más trabajas en matemáticas, más se descompone y reconstruye tu intuición en función del tema con el que trabajas. La hipótesis del continuo es perfectamente intuitiva y sencilla para mí, es cierto que la comprensión cómo puede ser indemostrable es difícil, pero la afirmación en sí no es muy difícil una vez que se aclaran las nociones básicas como la cardinalidad y los conjuntos de potencias.

Por último, permítanme añadir que hay muchas teorías que son completas y consistentes y que trabajamos con ellas. Algunas de ellas son incluso recursivamente enumerables. El teorema de incompletitud nos da tres condiciones de las que se desprende el carácter incompleto, dos cualesquiera no serán suficientes. (1) Consistente, (2) Recursivamente enumerable, (3) Interpreta la aritmética.

Hay teorías completas que satisfacen las dos primeras, y hay teorías completas que son consistentes e interpretan la aritmética, y por supuesto cualquier teoría inconsistente es completa.

Answer 3

La que me parece más intuitiva, como afirmación indemostrable de ZF sin Axioma de Elección, es que para dos conjuntos cualesquiera X y Y o bien hay una función inyectiva desde X a Y o hay uno de Y a X .

A grandes rasgos, y de manera informal, leo esto como: o bien X es al menos tan grande como Y o Y es al menos tan grande como X .

Quiero decir, ¿cuál es la alternativa? ¡¿Los dos son más grandes que el otro?!

Answer 4

La mayoría de los profanos entenderán lo siguiente. Si tienes un archivo que contiene datos aleatorios de más de 1 GB de tamaño, es poco probable que pueda comprimirse en un archivo autoextraíble de tamaño inferior a 1 MB. La probabilidad es astronómicamente pequeña de que un programa de autoextracción pueda generar su archivo.

Pero aunque la inmensa mayoría de estos archivos no pueden comprimirse por debajo de 1 MB de tamaño, nunca se puede tener una prueba matemática de este hecho para un archivo concreto. Esto se debe a que se pueden generar todas esas pruebas de forma recursiva utilizando un pequeño programa. Haga que este programa se detenga en el primer teorema comprobado que dice que tal o cual archivo de más de 1 GB no puede ser comprimido, y dé salida a ese archivo grande. Si el programa da salida, eso significa que el programa es la versión pequeña autoextraíble (comprimida) de su salida, la misma salida que el teorema dice que no se puede comprimir, lo cual es una contradicción.

Answer 5

En $\mathsf{ZF}$ (es decir, los axiomas de la teoría de conjuntos de Zermelo-Fraenkel, sin el Axioma de la Elección) las siguientes afirmaciones (entre muchas otras) son indemostrables:

1. La unión contable de conjuntos contables es contable.
2. Toda función sobreyectiva tiene un inverso derecho.
3. Todo espacio vectorial tiene una base.
4. Todo anillo tiene un ideal máximo.

Estas afirmaciones no son exactamente "verdades intuitivas para el profano", pero parecen naturales para muchos matemáticos. En particular, (2) se enseña probablemente en todas las universidades de matemáticas durante la primera semana del primer año.

Si está interesado en modelos de $\mathsf{ZF}$ en los que (1),(2),(3) o (4) no se cumplen, se puede empezar a echar un vistazo a Axioma de elección por Horst Herrlich. Tiene un apéndice muy bonito y bien organizado en el que se pueden buscar modelos en función de los enunciados (principales) que satisfacen.