Paradoja de la baya

La paradoja de Berry es una paradoja autorreferencial que surge de una expresión como "El entero positivo más pequeño no definible en menos de sesenta letras" (frase de cincuenta y siete letras).

Bertrand Russell, el primero en discutir la paradoja en forma impresa, la atribuyó a G. G. Berry (1867–1928), un bibliotecario junior en la Biblioteca Bodleian de Oxford. Russell llamó a Berry 'la única persona en Oxford que entendía la lógica matemática'. La paradoja se denominó "la paradoja de Richard" de Jean-Yves Girard.

Resumen

Considere la expresión:

"El entero positivo más pequeño no definible en menos de sesenta letras."

Dado que solo hay veintiséis letras en el alfabeto inglés, hay un número finito de frases de menos de sesenta letras y, por lo tanto, un número finito de números enteros positivos definidos por frases de menos de sesenta letras. Dado que hay una cantidad infinita de números enteros positivos, esto significa que hay números enteros positivos que no se pueden definir con frases de menos de sesenta letras. Si hay enteros positivos que satisfacen una propiedad dada, entonces hay un entero positivo menor que satisface esa propiedad; por lo tanto, hay un entero positivo más pequeño que satisface la propiedad "no definible en menos de sesenta letras". Este es el número entero al que se refiere la expresión anterior. Pero la expresión anterior tiene solo cincuenta y siete letras, por lo que es definible en menos de sesenta letras, y no es el entero positivo más pequeño no definible en menos de sesenta letras, y no está definido por esta expresión. Esto es una paradoja: debe haber un número entero definido por esta expresión, pero dado que la expresión es autocontradictoria (cualquier número entero que define es definible en menos de sesenta letras), no puede haber ningún número entero definido por ella.

Quizás otra analogía útil para la paradoja de Berry sería la frase "sentimiento indescriptible". Si el sentimiento es realmente indescriptible, entonces ninguna descripción del sentimiento sería verdadera. Pero si la palabra "indescriptible" comunica algo sobre el sentimiento, entonces puede considerarse una descripción: esto es contradictorio.

El matemático e informático Gregory J. Chaitin en The Unknowable (1999) añade este comentario: "Bueno, el historiador matemático mexicano Alejandro Garcidiego se ha tomado la molestia de encontrar esa letra [de Berry's de donde Russell escribió sus comentarios], y es una paradoja bastante diferente. La carta de Berry en realidad habla del primer ordinal que no se puede nombrar en un número finito de palabras. De acuerdo con la teoría de Cantor, tal ordinal debe existir, pero acabamos de nombrarlo en un número finito de palabras, lo cual es una contradicción."

Resolución

La paradoja de Berry, tal como se formuló anteriormente, surge debido a la ambigüedad sistemática en la palabra "definible". En otras formulaciones de la paradoja de Berry, como una que dice: "... no nombrable en menos..." el término "nombrable" es también uno que tiene esta ambigüedad sistemática. Términos de este tipo dan lugar a falacias de círculo vicioso. Otros términos con este tipo de ambigüedad son: satisfacible, verdadero, falso, función, propiedad, clase, relación, cardinal y ordinal. Resolver una de estas paradojas significa señalar exactamente dónde salió mal nuestro uso del lenguaje y establecer restricciones en el uso del lenguaje que puedan evitarlas.

Esta familia de paradojas puede resolverse incorporando estratificaciones de significado en el lenguaje. Los términos con ambigüedad sistemática pueden escribirse con subíndices que indican que un nivel de significado se considera de mayor prioridad que otro en su interpretación. "El número no nombrable₀ en menos de once palabras" puede ser nombrable₁ en menos de once palabras bajo este esquema.

