¿Hay más verdades que pruebas?

Question

Noson Yanofsky es un científico de la computación teórica en el Brooklyn College. Presenta el siguiente argumento en las páginas 329-330 de su libro The Outer Limits of Reason, publicado por el MIT Press.

1. El conjunto $\mathbb{N}$ de números naturales tiene un número incontable de subconjuntos.

2. Sea $x$ un número natural y $S$ un subconjunto de $\mathbb{N}$. Exactamente una de las siguientes afirmaciones expresa un hecho matemático: (a) $x \in S$, (b) $x \notin S$.

3. Se deduce de (1) y (2) que hay un número incontable de hechos matemáticos.

4. Sea $T$ una teoría de primer orden. Entonces $T$ tiene solo un número contable de fórmulas.

5. Se sigue de (3) y (4) que hay más hechos matemáticos que fórmulas en $T$.

6. Por lo tanto, $T$ no puede expresar, y mucho menos probar, todos los hechos matemáticos.

Para las propias palabras de Yanofsky, consulte el artículo: "La mayoría de verdades no pueden ser expresadas en lenguaje."

He escuchado a personas decir cosas similares en podcasts. Intentan explicar el primer teorema de incompletitud de Gödel como afirmando que hay más verdades que pruebas.

---

Pregunta.$\ \ $¿Es válido el argumento de Yanofsky? Si no, ¿por qué?

---

Parece contradecir las respuestas a las siguientes preguntas: 1, 2, 3. Sin embargo, Yanofsky parece ser un experto en esta área, y su argumento fue publicado por el MIT Press.

Tenga en cuenta que Yanofsky escribe:

"Todo se trata de hechos matemáticos, no de lo que se puede afirmar. Una afirmación matemática es un hecho matemático que puede expresarse en símbolos. Vimos arriba que... hay un número contable de afirmaciones matemáticas. Por lo tanto, hay considerablemente más hechos matemáticos que afirmaciones matemáticas."

Tal vez esto podría hacerse más preciso codificando hechos matemáticos como conjuntos.

Answer 1

Eso es correcto, pero no es muy interesante: no tenemos "acceso" a la mayoría de los hechos matemáticos. Ni siquiera está claro qué significaría una demostración de un hecho matemático arbitrario, porque para pedir una demostración de algo tenemos que escribirlo, y solo hay una cantidad numerable de cadenas que podemos escribir.

El teorema de Gödel es mucho más interesante: dice que hay una fórmula que es independiente de PA. Así que puedes escribir alguna afirmación en lenguaje aritmético (y realmente puede ser tan simple como "esta ecuación diofántica tiene una solución") y ni ella ni su negación pueden ser demostradas en PA.

Compáralo, por ejemplo, con la geometría euclidiana. Hay una cantidad no numerable de líneas y puntos, así que hay un número no numerable de "hechos" como "este punto está / no está en esta línea". Pero la geometría euclidiana es completa. Así que el teorema de Gödel muestra una diferencia entre la aritmética y la geometría.

Y también hay (asumiendo la consistencia de ZF) un modelo de ZF donde hay, desde un punto de vista externo, solo una cantidad numerable de conjuntos.

Answer 2

El argumento es falaz.

Podemos usar el mismo argumento básico en una configuración aún más simple, que claramente indica lo que falla.

Hay incontables subconjuntos de los números naturales. Solo hay un número contable de formas en las que podemos expresar una afirmación de la forma $\pi\not\in S$ para algún $S\subseteq \mathbb N$. Por lo tanto, hay muchos más hechos verdaderos de la forma $\pi\not\in S$ de los que podemos expresar, y mucho menos probar.

Pero por supuesto, podemos probar todos ellos, ya que podemos probar $\pi\not\in \mathbb N$ y, por lo tanto, $\pi\not\in S$ para cada $S\subseteq \mathbb N$. La falacia es que una sola prueba puede demostrar incontables hechos, por lo que ser capaz de enunciar un hecho no es un requisito previo para demostrarlo.

La cita "la mayoría de las verdades no pueden ser expresadas en lenguaje" es correcta, al menos para esta definición de "verdad". Pero no se deduce que no puedan ser probadas.

Answer 3

Una perspectiva ligeramente diferente - Sí, hay innumerables hechos matemáticos (triviales), pero no necesitas probar individualmente cada uno de esos hechos. Lo que es mucho más interesante es el hecho de que, en la mayoría de situaciones donde importa, puedes formular afirmaciones en el lenguaje de primer orden de manera que exprese, en teoría, un número incontable de hechos.

Por ejemplo, probando que alguna función $f: \mathbb{R} \to \mathbb{R}$ es continua. Lo cual es equivalente a la afirmación de que para cada real $x$ (claramente un número incontable de $x$), $f$ es continua en $x$. Obviamente podemos probar afirmaciones como esta, y por lo tanto esto muestra que no solo podemos, en efecto, afirmar un número incontable de "hechos", sino también probar tales "hechos" como "hechos" en un número finito de pasos.

En resumen, el argumento de Yanofsky es simplemente una variación de la paradoja de Zeno.

Answer 4

Nadie parece haber mencionado el siguiente punto. Deje que $\mathcal F$ sea el ultrafiltro principal en $\mathbb N$ generado por $1\in\mathbb N$. Entonces la afirmación $(\forall A\in \mathcal F) (1\in A)$ incluye incontables "verdades". Eso es todo lo que está diciendo el argumento de Yanofsky. Es difícil derivar ideas significativas de tal platitude.

Dado que la paradoja de Zenón está lejos de ser una platitude, está claro que el argumento de Yanofsky no tiene nada que ver con la paradoja de Zenón.

Answer 5

Discrepo ligeramente con la afirmación de que hay innumerables hechos, ya que solo se puede declarar una cantidad contable de estos hechos en realidad. Es decir, solo podemos describir una cantidad contable de subconjuntos de $\mathbb{N}$.