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" (una frase con cincuenta y siete letras).
Bertrand Russell , el primero en discutir la paradoja en forma impresa, la atribuyó a GG Berry (1867-1928), [1] un bibliotecario junior de la Biblioteca Bodleian de Oxford . Russell llamó a Berry "la única persona en Oxford que entendía la lógica matemática". [2] La paradoja fue denominada " paradoja de Richard " por Jean-Yves Girard . [3]
Considere la expresión:
Dado que sólo hay veintiséis letras en el alfabeto inglés, hay un número finito de frases de menos de sesenta letras y, por tanto, un número finito de números enteros positivos que están definidos por frases de menos de sesenta letras. Dado que hay infinitos números enteros positivos, esto significa que hay números enteros positivos que no pueden definirse mediante frases de menos de sesenta letras. Si hay números enteros positivos que satisfacen una propiedad determinada, entonces hay un entero positivo más pequeño que satisface esa propiedad; por lo tanto, existe 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 tanto, se puede definir en menos de sesenta letras y no es el entero positivo más pequeño que no se puede definir en menos de sesenta letras y no está definida por esta expresión. Esto es una paradoja: debe haber un número entero definido por esta expresión, pero como la expresión es contradictoria en sí misma (cualquier número entero que defina se puede definir en menos de sesenta letras), no puede haber ningún número entero definido por ella.
El matemático e informático Gregory 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 carta [de Berry a partir de la cual Russell escribió sus comentarios], y es bastante diferente". La paradoja de Berry en realidad habla del primer ordinal que no se puede nombrar en un número finito de palabras. Según la teoría de Cantor, dicho ordinal debe existir, pero acabamos de nombrarlo en un número finito de palabras, que es un. contradicció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 aquella que en cambio dice: "...no nombrable en menos..." el término "nombrable" también tiene esta ambigüedad sistemática. Términos de este tipo dan lugar a falacias de círculos viciosos . Otros términos con este tipo de ambigüedad son: satisfactible, verdadero, falso, función, propiedad, clase, relación, cardinal y ordinal. [4] Resolver una de estas paradojas significa señalar exactamente dónde falló nuestro uso del lenguaje y establecer restricciones en el uso del lenguaje que puedan evitarlos.
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 denotan que un nivel de significado se considera de mayor prioridad que otro en su interpretación. "El número que no se puede denominar 0 en menos de once palabras" puede denominarse 1 en menos de once palabras según este esquema. [5]
Sin embargo, se pueden leer las contribuciones de Alfred Tarski a la paradoja del mentiroso para descubrir cómo esta resolución en los idiomas se queda corta. Alfred Tarski diagnosticó que la paradoja surge sólo en lenguas que están "semánticamente cerradas", es decir, una lengua en la que es posible que una oración predique la verdad (o la falsedad) de otra oración en la misma lengua (o incluso de sí misma). ). Para evitar la autocontradicción, cuando se analizan valores de verdad es necesario imaginar niveles de lenguajes, cada uno de los cuales puede predicar la verdad (o la falsedad) sólo de lenguajes de un nivel inferior. Entonces, cuando una oración se refiere al valor de verdad de otra, es semánticamente más alto. 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 que oraciones en "lenguajes" superiores en la jerarquía semántica se refieran a oraciones inferiores en la jerarquía "lengua", 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 afirmaciones como "Por cada afirmación en el nivel α de la jerarquía, hay una afirmación en el nivel α +1 que afirma que la primera afirmación es falsa". Esta es una afirmació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 sentencia son posibles). [6] [7] A Saul Kripke se le atribuye la identificación de esta incompletitud en la jerarquía de Tarski en su artículo muy citado "Esquema de una teoría de la verdad", [7] y se reconoce como un problema general en los lenguajes jerárquicos. [8] [7]
Utilizando programas o pruebas de longitudes acotadas, 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, sí demuestra ciertos resultados de imposibilidad. [9]
Boolos (1989) se basó en una versión formalizada de la paradoja de Berry para demostrar el teorema de incompletitud de Gödel de una manera 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 sólo si x = n para algún número natural n puede llamarse una definición para n , y que el conjunto {( n , k ): n tiene una definición que Se puede demostrar que tiene k símbolos de largo} como 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.
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 determinada (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, por ejemplo, una palabra inglesa (como la palabra "once" utilizada en la paradoja), mientras que, por otro lado, es posible para referirse a cualquier palabra con un número, por ejemplo, por el número de su posición en un diccionario determinado o mediante una codificación adecuada. Algunas cadenas largas se pueden describir exactamente usando menos símbolos que los requeridos para su representación completa, como a menudo se logra mediante 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 hacer referencia (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 determinada. Se puede demostrar que la complejidad de Kolmogorov no es computable. La prueba por contradicción muestra que si fuera posible calcular la complejidad de Kolmogorov, entonces también sería posible generar sistemáticamente paradojas similares a ésta, es decir, descripciones más cortas de 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 necesitan para definir un número, y sabemos que dicho cálculo no es posible debido a la paradoja.
Reimpreso en Boolos (1998, págs. 383–388)