Sin embargo, uno puede leer las contribuciones de Alfred Tarski a la Paradoja del Mentiroso para encontrar cómo esta resolución en idiomas se queda corta. Alfred Tarski diagnosticó que la paradoja surge solo en idiomas que son "semánticamente cerrados", por lo que se refiere a un idioma en el que es posible que una oración predique la verdad (o la falsedad) de otra oración en el mismo idioma. (o incluso de sí mismo). Para evitar la autocontradicción, cuando se discuten los valores de verdad es necesario imaginar niveles de lenguajes, cada uno de los cuales puede predicar la verdad (o la falsedad) solo de los lenguajes en un nivel inferior. Entonces, cuando una oración se refiere al valor de verdad de otra, es semánticamente superior. La oración a la que se hace referencia es parte del "lenguaje objeto", mientras que la oración de referencia se considera parte de un "metalenguaje" con respecto al lenguaje objeto. Es legítimo para oraciones en "idiomas" superior en la jerarquía semántica para referirse a oraciones inferiores en el "lenguaje" jerarquía, pero no al revés. Esto evita que un sistema se vuelva autorreferencial.

Sin embargo, este sistema está incompleto. A uno le gustaría poder hacer declaraciones como "Para cada declaración en el nivel α de la jerarquía, hay una declaración en el nivel α+1 que afirma que la primera afirmación es falsa." Esta es una declaración verdadera y significativa sobre la jerarquía que define Tarski, pero se refiere a declaraciones en cada nivel de la jerarquía, por lo que debe estar por encima de cada nivel de la jerarquía y, por lo tanto, no es posible dentro de la jerarquía (aunque las versiones limitadas de la oración son posibles). A Saul Kripke se le atribuye la identificación de este carácter incompleto en la jerarquía de Tarski en su muy citado artículo 'Esquema de una teoría de la verdad'. y se reconoce como un problema general en los lenguajes jerárquicos.

Análogos formales

Usando programas o pruebas de longitudes limitadas, es posible construir un análogo de la expresión de Berry en un lenguaje matemático formal, como lo ha hecho Gregory Chaitin. Aunque la analogía formal no conduce a una contradicción lógica, prueba ciertos resultados de imposibilidad.

George Boolos (1989) se basó en una versión formalizada de la paradoja de Berry para probar el teorema de incompletitud de Gödel de una forma nueva y mucho más sencilla. La idea básica de su prueba es que una proposición que se cumple de x si y solo si x = n para algún número natural n se puede llamar una definición para n, y que el conjunto {(n, k): n tiene una definición que tiene k símbolos de largo} y se puede demostrar que es representable (usando números de Gödel). Entonces la proposición "m es el primer número no definible en menos de k símbolos" puede formalizarse y demostrarse que es una definición en el sentido que acabamos de exponer.

Relación con la complejidad de Kolmogorov

En general, no es posible definir sin ambigüedades cuál es el número mínimo de símbolos necesarios para describir una cadena dada (dado un mecanismo de descripción específico). En este contexto, los términos cadena y número pueden usarse indistintamente, ya que un número es en realidad una cadena de símbolos, p. una palabra en inglés (como la palabra "once" utilizada en la paradoja) mientras que, por otro lado, es posible referirse a cualquier palabra con un número, p. por el número de su posición en un diccionario dado o por una codificación adecuada. Algunas cadenas largas se pueden describir exactamente usando menos símbolos que los requeridos por su representación completa, como se logra a menudo usando la compresión de datos. La complejidad de una cadena determinada se define entonces como la longitud mínima que requiere una descripción para referirse (sin ambigüedades) a la representación completa de esa cadena.

La complejidad de Kolmogorov se define utilizando lenguajes formales o máquinas de Turing que evitan ambigüedades sobre qué cadena resulta de una descripción dada. Se puede probar que la complejidad de Kolmogorov no es computable. La prueba por contradicción muestra que si fuera posible calcular la complejidad de Kolmogorov, también sería posible generar sistemáticamente paradojas similares a esta, es decir, descripciones más cortas que lo que implica la complejidad de la cadena descrita. Es decir, la definición del número de Berry es paradójica porque en realidad no es posible calcular cuántas palabras se requieren para definir un número, y sabemos que tal cálculo no es posible debido a la paradoja.