La paradoja de Berry es una paradoja autorreferencial que surge de una expresión como "El entero positivo más pequeño no definible con menos de sesenta letras" (una frase con cincuenta y siete letras).
Bertrand Russell , el primero en analizar la paradoja en forma impresa, la atribuyó a GG Berry (1867-1928), [1] un bibliotecario adjunto 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 llamada " paradoja de Richard " por Jean-Yves Girard . [3]
Consideremos la expresión:
Como el alfabeto inglés tiene solo veintiséis letras, 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 que se definen mediante frases de menos de sesenta letras. Como hay un número infinito de números enteros positivos, esto significa que hay números enteros positivos que no se pueden definir mediante frases de menos de sesenta letras. Si hay números enteros positivos que satisfacen una propiedad dada, entonces hay un número entero positivo más pequeño que satisface esa propiedad; por lo tanto, hay un número 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 es definible en menos de sesenta letras, y no es el número 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 como la expresión es contradictoria en sí misma (cualquier número entero que defina es definible en menos de sesenta letras), no puede haber ningún número entero definido por ella.
El matemático y científico 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 de la que Russell escribió sus observaciones], y es una paradoja bastante diferente. La carta de Berry habla en realidad del primer ordinal que no puede nombrarse con un número finito de palabras. Según la teoría de Cantor, tal ordinal debe existir, pero lo hemos nombrado con un número finito de palabras, lo cual es una contradicción".
La paradoja de Berry, tal como se formuló anteriormente, surge debido a la ambigüedad sistemática de la palabra "definible". En otras formulaciones de la paradoja de Berry, como la que 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írculo vicioso . Otros términos con este tipo de ambigüedad son: satisfacible, 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 proporcionar restricciones al 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 denotan que un nivel de significado se considera de mayor prioridad que otro en su interpretación. "El número no nombrable 0 en menos de once palabras" puede ser nombrable 1 en menos de once palabras bajo este esquema. [5]
Sin embargo, se pueden leer las contribuciones de Alfred Tarski a la paradoja del mentiroso para ver cómo esta resolución en los idiomas se queda corta. Alfred Tarski diagnosticó que la paradoja surge solo en idiomas que son "semánticamente cerrados", con lo que quería decir un idioma en el que es posible que una oración predique la verdad (o falsedad) de otra oración en el mismo idioma (o incluso de sí misma). Para evitar la autocontradicción, es necesario, al discutir los valores de verdad, imaginar niveles de idiomas, cada uno de los cuales puede predicar la verdad (o falsedad) solo de idiomas en un nivel inferior. Por lo tanto, 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 referente se considera parte de un "metalenguaje" con respecto al lenguaje objeto. Es legítimo que las oraciones en "lenguajes" más altos en la jerarquía semántica se refieran a oraciones más bajas en la jerarquía del "lenguaje", pero no al revés. Esto evita que un sistema se vuelva autorreferencial.
Sin embargo, este sistema es incompleto. Uno quisiera poder hacer afirmaciones como "Para 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 Tarski define, pero se refiere a afirmaciones 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 son posibles versiones limitadas de la oración). [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 hizo Gregory Chaitin . Aunque el análogo formal no conduce a una contradicción lógica, sí prueba 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 simple. La idea básica de su demostración es que una proposición que se cumple para x si y sólo si x = n para algún número natural n puede ser llamada una definición para n , y que el conjunto {( n , k ): n tiene una definición que tiene k símbolos de longitud} puede demostrarse 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 como una definición en el sentido que acabamos de enunciar. [10]
En general, no es posible definir de manera inequívoca 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, por ejemplo, una palabra inglesa (como la palabra "once" utilizada en la paradoja) mientras que, por otro lado, es posible hacer referencia a cualquier palabra con un número, por ejemplo, por el número de su posición en un diccionario dado o por una codificación adecuada. Algunas cadenas largas pueden describirse exactamente utilizando menos símbolos que los requeridos por su representación completa, como se logra a menudo utilizando la compresión de datos . La complejidad de una cadena dada se define entonces como la longitud mínima que requiere una descripción para hacer referencia (inequívocamente) 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 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 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.