Indescriptibilidad de ciertos objetos infinitos

Question

Estaba pensando en las secuencias infinitas de números enteros y se me ocurrió que normalmente dependemos de algún tipo de fórmula para los elementos de la secuencia, por ejemplo $s_n = 2n$ sería la secuencia de números naturales pares.

Sin embargo, estuve pensando en ello y me pareció que es difícil describir exactamente todas las posibles secuencias de enteros en $\mathbb{Z}^\mathbb{N}$ . De hecho, me parece que sin que surja algún tipo de fórmula o patrón, no hay manera de describir la secuencia en una cantidad finita de información (por supuesto, siempre podríamos describir la secuencia una por una, pero esto no es realmente satisfactorio). También he oído hablar de la paradoja de Berry, que supongo que es similar a la pregunta que nos ocupa.

¿Existe alguna rama de las matemáticas que se ocupe de esta formalización de la "indescriptibilidad" de los objetos? ¿Existe algún tipo de axioma que lo regule?

Answer 1

Sí, esto es un foco de lógica matemática especialmente los subcampos de teoría de la computabilidad y teoría de conjuntos ¡!

Algunas respuestas inmediatas:

• Una noción razonable de "descriptible" es la de "computable", es decir, computable por una máquina de Turing. Dado que hay un número incontable de secuencias de números naturales y sólo un número contable de máquinas de Turing, la "mayoría" de las secuencias son indescriptibles en este sentido.

• Esto también es válido si sustituimos "computable" por cualquier noción similar de definibilidad, siempre que las definiciones formen una contable conjunto, la "mayoría" de las secuencias escaparán a nuestra red.

• Ahora bien, esto no es el final de la historia: dada una noción de describibilidad (digamos, la computabilidad) y un par de secuencias no descriptibles, podemos preguntar si una es "incluso menos descriptible que" la otra. Esto resulta no ¡ser una pregunta tonta! Véase computabilidad relativa. Otra forma (quizás menos tonta) de ver este tipo de preguntas es tomar una secuencia dada $A$ y preguntar: "¿Qué tipo de lenguaje necesito para poder describir $A$ ?"

• En el lado de la teoría de conjuntos, también podemos hacer versiones de esta pregunta dentro de los modelos de la teoría de conjuntos. Es decir, si tenemos alguna noción de describibilidad, y algún modelo $V$ de la teoría de conjuntos (es decir, $V$ puede no contener realmente todo conjuntos, pero $V$ contiene lo suficiente como para satisfacer las propiedades básicas de la teoría de conjuntos), podemos preguntar si toda secuencia en $V$ es descriptible. Resulta que, sorprendentemente, este puede en aparente (pero no real) contradicción con el primer punto; véase https://arxiv.org/abs/1105.4597 .

• Y, por supuesto, otras áreas de la lógica también tienen cosas que decir al respecto. Teoría de los modelos examina los conjuntos y las secuencias desde la perspectiva de la definibilidad lógica en una estructura, y estudia tanto los tipos de secuencias definibles en ciertas estructuras como las lógicas necesarias para definir ciertas secuencias sobre ciertas estructuras; y en teoría de la prueba prestamos atención a qué tipo de sistema axiomático puede verificar que una determinada descripción de una secuencia "se comporta bien" (por ejemplo, ¿tan difícil es demostrar que dos descripciones de la misma secuencia corresponden realmente al mismo objeto?)

Answer 2

Además de los excelentes subcampos descritos por Noah, me acuerdo de Entropía de Shannon del contenido de la información.

La entropía de Shannon mide la información contenida en un mensaje como en contraposición a la parte del mensaje que está determinada (o predecible).

Una secuencia con una fórmula simple como $x_n = 2n$ tiene poca entropía. Si se necesita un programa informático o un algoritmo para calcular la secuencia (digamos los dígitos de pi), la entropía es mayor. La entropía es máxima cuando la única forma conocida de expresar una secuencia es el propio contenido de la secuencia.

Answer 3

Para responder a la parte de la pregunta sobre la paradoja de Berry, efectivamente está relacionada, pero no tanto como se podría pensar, porque se trata más bien de la distinción entre la demostrabilidad dentro y fuera de un sistema formal. En concreto, para demostrar incluso que un único número entero positivo $k$ es definible de forma única en algún sistema formal $S$ tendrías que demostrar que hay algún $1$ -sentencia de parámetro $φ$ tal que $S$ demuestra " $φ(n)$ " si " $n$ "es el término para $k$ , es decir, " $\underbrace{1+\cdots+1}_\text{$ k $ times}$ ". Pero para ello hay que demostrar que $S$ no prueba un montón de frases, lo que implica que $S$ no es incoherente. Por lo tanto, el sistema formal en el que se trabaja para hacer todo esto no puede ser $S$ sí mismo a menos que sea incapaz de alguna aritmética básica (no puede demostrar lo que PA puede) o es impracticable (validez de la prueba indecidible), por el teorema de incompletitud de Godel.

Es instructivo ver lo que ocurre si intentamos definir la "definibilidad en $S$ " como simplemente que $S$ demuestra " $\forall n \in \mathbb{N}\ ( φ(n) \leftrightarrow n=k )$ " para algunos $1$ -sentencia de parámetro $φ$ . Si lo hacemos, entonces el número de enteros positivos que son definibles de esta manera por algún $φ$ con una longitud inferior a $c$ puede ser mayor que el número de posibles $φ$ de longitud inferior a $c$ porque $S$ podría demostrar una contradicción y, por tanto, demostrar que todo número entero positivo es definible por cada $φ$ ¡! Por lo tanto, todavía tenemos que demostrar que $S$ es consistente después de todo, de lo contrario no podemos acotar el número de enteros positivos definibles por una sola de tales $φ$ .

Como puedes ver, la paradoja de Berry desaparece, pero tiene muy poco que ver con la indescriptibilidad o el infinito. Lo que podrías estar buscando es la paradoja de Skolem. Si ZFC es consistente entonces tiene un modelo contable, pero la propia ZFC demuestra que hay un conjunto incontable, como el de tu pregunta. No hay contradicción, porque ZFC no puede demostrar que es consistente, y también porque el modelo simplemente no puede ver (no tiene) un objeto que represente una biyección entre su noción de $\mathbb{N}$ y $\mathbb{Z}^\mathbb{N}$ . Sin embargo, desde el exterior, puede haber de hecho una biyección entre las dos colecciones que representan esos dos en el modelo. En resumen, el metasistema sabe más que el modelo, porque no sólo ve todas las biyecciones que el modelo ve, sino que también ve todas las biyecciones que el modelo no ve.

Puede ser útil darse cuenta de que las secuencias que se pueden construir en ZFC son las que deben tener todos los modelos de ZFC. Sólo hay un número contable de ellas, pero eso no impide que algunos modelos tengan un número incontable. Además, hay una pequeña trampa en la "descripción". En ZFC el axioma de elección permite construir un conjunto que no se puede precisar, ya que no se da que sea único. Esto significa que tenemos que ser más cuidadosos cuando decimos "contablemente muchos objetos describibles". En cambio, esto es lo que podemos hacer. Extender ZFC a una teoría $T$ con un axioma $φ(c_φ)$ por cada $1$ -sentencia de parámetro $φ$ en $T$ tal que $T \vdash \exists x\ ( φ(x) )$ , donde $c_φ$ es un nuevo símbolo constante para cada $φ$ . (Esto puede hacerse por el límite de una construcción inductiva.) Entonces $T$ tiene un número contable de constantes, por lo que ningún modelo de ZFC con un conjunto incontable (como uno en el que $\mathbb{Z}^\mathbb{N}$ se interpreta como un conjunto incontable) puede extenderse para tener una constante para cada elemento de ese conjunto.

Por supuesto, Noah El post de la Sra. B. responde a la otra parte de tu pregunta sobre qué rama de las matemáticas se ocupa de todo esto. =)